Connect 4 Computer (Rust)

I have been quite interested in game playing machines recently, and thought I would make something to play connect 4 against. This is by no means an AI, or machine learning, although I do hope to make a project focusing on that more soon. Instead, it just tries to search all possibilities in the most efficient way possible, which is quite an interesting exercise especially in a language such as javascript, which isn’t really built with performance in mind.

The algorithm I used is called negamax (negated minimax), which is basically a variation on the minimax search that means we can write it as one function on the assumption that one player’s gain is the other’s loss, also known as a zero-sum property. Connect 4, like many other board games (e.g. chess), has this property. The basics of it are as follows:

int negamax(int depth) {
    // if the game is in a terminal state or we have reached the maximum depth,
    // return an evaluation of the position.
    if win() {
        return depth + 1
    } else if lose() {
        return -(depth + 1)
    }

    if drawn() || depth == 0 {
        return 0;
    }
   
    // otherwise find the best move we can make
    int max = -inf;
    for move in moves() {
        makeMove(move)
        score = -negamax(depth - 1) // worst outcome if opponent plays perfectly
        undoMove(move)
        if score > max {
            max = score
        }
    }
    return max;
}

The evaluation part is slightly modified to better fit with the idea of game states in connect 4. In a scenario like chess programming, you will probably want to use the version at (https://www.chessprogramming.org/Negamax) that has a proper evaluator for piece values. You may also notice that the AI prioritises moves that will win faster by using the current depth value to weight potential wins/losses.

The function doesn’t actually return the best move to make here, only its score – because it doesn’t need to! There is no use in knowing all of the next moves the AI wants to play for several reasons:

• The opponent may not make the optimal play, making the whole move chain useless
• A large memory and performance overhead would be incurred in the allocation and deallocation of the lists required to track the best move chain
• Even if the optimal play is made, the AI may not have had the depth in the last search to see that at the end of the chain, a different move would be more optimal as it would lead to a forced win. If a research is performed every move, the AI will spot this on the next turn

Of course, the AI will need to know which move to play, so there is a second version of the function that tracks the best move as well, returning it instead of the score it has.

From there, there are several optimisations that can be made to this function. The first implemented is usually called alpha-beta pruning. This is relatively simple to explain but becomes quite complicated when reading it, especially when in the negamax function as opposed to a minimax function. The way it works is by pruning nodes that cannot possibly yield a better score than the ones we have found already by tracking the worst case scenario. This stacks up pretty effectively as the algorithm goes deeper, and while I didn’t benchmark this one, it should always give performance benefits as the worst case scenario is searching all the moves – which is what we were doing before. In case you were wondering, it will always produce the same output as the full search when implemented correctly (which may have taken more than a few attempts 🙂 ).

This was good, so I decided to port the AI to WebAssembly to get a little more performance out of it. I did this by porting the JS to Rust, which was the fastest language choice other than C. I chose Rust just for the memory safety – which I think is incredible, and I thouroughly recommend trying it out if you haven’t already. I generated a WASM bundle the wasm-pack utility, and after a bit of debugging managed to get it working. I decided to do some benchmarking to see what performance increase (if any) the WASM was yielding, and was pleasantly surprised:

Time (WASM)	Time (JS)
4.538 s	22.033 s
0.937 s	9.976 s
0.808 s	9.773 s
0.531 s	7.798 s

As you can see, the WASM bundle consistently outperforms the JS one by a factor of around 10x when in the mid-game, which is way more than I thought it would!

That is about everything for this project. Note that in the demo below, WASM is turned off by default (which you can change using the “Show/hide CPU config” button). This is because I wasn’t sure that all browsers would support it. At the time of writing however, it is looking like I can maybe change this to be on by default soon (https://webassembly.org/features/). The depth is also set at 11, which I think is a good balance between speed and intelligence (at this depth it can see 6 placements of its tokens and 5 of yours). That being said, you can usually crank it up at least twice if using WASM 🙂

View project

View WASM source