Optimised Playout Implementations for the Ludii General Game System

Key insights

6 takeaways

01
Optimized playout strategies in the Ludii general game system achieved a median speedup of 5.08 times and a mean speedup of 6.17 times compared to standard implementations.See it on page 1
02
The research recorded a maximum performance gain of 34.31 times faster in the game of Go by utilizing specialized, rule-based playout optimizations.See it on page 10
03
Three new optimization strategies—Add-to-Empty, Filter, and No-Repetition playouts—were developed to bypass the computational overhead of generating full legal move lists during simulations.See it on page 4
04
These methods employ rejection sampling to maintain correct move distributions while significantly reducing the processing time required for tree search algorithms like MCTS.See it on page 5
05
The Ludii system automatically detects which optimization strategy to apply based on the game's description language, ensuring efficient execution across diverse game structures.See it on page 1
06
Empirical testing across 145 different games confirmed that these optimizations maintain the integrity of game-playing agents while enabling deeper and more effective search processes.See it on page 1

Summary

The primary objective of this research is to enhance the efficiency of playouts within the Ludii general game system, a critical component for tree search algorithms like Monte-Carlo Tree Search (MCTS). By developing specialized, rule-based optimizations, the system can significantly reduce the computational overhead associated with simulating game trajectories. The thesis posits that by tailoring playout implementations to specific game structures—specifically those involving simple placement, conditional filtering, or repetition constraints—the system can achieve substantial speedups without compromising the integrity of the game-playing agent.

The study introduces three distinct optimization strategies: Add-to-Empty playouts for games where pieces are placed on empty board positions without movement; Filter playouts for games where moves are subject to postconditions, such as in Chess or Go; and No-Repetition playouts for games governed by state-history constraints. These methods utilize rejection sampling to avoid the expensive computation of legal move lists and postconditions during the playout phase. The Ludii system automatically detects the applicability of these optimizations based on the game’s description language, ensuring that the most efficient method is applied to each game.

Empirical evaluation across 145 games demonstrates that these optimizations are highly effective. The median speedup observed is 5.08 times faster than standard implementations, with a mean speedup of 6.17 and a maximum speedup of 34.31 in the game of Go. The methodology involved running random playouts on a single CPU core, comparing the number of playouts per second between standard and optimized versions. The results confirm that these optimizations provide significant performance gains across a broad range of game types while maintaining correct move distributions, thereby enabling deeper and more effective search processes in general game playing.