Complexity and retrograde analysis of the game Dou Shou Qi

Complexity and retrograde analysis of the game Dou Shou Qi

Van Rijn, J.N.
Vis, J.K.

2013-11-07

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.

http://resolver.tudelft.nl/uuid:e5dd7ef8-cdb4-4e00-a164-b67eb2de51b1

Conference proceedings

conference paper

(c) 2013 Van Rijn, J.N.; Vis, J.K.