Solving the 15-Puzzle Game Using Local Value-Iteration

Bastian Bischoff, Duy Nguyen-Tuong, Heiner Markert, Alois Knoll

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},
}
Figure