Blokus Duo Arduino AI
Released: Februrary 15, 2018
Tags: C, Arduino
Shortly after my first semester in University, João Santos, a friend of mine, knew that I was a strong programmer and asked me to participate with him in the XIV Jornadas Sobre Sistemas Reconfiguráveis competition. The gist of it was that we had to develop an AI that could play the board game Blokus, which was to run on a small embedded system, and ultimately compete against other participants. Since we were first-year students, we would be developing on a more potent Arduino, which allowed us to use the C programming language. In the more advanced category, we would need to implement the game in Verilog or similar HDL since it would be running on a lower powered FPGA instead. The full rules of the competition are available here.
Our team, Voltage Spikes, won first place in the Newbie category, and second place overall (after the competition ended, we unofficially competed against all boards just for fun). For getting first place, we received a certificate and a DE10-Lite FPGA, which I offered to João since he would likely have more use for it than I would.
The C code for the AI is available on GitHub, linked below.
AI Overview
It has been 8 years since I wrote that code, so I might be missing some details (I had to give a presentation about the AI for the competition but I can't find my slides) but the gist of it relatively easy. The main strategy in Blokus is to use all your large pieces first, and to run towards the middle. The AI will start by choosing the highest scoring piece and position it where valid. If a valid move is found, the AI will store it as a possibility, keeping track of the score which said move gives. Once all moves have been checked, it will then attempt to go a layer deeper to find the next best possible move, and add that score to the original move. It will keep trying moves until either all pieces and moves have been checked or it close to elapsing the maximum allowed processing time by the competition. When that happens, it chooses the best scoring move from the list of possibilities.
It is a really simple algorithm, but it was more than enough to beat the competition. Had we had more time to dedicate to the competition, I would have tried to use a minimax tree with alpha-beta pruning and some custom heuristic function for evaluating moves, instead of bruteforcing it.
