Reference : Single-player games: introduction to a new solving method
Dissertations and theses : Master of advanced studies dissertation
Engineering, computing & technology : Computer science
Single-player games: introduction to a new solving method
Van Lishout, François mailto [Université de Liège - ULiège > 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
Wolper, Pierre mailto
Boigelot, Bernard mailto
Gribomont, Pascal mailto
de Marneffe, Pierre-Arnoul mailto
[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.

File(s) associated to this reference

Fulltext file(s):

Open access
vanlishout_dea06.pdfAuthor postprint1.09 MBView/Open

Bookmark and Share SFX Query

All documents in ORBi are protected by a user license.