Minimaxer Part 1 - Building a minimax library in Typescript

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

Some time ago I decided to try build an AI that could beat me at the board game Azul. It was a success, it beats me more often than not on the hardest difficulty, and I wrote an overview about how it works.

This post outlines the typescript library, named minimaxer, that I developed as the core part of the AI, that can be used with any deterministic 2-player turn based game.

The source code has changed a bit from the snippets in the post, but the core is the same

•   NPM Package
•   Source Code
•   Documentation

What is minimax? #

The general idea behind minimax is to look ahead a number of turns in a game at all the possible outcomes and select a move that minimises the maximum possible loss, hence the name minimax.

The algorithm assumes that each player plays perfectly, and sets an upper bound on the loss after the moves have been played.

For a game where the player is trying to maximise the score, the equivalent maximin algorithm can be used.

Imagine a game where each turn, the player has 2 moves to choose from. Player 1 is trying to get the largest score, Player 2 the smallest. Player 1 may have 2 options like this:

The above diagram is the game tree. The top node represents the current game state, which is 0 therefore a draw, each branch is a possible move to a child node representing new gamestates with associated values.

Player 1 is looking for the maximum score, which is 2, and this value propagates back to the root, such that the value of this tree looking 1 move in advance is 2. This is highlighted below:

What about the opponents possible moves in response? Player 2 is trying to minimise the value, so will choose the smallest of its child nodes, as highlighted in yellow:

The minimum and maximum child values propagate back up the tree depending on which player picks the moves. Looking 2 moves ahead actually shows that Player 1’s best move is the right side rather than the left, although the value at the root is still 2.

This is the minimax algorithm. A rigorous approach to searching ahead a certain number of moves and finding the sequence of optimal moves for each player that returns the move that guarantees the best minimum result for the first player.

For a more info, see wikipedia or this section of my previous post.

Game Tree #

As shown above, looking ahead into the future can be represented by a game tree. Each node on the tree is a state of the game, each branch is a move. The root node is the current game state from which the player is trying to pick the best move.

Representing the tree in code #

The main constituent of the tree is the nodes. A node is represented by a Node class that holds a reference to its parent (if it is not root), a list of its children, its best child and the value of the game state at that node.

Each node can either be a root, which is the start of the game, an inner node, or a leaf, which is the end of the game. The aim property represents the desired outcome for the player to play the next move at that node, i.e trying to maximise or minimise the score.

const enum NodeType {
    ROOT,
    INNER,
    LEAF,
}
const enum NodeAim {
    MIN = -1,
    MAX = 1,
}
class Node {
    parent: Node | undefined;
    children: Node[] = [];
    child: Node | undefined;
    value = 0;

    constructor(
        public type: NodeType,
        public aim
    ) {}

}

This is enough to represent a full tree, but not really useful for solving games and beating opponents. More is required to make it interact with the games, in a generic way.

Generics #

Each node represents a state in the game from which a number of moves can be played. E.g for chess the state is the position of all the pieces on the board, and the moves are all the possible squares the active player could move their pieces. Therefore the game tree needs to hold this information.

To add this in a game agnostic fashion, generic types are used for both the game state (GS) and moves (M). This way, the types can be specified for any game.

class Node<GS, M> {
    parent: Node<GS, M> | undefined;
    children: Node<GS, M>[] = [];
    child: Node<GS, M> | undefined;
    value = 0;

    constructor(
        public type: NodeType,
        public aim,
        public gamestate: GS,
        public moves: M[],
        public move?: M
    ) {}

}

The node constructor now requires a gamestate and a list of moves, which can be used by the minimax algorithm. It optionally takes a move argument, which is the move used to get to the node.

Growing the tree #

The process for creating the game tree goes as follows:

1. Start at the root node
2. Get all the moves and create child nodes
3. For each child that isn’t a LEAF node, repeat from step 2

We therefore need a method of creating child nodes, and a recursive function call to expand the child nodes.

Branching #

Creating a child node from a parent node is the equivalent of playing a move in the parent gamestate to get to the child gamestate. This is a game specific operation, so must be implemented for each game.

However, it would be nice to have a standardised way of calling the function, which is where typescript interfaces come in.

The interface specifies how the function should look, so that a user of the library can implement it correctly. This function is then passed to the library and used internally when child nodes are required to be made. It looks something like this:

interface CreateChildNodeFunc<GS, M> {
    (parent: Node<GS, M>, move: M): Node<GS, M>;
}

The arguments to the function are the parent node, which holds the gamestate, and the move to play to create the child node. The return type is another node (the child).

An implementation of this function may look like this.

function createChild(parent: Node<Gamestate, Move>, move: Move):Node<GameState,Move> {
    // Clone the gamestate first to not mess with parent
    const child_gamestate = clone(parent.gamestate);
    // Play the move
    play_move(child_gamestate, move)
    // Get the moves for the next player
    get_moves(child_gamestate)
    // Create the child node and return
    return new Node(
        child_gamestate.finished ? NodeType.LEAF : NodeType.INNER,
        child_gamestate.activeplayer ? NodeAim.MIN : NodeAim.MAX,
        child_gamestate,
        child_gamestate.moves,
        move
        )
}

The game has the types Gamestate and Move which resolve the generic types GS and M. The key functions that the game must implement are cloning of the gamestate, playing a move and generating a list of moves available.

The child is created with the node type set to LEAF if it is the end of the game or INNER otherwise. The aim is set to MIN or MAX depending on the player who plays the next turn.

Recursive branching #

Time to make a tree! The tree is also implemented as a class, because who doesn’t love OOP. It looks a little bit like this:

class Tree<GS, M> {
    constructor(public root: Node<GS, M, D>) {
    }

    CreateChildNode: CreateChildNodeFunc<GS, M, D> = () => {
        throw Error("Create child node callback is not implemented");
    };

    createChildren(node: Node<GS, M, D>) {
        node.children = new Array<Node<GS, M, D>>(n_moves);
        for (let i = 0; i < n_moves; i++) {
            const child = this.CreateChildNode(node, node.moves[i]);
            child.parent = node;
            node.children[i] = child;
        }
    }

    createTree(node: Node<GS, M, D>) {
        // Create child nodes
        this.createChildren(node);
        // Create grandchild for each child that isn't a LEAF node
        for (const child of node.children) {
            if (child.type != NodeType.LEAF) {
                this.createTree(child);
            }
        }
    }

}

The CreateTree method is called recursively on each non leaf node in the tree. Calling it from the root node will branch out the entire tree. For the imaginary game from before, it would look like this:

// Create gamestate and get moves
const gamestate = new Gamestate()
get_moves(gamestate)
// Create root node
const root = new Node (
    NodeType.ROOT,
    NodeAim.MAX,
    gamestate,
    gamestate.moves
)
// Create the tree and assign the callback function
const tree = new Tree(root)
tree.CreateChldNode = createChild
// Create the full tree
tree.createTree(tree.root)

Minimax / Maximin #

Evaluation #

There is one more piece of the puzzle to perform a minimax search. Game state evaluation. A function is required that takes a gamestate and returns a number that represents its relative value.

This could be as simple as 1 for a win, -1 for a loss, and 0 otherwise. It could be the difference between the player’s scores (for games that have score) or it could be some complex series of calculations such as those used in chess engines.

This is the interface for the game state evaluation function that takes a node and returns the gamestate evaluation.:

interface EvaluateNodeFunc<GS, M> {
    (node: Node<GS, M>): number;
}

This needs adding to the tree class so it can be overridden and called when required:

class Tree<GS, M> {
    ...
    EvaluateNode: EvaluateNodeFunc<GS, M> = (node: Node<GS, M>) => {
        // empty
    };

}

The core of the algorithm #

Everything is ready, time to search the tree. The minimax function is very similar to the createTree method used earlier. It acts recursively on nodes until a condition has been reached. However instead of searching the whole tree (as that may be completely unfeasible), the search will end at a certain depth.

Below is an implementation of minimax/maximin that sits as a method on the Tree class.

class Tree<GS, M> {
    ...
    minimax (node: Node<GS, M>, depth:number ) {
        // Check if node is LEAF or reached depth
        if (node.type == NodeType.LEAF || depth == 0){
            node.value = this.EvaluateNode(node)
        } else {
            // Create all the children for the node
            this.createChildren(node)
            // Iterate through children to find the best (aim dependant)
            let best = node.children[0];
            for (const child of node.children){
                // Recursive minimax call at depth - 1
                this.minimax(child, depth-1)
                // Check if child is better
                if (node.type == NodeType.MAX){
                    if (child.value > best.value){
                        best = child
                    }
                } else {
                    if (child.value < best.value){
                        best = child
                    }
                }
            }
            // Assign the best child and value to parent
            node.child = child
            node.value = child.value
        }
    }

}

As in the example from the start of the post, the maximum or minimum value (depending on turn) from the children at each level propagate back up to the root node.

To use this new method, the tree would be constructed in the same way as before, the callbacks assigned, and then minimax called on the root node to a certain depth.

// Create gamestate and get moves
const gamestate = new Gamestate()
get_moves(gamestate)
// Create root node
const root = new Node (
    NodeType.ROOT,
    NodeAim.MAX,
    gamestate,
    gamestate.moves
)
// Create the tree and assign the callback functions
const tree = new Tree(root)
tree.CreateChldNode = createChild
tree.EvaluateNode = evaluateNode
// Run the minimax algorithm
tree.evaluate(tree.root, 3)

The evaluation of the root could then be accessed at tree.root.child.value and the best move at tree.root.child.move.

Job done!

Negamax #

There is another algorithm I would like to add to the current iteration, and that is negamax. In reality it is exactly the same as minimax, but the implementation can be a little simpler, and potentially more performant.

Negamax exploits the fact that the aim (maximising or minimising) alternates every move, and tweaks the tree slightly so that it is always looking for a maximum.

class Tree<GS, M> {
    ...
    negamax (node: Node<GS, M>, depth:number, aim:NodeAim ) {
        // Check if node is LEAF or reached depth
        if (node.type == NodeType.LEAF || depth == 0){
            node.value = - aim * this.EvaluateNode(node)
        } else {
            // Create all the children for the node
            this.createChildren(node)
            // Iterate through children to find the best (aim dependant)
            let best = node.children[0];
            for (const child of node.children){
                // Recursive minimax call at depth - 1
                this.negamax(child, depth-1, -aim)
                // Check if child is better
                if (child.value > best.value){
                    best = child
                }
            }
            // Assign the best child and value to parent
            node.child = child
            node.value = -child.value
        }
    }

}

The changes from the minimax function are as highlighted:

• The constructor now takes an aim argument, instead of using the one on the node.
• The value assigned to the node depends on the aim.
• The aim is alternated by the recursive call to negamax.
• The condition for finding the best value is always the maximum value
• The value assigned from the best child to the parent is negated

Its a small change but can be very useful for simplifying the addition of other features later on.

Conclusion #

Presented is an implementation of the minimax algorithm for 2 player games in typescript. It’s built using generics to work with any game and even has negamax for some potential performance boosts, but there is a lot more to add yet.

Read Part 2 for alpha-beta pruning, iterative deepening, node sorting and more.