Abstract: In this post, we discuss some of the important terms of basic game theory, and using the Minimax algorithm, create a strong solution for the abstract-strategy game of Tic-Tac-Toe.
Tic-Tac-Toe, from a game design standpoint, is horrible. It lacks any real decision making, and assuming all players act optimally, will always end in a draw. However, because the game is so simple, it can be used as a great teaching tool and set the framework for more complex game analysis. Because of this, I feel that it is appropriate to start here, as it will allow me to introduce terms that will be used in the rest of my posts.
To start, lets first look at what exactly Tic-Tac-Toe is. Tic-Tac-Toe is a game for two players, in which players take alternating turns, marking either an X or O on a 3×3 grid. The first player who succeeds in placing three of their marks in a diagonal, horizontal, or vertical row is the winner.
In game theory, Tic-Tac-Toe is referred to as a deterministic game. A deterministic game is one in which no randomness is involved in the development of future states. Or, a game that will always produce the same result, if player actions are kept constant. An example of a non-deterministic game would be something like Catan or Monopoly, as both rely on dice rolls. Tic-Tac-Toe is always a perfect information game, or one in which both players see all of the states and decisions. Looking back to Catan and Monopoly, Monopoly would also be a perfect information game as no information is hidden from the players. Catan, on the other hand, is an imperfect information game, as each player has a hand of cards, hidden from other players. Finally, Tic-Tac-Toe is what is referred to as a zero-sum game. A zero-sum game is defined as a game in which the sum of all gains of participants totals to zero. In Tic-Tac-Toe, one of the players must win, or the game is considered a draw.
Tic-Tac-Toe is also a game that is considered to be “solved”. There are a couple of different levels on which a game can be solved, but for now lets just worry about that top level – strong. A strong solved game, is one in which an algorithm exists that can predict perfect moves from any position even if mistakes have already been made by either side. These proofs often require a “brute force” method in which all possible states are calculated, giving the AI an optimal strategy for every possible board combination. As mentioned before, Tic-Tac-Toe is one such game, and has been solved as a draw. Meaning that, assuming optimal play from each player, the game will always end in a draw. Finally, I would like to make note that this concept usually only applies to abstract-strategy games, and more importantly deterministic games with perfect information.
As mentioned in the abstract, we will be using the Minimax algorithm to produce a strong solution for Tic-Tac-Toe. First, let us discuss the algorithm. The Minimax algorithm was originally created for n-player zero-sum games. In this post, we will use a simple version of this algorithm in which is used in 2 player games, which each player can win, lose, or draw. Because Tic-Tac-Toe has such a small decision space, the Minimax algorithm will check all possible end states, and find which move is best, assuming that the opponent acts optimally.
To do this, we must iterate through all possible moves, calculate the best result from each, assuming optimal play from the opponent, then select which move which is best. The sudo-code can be found below,
function findBestMove(currentState):
bestMove = NULL
for each move in possibleMoves(currentState):
if move is better than bestMove:
bestMove = move
return bestMoveNow that the easy part is done, we know must come up with a system for comparing possible moves. To do this, we use the Minimax algorithm. The Minimax algorithm is a recursive algorithm, in which each state is assigned a value, based on what the outcome of the state will be, assuming optimal play from the opponent (this is important). The sudo-code can be found below.
function minimax(boardState, depth, ismaximizingPlayer) is
if current bpardState is a terminal state:
return the value of the boardState
if maximizingPlayer then
value = −∞
for each move in possibleMoves(boardState):
value = max(value, minimax(move, depth + 1, FALSE))
return value
else (* minimizing player *)
value = +∞
for each move in possibleMoves(currentState):
value = min(value, minimax(move, depth + 1, TRUE))
return valueWhen checking for a terminal state, we simply check to see if one of the 8 possible win conditions has been met, and if so return a value based on who has won. In my implementation, the AI is always zero, so O winning is a score of +10, while X winning is a score of -10.
Here is my full implementation of the Minimax algorithm using Python and a simple Tic-Tac-Toe game also created by me. The full py file is available on the linked GitHub at the end of the post.
# Begin Tic-Tac-Toe AI
# Creates a list of all possible moves for a given player
def generateAllPossibleMoves(board, player):
listOfBoards = []
for i in range(3):
for k in range(3):
if board[i][k] == " ":
newBoard = copy.deepcopy(board)
newBoard[i][k] = player
listOfBoards.append(newBoard)
return listOfBoards
# Iterates through all possible moves and finds the best one
def findNextMove(board):
bestMove = None
bestVal = -1000
possibleMoves = generateAllPossibleMoves(board, 'O')
for move in possibleMoves:
moveValue = minimax(move, 0, False)
if moveValue > bestVal:
bestMove = move
bestVal = moveValue
return bestMove
# Minimax function used to determine value of specific moves
def minimax(board, depth: int, isMax: bool):
global moveCounter
if isMax:
player = 'O'
else:
player = 'X'
if checkForWin(board, 'O'):
return 10 - depth
if checkForWin(board, 'X'):
return -10 + depth
possibleMoves = generateAllPossibleMoves(board, player)
if not possibleMoves:
return 0
if isMax:
bestValue = -1000
for move in possibleMoves:
value = minimax(move, depth + 1, False)
bestValue = max(bestValue, value)
return bestValue
else:
bestValue = 1000
for move in possibleMoves:
value = minimax(move, depth + 1, True)
bestValue = min(bestValue, value)
return bestValue
There is one thing I wish to address with this implementation of Minimax on Tic-Tac-Toe. As mentioned before, Minimax relies on the opponent making the optimal move. In Tic-Tac-Toe a common strategy is a “fork”. A fork is when the player creates two opportunities to win, essentially winning the game. If we assume that our opponent is also playing perfectly, it is more beneficial to start in one of the corners (which are all essentially the same), as it gives the opponent the smallest choice of squares which must be played to avoid losing. However, there seems to be a study that suggests that if playing against an imperfect opponent, playing in the center may be better. I may revisit this topic, of which opening is better for imperfect opponents, but for now, my implementation goes off the assumption that you are playing a perfect opponent, defaulting to the first move tested, which will have it open in the top right.
Finally, let us look at the basic rules that you can use to play a perfect game of Tic-Tac-Toe. After all, what good is this, if it doesn’t help you win the game? These rules are based on the ones used in Newell and Simon’s 1972 tic-tac-toe program.
- Win: If you have two in a row, and can place a third to get three in a row.
- Block: If the opponent has two in a row, you must play the third to block the opponent.
- Fork: Create an opportunity where you have two ways to win (two non-blocked lines of 2).
- Blocking an opponent’s fork: If there is only one possible fork for your opponent, you should block it. Otherwise, you should block all forks in any way that simultaneously allows them to create two in a row. Otherwise, you should create a two in a row to force your opponent into defending, as long as it doesn’t result in them creating a fork.
- Center: You should mark the center. (There have been claims made that as a first player starting in a corner is best, as it gives more opportunity for error. Against a perfect opponent it should not matter.)
- Opposite corner: If your opponent is in a corner, you should play the opposite corner.
- Empty corner: You play in a corner square.
- Empty side: You play in a middle square on any of the 4 sides.
Final Thoughts and Works Cited:
That’s, pretty much it for Tic-Tac-Toe. Although the game is quite simple, there can still be a lot to learn from it. I will probably continue to do classic abstract strategy games for the first couple of weeks, before moving to tackle more modern thematic board games. Likely starting with the Reiner Knizia classic: Lost Cities
Also here are the works that I consulted while making this post. Some of them are quite long, and I have only read parts of them.
PhD thesis: Searching for Solutions in Games and Artificial Intelligence
The best opening move in a game of tic-tac-toe
Games solved: Now and in the future
Also also, here is the link to the complete code, which can be found on my GitHub
The Board Game Scholar 