Shut The Box

Monte Carlo Tree Search (MCTS) is a powerful heuristic search algorithm that has revolutionized artificial intelligence in game playing. This project showcases MCTS in a simple classic pub game “Shut The Box” in Unity 3d .

“Shut The Box” is a game of strategy and chance:

1. Players face a box with 9 or 12 numbered tiles (1-9 or 1-12).
2. On each turn, a player rolls dice and must “shut” (close) tiles that sum to the roll.
3. Play continues until no more moves are possible.
4. The winner is the player who shuts all tiles or has the lowest sum of remaining open tiles.

Here is the project repository on Github.

MCTS: The Time Stone of search algorithms

“I went forward in time… to view alternate futures. To see all the possible outcomes of the coming conflict.” - Doctor Strange

In “Avengers: Infinity War”, Doctor Strange uses the Time Stone to view 14,000,605 possible futures, searching for the one path that leads to victory against Thanos.

Just as Doctor Strange, MCTS simulates millions of potential moves to find the best one, leading to victory

The key differences?

MCTS doesn’t require an Infinity Stone.

Pseudo code which shows how MCTS works:

while (timeRemaining() > 0)
{
    // Selection: Choose the most promising node
    Node selected = Selection(rootNode);

    // Expansion: Add a new child node
    Node expanded = Expansion(selected);

    // Simulation: Play out the game randomly
    double result = Simulation(expanded);

    // Backup: Update the statistics
    Backup(expanded, result);
}

private Node Selection(Node node)
{
    while (node.IsFullyExpanded() && !node.IsTerminal())
    {
        node = node.SelectBestChild(UCB1);
    }
    return node;
}

private Node Expansion(Node node)
{
    if (node.IsTerminal()) return node;

    var unexpandedMoves = node.GetUnexpandedMoves();
    var move = unexpandedMoves[Random.Range(0, unexpandedMoves.Count)];
    return node.Expand(move);
}

private double Simulation(Node node)
{
    while (!node.IsTerminal())
    {
        node = node.MakeRandomMove();
    }
    return node.GetScore();
}

private void Backup(Node node, double result)
{
    while (node != null)
    {
        node.UpdateStats(result);
        node = node.Parent;
    }
}

This loop continually improves the search tree, gathering more accurate statistics with each iteration.

Some benchmarks that I did in the game:

AI vs RandomPlayer (12 tiles, MCTS 500k iterations):

Strategy vs AI (12 tiles, MCTS 1 million iterations):

Note that more iterations -> more accurate

Future Enhancements

Key points to consider:

1. MCTS is inherently parallelizable, especially at the simulation level.
2. Unity’s Job System is well-suited for this task. It allows you to run multiple simulations in parallel across available CPU cores.
3. The fun part will be managing shared data and combining results from parallel simulations.

Looking ahead, there are several exciting avenues to explore:

1. Adapt the algorithm for more complex games. MCTS is applicable to any game as long as a “scoring function” or way to evaluate the playouts is well defined.
2. Combine MCTS with machine learning techniques, inspired by AlphaGo’s success.

Check full source code on GitHub, experiment with the parameters, and perhaps adapt it to other games.