An Efficient Chinese Checkers Implementation: Ranking, Bitboards, and BMI2 pext and pdep Instructions

摘要: The game of Chinese Checkers has a computationally expensive move generation function. Finding legal moves dominates the performance of a Chinese Checkers program. This paper describes a bitboard representation of the Chinese Checkers board, how to efficiently generate and apply moves to the board, and how to rank and unrank states. When available, the BMI2 PDEP (parallel bits deposit) and PEXT (parallel bit extract) instructions offer significant efficiency gains, especially over a non-bitboard based implementation.