Alphazzle: Jigsaw Puzzle Solver with Deep Monte-Carlo Tree Search

• URL: http://arxiv.org/abs/2302.00384v1
• Date: Wed, 1 Feb 2023 11:41:21 GMT
• Title: Alphazzle: Jigsaw Puzzle Solver with Deep Monte-Carlo Tree Search
• Authors: Marie-Morgane Paumard, Hedi Tabia, David Picard
• Abstract summary: We introduce Alphazzle, a reassembly algorithm based on single-player Monte Carlo Tree Search (MCTS) A major difference with DRL algorithms lies in the unavailability of game reward for MCTS. We perform an in-deep ablation study that shows the importance of MCTS and the neural networks working together.
• Score: 30.43614740245788
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Solving jigsaw puzzles requires to grasp the visual features of a sequence of patches and to explore efficiently a solution space that grows exponentially with the sequence length. Therefore, visual deep reinforcement learning (DRL) should answer this problem more efficiently than optimization solvers coupled with neural networks. Based on this assumption, we introduce Alphazzle, a reassembly algorithm based on single-player Monte Carlo Tree Search (MCTS). A major difference with DRL algorithms lies in the unavailability of game reward for MCTS, and we show how to estimate it from the visual input with neural networks. This constraint is induced by the puzzle-solving task and dramatically adds to the task complexity (and interest!). We perform an in-deep ablation study that shows the importance of MCTS and the neural networks working together. We achieve excellent results and get exciting insights into the combination of DRL and visual feature learning.

Related papers

• LinSATNet: The Positive Linear Satisfiability Neural Networks [116.65291739666303]
  This paper studies how to introduce the popular positive linear satisfiability to neural networks. We propose the first differentiable satisfiability layer based on an extension of the classic Sinkhorn algorithm for jointly encoding multiple sets of marginal distributions.
  arXiv  Detail & Related papers  (2024-07-18T22:05:21Z)
• Bridging Logic and Learning: A Neural-Symbolic Approach for Enhanced Reasoning in Neural Models (ASPER) [0.13053649021965597]
  This paper introduces an approach designed to improve the performance of neural models in learning reasoning tasks. It achieves this by integrating Answer Set Programming solvers and domain-specific expertise. The model shows a significant improvement in solving Sudoku puzzles using only 12 puzzles for training and testing.
  arXiv  Detail & Related papers  (2023-12-18T19:06:00Z)
• Active search and coverage using point-cloud reinforcement learning [50.741409008225766]
  This paper presents an end-to-end deep reinforcement learning solution for target search and coverage. We show that deep hierarchical feature learning works for RL and that by using farthest point sampling (FPS) we can reduce the amount of points. We also show that multi-head attention for point-clouds helps to learn the agent faster but converges to the same outcome.
  arXiv  Detail & Related papers  (2023-12-18T18:16:30Z)
• Monte-Carlo Tree Search for Multi-Agent Pathfinding: Preliminary Results [60.4817465598352]
  We introduce an original variant of Monte-Carlo Tree Search (MCTS) tailored to multi-agent pathfinding. Specifically, we use individual paths to assist the agents with the the goal-reaching behavior. We also use a dedicated decomposition technique to reduce the branching factor of the tree search procedure.
  arXiv  Detail & Related papers  (2023-07-25T12:33:53Z)
• The Clock and the Pizza: Two Stories in Mechanistic Explanation of Neural Networks [59.26515696183751]
  We show that algorithm discovery in neural networks is sometimes more complex. We show that even simple learning problems can admit a surprising diversity of solutions.
  arXiv  Detail & Related papers  (2023-06-30T17:59:13Z)
• Pathfinding Neural Cellular Automata [23.831530224401575]
  Pathfinding is an important sub-component of a broad range of complex AI tasks, such as robot path planning, transport routing, and game playing. We hand-code and learn models for Breadth-First Search (BFS), i.e. shortest path finding. We present a neural implementation of Depth-First Search (DFS), and outline how it can be combined with neural BFS to produce an NCA for computing diameter of a graph. We experiment with architectural modifications inspired by these hand-coded NCAs, training networks from scratch to solve the diameter problem on grid mazes while exhibiting strong ability generalization
  arXiv  Detail & Related papers  (2023-01-17T11:45:51Z)
• Are Deep Neural Networks SMARTer than Second Graders? [85.60342335636341]
  We evaluate the abstraction, deduction, and generalization abilities of neural networks in solving visuo-linguistic puzzles designed for children in the 6--8 age group. Our dataset consists of 101 unique puzzles; each puzzle comprises a picture question, and their solution needs a mix of several elementary skills, including arithmetic, algebra, and spatial reasoning. Experiments reveal that while powerful deep models offer reasonable performances on puzzles in a supervised setting, they are not better than random accuracy when analyzed for generalization.
  arXiv  Detail & Related papers  (2022-12-20T04:33:32Z)
• Understanding Deep Neural Function Approximation in Reinforcement Learning via $\epsilon$-Greedy Exploration [53.90873926758026]
  This paper provides a theoretical study of deep neural function approximation in reinforcement learning (RL) We focus on the value based algorithm with the $epsilon$-greedy exploration via deep (and two-layer) neural networks endowed by Besov (and Barron) function spaces. Our analysis reformulates the temporal difference error in an $L2(mathrmdmu)$-integrable space over a certain averaged measure $mu$, and transforms it to a generalization problem under the non-iid setting.
  arXiv  Detail & Related papers  (2022-09-15T15:42:47Z)
• Deep Reinforcement Learning Using a Low-Dimensional Observation Filter for Visual Complex Video Game Playing [1.2468700211588883]
  It requires the processing of large amounts of data from high-dimensional observation spaces, frame by frame, and the agent's actions are computed according to deep neural network policies. In this paper, we propose a low-dimensional observation filter that allows a deep Q-network agent to successfully play in a visually complex and modern video-game, called Neon Drive.
  arXiv  Detail & Related papers  (2022-04-24T22:17:08Z)
• Dual Monte Carlo Tree Search [0.0]
  We show that Dual MCTS performs better than one of the most widely used neural MCTS algorithms, AlphaZero, for various symmetric and asymmetric games. Dual MCTS uses two different search trees, a single deep neural network, and a new update technique for the search trees using a combination of the PUCB, a sliding-window, and the epsilon-greedy algorithm.
  arXiv  Detail & Related papers  (2021-03-21T23:34: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.