This paper considers the variation of a popular 2-player imperfect information game Chinese dark chess (CDC). The version is solved by computing the game-theoretical value of each position for all possible material combinations with at most four red pieces and four black pieces. The experimental results show that where to make the first move, which must be a flip, is the most important factor to affect the outcome of a game. We find that choosing a square to flip that has the best-expected outcome may not be the best strategy. Instead, a square that has the best-expected difference before and after the first move is made should be chosen. We also discover that CDC is unfair and it is favorable to the second player, but some openings are fair. We believe observations and techniques made here can be used to improve the performance of programs for playing the original full version of CDC.
Althöfer, I. & Voigt, R. (2014). Einstein würfelt nicht. In Spiele, Rätsel, Zahlen (pp. 41–47). Springer.
2.
Bonnet, F. & Viennot, S. (2017). Toward solving “Einstein würfelt nicht!”. In In Advances in Computer Games (pp. 13–25). Springer. doi:10.1007/978-3-319-71649-7_2.
3.
Chang, H.-J., Chen, J.-C., Fan, G.-Y., Hsueh, C.-W. & Hsu, T.-s. (2018). Using Chinese dark chess endgame databases to validate and fine-tune game evaluation functions. ICGA Journal, 40(2).
4.
Chang, H.-J., Hsueh, C.-W. & Hsu, T.-s. (2015). Convergence and correctness analysis of Monte-Carlo tree search algorithms: A case study of 2 by 4 Chinese dark chess. In Computational Intelligence and Games (CIG), 2015 IEEE Conference on (pp. 260–266). IEEE. doi:10.1109/CIG.2015.7317963.
5.
Chen, B.-N., Shen, B.-J. & Hsu, T.-s. (2010). Chinese dark chess. ICGA Journal, 33(2), 93–106. doi:10.3233/ICG-2010-33204.
6.
Chen, J.-C., Lin, T.-Y., Chen, B.-N. & Hsu, T.-s. (2015). Equivalence classes in Chinese dark chess endgames. IEEE Transactions on Computational Intelligence and AI in Games, 7(2), 109–122. doi:10.1109/TCIAIG.2014.2317832.
7.
Chen, J.-C., Lin, T.-Y., Hsu, S.-C. & Hsu, T. (2012). Design and implementation of computer Chinese dark chess endgame database. In Proceeding of TCGA Workshop (pp. 5–9).
8.
Ciancarini, P. & Favini, G.P. (2010). Playing the perfect kriegspiel endgame. Theoretical Computer Science, 411(40–42), 3563–3577. doi:10.1016/j.tcs.2010.05.019.
9.
Hsueh, C.-H., Wu, I-C., Hsu, T.-s. & Chen, J.-C. (2018). An investigation of strength analysis metrics for game-playing programs: A case study in Chinese dark chess. ICGA Journal, 40(2).
10.
Knuth, D.E. (2008). The Art of Computer Programming, Volume 4, Fascicle 0: Introduction to Combinatorial Algorithms and Boolean Functions (1st ed.). Addison-Wesley Professional.
11.
Korf, R.E. (1985). Depth-first iterative-deepening: An optimal admissible tree search. Artificial intelligence, 27(1), 97–109. doi:10.1016/0004-3702(85)90084-0.
12.
Lin, C.-H., Shan, Y.-C. & Wu, I-C. (2011). Tournament framework for computer mahjong competitions. In Technologies and Applications of Artificial Intelligence (TAAI), 2011 International Conference on (pp. 286–291). IEEE. doi:10.1109/TAAI.2011.56.
13.
Scott, D. (1991). The problematic nature of participation in contract bridge: A qualitative study of group-related constraints. Leisure Sciences, 13(4), 321–336. doi:10.1080/01490409109513148.
14.
Silver, D., Huang, A., Maddison, C.J., Guez, A., Sifre, L., Van Den Driessche, G., Schrittwieser, J., Antonoglou, I., Panneershelvam, V., Lanctot, M., et al. (2016). Mastering the game of go with deep neural networks and tree search. nature, 529(7587), 484–489. doi:10.1038/nature16961.
15.
Silver, D., Hubert, T., Schrittwieser, J., Antonoglou, I., Lai, M., Guez, A., Lanctot, M., Sifre, L., Kumaran, D., Graepel, T., et al. (2017). Mastering chess and shogi by self-play with a general reinforcement learning algorithm. Arxiv preprint. Available at arXiv:1712.01815.
16.
Sturtevant, N.R. & Saffidine, A. (2017). A study of forward versus backwards endgame solvers with results in Chinese checkers. In Workshop on Computer Games (pp. 121–136). Springer.
17.
Tesauro, G. (1995). Td-gammon: A self-teaching backgammon program. In Applications of Neural Networks (pp. 267–285). Springer. doi:10.1007/978-1-4757-2379-3_11.
18.
Thompson, K. (1986). Retrograde analysis of certain endgames. ICCA Journal, 9(3), 131–139.
19.
van den Herik, H.J., Uiterwijk, J.W.H.M. & Van Rijswijck, J. (2002). Games solved: Now and in the future. Artificial Intelligence, 134(1–2), 277–311. doi:10.1016/S0004-3702(01)00152-7.
20.
Yen, S.-J., Chou, C.-W., Chen, J.-C., Wu, I-C. & Kao, K.-Y. (2015). Design and implementation of Chinese dark chess programs. IEEE Transactions on Computational Intelligence and AI in Games, 7(1), 66–74. doi:10.1109/TCIAIG.2014.2329034.
