CS50AI - Tic Tac Toe algorithm

Check out the code for this project here

Building an algorithm that Solves Tic-Tac-Toe

Tic-tac-toe is a very easy game to solve. What we mean by this is that if both players know what they are doing the game always ends in a draw. This is often the case as it is pretty easy to know what to do in Tic-Tac-Toe. Despite this it is still somewhat of a challenge to teach a computer how to play.

For one of my projects as part of Harvard's CS50’s Introduction to Artificial Intelligence with Python I built an algorithm in python that is able to play Tic-Tac-Toe flawlessly i.e. it is totally impossible to beat it, the best you can do is draw. This was a good hands-on introduction to learn how to algorithmically make optimal decisions in competitive environments.

credit

To solve this we could do a list of "If-Then" rules for the algorithm to follow. However, despite the fact there are a limited number of possible moves in Tic-Tac-Toe this would still require a lot of and be very inefficient. Instead we use a strategy of trying to project every possible move and counter move into the future and then work back to choose the best action for the algorithm to choose.

The Architecture

For this project we use a Minimax algorithm. First we have a utility function that assigns a numerical value to the outcome of the game:

• +1 if Player X wins.

• -1 if Player O wins.

• 0 if the game is a tie.

In this algorithm we assume that both the players play the optimal moves. In this case player X is the "Maximiser" meaning that their goal is to get the highest possible score. Player O is the "Minimiser" meaning that their goal is to get the lowest possible score.

In the program we have a minimax function that plays out the entire rest of the game that could occur. It imagines each of the possible moves from each of the possible players creating a decision tree until it reachers a terminal state. It then looks at the final branch with the best outcome and goes back up the tree to see the moves it should make.

How the code works

Here are the main functions I am using in the algorithm and how they work:

• actions: Scans the grid and retunrs a set of all the empty cells where it is possible to make a move.

• result: This function generates a copy.deepcopy of the board currently and sees what happens to it if a hypothetical move happens on the board. We need a deep copy as the program needs to simulate future states of the board without permanently altering the actual game board.

• winner and terminal: These functions constantly iterate through the diagonals, rows, and columns to decide if the game is over and who as won the game.

• Early Stopping in Minimax: I used a slightly modified version of the Minimax search where I added an early-exist optimisation into my max_value and min_value functions. What this means is that if the algorithm finds a path that guarantees a win then its stops searching. This reduces the amount of computation and make the program more efficient.

What's Next?

Tic-Tac-Toe is a good way to implement the Minimax algorithm as the total number of moves is very small. However, this doesn't work well with other games. Even if we have very powerful computation this can still take a while for some games as there are so many possible moves.

If I were to go back to this project here is what I would add:

• Alpha-Beta Pruning: I would add a full version of Alpha-Beta pruning instead of just my early-stopping optimisation so that the algorithm will keep track of the best alternative moves along the path.

• Depth-Limited Search: So we can apply this algorithm to other games with more moves we would have to have a way of estimating who would win with a set of moves without going all the way to the end. If we did go all the way to the end in a game like chess there would be more moves then atoms in the universe.