2021/12/06 by Wang, Cong, Lu, Tongwei
#Artificial Intelligence (cs.AI) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2112.02989
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.