For the past couple of weeks, team members have been focusing on the Artificial Intelligence for our robot to play Connect-4. We are using a Minimax algorithm, which is a well-established AI approach for two-player games. The idea is that you consider all next moves you might take, and the moves your opponent will take in response. You expect that your opponent will make whichever move will minimise your score, while you will make whichever move will maximise your score. This is where the name Minimax comes from.

Even though Minimax is quite an old AI algorithm, it is still at the heart of modern game-playing AI systems, such as DeepBlue and other AI systems that play chess.

In CoderDojo, we started thinking about this algorithm by watching an good YouTube video by Daniel Shiffman, where he demonstrated how to write the Minimax algorithm in JavaScript to play the game of tic-tac-toe (Xs and Os):

After that, coder Adam in our group took over the work. While the Coding Train video was good for an understanding of the algorithm, Adam had to write the code from scratch:

• We are using Python, so Adam had to re-write the Minimax algorithm in Python instead of JavaScript.
• Connect-4 is of course a completely different game to Tic-Tac-Toe, so Adam had to write code to display the Connect-4 board, store the internal representation of the board, and take moves such as Yellow or Red dropping a token.
• Adam added alpha-beta pruning to speed up the algorithm.

In the Tic-Tac-Toe video, they identify the best move by considering all possible sequences of moves until the end of the game, but Connect-4 has a lot more moves. Therefore, Adam implemented a depth limit and an evaluation function.

The evaluation function generates a score for the current state of the board: for example, if you are the Red player, then if you have 3 red tokens in a row that’s more valuable than 2 in a row, and they are a lot less valuable if they don’t have empty spaces around them.

Designing a good evaluation function makes a big difference to how well the AI performs. The hackers, particularly Adam and Mark, spent quite a bit of time thinking about how to evaluate the board, and then Adam wrote a really nice score calculator for it.

As a result, the AI is so good that even when it only looks ahead 2 steps, it is a very strong opponent for humans. With 2-step lookahead, it beat us every time, though Mark was its strongest opponent, finally losing to the AI with only 2 spaces left on the whole board (see photo above: AI is yellow, Mark is red).

When the AI does 4-step look-ahead, it wins quite quickly against humans. It can do deeper look-ahead, but in our tests, it got slow beyond 5-step, and anyway it’s too tough to play against.

Our next step will be to work on the robot arm – coder Mark is taking the lead on this, with the support of mentor Kevin.