Maastricht University

Anytime Sequential Halving in Monte-Carlo Tree Search

This research introduces "Anytime Sequential Halving," a novel selection strategy for Monte-Carlo Tree Search (MCTS) designed to address the limitations of standard Sequential Halving (SH).

• Anytime Sequential Halving (ASH) enables the use of Sequential Halving in MCTS by allowing the algorithm to be interrupted at any moment while maintaining the simple regret optimization benefits of standard Sequential Halving.
• ASH functions by executing iterative passes of the standard Sequential Halving process, ensuring the agent can return a decision at any arbitrary time budget.
• In empirical testing across ten distinct board games within the Ludii general game playing system, ASH demonstrated performance competitive with standard UCT.

Measuring Board Game Distance

This analysis explores methodologies for quantifying the distance between board games within the Ludii general game system.

Automatic Generation of Board Game Manuals

The research introduces a framework for the automatic generation of board game manuals within the Ludii general game system.

Optimised Playout Implementations for the Ludii General Game System

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).

• 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.
• The research recorded a maximum performance gain of 34.31 times faster in the game of Go by utilizing specialized, rule-based playout optimizations.
• 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.

General Board Geometry

The Ludii general game system provides a comprehensive framework for modeling the geometry of diverse board games through graph-based representations.

• The Ludii system utilizes a graph-based framework of vertices, edges, and cells to model board geometry, successfully supporting the implementation of over 950 traditional strategy games.
• The system employs a modular methodology of tilings, shapes, and graph operators to construct complex, non-standard board topologies from simple primitives.
• Automated topological detection enables the system to identify relationships like adjacency and orthogonality, allowing movement rules to remain consistent across diverse board structures.