Affiliations: [a] School of Information Engineering, Nanchang University, Nanchang, Jiangxi, China | [b] School of Software Engineering, Jiangxi Argricultural University, Nanchang, Jiangxi, China
Abstract: The Mahjong game has widely been acknowledged to be a difficult problem in the field of imperfect information games. Because of its unique characteristics of asymmetric, serialized and multi-player game information, conventional methods of dealing with perfect information games are difficult to be applied directly on the Mahjong game. Therefore, AI (artificial intelligence)-based studies to handle the Mahjong game become challenging. In this study, an efficient AI-based method to play the Mahjong game is proposed based on the knowledge and game-tree searching strategy. Technically, we simplify the Mahjong game framework from multi-player to single-player. Based on the above intuition, an improved search algorithm is proposed to explore the path of winning. Meanwhile, three node extension strategies are proposed based on heuristic information to improve the search efficiency. Then, an evaluation function is designed to calculate the optimal solution by combining the winning rate, score and risk value assessment. In addition, we combine knowledge and Monte Carlo simulation to construct an opponent model to predict hidden information and translate it into available relative probabilities. Finally, dozens of experiments are designed to prove the effectiveness of each algorithm module. It is also worthy to mention that, the first version of the proposed method, which is named as KF-TREE, has won the silver medal in the Mahjong tournament of 2019 Computer Olympiad.
Keywords: Computer game, game-tree search, Mahjong, imperfect information game
DOI: 10.3233/ICG-210179
Journal: ICGA Journal, vol. 43, no. 1, pp. 2-25, 2021
