Complexity and retrograde analysis of the game Dou Shou Qi

Conference paper (2013)
Copyright: © 2013 Van Rijn, J.N.; Vis, J.K.
More Info
expand_more

Published Date

07-11-2013

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Abstract

Dou Shou Qi is a game in which players control a number of pieces, aiming to move one of these onto a certain square. We will present a proof showing that this game is PSPACE-hard. Furthermore, we have implemented an analyzing engine and created an endgame tablebase containing all configurations with up to four pieces. These are the first steps towards theoretically solving the game. Finally, we report on some interesting patterns which we found by analyzing the endgame tablebase.

Files

Paper_48.pdf
(pdf | 0.191 Mb)