💻 computer science

Mastering Baghchal by Self-Play with Deep Reinforcement Learning

This paper presents a systematic evaluation of four deep reinforcement learning algorithms (DQN, REINFORCE, PPO, and MuZero) for mastering the asymmetric Nepali board game Baghchal through self-play, revealing that MuZero achieves the highest win rates via model-based planning while PPO offers the most practical balance of performance and computational efficiency.

Original authors: Ranjit Raut, Aarav Subedi, Sagun Rai

Published 2026-10-29

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Ranjit Raut, Aarav Subedi, Sagun Rai

Original paper licensed under CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

For decades, the field of artificial intelligence has been obsessed with games, using them as a proving ground to teach machines how to think. The goal is not merely to win at chess or Go, but to understand how an agent can learn complex strategies from scratch, without being told the rules by a human teacher. This process, known as reinforcement learning, works like a digital form of trial and error. An agent plays a game, receives a reward for a good move or a penalty for a bad one, and slowly adjusts its internal logic to maximize future rewards. While this approach has mastered symmetric games where both players have identical pieces and goals, it faces a much steeper climb when the players are fundamentally different. In these asymmetric scenarios, one side might have a few powerful units while the other commands a large, slower army, creating a puzzle where the path to victory looks completely different for each player. Understanding how machines navigate these uneven playing fields is crucial, not just for better game bots, but for developing artificial intelligence that can handle the messy, unequal realities of the real world.

In a recent study, researchers from Kathmandu University in Nepal turned their attention to Baghchal, a traditional board game from their own culture that perfectly embodies this asymmetry. Played on a five-by-five grid, the game pits four agile tigers against twenty goats. The tigers move first and can jump over goats to capture them, aiming to remove five goats from the board to win. The goats, who are placed on the board one by one in the opening phase, must work together to surround the tigers and cut off all their movement. If the goats succeed in trapping the tigers so they cannot move, the goats win. The game is played with perfect information, meaning both sides see the entire board at all times, yet the challenge lies in the vastly different roles: the tigers need aggressive, short-term tactics to hunt, while the goats require long-term, coordinated planning to build a defensive wall. Despite its strategic depth, Baghchal had received little attention from modern artificial intelligence researchers, who had largely focused on Western or East Asian games.

To explore how machines handle this unique challenge, the team trained four different types of learning algorithms to play both sides of the game against themselves. They did not program the agents with specific strategies; instead, they let the algorithms play thousands of games against copies of themselves, learning from the outcomes. The researchers tested a variety of learning styles: one that learned by memorizing the value of specific board positions, another that learned by guessing and checking entire game sequences, a third that balanced learning with stability, and a fourth that built an internal model of the game to imagine future moves. By having each algorithm play both the tiger and the goat, the researchers could see if a single learning method could adapt to two completely different ways of thinking, or if it would struggle to master one role while failing at the other.

The results revealed a clear hierarchy in how well these machines learned to play. The most successful algorithm was the one that built an internal model of the game, allowing it to simulate future scenarios before making a move. This approach, known as model-based planning, enabled the agent to think several steps ahead, a crucial skill for the goats who must plan their encirclement carefully. In the simulations, this advanced agent won 86 percent of the games when playing as the tiger and 62 percent when playing as the goat. It learned to make sacrifices, such as letting a goat escape temporarily to set up a better trap later, and it excelled at the long-term coordination required to stop the tigers. The researchers found that this ability to plan ahead was the single biggest factor in winning, as it allowed the agent to see the consequences of its actions far into the future.

However, the study also highlighted a practical trade-off. While the model-based agent was the strongest player, it was also the most demanding, requiring significantly more computer power and time to train. It took nearly twenty-five hours of continuous processing to reach its peak performance, and it was slower to make decisions during a game. In contrast, another algorithm, which learned by balancing exploration with stability, offered a compelling middle ground. It achieved strong win rates for both sides—73 percent as the tiger and 58 percent as the goat—but did so with much less computational effort and in less than half the training time. This suggests that for many real-world applications where resources are limited, a slightly less powerful but much more efficient system might be the better choice.

The researchers also uncovered how the nature of the game itself shaped the learning process. The tiger role proved easier for all the algorithms to master because the rewards were immediate and clear: capturing a goat gave an instant boost. This made the learning process stable and fast. The goat role, however, was much harder. The goats receive rewards only when they successfully trap the tigers, which can happen many moves after the initial setup. This delay made it difficult for the algorithms to figure out which early moves were helpful and which were not. Consequently, the algorithms that relied on immediate feedback struggled more with the goats, often failing to coordinate the twenty pieces into a cohesive defense. The study showed that while machines can learn to play asymmetric games, the difficulty of the role depends heavily on how quickly the game provides feedback on success.

Ultimately, this work demonstrates that modern artificial intelligence can learn to navigate complex, uneven playing fields without human instruction. The study confirms that the ability to plan ahead is the key to mastering games like Baghchal, where the path to victory requires thinking beyond the immediate next move. While the most powerful systems require significant computing resources, the findings suggest that efficient algorithms can still achieve high levels of skill, making advanced game-playing technology accessible even in environments with limited hardware. By applying these methods to a traditional Nepali game, the researchers not only advanced the science of artificial intelligence but also helped preserve a cultural heritage, proving that ancient strategies can teach modern machines valuable lessons about cooperation, strategy, and the art of thinking ahead.

Technical Summary: Mastering Baghchal by Self-Play with Deep Reinforcement Learning

1. Problem Statement

The paper addresses the application of modern deep reinforcement learning (RL) to Baghchal, a traditional Nepali asymmetric board game. Unlike the symmetric zero-sum games (e.g., Chess, Go) that dominate AI research, Baghchal presents unique challenges:

Role Asymmetry: Two players have structurally distinct roles. The Tiger player controls 4 pieces with aggressive capture mechanics, while the Goat player controls 20 pieces with defensive immobilization goals.
Heterogeneous Mechanics: The game features two distinct phases (placement and movement), varying action spaces, and different win conditions (Tigers win by capturing 5+ goats; Goats win by immobilizing all tigers).
Sparse and Delayed Rewards: The Goat role suffers from a "credit assignment" problem, where rewards are sparse and delayed (only upon successful immobilization), making it difficult to learn effective coordination among 20 pieces without communication.
Research Gap: While prior work utilized tabular Q-learning or AlphaZero-inspired variants, there was a lack of comprehensive benchmarks comparing modern deep RL paradigms (value-based, policy gradient, actor-critic, and model-based) specifically for this asymmetric, perfect-information environment.

2. Methodology

The authors implemented a systematic self-play training framework using PyTorch to evaluate four distinct deep RL algorithms: Deep Q-Network (DQN), REINFORCE, Proximal Policy Optimization (PPO), and MuZero.

Environment Design

State Representation: A $5 \times 5$ NumPy array (0=empty, 1=goat, 2=tiger) augmented with game features (goats in hand, captured count, phase indicator, move history).
Action Space: Discrete, position-based encoding with dynamic legal-move masking to prevent invalid actions.
Reward Structure: Designed to encourage strategic play. Tigers receive rewards for captures (+10) and winning (+100), with penalties for moves (-1) and illegal actions (-50). Goats receive rewards for survival (+5), strategic positioning (+10), and winning (+100), with penalties for being captured (-20) and illegal actions (-50).

Algorithm Implementations

DQN (Value-Based): Uses a Multi-Layer Perceptron (256-128 units) to estimate Q-values. Trained with experience replay (100k buffer) to handle sequential patterns.
REINFORCE (Policy Gradient): A Monte Carlo policy-gradient method using a state-independent baseline and entropy regularization to prevent premature convergence to deterministic policies.
PPO (Actor-Critic): Employs a clipped surrogate objective ( $\epsilon=0.2$ ) and Generalized Advantage Estimation ( $\lambda=0.95$ ) to ensure training stability, crucial for the Goat's defensive role.
MuZero (Model-Based): Learns a latent world model (representation, dynamics, and prediction networks) to plan 8–10 moves ahead via Monte Carlo Tree Search (MCTS) without explicit rule access.

Training Infrastructure

Hardware: Intel i7 (16 cores), NVIDIA RTX 3080 Ti (12 GB VRAM).
Protocol: All agents trained via self-play (100,000 games per algorithm). Models were evaluated every 1,000 games, with checkpoints saved every 5,000.
Fairness: Identical observation inputs and hardware settings were used for all algorithms to ensure performance differences reflect algorithmic properties rather than environmental artifacts.

3. Key Results

The study evaluated performance based on win rates, draw rates, average captures, convergence speed, and computational cost.

Quantitative Performance

MuZero achieved the highest performance across both roles:
- Tiger Win Rate: 86% ± 1.2%
- Goat Win Rate: 62% ± 2.1%
- Average Captures: 7.2
PPO emerged as the most balanced and practical algorithm:
- Tiger Win Rate: 73% ± 1.8%
- Goat Win Rate: 58% ± 2.7%
- It offered competitive performance with significantly lower computational overhead than MuZero.
DQN showed a strong bias toward the Tiger role (67% win rate) but struggled with the Goat role (47% win rate), suggesting value-based methods favor roles with denser reward signals.
REINFORCE exhibited high variance and slower convergence but demonstrated diverse strategic exploration.

Learning Dynamics and Strategic Behavior

Tiger Strategies: MuZero and PPO demonstrated long-term planning, utilizing tactics like "pincer moves," "sacrifice" (allowing a goat escape for better future captures), and "tempo control." DQN focused on immediate tactical captures but lacked long-term strategy.
Goat Strategies: MuZero excelled at defensive coordination, creating intricate structures and anticipating tiger moves. DQN failed at coordinated defense, prioritizing individual piece survival.
Convergence: DQN converged fastest (25,000 episodes) but plateaued early. MuZero took the longest to converge (45,000 episodes, 24.5 hours) but continued to improve beyond the convergence points of other algorithms.

Computational Efficiency

MuZero: Highest resource cost (3.8 GB peak memory, 85 ms inference time, 24.5 hours training).
DQN/REINFORCE: Lowest resource footprint (1.2 GB and 0.9 GB memory respectively; ~15-18 ms inference).
PPO: Achieved the best performance-to-resource ratio, making it suitable for resource-constrained environments.

4. Key Contributions

First Comprehensive Benchmark: This study provides the first head-to-head comparison of four major deep RL paradigms (DQN, REINFORCE, PPO, MuZero) on the asymmetric Baghchal game.
Analysis of Asymmetry: It highlights how algorithmic paradigms interact with role-based asymmetry, specifically noting that model-based planning (MuZero) is superior for long-horizon coordination, while value-based methods (DQN) struggle with sparse-reward defensive roles.
Cultural Preservation via AI: The work applies modern AI techniques to a Himalayan cultural game, addressing a gap in the literature where South Asian traditional games have received less attention compared to Western or East Asian games.
Strategic Insights: The paper documents emergent human-like strategies (e.g., sacrifice, tempo control) learned by agents, particularly by MuZero, demonstrating the capability of deep RL to master complex asymmetric multi-agent environments.

5. Significance and Claims

The authors claim that this work demonstrates the viability of modern deep RL in asymmetric board games where players have distinct roles and win conditions. The study concludes that:

MuZero is the most powerful agent for Baghchal due to its ability to perform model-based planning in a latent space, effectively solving the long-horizon credit assignment problem inherent in the Goat role.
PPO represents the most practical solution, offering a strong balance between playing strength and computational efficiency.
Role Asymmetry significantly impacts learning; algorithms that rely on dense reward signals (like DQN) naturally favor the Tiger role, whereas algorithms with better exploration and stability (like PPO and MuZero) are required to master the Goat role.

The paper modestly notes limitations, including MuZero's high computational cost and its specialization to the specific Baghchal environment, suggesting future work could explore Soft Actor-Critic (SAC) for sample efficiency and Multi-Agent DDPG (MADDPG) for explicit coordination.