Abstract
Reinforcement Learning has recently surfaced as a very powerful tool to solve complex problems in the domain of board games, wherein an agent is generally required to learn complex strategies and moves based on its own experiences and rewards received. While RL has outperformed existing state-of-the-art methods used for playing simple video games and popular board games, it is yet to demonstrate its capability on ancient games. Here, we solve one such problem, where we train our agents using different methods namely Monte Carlo, Qlearning and Expected Sarsa to learn optimal policy to play the strategic Royal Game of Ur. The state space for our game is complex and large, but our agents show promising results at playing the game and learning important strategic moves. Although it is hard to conclude that when trained with limited resources which algorithm performs better overall, but Expected Sarsa shows promising results when it comes to fastest learning.
Introduction
The Royal Game of Ur is a 4,500-year-old Mesopotamian strategy game that combines stochasticity from dice rolls with high-stakes positioning. Unlike modern games like Go or Chess, ancient board games remain relatively under-explored in the field of Reinforcement Learning (RL). The game presents a unique challenge due to its "war zones"—where pieces can be captured and sent back to the start—and "safe zones" where they are protected. This structure creates a complex state space and a significant "credit assignment problem," making it difficult for agents to determine which early-game moves lead to eventual victory. This study investigates whether standard RL algorithms can navigate these complexities and discover optimal strategies without prior domain knowledge.
Methodology
The researchers developed a custom simulator to train agents using three classic RL approaches: Monte Carlo (MC), Q-learning, and Expected Sarsa.
Learning Algorithms
- Monte Carlo (MC): Updates value estimates only after an entire game (episode) concludes.
- Q-learning: An off-policy Temporal Difference (TD) learner that updates based on the maximum possible future reward.
- Expected Sarsa: An on-policy TD learner that updates based on the expected value of future actions, considering the agent's current exploration policy.
Reward Shaping and State Representation
To overcome the sparsity of rewards in a simple win/loss scenario, the authors implemented reward shaping. Agents received +10 for capturing an opponent, +20 for landing on a safe square, -1 for each turn spent in a vulnerable war zone, and +100 for winning.
Furthermore, the state space was generalized by encoding board positions as integers from 1 to 24. This allowed agents to learn the value of specific squares regardless of which piece occupied them, facilitating better generalization across different game scenarios.
Results and Discussion
Agents were trained for 100,000 episodes through self-play and against a random-move baseline.
Performance Metrics
- Win Rates: Q-learning achieved the highest win rate at 60%, followed by Monte Carlo (55%) and Expected Sarsa (54%).
- Learning Efficiency: Expected Sarsa demonstrated the fastest learning curve, showing a rapid decrease in the number of moves required to finish a game.
- Strategic Discovery: The agents independently discovered sophisticated strategies, such as prioritizing moves that transition pieces from the end of the vulnerable "war zone" into a "safe zone."
Limitations
Due to computational constraints, the simulation was limited to 4 pieces per player instead of the traditional 7. Additionally, 100,000 training episodes represent a relatively small sample size for a state space of this complexity.
Conclusion
This research demonstrates that standard RL algorithms can effectively learn to play the Royal Game of Ur. While Q-learning provided the highest win rate in this study, Expected Sarsa proved to be the most efficient learner. Future work will focus on scaling the simulation to the full 7-piece game and implementing Deep Reinforcement Learning techniques to further enhance agent performance.
Summary updated