Single-player games: introduction to a new solving method
Van Lishout, François[Université de Liège - ULg > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Systèmes et modélisation >]
University of Liège, Liège, Belgium
DEA en sciences appliquées
de Marneffe, Pierre-Arnoul
[en] Sokoban ; artificial intelligence ; games
[en] In many games, the machine has become stronger than the best human players. Machines have already beaten the human World Champion in famous games like Checkers, Chess, Scrabble and Othello. However, mankind has not been humbled by chips in all games. The best human players are still stronger than computers in games like Go, Poker, Chinese Chess and Hex. In this thesis, we will focus on a new way to model single-player games in order to improve the performances of the machine. We will demonstrate this technique on the game of Sokoban.
This thesis gives also an original presentation of the classical state-space algorithms. Usually, only a high-level description with abstract data types is given. Here we will present all the algorithms with the semi-formal-method proposed by de Marneffe. The invariants specified in this work have not been taken from the literature. They have all been reconstructed from the original idea of the algorithm in order to produce a clear description of the latter and to prove its correctness. This approach has led to a contribution for the A* algorithm. The practical performances have indeed been improved for a particular implementation choice of practical interest.