Solving the 15-Puzzle Game Using Local Value-Iteration
Lists
Only you see this
Abstract
The 15-puzzle is a well-known game which has a long history stretching back in the 1870's. The goal of the game is to arrange a shuffled set of 15 numbered tiles in ascending order, by sliding tiles into the one vacant space on a 4×4 grid. In this paper, we study how Reinforcement Learning can be employed to solve the 15-puzzle problem. Mathematically, this problem can be described as a Markov Decision Process with the states being puzzle configurations. This leads to a large state space with approximately 1013 elements. In order to deal with this large state space, we present a local variation of the Value-Iteration approach appropriate to solve the15-puzzle starting from arbitrary configurations. Furthermore, we provide a theoretical analysis of the proposed strategy for solving the 15-puzzle problem. The feasibility of the approach and the plausibility of the analysis are additionally shown by simulation results.
BibTeX
@inproceedings{bischoff2013solving,
author = {Bastian Bischoff and Duy Nguyen-Tuong and Heiner Markert and Alois Knoll},
title = {{Solving the 15-Puzzle Game Using Local Value-Iteration}},
booktitle = {SCAI},
year = {2013},
doi = {10.3233/978-1-61499-330-8-45},
}| Solving the Rubik's Cube Without Human Knowledge | arXiv · 2018 |
| Value Iteration with Options and State Aggregation | arXiv · 2015 |
| On Bootstrapping Local Search with Trail-Markers | IJCAI · 1995 |
| Graph Value Iteration | arXiv · 2022 |
| Potential-based Reward Shaping in Sokoban | arXiv · 2021 |
| Solitaire: Man Versus Machine | NeurIPS · 2004 |