International Draughts is a fun board game that's a bit like checkers but with more pieces and on a bigger board. It's all about moving your pieces, capturing your opponent, and trying to outsmart them. When one of your pieces reaches the other side, it becomes a 'king,' which is powerful. You win by capturing all your opponent's pieces or blocking them so they can't move.

Now, imagine trying to make a computer play this game. It's pretty hard because there are so many moves to think about. That's where the minimax and alpha-beta search algorithm come in. It's a smart way to help computers play games like International Draughts and Checkers.

The "minimax" part comes from maximizing your gains while minimizing your opponent's gains.

The alpha-beta algorithm is like a shortcut for the computer. Instead of looking at every move, it ignores the ones that don't matter much. This way, the computer doesn't waste time on bad moves and can think more about the good ones. It's like if you were playing and only focused on your best moves.

By using this algorithm, computers can play well. They can think ahead and make smart choices without taking too long. So, the alpha-beta algorithm helps computers be tough opponents in games like International Draughts, making the game exciting and challenging.

Draughts

International Draughts is a cool board game that's a bit like checkers but bigger and with more pieces. It's played on a big 10x10 board, each player starting with 20 pieces. The game is about diagonally moving your pieces and trying to capture your opponent's pieces by jumping over them.

Here's how it works: you move your pieces forward on the dark squares. If you see an opponent's piece next to yours and there's a space just past it, you can jump over their piece and capture it. If you can keep jumping over more pieces, you can capture them, too!

The game gets exciting when one of your pieces reaches the other side of the board. Then it turns into a "king," which can move forward and backward, making it super powerful.

You win the game if you capture all your opponent's pieces or if they can't move anymore. International Draughts is fun because it's easy to learn but makes you think hard about your moves. It's a popular game worldwide; there are even big tournaments where people compete to be the best.

Minimax

The essence of the algorithm comes down to a simple thing: find the move that will bring us the greatest increase in points and, at the same time, minimize the potential number of points of the opponent. This algorithm is often used in games in conjunction with alpha-beta search

Alpha-Beta Search

The alpha-beta search algorithm is a significant concept in computer AI, particularly in board games like Checkers. At its core, this algorithm is a smarter, more efficient version of the minimax algorithm, which is used to determine the best move in a game by considering all possible moves.

The alpha-beta algorithm enhances the minimax process by "pruning" or cutting off branches in the game tree that it deems unnecessary to explore. Essentially, it skips analyzing moves that won't affect the final decision, reducing the number of calculations the computer has to make. This is especially important in games like checkers, where the number of possible moves can be very large.

By employing this algorithm, AI in games can analyze possible moves more quickly and deeply, leading to stronger play. In practice, this means that an AI using alpha-beta search can be a formidable opponent, capable of foreseeing several moves ahead and making strategically sound decisions, all within a reasonable amount of computing time.

Scoring

For the algorithm to work correctly, we will need to evaluate the quality of each move, and for this, we will use the following scoring functions:

Score by piece count: we count the left items on the deck.
Score by defensive position: the deeper we move to the enemy’s side, the more points we get. For each next row, we get an extra 0.5 points.
Score by offensive positioning: The more first cells we have occupied by our checkers, the more points. This prevented the enemy from transferring his checker to the king.
Score by mobility: The more moves we can make, the more points

The final score for each color is a sum of all scores

Prepare

First, we need to initialize the project. I’m a little bit lazy, I’m going to use vite package

yarn create vite client --template vanilla-ts

Also we need checkers engine

yarn add @jortvl/draughts

And d3.js for render

yarn add d3
yarn add @types/d3 --dev

That’s enough for our project =)

Calculations

On each move we get FEN from the game engine

FEN

The initial position of the checkers board. This is used to record partial games (starting at some initial position). It is also necessary for some draughts variants where the initial position is not always the same as traditional checkers. If a FEN tag is used, a separate tag pair "SetUp" is required and have its value set to "1". as said wiki.

Example of fen:

B:W27,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50:B1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20

If we can simplify - it current board positions

export function getFen(fen: string): FEN {
    const regex = /^(B|W):(W(.*)):(B(.*))$/;

    let m = regex.exec(fen)

    if (!m) {
        throw new Error('Invalid FEN')
    }

    return {
        move: m[1] === "B" ? "B" : "W",
        white: m[3].split(','),
        black: m[5].split(','),
    }
}

convert fen to our purposes:

Count checkers for each color

export function scoreByPieceCount(board: FEN) {
    const KING_WEIGHT = 1.5; // Kings are usually more valuable
    let white_player_score = board.white.reduce((acc, row) => acc + (row.startsWith('K') ? KING_WEIGHT : 1), 0);
    let black_player_score = board.black.reduce((acc, row) => acc + (row.startsWith('K') ? KING_WEIGHT : 1), 0);

    return [white_player_score, black_player_score];
}

Score by defensive position. Each next row add 0.5 points to ~~griffindor~~ color and if we have king - it weight 6 points, for reason is king can be everywhere and not going to turn into king

export function scoreByDefensivePositioning(board: FEN) {
    let white_score = board.white.reduce((acc, row) => acc + (row.startsWith('K') ? 6 : (Math.floor((50 - parseInt(row, 10)) / 5) + 1) * 0.5), 0);
    let black_score = board.black.reduce((acc, row) => acc + (row.startsWith('K') ? 6 : (Math.floor(parseInt(row, 10) / 5) + 1) * 0.5), 0);

    return [white_score, black_score];
}

Offensive: we check initial positions for checkers

export function scoreByOffensivePositioning(board: FEN) {
    let white_score = ['46', '47', '48', '49', '50', 'K46', 'K47', 'K48', 'K49', 'K50'].filter((x) => board.white.includes(x)).length;
    let black_score = ['1', '2', '3', '4', '5', 'K1', 'K2', 'K3', 'K4', 'K5'].filter((x) => board.black.includes(x)).length;

    return [white_score, black_score];
}

Score by mobility: we check how much moves we can make. if we can take checker, it give us addition 10 points

export function scoreByMobility(fen: FEN) {
    let d1 = new Draughts();
    d1.load(`B:W${fen.white.join(',')}:B${fen.black.join(',')}`);

    let black_score = d1.moves().reduce((acc, cap) => acc + 1 + (cap.takes.length * 10), 0)
    d1.load(`W:W${fen.white.join(',')}:B${fen.black.join(',')}`);
    let white_score = d1.moves().reduce((acc, cap) => acc + 1 + (cap.takes.length * 10), 0)

    return [white_score, black_score];
}

And the most interesting thing is why I started writing this article:

function isGameOver(gameState: FEN) {
    return gameState.black.length === 0 || gameState.white.length === 0;
}

function getLegalMoves(gameState: FEN) {
    const d1 = new Draughts();
    d1.load(`${gameState.move}:W${gameState.white.join(',')}:B${gameState.black.join(',')}`);

    return d1.moves().map((x) => `${x.from}-${x.to}`).sort(() => Math.random() - 0.5);
}

function applyMove(gameState: FEN, move: string) {
    const d1 = new Draughts();
    d1.load(`${gameState.move}:W${gameState.white.join(',')}:B${gameState.black.join(',')}`);
    d1.move(move);
    return getFen(d1.fen());
}

export function alphaBeta(
    gameState: FEN,
    depth: number,
    paths: ABScore = {
        score: 0,
        path: []
    },
    alpha: number = -Infinity,
    beta: number = Infinity,
    maximizingPlayer: "B" | "W"
):
    ABScore {
    if (depth === 0 || isGameOver(gameState)) {
        return {
            score: combinedScore(gameState)[maximizingPlayer === "B" ? 1 : 0],
            path: paths.path
        };
    }

    if (gameState.move === maximizingPlayer) {
        let maxEval = {score: -Infinity, path: []};
        for (const move of getLegalMoves(gameState)) {
            const ev = alphaBeta(
                applyMove(gameState, move), depth - 1, {
                    score: 0,
                    path: paths.path.concat(move)
                }, alpha, beta, maximizingPlayer === "B" ? "W" : "B"
            );
            if (ev.score > maxEval.score) {
                maxEval = ev;
            }

            if (ev.score > alpha) {
                alpha = ev.score;
            }

            if (beta <= alpha) {
                break;
            }
        }
        return maxEval;
    } else {
        let minEval = {score: Infinity, path: []};
        for (const move of getLegalMoves(gameState)) {
            const ev = alphaBeta(
                applyMove(gameState, move),
                depth - 1,
                {
                    score: 0,
                    path: paths.path.concat(move)
                },
                alpha, beta,
                maximizingPlayer === "B" ? "W" : "B"
            );

            if (ev.score < minEval.score) {
                minEval = ev;
            }

            if (ev.score < beta) {
                beta = ev.score;
            }

            if (beta <= alpha) {
                break;
            }
        }
        return minEval;
    }
}

The basic principle by which the search works: at the first stage, find the move that will give us the highest score, then we look at all the opponent’s moves and see which moves will give him the minimum score and again look at our moves and discard the least relevant moves

Game

Basic markup

<!doctype html>
<html lang="en">
<head>
    <meta charset="UTF-8"/>
    <link rel="icon" type="image/svg+xml" href="/vite.svg"/>
    <meta name="viewport" content="width=device-width, initial-scale=1.0"/>
    <title>Vite + TS</title>
</head>
<body>
<div id="app"></div>
<div>
    <label for="depth">
        <input id="depth" value="2"/>
    </label>
    <button id="game">Run game</button>
</div>
<script type="module" src="/src/main.ts"></script>
</body>
</html>

Main game class:

export class Board {
    _board: Draughts
    _el: string;
    _moves: number;

    constructor(element: string) {
        this._board = Draughts()
        this._el = element;
        this._container = d3.select(element);
        this._moves = 0;
    }

    gameOver() {
        return this._board.gameOver();
    }

    fen() {
        return this._board.fen();
    }
}

Draw initial board

export class Board {
    constructor(element: string) {
				...
				this.drawBoard();
    }

		drawBoard() {
        const svg = this._container.append("svg")
            .attr("width", 600)
            .attr("height", 400);

        const gameBoard = svg.append('g')

        const checkers = svg.append('g')
        checkers.attr('class', 'checkers');

        let position_index = 0;
        for (let i = 0; i < 100; i += 1) {
            if ((i % 2) != Math.floor(i / 10) % 2) {
                position_index += 1;

                const cell = gameBoard.append('g').attr('class', `tile`).attr('transform', `translate(${(i % 10) * 40}, ${Math.floor(i / 10) * 40})`)
                cell.append('rect').attr('width', 40).attr('height', 40).attr("rx", 4).attr("ry", 4).style('fill', 'gray')
                cell.append('text').text(position_index).attr("x", 0).attr("y", 12);
            }
        }

        const score = svg.append('g').attr('class', 'score').attr('transform', `translate(410, 0)`);

        score.append('text').text('white').attr("x", 80).attr("y", 12);
        score.append('text').text('black').attr("x", 150).attr("y", 12);
        score.append('text').text('piece:').attr("x", 10).attr("y", 48);
        score.append('text').attr('class', 'white-piece').text('0').attr("x", 80).attr("y", 48);
        score.append('text').attr('class', 'black-piece').text('0').attr("x", 150).attr("y", 48);
        score.append('text').text('def:').attr("x", 10).attr("y", 84);
        score.append('text').attr('class', 'white-def').text('0').attr("x", 80).attr("y", 84);
        score.append('text').attr('class', 'black-def').text('0').attr("x", 150).attr("y", 84);
        score.append('text').text('mobility:').attr("x", 10).attr("y", 120);
        score.append('text').attr('class', 'white-mobility').text('0').attr("x", 80).attr("y", 120);
        score.append('text').attr('class', 'black-mobility').text('0').attr("x", 150).attr("y", 120);
        score.append('text').text('offensive:').attr("x", 10).attr("y", 156);
        score.append('text').attr('class', 'white-offensive').text('0').attr("x", 80).attr("y", 156);
        score.append('text').attr('class', 'black-offensive').text('0').attr("x", 150).attr("y", 156);
        score.append('text').text('total:').attr("x", 10).attr("y", 192);
        score.append('text').attr('class', 'white-total').text('0').attr("x", 80).attr("y", 192);
        score.append('text').attr('class', 'black-total').text('0').attr("x", 150).attr("y", 192);
        score.append('text').text('move:').attr("x", 10).attr("y", 228);
        score.append('text').attr('class', 'moves').text('0').attr("x", 80).attr("y", 228);
    }
}

Draw checkers (we redraw them after each move)

export class Board {
    constructor(element: string) {
				...
				this.draw();
    }

		draw() {
        d3.selectAll('g.checker').remove()
        const checkers = d3.select('g.checkers')
        const external_position = this._board.position();
        let position_index = 0;
        for (let row = 0; row < 10; row++) {
            const shifted = row % 2 !== 0 ? 1 : 0
            for (let col = 0; col < 10; col++) {
                if ((col + shifted) % 2 === 1) {
                    position_index += 1;
                    const pieceGroup = checkers.append('g')
                        .attr('transform', `translate(${col * 40 + 20}, ${row * 40 + 20})`)
                        .attr('class', `checker ${external_position[position_index]}`)
                        .attr('data-index', position_index)

                    switch (external_position[position_index]) {
                        case 'b':
                            pieceGroup.append('circle').attr('r', 10).style('fill', 'black')
                            break;
                        case 'B':
                            pieceGroup.append('circle').attr('r', 10).style('fill', 'black').style('opacity', 0.4)
                            break;
                        case 'w':
                            pieceGroup.append('circle').attr('r', 10).style('fill', 'white')
                            break;
                        case 'W':
                            pieceGroup.append('circle').attr('r', 10).style('fill', 'white').style('opacity', 0.4)
                            break;
                    }
                }
            }
        }
    }
}

Make move:

export class Board {
  	move(depth: number) {
        if (this._board.gameOver()) {
            console.log('game over')
            return;
        }

        let ab1 = alphaBeta(getFen(this._board.fen()), depth, {
                score: 0,
                path: []
            },
            -Infinity,
            Infinity,
            this._board.turn().toUpperCase()
        );

        let path = ab1.path.length ? ab1.path[0] : this.getRandomeMove();
        this._board.move(path);
        this.draw()
        this._moves += 1;
    }
}

And initialize game =)

const game = new Board('#app');

document.querySelector('#game').addEventListener('click', async () => {
    const depth = parseInt((document.querySelector('#depth') as HTMLInputElement).value, 10);

    let i = 1;
    while (!game.gameOver() && i < 300) {
        game.move(depth);
        game.drawScore();
        await new Promise((resolve) => setTimeout(resolve, 1000));
        i += 1;

    }
});

Basic game is done =) If I forget something, working example on GitHub

Results

Depth: 1

Depth: 2

Depth: 3

As the search depth increases, moves become more meaningful and less random, although the time spent calculating each move increases.

Conclusion

In the article, we quickly went over the minimax alpha-.beta search. Maybe I forgot something, but I’ll hope not =) Next time, I’ll try to add a couple of genetic algorithms here and see the results. The game’s code is available on Github.

Teaching a Machine to Play International Draughts Through Alpha-Beta Search