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.
More recently, researchers focus on frameworks which could be used to prove hardness of games. In 2010, Fori s ek @cite_4 introduced a basic NP-hardness framework for 2D platform games. In 2012, Aloupis, Demaine and Guo @cite_15 introduced a elegant NP-hardness framework, and they used the framework to analyse complexity of several video games. In 2014, Viglietta @cite_0 established some general schemes relating the computational complexity of 2D platform games. In 2015, @cite_10 introduced a new PSPACE-hardness framework. In our note @cite_7 , we introduced a EXPTIME-hardness framework for 2D games, and we will use this framework to discuss complexity of Dou Shou Qi in this note.
@cite_4 @cite_7 @cite_0 @cite_15 @cite_10
1501441673 2925971084 2152152733 1749523692
We analyze the computational complexity of various two-dimensional platform games. We state and prove several meta-theorems that identify a class of these games for which the set of solvable levels is NP-hard, and another class for which the set is even PSPACE-hard. Notably COMMANDERKEEN is shown to be NP-hard, and PRINCE OF PERSIA is shown to be PSPACE-complete. We then analyze the related game Lemmings, where we construct a set of instances which only have exponentially long solutions. This shows that an assumption by Cormode in [3] is false and invalidates the proof that the general version of the LEMMINGS decision problem is in NP. We then augment our construction to only include one entrance, which makes our instances perfectly natural within the context of the original game. We review NP-hardness framework and PSPACE-hardness framework for a type of 2D platform games. We introduce a EXPTIME-hardness framework by defining some new gadgets. We use these hardness frameworks to analyse computational complexity of Xiangqi (Chinese Chess) and Janggi (Korean Chess). We construct all gadgets of the hardness frameworks in Xiangqi and Janggi. In conclusion, we prove that Xiangqi and Janggi are both EXPTIME-complete. We establish some general schemes relating the computational complexity of a video game to the presence of certain common elements or mechanics, such as destroyable paths, collectible items, doors opened by keys or activated by buttons or pressure plates, etc. Then we apply such "metatheorems" to several video games published between 1980 and 1998, including Pac-Man, Tron, Lode Runner, Boulder Dash, Pipe Mania, Skweek, Prince of Persia, Lemmings, and Starcraft. We obtain both new results, and improvements or alternative proofs of previously known results. We prove NP-hardness results for five of Nintendo's largest video game franchises: Mario, Donkey Kong, Legend of Zelda, Metroid, and Pokemon. Our results apply to generalized versions of Super Mario Bros.?1-3, The Lost Levels, and Super Mario World; Donkey Kong Country 1-3; all Legend of Zelda games; all Metroid games; and all Pokemon role-playing games. In addition, we prove PSPACE-completeness of the Donkey Kong Country games and several Legend of Zelda games.