Solving Witness-type Triangle Puzzles Faster with an Automatically Learned Human-Explainable Predicate

• URL: http://arxiv.org/abs/2308.02666v1
• Date: Fri, 4 Aug 2023 18:52:18 GMT
• Title: Solving Witness-type Triangle Puzzles Faster with an Automatically Learned Human-Explainable Predicate
• Authors: Justin Stevens, Vadim Bulitko, David Thue
• Abstract summary: We develop a search-based artificial intelligence puzzle solver for The Witness game. We learn a human-explainable predicate that predicts whether a partial path to a Witness-type puzzle is not completable to a solution path. We prove a key property of the learned predicate which allows us to use it for pruning successor states in search.
• Score: 0.29005223064604074
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Automatically solving puzzle instances in the game The Witness can guide players toward solutions and help puzzle designers generate better puzzles. In the latter case such an Artificial Intelligence puzzle solver can inform a human puzzle designer and procedural puzzle generator to produce better instances. The puzzles, however, are combinatorially difficult and search-based solvers can require large amounts of time and memory. We accelerate such search by automatically learning a human-explainable predicate that predicts whether a partial path to a Witness-type puzzle is not completable to a solution path. We prove a key property of the learned predicate which allows us to use it for pruning successor states in search thereby accelerating search by an average of six times while maintaining completeness of the underlying search. Conversely given a fixed search time budget per puzzle our predicate-accelerated search can solve more puzzle instances of larger sizes than the baseline search.

Related papers

• Making New Connections: LLMs as Puzzle Generators for The New York Times' Connections Word Game [6.136654326170453]
  The Connections puzzle is a word association game published daily by The New York Times (NYT) generating novel puzzles requires a form of metacognition: generators must be able to accurately model the downstream reasoning of potential solvers. Our findings show that LLMs are capable puzzle creators, and can generate diverse sets of enjoyable, challenging, and creative Connections puzzles as judged by human users.
  arXiv  Detail & Related papers  (2024-07-15T21:05:25Z)
• Solving Zebra Puzzles Using Constraint-Guided Multi-Agent Systems [25.0042181817455]
  We introduce a multi-agent system, ZPS, that integrates Large Language Models with an off the shelf theorem prover. This system tackles the complex puzzle-solving task by breaking down the problem into smaller, manageable parts. We also introduce an automated grid puzzle grader to assess the correctness of our puzzle solutions and show that the automated grader is reliable by evaluating it in a user-study.
  arXiv  Detail & Related papers  (2024-07-04T14:22:25Z)
• Are Language Models Puzzle Prodigies? Algorithmic Puzzles Unveil Serious Challenges in Multimodal Reasoning [24.386388107656334]
  This paper introduces the novel task of multimodal puzzle solving, framed within the context of visual question-answering. We present a new dataset, AlgoVQA, designed to challenge and evaluate the capabilities of multimodal language models in solving algorithmic puzzles.
  arXiv  Detail & Related papers  (2024-03-06T17:15:04Z)
• PathFinder: Guided Search over Multi-Step Reasoning Paths [80.56102301441899]
  We propose PathFinder, a tree-search-based reasoning path generation approach. It enhances diverse branching and multi-hop reasoning through the integration of dynamic decoding. Our model generalizes well to longer, unseen reasoning chains, reflecting similar complexities to beam search with large branching factors.
  arXiv  Detail & Related papers  (2023-12-08T17:05:47Z)
• Large Search Model: Redefining Search Stack in the Era of LLMs [63.503320030117145]
  We introduce a novel conceptual framework called large search model, which redefines the conventional search stack by unifying search tasks with one large language model (LLM) All tasks are formulated as autoregressive text generation problems, allowing for the customization of tasks through the use of natural language prompts. This proposed framework capitalizes on the strong language understanding and reasoning capabilities of LLMs, offering the potential to enhance search result quality while simultaneously simplifying the existing cumbersome search stack.
  arXiv  Detail & Related papers  (2023-10-23T05:52:09Z)
• Solving and Generating NPR Sunday Puzzles with Large Language Models [0.0]
  State-of-the-art large language models can solve many PUZZLEQA puzzles. The best model achieves, GPT-3.5, 50.2% loose accuracy. GPT-3.5 generates puzzles with answers that do not conform to the generated rules.
  arXiv  Detail & Related papers  (2023-06-21T13:23:48Z)
• Multi-Phase Relaxation Labeling for Square Jigsaw Puzzle Solving [73.58829980121767]
  We present a novel method for solving square jigsaw puzzles based on global optimization. The method is fully automatic, assumes no prior information, and can handle puzzles with known or unknown piece orientation.
  arXiv  Detail & Related papers  (2023-03-26T18:53:51Z)
• Automated Graph Genetic Algorithm based Puzzle Validation for Faster Game Desig [69.02688684221265]
  This paper presents an evolutionary algorithm, empowered by expert-knowledge informeds, for solving logical puzzles in video games efficiently. We discuss multiple variations of hybrid genetic approaches for constraint satisfaction problems that allow us to find a diverse set of near-optimal solutions for puzzles.
  arXiv  Detail & Related papers  (2023-02-17T18:15:33Z)
• Video Anomaly Detection by Solving Decoupled Spatio-Temporal Jigsaw Puzzles [67.39567701983357]
  Video Anomaly Detection (VAD) is an important topic in computer vision. Motivated by the recent advances in self-supervised learning, this paper addresses VAD by solving an intuitive yet challenging pretext task. Our method outperforms state-of-the-art counterparts on three public benchmarks.
  arXiv  Detail & Related papers  (2022-07-20T19:49:32Z)
• Brain-inspired Search Engine Assistant based on Knowledge Graph [53.89429854626489]
  DeveloperBot is a brain-inspired search engine assistant named on knowledge graph. It constructs a multi-layer query graph by splitting a complex multi-constraint query into several ordered constraints. It then models the constraint reasoning process as subgraph search process inspired by the spreading activation model of cognitive science.
  arXiv  Detail & Related papers  (2020-12-25T06:36:11Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.