Minimaxer Part 3 - Implementing an AI player and benchmarking

• Part 1 - Minimax and negamax
• Part 2 - Alpha-beta pruning and iterative deepening
• Part 3 - Mancala AI and benchmarking
• Part 4 - Code Optimisation

Mancala is a relatively simple game with many variations. The game revolves around picking up stones from pits and trying to get more stones in your store than the opponent. The rules I am using are based on these, but I have removed the rule about double turns as it complicates the minimax search a little bit.

This post looks at using the minimaxer library with mancala and then benchmarking the different search configurations to see which is best.

Minimaxer

•   NPM Package
•   Source Code
•   Documentation

Making mancala #

I won’t get too bogged down in the details here, I’ll but give a quick overview of how the game is implemented. It should also give an insight into how any game could utlise the library.

The full implementation can be found on Github.

export class mancala {
    pits: Array<Array<number>> = [];
    stores: Array<number> = [];
    activePlayer = 0;
    moves: Array<number> = [];
    end = false;

    constructor() {}

    start() {
        // Fill the pits, empty the stores
        // Generate the list of moves
    }

    generateMoves() {
        // Generate a list of moves: this.moves
    }

    playMove(move: number) {
        // Move tokens around the board
        // Check for steal
        // Check for game end condition
        // Generate moves for the next turn
    }

    clone(): mancala {
        const clone = new mancala();
        clone.pits = this.pits.map((pit) => {
            return pit.slice();
        });
        clone.stores = this.stores.slice();
        clone.activePlayer = this.activePlayer;
        clone.moves = this.moves.slice(0);
        clone.end = this.end;
        clone.enableDoubleMove = this.enableDoubleMove;
        return clone;
    }

}

The main game methods are self-explanatory with the comments above. The most interesting and important method is probably clone so I have left that in. It is required as every time a new child node is made, the parent game state must be cloned before playing a move to ensure that the child game state does not interfere with the parent.

Bringing in the minimaxer library #

The game is made, now it needs connecting to minimaxer to create an ‘AI’ player. For that we need a callback function that can play a move in the game to create a new node:

import * as minimax from "minimaxer";
// callback function
export const createChildCallback: minimax.CreateChildNodeFunc<mancala, number, number> = (parent, move) => {
    // First create a clone of the gamestate
    const new_gamestate = parent.gamestate.clone();
    // Apply the move
    new_gamestate.playMove(move);
    // Create a new node with correct node type
    const node = new minimax.Node(
        new_gamestate.end ? minimax.NodeType.LEAF : minimax.NodeType.INNER,
        new_gamestate,
        move,
        0,
    );
    // Assign value and moves and return.
    node.value = new_gamestate.stores[0] - new_gamestate.stores[1];
    node.moves = new_gamestate.moves;
    return node;
};

This does everything we need: cloning, playing a move, creating a child node, evaluating the node and attaching the next moves to the node.

The value is relatively simple for mancala, as the difference between the amount of stones in the player’s pits does a sufficiently good job of evaluating the game state.

Running a search #

If you are reading this post after Part 1 and 2, the library interface may look a little different. The principles are the same but now there is a Negamax class that extends the Tree class. It has an opts property used to set different search parameters, and a result object is returned via a call to the evaluate method.

Using it looks like this:

import *as mancala from "./games/mancala.js";
import* as minimax from "../dist/index.js";

// Create game and start it
const game = new mancala.mancala();
game.start();
// Create root node
const root = new minimax.Node(minimax.NodeType.ROOT, game, 0, 0, minimax.NodeAim.MAX, game.moves);
// Create tree from root
const tree = new minimax.Negamax(root);
// Assign the callback
tree.CreateChildNode = mancala.createChildCallback;
// Choose the search depth and method
tree.opts.depth = 7;
tree.opts.method = minimax.SearchMethod.DEPTH;
// Run the search
const result = tree.evaluate();
console.log(result);

The result printed to the screen is:

{
    exit: 0,
    move: 5,
    value: 2,
    depth: 7,
    outcomes: 116944,
    nodes: 146630,
    pathLength: 8
}

This shows that:

• The searched finished because it reached the specified depth
• The best move is 5 (picking the stones from the far-right pit)
• The score difference between the players will be 2 (if perfect moves are played)
• The tree was searched to depth 7
• There are 116944 possible positions after 7 turns
• There are 146630 total nodes in the tree
• The shortest possible path to the end of the game is at least 8 moves.

Benchmarking #

Now that the minimax algorithm has been developed, improvements such as alpha-beta pruning have been added, and there is a game to try out, it is time to see how well it all performs.

I have been using the benny package to run the benchmark tests. It is a wrapper around the benchmark package that is really simple to use and gives some nice results.

I also followed this great article about getting consistent benchmarking results on Linux. It basically suggests temporarily turning off lots of fancy CPU features, pinning the task to a single core and prevent other applications from interfering with results. The results before doing that were quite variable and unreliable, so it definitely works.

What to compare #

Within the opts property of the Negamax class in the example above there are a few parameters that can be changed to alter the behavior of the search.

The ones I have mentioned in the previous 2 posts are

• opts.pruning: none or alpha-beta
• opts.presort: true to sort child nodes before searching
• opts.method: depth, deepening or time-limited search.

For depth based searches, this gives a few possible combinations for a search to particular depth.

How to compare #

The benny benchmarking library repeatedly calls a function, timing its execution, and delivering an average operations/second (op/s). The higher the better.

Results #

A search to depths 5 and 6 on mancala is used, and here are the results:

A few conclusions can be drawn from these results:

• Deepening is not significantly slower than a depth search, likely because most of the time is spent in the final depth anyway.
• Alpha-beta pruning is a significant improvement over standard negamax/minimax for mancala. Between 4-12x performance at these depths.
• Presorting nodes in deepening alpha-beta search is another huge jump in performance, and by far the best method.
• That Alpha-beta is probably more effective the deeper the search goes.

Time limited search #

Another way of comparing the performance of the configurations is to see what depth they reach in a given time-period. This is perhaps a more useful metric for creating an AI player.

The results table below shows the depth reached (and fully searched) for each configuration when given 100ms, 1s and 10s

The seemingly large improvement of presorting over standard alpha-beta doesn’t necessarily translate to better time limited searches. Due to the exponential growth of the tree with every move, each configuration can just get stuck searching for a long time on the final depth, with nothing to differentiate them.

Both the alpha-beta methods are still noticeably better than the standard minimax.

Conclusion #

The game mancala has been implemented in typescript, and using the minimaxer library, an game playing ‘AI’ has been created to select moves.

In benchmarks it was found that adding alpha-beta pruning brings a large performance boost, and then presorting the child nodes improves it even more.

Most importantly, it turns out that picking the tiles closest to your store on the first turn is the best option.

Part 4 will look at making the search even faster, this time by making code optimisations.