Gaming AI - A first step into a larger world

Although we’re not game developers here at Abstrakt, I’ve always been fascinated with the idea of creating an AI for one ever since I started programming. The following article is a summary of how I approached the problem of developing my first AI, the game I chose for this was noughts and crosses.

Noughts and Crosses is a simple game that we learn from such a young age that it’s practically part of our DNA. The rules are simple, there are two players who are either an X or an O, who take turns marking the spaces in a 3×3 grid. The winner is the player who has 3 of their marks in a horizontal, vertical or diagonal line. It’s so simple that we rarely think about the strategy involved in winning, hence why I found the exercise so interesting that I had to write about it.

On the one hand, you could assume that this would be a simple case of getting the AI opponent to randomly pick a space on the grid and then if it’s lucky enough it might win from time to time. However, that isn’t what playing the actual game is like at all.

The whole aim of creating a good AI opponent is to craft it such that it’s trying to defeat you as much as you are trying to defeat it; furthermore, it also has to adapt its strategy based on the moves that have been made so far. With that in mind, I decided to approach the task in terms of strategies at different stages of the game.

In its simplest form winning Noughts and Crosses is about attack and defence, normally when playing the game, as soon as your opponent has 2 of their marks in a line, you are forced to block their line or else lose the game on the next turn. Therefore, initially the first strategy I chose to implement on the AI’s turn was to check whether the AI was in immediate danger of losing the game.

This was done by checking each row, column and diagonal line and counting the number of marks belonging to the player. If at any point this number is 2 and the 3rd space in the line is empty, the AI was programmed to mark that space and block the player.

This strategy seems fair enough, it means that the AI will constantly try to stop itself from losing and therefore be more challenging; the problem with this however, is that not losing is not the same as winning.

In my early tests using the defence first strategy, it soon became apparent that even when the AI had 2 marks in a line and was able to win during the current turn, it chose to defend instead of take the victory. Therefore the first part of the strategy should have been to check if the AI could imminently win before checking whether it could imminently lose.

The next part of developing the AI’s playing strategy was determine how it should act in scenarios when it is not in a position to imminently win or lose. Instead of it simply choosing a random space from what’s available I decided to introduce some aggressiveness to the AI’s tactics.

With this in mind the AI needed to ascertain its best chances of winning from any of the available spaces within the grid. By looping through all the empty spaces within the grid, each space then checks whether it was part of a row, column or diagonal line that has the potential of winning. From the start of the game (assuming the AI goes first), this looks as follows:

From the above illustration we can determine the following:

• The centre space has the most chances of being part of a winning line - horizontal, vertical and both ways diagonally.
• The corner spaces can win from 3 lines - horizontal, vertical and a single diagonal.
• The edges have 2 chances - just horizontal and vertical.

The AI uses this methodology to generate a list of potential spaces and then choosing the space with the most chances of winning; as the game progresses and spaces become occupied, the chances of winning within each space are reduced so that only a specific route remains.

With both defensive and offensive strategies established the AI performed well at choosing where best to play its move in order to win as well as ensure that it defends itself when in danger of losing; however, after testing this out a few times it soon became apparent that the AI was very predictable at the start of the game.

The AI would always choose the centre space when available (as it should do) and after that would always go for the top-left corner if that was available; the top corner being the first space it finds with 2 chances of winning, as shown in the illustration below.

Although not necessarily a massive problem, in order to keep the game interesting I decided to introduce some randomness. First of all, when determining an offensive move, the list of spaces with their chances of winning were first randomised before being ordered by the winning chance; this means that in the scenario above, the AI would choose any of the 4 available corners as it made no difference to the outcome at that particular point.

Finally, if the AI starts the game I decided that it should simply choose a random space instead of always picking the centre one, this happens in real life, even though the chances of winning from that space are greatest. Adding randomness to the AI, whilst still programmed to win helped to give it a human touch and ensured that no two games would be played out the same every time.

Creating the AI for Noughts and Crosses gave me an insight into how the process is approached in other games, I also had fun with it too. I added the final game to our gamified employee advocacy platform Brand Message as something to give to employees after they’ve shared the current available content.

You can find out more about Brand Message.