Tree Search Algorithms For Chinese Chess
DOI:
https://doi.org/10.54097/hset.v12i.1358Keywords:
Minimax, Alpha-beta pruning, Monte Carlo Tree Search, AlphaZero.Abstract
Computer Games are an important aspect of Artificial Intelligence (AI) which has produced many representative algorithms of optimal strategies. Therefore, many AI researchers have applied game theory to various board games in an attempt to find the essence of games and grasp the core of AI behaviour. AlphaGo is a very famous and typical chess-playing program that uses Monte Carlo tree search (MCTS) to estimate the value of each node in the search tree and optimize the possible results. Chinese chess is one of the traditional chess versions with its typical strategy. However, due to its late start and high complexity, there are many more technical problems to be solved. In this paper, we recommend two commonly used search frameworks for Chinese chess: the minimax algorithm and the alpha-beta pruning algorithm. On this basis, to deal with the complex and changeable situation, the Chinese chess algorithm based on Monte Carlo tree search and appropriate neural network evaluation function is studied.
Downloads
References
Campbell, M., Hoane Jr, A. J., & Hsu, F. H. (2002). Deep blue. Artificial intelligence, 134(1-2), 57-83.
Sang-Hun, C. (2016). Google’s computer program beats Lee Sedol in Go tournament. New York Times.
J. X. Chen, "The Evolution of Computing: AlphaGo," in Computing in Science & Engineering, vol. 18, no. 4, pp. 4-7, July-Aug. 2016, doi: 10.1109/MCSE.2016.74.
Shannon, C. E. (1950). XXII. Programming a computer for playing chess. The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science, 41(314), 256-275.
G. Wu, "The Total Number Calculation of States of Chinese Chess Based on the Dynamic Programming of Computer Games," 2021 33rd Chinese Control and Decision Conference (CCDC), 2021, pp. 2188-2191, doi: 10.1109/CCDC52312.2021.9601527.
Strong, G. (2011). The minimax algorithm. Trinity College Dublin.
Knuth, D. E., & Moore, R. W. (1975). An analysis of alpha-beta pruning. Artificial intelligence, 6(4), 293-326.
Browne, C. B., Powley, E., Whitehouse, D., Lucas, S. M., Cowling, P. I., Rohlfshagen, P., ... & Colton, S. (2012). A survey of monte carlo tree search methods. IEEE Transactions on Computational Intelligence and AI in games, 4(1), 1-43.
Gelly, S., & Wang, Y. (2006, December). Exploration exploitation in go: UCT for Monte-Carlo go. In NIPS: Neural Information Processing Systems Conference On-line trading of Exploration and Exploitation Workshop.
P. Auer, N. Cesa-Bianchi and P. Fischer, "Finite-time analysis of the multiarmed bandit problem", Mach. Learn., vol. 47, no. 2, pp. 235-256, 2002.
Zhang, H., & Yu, T. (2020). AlphaZero. In Deep Reinforcement Learning (pp. 391-415). Springer, Singapore.
Liu, J., Qi, Y., Meng, Z. Y., & Fu, L. (2017). Self-learning monte carlo method. Physical Review B, 95(4), 041101.
C. -H. Hsueh, K. Ikeda, S. -G. Nam and I. -C. Wu, "Analyses of Tabular AlphaZero on NoGo," 2020 International Conference on Technologies and Applications of Artificial Intelligence (TAAI), 2020, pp. 254-259, doi: 10.1109/TAAI51410.2020.00054.
Downloads
Published
Issue
Section
License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.