TL;DR
This paper explores the generality of Monte Carlo Tree Search (MCTS) with Upper Confidence Trees (UCT) by applying it to Havannah, a complex board game known for its difficulty for AI. The authors demonstrate that UCT, a technique highly successful in Go, also performs well in Havannah, validating its broad applicability to strategy games.
What Problem Does This Paper Address?
While AI has made significant strides in games like Go, achieving superhuman performance, other complex strategy games remain challenging. Havannah, a game played on a hexagonal board, is particularly difficult for computers due to its lack of easily identifiable patterns, absence of a natural evaluation function, and a large action space. The best Havannah-playing software currently lags far behind human experts, with a prize even offered for a computer program that can beat a human expert. This paper investigates whether the successful MCTS/UCT approach, which revolutionized computer Go, can be effectively applied to Havannah, thus testing its generality.
Methods
The core of the paper focuses on applying and adapting the Monte Carlo Tree Search (MCTS) algorithm, specifically using the Upper Confidence Trees (UCT) variant. UCT balances exploration (trying new moves) and exploitation (focusing on moves that have historically performed well) by using a bandit formula to select moves for simulation.
The authors explore several key components of UCT:
- Bandit Formulas: They compare Hoeffding's bound and Bernstein's bound for the exploration term in the UCT formula. Bernstein's bound is shown to be more effective.
- Scaling of UCT: They investigate how increasing the number of simulations per move affects performance, observing that while performance generally improves, the gains might plateau or require re-tuning.
- Guiding Exploration: They examine techniques to improve exploration beyond standard UCT:
- Progressive Widening: This method prioritizes exploring a subset of moves, gradually expanding the set of considered moves as simulations increase. The authors found this technique, when used without a heuristic, did not significantly improve performance in Havannah.
- Rapid Action Value Estimate (RAVE): This heuristic leverages statistics from all simulations that include a particular move, not just those from the current node. RAVE showed promise, especially with larger action spaces, but required careful tuning.
Datasets
The paper does not introduce new datasets. Instead, it uses the game of Havannah itself as the benchmark. Experiments are conducted on boards of size 5 and 8. The program is also tested against an existing Havannah-playing program called "Havannah-Applet."
Key Insights and Ideas
- Generality of UCT: The most significant insight is that UCT, a technique that revolutionized computer Go, is indeed effective for Havannah, a game with different characteristics. This suggests MCTS/UCT is a robust framework for a wide range of complex strategy games.
- Bernstein's Bound Superiority: Bernstein's bandit formula consistently outperformed Hoeffding's bound, indicating its better suitability for balancing exploration and exploitation in this context.
- RAVE's Potential and Pitfalls: RAVE shows promise, particularly for games with large action spaces like Havannah, and its efficiency can increase with board size. However, it requires more tuning than standard UCT, especially with a high number of simulations.
- Progressive Widening's Limited Impact (without heuristics): While progressive widening is effective in Go (often with pattern-based heuristics), its benefit in Havannah was not significant when used without such domain-specific knowledge.
Key Results
- Bernstein's Formula: Achieved success rates up to 65% compared to Hoeffding's formula.
- UCT Scaling: The success rate of UCT with 2k simulations against UCT with k simulations was nearly 75%, a strong result compared to the typical 63% in Go.
- RAVE Performance: RAVE showed significant improvements, reaching 100% success on 1347 games on size 8 boards when K=0 (effectively disabling the exploration term in the UCT formula). However, its efficiency decreased with a large number of simulations per move, requiring more tuning.
- Havannah-Applet Match: The authors' program, using RAVE with no exploration term and no progressive widening, defeated the Havannah-Applet easily, even when playing as black and with significantly fewer simulations per move.
Limitations and Future Work
- Progressive Widening without Heuristics: The paper notes that progressive widening, while shown to be effective in Go with pattern-based heuristics, did not yield significant improvements in Havannah when used without such heuristics. This suggests that incorporating domain-specific knowledge could enhance its performance.
- RAVE Tuning: RAVE's efficiency can decrease with a large number of simulations per move, requiring more tuning. The authors suggest that better tuning might yield better results.
- Automated Interface: The authors mention that running more extensive experiments was difficult due to the lack of an automated interface for the Havannah-Applet.
- Future Work: The paper implies that further tuning of RAVE and potentially combining it with other techniques could lead to even stronger performance. Investigating the impact of patterns, if they can be discovered for Havannah, could also be a fruitful direction.
Summary updated