3D Noughts and Crosses AI

[back]

This is a 2-week piece of coursework in second year, to create an AI that will play 3D Noughts and Crosses against a human player. This was for a module in programming in Prolog. For this I designed an AI algorithm which decides the best possible move based on the current state of the game. I will explain the game, and then the algorithm.

3D noughts and crosses is a game involving three noughts and crosses boards stacked on top of each other. Two players take turns placing their own mark on any square that does not already have a mark, on any of the three boards. A player wins when there is a straight line of three of their own mark anywhere on the board. This line can be in any direction in all 3 dimensions as long as it is straight through the exact centre of any three squares on any of the three boards. The three boards are stacked on top of each other lining up exactly with equal spacing between them, as in the picture below.

The algorithm

The AI uses a rating system to choose which square would be the best next move, based on a loose idea of 'freeness' of the square. We will use the term 'triplet' to describe any set of 3 squares such that if a player has their mark on all 3 squares that player has won.

When the AI wants to choose a square to place a mark, there are a number of options, that is every square where there is not already a mark. This algorithm will give each square a rating which will tell it the best places to go. Obviously the highest rated squares will be those in a triplet with two of the AI's marks, so that if the AI goes there it will win immediately. Next are squares in a triplet with two of the other player's marks, so that if the AI doesn't go there it could lose on the next turn. If there are no squares that meet either of these descriptions the AI will go on to rate every possible square. The basic way of rating a square is to rate every triplet that it is part of with a score of 0, 1 or 2. 0 means that the triplet contains a mark that does not belong to the AI. 1 means that it contains no marks. 2 means that it contains marks only belonging to the AI.

There are two ways of rating a square when you have the ratings of its triplets. One is to add up the ratings of its triplets, and the other is to take the average rating of its triplets. The AI uses both of these ratings. If there exists a square with an average rating of over 1, it will choose the square with the highest average rating. Otherwise, it will choose the square with the highest sum rating. The average rating exists to make the AI always seek to complete lines. The sum rating exists to make the AI go in the position with the greatest possibility for completing a line (that is, the position with the most space).

The code