On Grid Graph Reachability and Puzzle Games

• URL: http://arxiv.org/abs/2310.01378v1
• Date: Mon, 2 Oct 2023 17:41:35 GMT
• Title: On Grid Graph Reachability and Puzzle Games
• Authors: Miquel Bofill, Cristina Borralleras, Joan Espasa, and Mateu Villaret
• Abstract summary: Many puzzle video games, like Sokoban, involve moving some agent in a maze. The difficulty of the game is mainly related to performing actions on objects, such as pushing (reachable) boxes. In this paper we study CP and SAT approaches for solving these kind of problems.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Many puzzle video games, like Sokoban, involve moving some agent in a maze. The reachable locations are usually apparent for a human player, and the difficulty of the game is mainly related to performing actions on objects, such as pushing (reachable) boxes. For this reason, the difficulty of a particular level is often measured as the number of actions on objects, other than agent walking, needed to find a solution. In this paper we study CP and SAT approaches for solving these kind of problems. We review some reachability encodings and propose a new one. We empirically show that the new encoding is well-suited for solving puzzle problems in the planning as SAT paradigm, especially when considering the execution of several actions in parallel.

Related papers

• Nash Meets Wertheimer: Using Good Continuation in Jigsaw Puzzles [7.716132543734369]
  Jigsaw puzzle solving is a challenging task for computer vision since it requires high-level spatial and semantic reasoning. We introduce a new challenging version of the puzzle solving problem in which one deliberately ignores conventional color and shape features. We evaluate our approach on both synthetic and real-world data and compare it with state-of-the-art algorithms.
  arXiv  Detail & Related papers  (2024-10-22T09:46:09Z)
• Hardness of Independent Learning and Sparse Equilibrium Computation in Markov Games [70.19141208203227]
  We consider the problem of decentralized multi-agent reinforcement learning in Markov games. We show that no algorithm attains no-regret in general-sum games when executed independently by all players. We show that our lower bounds hold even for seemingly easier setting in which all agents are controlled by a centralized algorithm.
  arXiv  Detail & Related papers  (2023-03-22T03:28:12Z)
• 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)
• Turning Mathematics Problems into Games: Reinforcement Learning and Gr\"obner bases together solve Integer Feasibility Problems [4.746723775952672]
  We consider the integer feasibility problem, a challenge of deciding whether a system of linear equations and inequalities has a solution with integer values. Our paper describes a novel algebraic reinforcement learning framework that allows an agent to play a game equivalent to the integer feasibility problem. As a proof of concept we demonstrate in experiments that our agent can play well the simplest version of our game for 2-way tables.
  arXiv  Detail & Related papers  (2022-08-25T16:24:34Z)
• 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)
• Brick-by-Brick: Combinatorial Construction with Deep Reinforcement Learning [52.85981207514049]
  We introduce a novel formulation, complex construction, which requires a building agent to assemble unit primitives sequentially. To construct a target object, we provide incomplete knowledge about the desired target (i.e., 2D images) instead of exact and explicit information to the agent. We demonstrate that the proposed method successfully learns to construct an unseen object conditioned on a single image or multiple views of a target object.
  arXiv  Detail & Related papers  (2021-10-29T01:09:51Z)
• On Applying the Lackadaisical Quantum Walk Algorithm to Search for Multiple Solutions on Grids [63.75363908696257]
  The lackadaisical quantum walk is an algorithm developed to search graph structures whose vertices have a self-loop of weight $l$. This paper addresses several issues related to applying the lackadaisical quantum walk to search for multiple solutions on grids successfully.
  arXiv  Detail & Related papers  (2021-06-11T09:43:09Z)
• Using Small MUSes to Explain How to Solve Pen and Paper Puzzles [4.535832029902474]
  We present Demystify, a tool which allows puzzles to be expressed in a high-level constraint programming language. We give several improvements to the existing techniques for solving puzzles with MUSes. We demonstrate the effectiveness and generality of Demystify by comparing its results to documented strategies for solving a range of pen and paper puzzles by hand.
  arXiv  Detail & Related papers  (2021-04-30T15:07:51Z)
• Non-Rigid Puzzles [50.213265511586535]
  We present a non-rigid multi-part shape matching algorithm. We assume to be given a reference shape and its multiple parts undergoing a non-rigid deformation. Experimental results on synthetic as well as real scans demonstrate the effectiveness of our method.
  arXiv  Detail & Related papers  (2020-11-26T00:32:30Z)
• Finding Game Levels with the Right Difficulty in a Few Trials through Intelligent Trial-and-Error [16.297059109611798]
  Methods for dynamic difficulty adjustment allow games to be tailored to particular players to maximize their engagement. Current methods often only modify a limited set of game features such as the difficulty of the opponents, or the availability of resources. This paper presents a method that can generate and search for complete levels with a specific target difficulty in only a few trials.
  arXiv  Detail & Related papers  (2020-05-15T17:48:18Z)

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.