Name
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 4x4 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 10(13) elements. In order to deal with this large state space, we present a local variation of the Value-Iteration approach appropriate to solve the 15-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. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.3233/978-1-61499-330-8-45 | Frontiers in Artificial Intelligence and Applications |
Keywords | Field | DocType |
15-Puzzle Game,Reinforcement Learning,Value-Iteration | Combinatorial game theory,Computer science,Markov decision process,Theoretical computer science,15 puzzle,Artificial intelligence,Machine learning,Mathematical game | Conference |
Volume | ISSN | Citations |
257 | 0922-6389 | 1 |
PageRank | References | Authors |
0.36 | 2 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Bastian Bischoff | 1 | 154 | 10.64 |
| duy nguyentuong | 2 | 438 | 26.22 |
| Heiner Markert | 3 | 53 | 5.97 |
| Alois Knoll Knoll | 4 | 1700 | 271.32 |