January 21, 2021 - 1265 words - comments
After not finishing my triomino project I started working on an implementation of the Reversi game. According to Wikipedia my implementation is technically an Othello game but this name was patented in Japan in 1971 and I decided to play it safe and calling it Reversi (no doubt that the owner of the name would have felt greatly threatened by my amazing implementation of his game).
The rules being pretty simple and the grid a traditional square, implementing the game wasn't the most interesting part of this project. Implementing the AI however was pretty fun. At first I went with the most basic method possible: The Great Random!
Once all the tooling is in place to spot the playable cells on the grid, implementing an AI which chose one spot randomly is pretty straight forward. It then quickly evolved to a slightly less dumb AI which choose the spot where it will turn the most possible disks.
With these AI implemented I spent a bit of time to add a "hint" button which uses the AI to play for the player and an "autoplay" button which makes the AI play the whole game for the player. Watching my programmed piece of silicon playing against itself amuse me to no end and I can stay hours watching it tirelessly placing disks on the board (Ok, not hours but at least five good minutes).
After creating my basic AIs I went one step further and implemented a new one with the minmax algorithm. I had already implemented one on a student project for a tic-tac-toe game and I wanted to do that on something more complex ever since, that was a great opportunity.
Although the algorithm itself isn't really groundbreaking I got to learn something pretty interesting during its implementation: I got pretty quickly a first working version but I quickly realized that my implementation had a memory leak, after a few turns the memory usage of the page would grow up and never go down. I spent two days debugging my code in a lot of different ways, trying to use the Chrome debugging tools to inspect memory snapshots.
I quickly understood that my issue was that my
Board objects were not garbage collected: To create the different nodes of the algorithm I copy the
Board object holding the current state of the game, add a new disk, turn the other disks accordingly and iterate on these new boards. These
Board object hold an array of
Cells representing the different spots and the disks played on them. As my boards were not garbage collected I suspected that when I was done using them I didn't released the references to these cells and so I spent hours trying different things to make sure that all the child references were deleted.
setTimeout they create global references and that's no good" which I had immediately dismissed since I always try to be cautious about my
setTimeout... Except I hadn't :🤦
Board objects have a
lastPlayed property which is used by the GUI to show the user which disk they have placed last. And being an amazing UX designer I thought it would be nice to highlight this cell and stop highlighting it after a few seconds... Sure enough I had used a
setTimeout to do that and each time the AI placed a disk on a Board it created this timeout, preventing the garbage collector to get rid of the board. After getting rid of that my algorithm worked like a charm... Almost.
It turns out that for a game of Othello there are a lot of different possibilities so I couldn't run my MinMax with a depth greater than 3 to keep the execution time under a few seconds. That was something I had anticipated and that lead me to implementing an Alpha Beta pruning algorithm to improve the performances. Unfortunately, this kind of algorithm requires a heuristic function in addition of the evaluation function used by MinMax. That's when I stopped working on this project, I have quite a good idea of the different heuristic I want to create (mainly thanks to a great research paper I can't find back at the time of this writing) but I'll have to spend more time on this project and I'm not sure when that will happen.
While I was implementing my different AIs I needed to compare them together to make sure I was heading in the right direction, so in addition of the GUI I also developed a testing program which runs thousands of games and collects some simple statistics. Here are some results:
|Random vs. Random||win percentages||nb of games won|
|player 1 (Random)||49.11%||4911|
|player 2 (Random)||50.89%||5089|
|Random vs. Most disks||win percentages||nb of games won|
|player 1 (Random)||42.82%||4282|
|player 2 (Most disks)||57.18%||5718|
|Random vs. MinMax (depth 3)||win percentages||nb of games won||avg. nodes evaluated by turn|
|player 1 (Random)||26.55%||478|
|player 2 (MinMax)||73.44%||1322||12 179 319|
|Random vs. AlphaBeta (depth 3)||win percentages||nb of games won||avg. nodes evaluated by turn|
|player 1 (Random)||35.33%||1590|
|player 2 (AlphaBeta)||64.66%||2910||2 785 672|
Nothing really surprising here but at least the results seem to be pretty coherent with what I was expecting:
Math.random()seems to be working good enough for this use case
I am really pleased with this project because it was a nice opportunity to get back to a bit of game theory and some decision algorithm which I really enjoy playing with. Also it was pretty cool to finally add Typescript to my toolbox for side projects and I'm looking forward to continue using it in my next coding adventure.