Implementing checkers with minimax using alpha-beta pruning in C#

December 10, 2019

I recenlty finished a fun project: an engine for simplified version of checkers using Minimax with Alpha-Beta with pruning for selecing best move.

You can find the source code here, and here’s a short video showing the engine playing against itself:

This project was fun for a couple of reasons, one of the was I haven’t used C# for quite some time but the whole experience on Mac and Linux was very nice, the language and the tooling is really great, I would not mind using it for some projects in the future.

One other reason this was an interesting experience for me is the complexity of it and to be more specific, estimating where the complexity will be before the project started.

I don’t remember when I started doing this but in general before every task or project I try to figure out, what the hard part will be. It’s very helpful for many obvious reasons and I’m mostly good at it but here I completely failed.

I thought the most difficult and time consuming part would be implementing the Minimax and those alpha and beta cuts but in fact it only took me linke an hour or two to have it done.

What is remarkable about the minimax algorithm itself is that it is quite simple in its basic form, even with the alpha-beta pruning. If you read through the Wikipedia article you will find this piece of pseudo code:

function alphabeta(node, depth, α, β, maximizingPlayer) is
    if depth = 0 or node is a terminal node then
        return the heuristic value of node
    if maximizingPlayer then
        value := −∞
        for each child of node do
            value := max(value, alphabeta(child, depth − 1, α, β, FALSE))
            α := max(α, value)
            if α ≥ β then
                break (* β cut-off *)
        return value
    else
        value := +∞
        for each child of node do
            value := min(value, alphabeta(child, depth − 1, α, β, TRUE))
            β := min(β, value)
            if α ≥ β then
                break (* α cut-off *)
        return value

And now if you compare it to the implementation it just looks very similar.

public int ScoreAlphaBeta(bool maxLevel, int alpha = int.MinValue, int beta = int.MaxValue) {
    if (this.Children.Count == 0) {
        return this.Value.boardAfterMove.CurrentScore();
    }

    if (maxLevel) {
        foreach (var child in this.Children) {
            alpha = Math.Max(alpha, child.ScoreAlphaBeta(false, alpha, beta));
            if (alpha >= beta)
            {
                return alpha;
            }
        }
        return alpha;
    } else {
        foreach (var child in this.Children) {
            beta = Math.Min(beta, child.ScoreAlphaBeta(false, alpha, beta));
            if (alpha >= beta)
            {
                return beta;
            }
        }

        return beta;
    }
}

What was the hard part?

It turns out that in fact the most difficult part was implementing the game rules and the board mechanics. As a former chess player I had some experience with board games domain and this version of checkers was very simplified (no queens - if the pawn reaches the last line it just stays there) so I thought it would be very easy.

In fact I spend a couple of hours on every single small item here… Finding correct move candidates, filtering captures, executing a move, etc. At first this threw me off (did I mention I’m usualy good at this?) but after some time I though this should be expected, I mean this is far enough from my usual domains to be “new” for me, and I guess this proves that this kind of knowledge is not transferable without some work.

I’m sure now I’d be able to predict which parts of project like this would be difficult way better if I’d started from 0. So I guess the real learning here is that if the domain is just outside of my comfort zone I’ll probably need to at least get my feet wet before my predictions and estimations can be acurate.