On the complexity of Dark Chinese Chess
This work addresses the challenge of analyzing complex imperfect-information games, which is incremental as it applies known computational methods to a specific game variant.
The paper tackles the complexity analysis of dark Chinese chess, a variant with imperfect information and stochastic elements, by designing a self-play program to compute game tree complexity and average information set size, and proposing an algorithm to count information sets.
This paper provides a complexity analysis for the game of dark Chinese chess (a.k.a. "JieQi"), a variation of Chinese chess. Dark Chinese chess combines some of the most complicated aspects of board and card games, such as long-term strategy or planning, large state space, stochastic, and imperfect-information, which make it closer to the real world decision-making problem and pose great challenges to game AI. Here we design a self-play program to calculate the game tree complexity and average information set size of the game, and propose an algorithm to calculate the number of information sets.