Mastering Baghchal by Self-Play with Deep Reinforcement Learning

Abstract Baghchal is a two-player asymmetric board game of Nepali origin. In the gameplay, four tigers attempt to capture goats while twenty goats seek to immobilize the tigers. Baghchal has received limited attention in the deep reinforcement learning (RL) literature despite its strategic complexity, perfect information structure, and cultural significance. We present a systematic investigation of four deep reinforcement learning algorithms, viz. Deep Q-Network (DQN), REINFORCE, Proximal Policy Optimization (PPO), and MuZero. These algorithms are applied to both sides of asymmetric gameplay through self-play training in Baghchal. Each of these algorithms is evaluated in terms of win rate, draw rate, average captures, training convergence, and computational cost. In our experimental results, MuZero achieves the highest performance in both roles, attaining 86% Tiger win rate and 62% Goat win rate. This is attributed to its model-based planning via Monte Carlo Tree Search (MCTS). PPO emerges as the most practical algorithm as it offers competitive performance across both asymmetric roles at substantially lower computational overhead than the rest of the algorithms, including MuZero. While analyzing emergent strategic behavior of these algorithms, a model-based approach, viz. MuZero, excels at long-horizon planning, whereas value-based methods, viz. DQN, exhibit a strong preference for the Tiger role due to its denser reward signal.