The game is a classic turn-based zero-sum game with two players each taking turns in placing a single stone of differing color; the first player to have five or more stones in a row (diagonal/horizontal/vertical) wins. The traditional board size is a 15-by-15 board, but because of limited screen space I had to use a 13-by-13 board to keep things readable.
Please give it a spin and let me know of any bugs/problems.
Maxigo game modes
Two player mode: two human players take turns in placing a stone; the first player to have five or more stones in a row (diagonal/horizontal/vertical) wins.
One player mode: the second player is played by an AI (there is an “easy” AI and a “hard” AI.
AI playing strength: the AI is strong enough to comfortably beat beginners and provide a challenge to intermediate players but anyone with more experience in Gomoku/Wuziqi can build up longer threat sequences that AI will be blind to.
Codesize versus speed: the game comfortably fits in the Arduboy space when compiled to save space (-Os gcc option in platform.txt). However, my unit tests showed a 2.5x speedup when I compile with optimization (-O1), but the full game runs out of space then. The easiest workaround was to use -O1 -finline-limit=140, where I found the value 140 by binary search (a large value produced faster/larger executables, a smaller value produced smaller/slower executables). The optimal tradeoff curve was quite smooth and picking 140 made the image fit into the Arduboy limitations while providing almost all the speedup the -O1 unit tests demonstrated.
I may release the source code under MIT license if there is any interest in it.
Changes in version 1.2, released 4th July 2022
AI code optimizations. The AI is now 40 percent faster on average. This speed-up was achieved by manual optimization of the heuristic move evaluation.
Multi-step undo/redo function. During a game just hold down the B button and while holding it down move left or right to move to a prior state in the game. Once you have gone to a prior state but have not made any new moves yet, you hold B and move right to “redo” all the moves one-by-one. This is useful to slowly revisit a game after play.
Two AI hardness levels: easy and hard. The easy AI is similar to the hard AI but stochastically makes mistakes. Exploit the mistakes to win the game!
Enlarged board size. The board is now 13x13 instead of 12x12. While Gomoku/Wuziqi is traditionally played on a 15x15 board, variants on 13x13 and 19x19 are also common, so 13x13 is a good choice.
Different board rendering. The lines around the board have been removed and instead the four corners are marked.
Move counter. Within a game the top left displays the current move count. This works well with the undo/redo function but also allows to challenge yourself or another player in terms of how many moves are needed to beat the other player.
URL changed. I changed https:// to http:// to make the URL work in the title screen.
Version number displayed. The game now displays the version, 1.1 in the bottom left corner.
More robust button handling. Moves are now made using only the A button, as the B button now is used for the UNDO function. Moves with the A button are now made upon release of the button, not on press.
Please feel free to include the game in any form into any collection/cart/image.
Go is basically a larger version of tic-tac-toe so you’re asking the AI to intentionally make bad moves.
The real trick is trying to create one that is somehow able to distinguish a “small” bad move from a “very obvious” bad move, because simply picking randomly will often produce a very obviously bad move which can really spoil the immersion for a game like this, as you’re effectively waiting for it to make a critical error randomly.
Some of you probably know that making an AI that makes believable mistakes is extremely difficult.
Even though go is based on extremely simple rules, the same way you are trying to catch the person on making a mistake. This is why this game, as many others like chess, is considered to be playing as much against the psyche of your opponent and knowing who they are and what kind of decisions they are likely to make are as important as the rules of the game themself.
That’s why playing chess against AI can feel so “soulless”. Further more the time delay that can be added to “simulate” thinking because it can get depressing when you keep getting checkmate instantly and you are aware the computer is so much more intelligent than you.
This is an area of study I’m actually pretty interested in and I’ve always wondered why we aren’t seeing any application of machine learning or other AI models deployed into video games yet. Lots of image recognition, video processing, now we are seeing natural language and image generation really taking off.
Sometimes it’s fun to watch competition between AI, there is a whole league of Starcraft 2 for AI I think that’s pretty fascinating.
Gomoku, not Go. Two different games with different rules.
Go is actually more complex than chess.
Probably because most ‘machine learning’ techniques in current use are based on neural networks and those have some notably prohibative factors…
The actual training is very computationally expensive, which is why it’s usually only well-funded corporations that can afford to do the training stage
What usually happens in that the large corporations do the training and then sell or make available their pre-trained systems for other people to use
Obtaining and/or curating high-quality data can be difficult, and poor data can lead to unexpected results (e.g. biases or miscategorisations) in the output
Even when training has produced a decent model, computing a result can still be relatively expensive, which would be fine for a turn-based game, but possibly not for something that requires real-time decision making
Most neural networks only run on simple data of limited dimension (e.g. sound waves, text or images), whereas most game states are much more complicated than that, so it’s likely that the data would have to be reduced somehow
Together, these factors make it difficult and expensive to use neural networks in video game AI.
It’s much cheaper and easier to just take ‘perfect’ algorithms (e.g. Dijkstra’s algorithm, Monte Carlo tree search) and add something that degrades their quality, such as randomised failure. Merely making random mistakes probably isn’t going to be very convincing, but it would achieve the goal of weakening the AI enough to allow an average human player to beat it. A better way would probably be to ‘curate’ the kind of mistakes than an AI could make (i.e. have a human decide what set of mistakes would be believable), in addition to skewing the likelihood of it making those mistakes.
It’s more akin to ‘knowledge’ than ‘intellgence’.
The computer merely has a list of rules to follow and a greater computational speed.
If you gave a human (with relatively little chess experience) the same book of rules (i.e. ‘algorithms’) and enough time to understand them and apply them properly, then the human would be just as effective as the computer (though admittedly much slower).
I agree making a believable weaker AI is hard. I experimented with randomizing score values computed during search but for Gomoku one path in the search tree often dominates everything and randomization does not help.
Regarding machine learned AIs: I am a reasonable expert in deep learning (but not in reinforcement learning), so I did a back-of-the-envelope calculation of whether it is possible to evaluate a reasonable neural network on the Arduboy and it would be very challenging. The main tool chain (TinyML via Tensorflow Lite) makes it feasible to convert neural networks to the Arduino, but the 2kb RAM limitation is severe for storing neural network activations during inference.
For training a strong AI for Gomoku using AI the easiest pathway would be to use the excellent AlphaZero.jl implementation of the AlphaZero learning method which can be run on a limited nvidia GPU such as my laptop’s GeForce RTX 3050. Designing a neural network that would fit within ~10kb (10k 8-bit weights) would be a challenge but is likely possible. Such neural network can be used to play directly, or combined with search methods as in AlphaGo.