Maxigo - Five-in-a-row/Gomoku/Wuziqi board game, with good AI

Hi,

I am pleased to release a new version 1.2 of my “five in a row” game (also known as Gomoku in Japan or Wuziqi in China).

maxigo.v1.2.hex (78.6 KB)

Start screen:
maxigo.v1.2

Game description
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.

Technical details

  • Open-source. The full source code is now available under MIT license at the maxigoarduboy GitLab repository.
  • The AI is an alpha-beta search NegaMax method based on my prior implementation of the Javascript version of Maxigo. The search procedure is standard but there is some clever heuristic evaluation based on detailed “threat types” which are recognized. The Arduboy is quite limited computationally and the pattern matching is pre-computed into a lookup table.
  • 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.
  • History: in 2020 I built a Javascript version of the game for the 5th birthday of my son (“five in a row” is a matching theme :slight_smile: ), so it was fun to revisit the game for the Arduboy. The boy shown on the start screen is him, and he is actually quite good at the game.
  • 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.
  • Open-source. The full source code, data, and documentation is now available under MIT license at the maxigoarduboy GitLab repository.

Changes in version 1.1, released 23rd June 2022

  • 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.

Sebastian

8 Likes

Nice game! Thank you for sharing this.

Fun game :slight_smile: Challenging too.

Nice game! Very challenging! The AI shows no mercy :joy:

Hi @snboot9000 - welcome to the community! :tada:
Thanks for sharing this fantastic game.
Wow- beating the AI is hard
…would an easy mode be possible?.. :sweat_smile: :pray:

Great little game.

I have found your upload in the cart web site so will add it into the puzzle section tonight (Australian time!)

Haha this AI is like, perfect isn’t it?

I was pretty good at connect 4 but this is something else.

Added! Thanks.

I just added an easy mode in version 1.1, have a try to see if you can beat the AI now!

Your comment made me think of it being important that beginners will also enjoy the game initially so they get slowly drawn into it :slight_smile:

1 Like

Thanks Simon. I just released version 1.1 with many small improvements and two big changes: an “easy AI” mode and a multi-step undo/redo function. Please consider updating it in the Cart.

Thanks! If you find the AI too challenging, I just added version 1.1 with an additional “easy AI” mode, where the AI makes random mistakes every once in a while.

2 Likes

Thanks! The AI is good but not perfect.

Sidenote: from a game theory point of view the Gomoku game has been fully analyzed in 1991 in Victor Allis’s PhD thesis, where he proved a certain win for perfect play for the first player.

1 Like

Updated have updated the cart.

1 Like

Thanks for the update…
I’m still mainly losing to the ‘easy’ AI… :flushed: :sweat_smile:
Do you plan to share the source code in future?

Yep me too. Its punishing, isn’t it?

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.

Maybe it needs a “Let the wookie win” option :smile:

2 Likes

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).

(See also: the Chinese room experiment.)

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.

Andrew, I just released the full source code and documentation under MIT license here: Sebastian Nowozin / maxigoArduboy · GitLab

2 Likes