2019/04/27 by Zhang, Zhujun
#Computational Complexity (cs.CC) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1904.13205
Dou Shou Qi is a Chinese strategy board game for two players. We use a EXPTIME-hardness framework to analyse computational complexity of the game. We construct all gadgets of the hardness framework. In conclusion, we prove that Dou Shou Qi is EXPTIME-complete.