Building a game bot with machine learning

One of the things I enjoy about agentic coding is being able to work on those projects that sat around dormant because time didn't allow for them to be worked on.

I have a personal traditional game website, designed for older people, and one of the things I wanted to do years ago was add bots for the games. Part of the reason why I initially didn't add it in was skill set. While I'm not going to go into its full history here, the site was built out of necessity. It was also built on a tech stack I had never used before. So it was very much a raw learning experience. I was definitely not ready for creating bots. Years later, when I did have the skill set to do it, I didn't have the time (unfortunately also out of necessity).

But now with the combination of the better skills and agentic coding, working on projects like machine learning became possible.

While machine learning in games is nothing new, there is a difference between knowing the theory and working out the practicals.

Different games have different challenges. You can't paint each game with the same brush and get a good outcome.

For this article I am concentrating on Mancala; it's an easy game to play, hard to master, and has some quirks in the game that make things interesting.

Mancala quirks

Before starting to build a machine learning neural network, understanding the quirks of the game matters. These quirks are things that needed to be solved on my website long ago.

Traditional Mancala is set up by placing 4 stones in each pit at the start of a game. This makes the game player 1 biased. Once you work out the best opening moves, it's hard for player two to recover.

If both player one and player two play perfectly, player one wins. While with humans it's not quite that straightforward, I found that even with humans of varying skills, Player One still won about 75% of the time. This was an issue in tournaments, when most tournament games were decided before a stone was moved.

To fix this, I introduced random stones. Still 24 stones on each side of the board, still stones in every pit, but the number of stones in each one varies from game to game. An imperfect, but better outcome than traditional Mancala. The game is still player one biased. While it is still possible to end up with very favourable starting positions for player one, so can player two. The bias is in being able to see the favourable position at the start of the game and either scoring high points on the first turn or recognising player two's favourable position and being able to negate the advantage before they take a turn.

This all matters when it comes time to train a bot. The unpredictability of the starting positions, recognising the other players' good positioning, and being able to learn to play when every game has a different starting point.

Training the bot

To train the bot, a game simulator is needed. Building one in Python was what I found most beneficial. The NumPy extension was great for efficient vectorised matrices, making it a solid choice on its own.

The simulator plays against itself. As the neural network becomes more intelligent, it continues to play against itself, just at a higher level of skill. Also dropped into it is a 15% randomiser. 15% of the time the move made will be a random one and not a perfect solution from its neural network. This exposes it to new board positions. Sometimes those moves are terrible moves, sometimes they turn out to be genius moves. By setting the value to 15%, it's enough to get those unusual moves and evaluate them along with more standard moves.

Choosing a neural network size

The size of the neural network matters. If the network is too small, the data starts to get squashed, losing valuable data as you gather more data from more games.

If the network is too big, depending on the game being trained, it can end up where the training data is saturated before filling up the network, and while this isn't necessarily harmful from a training point of view, it's important to take it into account when it comes time to using the data. The larger the network, the slower the thinking. From a user experience point of view, this matters. Users don't want to be waiting a long time while the bot is thinking. So finding the right sized network matters. Too small, it never reaches its potential intelligence, too big and it's too slow.

The anatomy of a neural network

The neural network is made of four layers of data, together adding up to the total number of parameters that the network can use to build intelligence on.

Inputs: 14 values representing the six pits on each side and the two home areas.

Hidden 1: 32 neurons combining those inputs using learned weights and biases.

Hidden 2: Another 32 neurons that further transform those values.

Output: A single value between -1 and 1 representing how favourable the position is.

For the first training, the hidden layers were set to 32 neurons.

1,504 weights and 65 biases.
1,569 total parameters

When talking about choosing the right model capacity for a network, the total parameters are what to look at.

The question is, in a game of Mancala, is 1,569 parameters enough?

Training & evaluating Mancala

After running a round of training games, there needs to be a way to evaluate the outcomes. The complexity in random starting positions is that each time the neural network is evaluated, the starting positions are different, which leads to skewed results.

To fix this, the opponent was set up with 300 starting positions that could be used across multiple evaluation sessions. Those positions may not have been the greatest starting positions you might hope for, but they became the standard for measuring success.

The evaluator itself was a simple handwritten heuristic paired with a search. It doesn't learn, and it never changes, so any movement in the win rate is coming from the network and not from the thing measuring it.

On the first run, success was measured every 30,000 games and provided some interesting insights.

It was interesting that once the training reached 90,000 games, that the win ratio plateaued, which seemed like it had reached saturation in the network.

Despite the low win rate, the game itself played pretty decent. Good enough for beginners or intermediate players, however reasonably decent players would win games easily.

Why the low win ratio?

This is where knowledge of the game helps. The neural network is essentially evaluating one position at a time. It can tell us how good a position looks, It doesn't know what effect that move has on the next few moves.

Mancala on the other hand is not one dimensional. To be good at it, it requires being tactical, creating setups for next turn, hiding good moves from your opponent inside innocuous looking moves, trying to trick the opponent into making a mistake.

To simulate this, the bot not only needed the positional evaluation, but also a look-ahead, to see what those positional changes mean for upcoming moves, both their own and their opponents.

In game theory, this look-ahead process is known as minimax search with heuristic evaluation (yes it's quite the mouthful).

The training data gives you positional judgement. The look-ahead gives you the consequences. The neural network tells you which moves look good, and the look-ahead says "if I play this, and my opponent replies with the best move where do I end up?"

Adding look-ahead

For a look-ahead to work, it needs a list of possible moves and then rolls through each one, looking at what happens next, using the network as a guide to evaluate each move. It allows the bot to see that if they make this seemingly great move, that 3 moves down the road, it ends up allowing their opponent to capture pieces.

In this scenario, while the initial move seems good, the look-ahead will downgrade its value because of the outcome.

Adding the look-ahead gave a much better outcome

It's worth pointing out these numbers are all against the same fixed opponent used earlier, one that only looks 5 moves ahead itself. Part of the jump at 7 and 8 moves comes from having more lookahead than the opponent being tested against, on top of whatever real improvement there is in reading the position. Testing two versions of the bot at the same depth against each other showed a smaller gap, more like 47% to 58%.

Look ahead considerations

When deciding how many moves ahead to set the look-ahead, you have to take into consideration how long the search will take at each depth.

One move ahead takes no time at all; five moves ahead and it takes about 41 ms, seven moves ahead around 300 ms, and eight moves ahead 1100 ms.

So while the number of moves ahead will help the bot make better moves, the advantages need to outweigh the disadvantages. In this case, 7 moves was the sweet spot; 8 moves only provided a marginal increase in intelligence for 3x the time taken.

Experimenting with hidden layer sizes

Since the wins plateaued at 21%, the suspicion was that the neural network might have been saturated. So trying to expand the size of the network from 32 to 64 and 128 made sense to see what the effect would be.

At 64 neurons per layer, the network now had 5,185 parameters. At 128, the number of parameters was 18,561.

Testing 64 neurons directly against the 32 version, with the same training and same look-ahead, the 64 version won 49.9% of games, the 32 version won 41.2%, the rest were draws. About an 8 point gap in a head-to-head test. A larger network means slower thinking, but the 8 point gap was worth the extra time.

At 128 neurons per layer, the win rate against the 64 version only moved by about 2 points, which is inside the normal noise for that many games. The thought was maybe 128 just needed more training to catch up, so it was trained again, this time for 90,000 games instead of 30,000. It came back slightly worse, not better. That rules out training volume as the explanation. 64 still looks like the right size, and the limit seems to be how much capacity this game actually needs rather than how much training the bigger network got.

Structuring difficulty levels

In a game, while it's great to have the highest level of intelligence, other levels are needed to make the game accessible to all. Not everyone is an expert and they want to win some games too.

For Mancala, four difficulty levels were picked, each with different characteristics.

When playing against the bot, this gave a nice difficulty bump with each level of play.

Final Evaluation

To do a final evaluation on the difficulty levels, a tournament was set up, where Expert difficulty played each of the other levels to see what the win rate would be.

I set up some rough expected ranges for the results to compare against. These estimates were based on hunches, not derived from data. They are what I thought would make a good spread for varying difficulty levels.

Evaluation results

The results were close enough to the expected to be considered OK. The results against Intermediate were higher than anticipated, but after considering this, it was determined that the expectation of 75-90% was wrong. Intermediate was set up closer to Beginner than Advanced, so it made sense that the win rate was still high.

Against Advanced, and against Beginner, the estimation was where they were expected.

Overall results

Breaking the data down into results when playing first and playing second shows some interesting patterns.

The bias of going first is evident in these results. Against every opponent, Expert level wins were higher going first than going second.

Expert's win rate going second against Advanced was much lower than expected. The bias of going first against an opponent that was still a deep thinker was enough to tip the scale too much. The conclusion on that is that the skill level of Advanced is too close to Expert and might need to be adjusted.

First vs second

Proving a theory

Earlier I spoke about the bias in traditional Mancala. How playing first caused an imbalance, and why I changed the rules for my site to random stones.

During this testing, I ran a test to see if the two strongest bots would produce the "Player one always wins" result when playing traditional Mancala.

The results confirmed the theory, that there is a significant bias in the traditional layout. While there is still a lean towards advantages for player one in the random stone placement version, it's a much softer bias than in traditional Mancala.

Outcome

The outcome was good. The game can be beaten, but it's hard to do so. It sees things and plans ahead in such a way that it is hard to defend against, and it's good enough to recover from a favourable start for the human. The idea was not to make it impossible to win, but to challenge the player enough to make it fun to play against.

While none of the methods I used are new concepts; there are many papers that have been written by people much smarter than me on the subject. Breaking it down and actually implementing it was a great learning experience, and most of what I took from it wasn't really about neural networks. It was about measuring things properly. Pick an opponent that doesn't move. Keep the starting conditions the same. And when a number stops improving, don't assume you know why.

Often you will hear how AI takes away learning, but it really doesn't. It enables you to expand your learnings into new areas you had not previously explored.