JiangJun: Mastering Xiangqi by Tackling Non-Transitivity in Two-Player Zero-Sum Games

Yang Li, Kun Xiong, Yingping Zhang, Jiangcheng Zhu, Stephen Mcaleer +4 more
8/9/2023
cs.AI

No confident code implementation found for this paper.

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 \url{https://sites.google.com/view/jiangjun-site/}.

View on arXivView PDF

Code Implementations

No confident code match yet

We couldn't find an author-owned or strongly-evidenced community implementation for this paper. Any repos shown below are weak matches — verify before relying on them.

No code implementations found yet.

Know of an implementation? Let us know in the comments below!

Similar Papers

Minibal: Balanced Game-Playing Without Opponent Modeling

85% match2026

Dominated Actions in Imperfect-Information Games

84% match2025

Dominated Actions in Imperfect-Information Games

84% match2025

Proof Number Based Monte-Carlo Tree Search

82% match1 repo32023

Computing Evolutionarily Stable Strategies in Imperfect-Information Games

82% match2025

CFR-p: Counterfactual Regret Minimization with Hierarchical Policy Abstraction, and its Application to Two-player Mahjong

82% match2023

Cite this paper

@article{li2023jiangjun,
  title  = {JiangJun: Mastering Xiangqi by Tackling Non-Transitivity in Two-Player Zero-Sum Games},
  author = {Yang Li and Kun Xiong and Yingping Zhang and Jiangcheng Zhu and Stephen Mcaleer and Wei Pan and Jun Wang and Zonghong Dai and Yaodong Yang},
  year   = {2023},
  eprint = {2308.04719},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/abs/2308.04719v1}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2308.04719.svg)](https://codeofpaper.com/paper/2308.04719)

Discussion