Complexity and retrograde analysis of the game Dou Shou Qi
Jan N. van Rijn, Jonathan K. Vis · Research Repository (Delft University of Technology) · 2013
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. 1