A brute force approach to Tic Tac Toe
I have just created a fully working Tic-Tac-Toe AI which will never lose! It was an extremely interesting project as it helped me understand the concepts of recursion and the minimax algorithm. All the code in the project is available for download HERE.
To make this binary opponent of ours truly unbeatable I had to use a very useful algorithm which would allow the computer to calculate all possible moves and select the best one. This is known as a Shannon Type A algorithm as it uses a brute-force strategy to find the optimal play.
Introduction to Tic-Tac-Toe
Tic-Tac-Toe or Noughts and Crosses was invented during the Roman Empire and first computerised in 1952 at Cambridge University by Alexander S. Douglas.
In our game of Tic-Tac-Toe, we will assign each square an individual number as the board will be stored in a one-dimensional list. The squares of the board will be assigned the numbers as follow:
To specify a streak (i.e. a line) of squares we will use the notation <squareBEGIN><squareEND>. For example, in this board:
Player X won in <2><6> while player O tried to win in <6><8> but X player played in <6> first.
A few numbers
According to calculations made by Henry Bottomley, there are exactly 255 168 possible board combinations without taking into account symmetry.
- There are 131 184 possible board combinations where the first player wins
- There are 77 904 possible board combinations where the second player wins
- There are 46 080 possible combinations where the end state is a tie
This is actually very good for us as it means that a computer will go through all those combinations in no time.
Let’s analyse what a perfect game means
Perfect play means that when you play you will always win or tie the game, but you will never lose. We can logically conclude that if we play against another perfect player we will always tie the game.
Obviously, your computer (or mine by the way) has strictly no idea what win, lose or tie means so we are going to have to convert these states into numbers:
- 1 point if I win
- -1 point if I lose
- 0 points if I tie
Let’s do some programming!
Creating a game environment
When we play Tic-Tac-Toe, we often do exactly the same things over and over again. We play on a square, check if somebody won, draw the board and start again.
To make this easier, let’s create a game environment with a class called Board that will handle all of this for us.
A bit of planning first
Even though planning things out is boring it is an extremely useful step to not get lost and keep your focus.
What will our environment need?
The game environment will obviously need some variables to remember things:
- A variable to hold the board which we will call “board”
- A variable to hold all the winning streaks (<0><2>; <3><5>; …) which we will call “winning streaks”
That’s all the variables we need!
However, we will also need some methods to actually do the boring work!
- A method to draw the board called “output”
- A method to get the empty spaces called “legal_moves”
- A method to tell us whether the board is full or someone won the game which we will call “leaf”
- A method to get the winner of the board (if there is one) called “winner”
- A method to get a list of all the squares taken by a certain player called “get_squares”
- A method to actually move a player to a certain square called “move”
- A method to tell us if X won called “X_won”
- A method to tell us if O won called “O_won”
- And a method to tell us if it was a tie called “tie”
We will also need a function that will return the opposite player. For example, if you pass an O it will return an X, if you pass an X it will return an O. This function doesn’t need to use the environment variables so it won’t be in the Board class.
Just to give you an example, here’s my plan:
Time to code!
Here’s my code for the game environment. I saved it in a file called environment.py.
class Board(object): """ Game Environment Class""" def __init__(self, board=): """ Initialize the environment variables """ # Generate a new board if the passed board is empty if len(board) == 0: self.board = [' ' for square in range(9)] # Set new board as old board else: self.board = board self.winning_streaks = ( [0,1,2], [3,4,5], [6,7,8], [0,3,6], [1,4,7], [2,5,8], [0,4,8], [2,4,6]) def output(self): """ Print the board""" print() print(self.board + '|' + self.board + '|' + self.board) print('-----') print(self.board + '|' + self.board + '|' + self.board) print('-----') print(self.board + '|' + self.board + '|' + self.board) print() def legal_moves(self): """ Get the empty spaces """ return [index for index, square in enumerate(self.board) if square == ' '] def leaf(self): """ Is the board full or has someone won the game """ if ' ' not in [square for square in self.board]: return True if self.winner() != None: return True return False def X_won(self): """ Did player X win """ return self.winner() == 'X' def O_won(self): """ Did player O win """ return self.winner() == 'O' def tied(self): """ Is the game a tie? """ return self.leaf() == True and self.winner() is None def winner(self): """ Get the winner of the board """ for player in ('X', 'O'): positions = self.get_squares(player) for streak in self.winning_streaks: win = True for pos in streak: if pos not in positions: win = False if win: return player return None def get_squares(self, player): """ Get a list of all squares taken by a certain player """ return [index for index, square in enumerate(self.board) if square == player] def move(self, position, player): """ Move player to position """ self.board[position] = player def get_opponent(player): """ Gives us the opponent of player """ if player == 'O': return 'X' else: return 'O'
That’s all for this post! In the next post, we will try and create a very basic and far from perfect opponent to test our environment.
Sign up to our email list to get notified when I post part 2 of this tutorial!