2 citations · 4 across the 7 of their papers we have counts for
6 papers · 1 filter
Perfect Information Hearthstone is PSPACE-hard
Zhujun Zhang
We consider the computational complexity of Hearthstone which is a popular online CCG (collectible card game). We reduce a PSPACE-complete problem, the partition game, to perfect i…
A Note on the Computational Complexity of Selfmate and Reflexmate Chess Problems
Zhujun Zhang
A selfmate is a Chess problem in which White, moving first, needs to force Black to checkmate within a specified number of moves. The reflexmate is a derivative of the selfmate in…
A Note on Computational Complexity of Kill-all Go
Zhujun Zhang
Kill-all Go is a variant of Go in which Black tries to capture all white stones, while White tries to survive. We consider computational complexity of Kill-all Go with two rulesets…
A Note on Computational Complexity of Dou Shou Qi
Zhujun Zhang
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 h…
A Note on Hardness Frameworks and Computational Complexity of Xiangqi and Janggi
Zhujun Zhang
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…
Complexity Analysis of 2-Heterogeneous Minimum Spanning Forest Problem
Zhujun Zhang, Qiang Sun
For complexity of the heterogeneous minimum spanning forest problem has not been determined, we reduce 3-SAT which is NP-complete to 2-heterogeneous minimum spanning forest problem…