JiangJun: Mastering Xiangqi by Tackling Non-Transitivity in Two-Player Zero-Sum Games
Abstract
This paper presents an empirical exploration of non-transitivity in perfect-information games, specifically focusing on Xiangqi, a traditional Chinese board game comparable in game-tree complexity to chess and shogi. By analyzing over 10,000 records of human Xiangqi play, we highlight the existence of both transitive and non-transitive elements within the game’s strategic structure. To address non-transitivity, we introduce the JiangJun algorithm, an innovative combination of Monte-Carlo Tree Search (MCTS) and Policy Space Response Oracles (PSRO) designed to approximate a Nash equilibrium. We evaluate the algorithm empirically using a WeChat mini program and achieve a Master level with a 99.41% win rate against human players. The algorithm’s effectiveness in overcoming non-transitivity is confirmed by a plethora of metrics, such as relative population performance and visualization results. Our project site is available at https://sites.google.com/view/jiangjun-site/.
Cite
Text
Li et al. "JiangJun: Mastering Xiangqi by Tackling Non-Transitivity in Two-Player Zero-Sum Games." Transactions on Machine Learning Research, 2023.Markdown
[Li et al. "JiangJun: Mastering Xiangqi by Tackling Non-Transitivity in Two-Player Zero-Sum Games." Transactions on Machine Learning Research, 2023.](https://mlanthology.org/tmlr/2023/li2023tmlr-jiangjun/)BibTeX
@article{li2023tmlr-jiangjun,
title = {{JiangJun: Mastering Xiangqi by Tackling Non-Transitivity in Two-Player Zero-Sum Games}},
author = {Li, Yang and Xiong, Kun and Zhang, Yingping and Zhu, Jiangcheng and McAleer, Stephen Marcus and Pan, Wei and Wang, Jun and Dai, Zonghong and Yang, Yaodong},
journal = {Transactions on Machine Learning Research},
year = {2023},
url = {https://mlanthology.org/tmlr/2023/li2023tmlr-jiangjun/}
}