Computer games are one of the most important research areas in artificial intelligence. These games fall into two fundamentally different classes: perfect information games and imperfect information games. In perfect information games such as Go and Chess, the current state of the game is fully accessible to both players. In games such as Dark Chess and Poker, the players have imperfect information: they have only partial knowledge about the current state of the game. Particularly, many Dark Chess programs have just been developed in recent years and they have a lot of room to improve their algorithms and implementations.
The data structure is the foundation of programming and algorithm design. A proper data structure can improve code efficiency. In this research, we apply the BitBoard data structure which was commonly used in chess programs to build our Dark Chess program DarkCraft. We also investigate the special characteristics of Dark Chess to fit the requirements of BitBoard and hence reduce the computation time. Furthermore, some techniques are integrated to improve the playing strength.
In this study, we have designed and implemented a Dark Chess program DarkCraft which participated in the 16th Computer Olympiad held in Tilburg, the Netherlands in 2011, and won the gold medal in the Dark Chess tournament.