Save 37% on Classic Computer Science Problems in Swift. Just enter code fcckopec into the discount code box at checkout at manning.com.

Tic-Tac-Toe

Tic-tac-toe is undoubtedly a simple game. It can also be used to illustrate the same minimax algorithm that has applications in advanced strategy games like connect four, checkers, and chess. We’ll build a tic-tac-toe AI that plays perfectly using minimax.

Managing State

Let’s develop some structures to keep track of the state of the game as it progresses. First, we need a way of representing each square on the tic-tac-toe board. We’ll use an enum called Piece. A piece can either be X, O, or empty (represented by E in the enum).

  
 enum Piece: String {
     case X = "X"
     case O = "O"
     case E = " "
     var opposite: Piece {
         switch self {
         case .X:
             return .O
         case .O:
             return .X
         case .E:
             return .E
         }
     }
 }
  

The enum Piece has a computed property opposite that returns another Piece. This is useful for flipping from one player’s turn to the other player’s turn after a tic-tac-toe move. To represent moves, we’ll use an integer that corresponds to a square on the board where a piece is placed.

  
 // a move is an integer 0-8 indicating a place to put a piece
 typealias Move = Int
  

A tic-tac-toe board has nine positions organized in three rows and three columns. For simplicity, these nine positions can be represented using a one-dimensional array. Which squares receive which numeric designation (aka index in the array) is arbitrary, but we’ll follow the scheme outlined in Figure 1.

Figure 1 This figure illustrates the one-dimensional array indices that correspond to each square in the tic-tac-toe board.

The main holder of state is a struct, Board. Board keeps track of three different pieces of state: the position (represented by the aforementioned one-dimensional array), the player who’s turn it is, and the last move made. The last move made comes in handy later when we implement minimax.

  
 struct Board {
     let position: [Piece]
     let turn: Piece
     let lastMove: Move
  

A default board is one where no moves have yet been made (an empty board). The constructor for Board has default parameters that initialize such a position, with X to move (the usual first player in tic-tac-toe), and lastMove being set to the sentinel value -1.

  
     // by default the board is empty and X goes first
    // lastMove being -1 is a marker of a start position
     init(position: [Piece] = [.E, .E, .E, .E, .E, .E, .E, .E, .E], turn: Piece = .X, lastMove: Int = -1) {
         self.position = position
         self.turn = turn
         self.lastMove = lastMove
     }
  

As you probably noticed, all of the instance variables of Board are defined with let. Board is an immutable data structure. Board won’t be modified. Instead, every time a move needs to be played, a new Board with the position changed to accommodate the move is generated.

  
     // location can be 0-8, indicating where to move
     // return a new board with the move played
     func move(_ location: Move) -> Board {
         var tempPosition = position
         tempPosition[location] = turn
         return Board(position: tempPosition, turn: turn.opposite, lastMove: location)
     }
  

A legal move in tic-tac-toe is any empty square. The following computed property, legalMoves, uses filter() to efficiently generate potential moves for a given position.

  
     // the legal moves in a position are all of the empty squares
     var legalMoves: [Move] {
         return position.indices.filter { position[$0] == .E }
     }
  

The indices that filter() acts on are Int indexes into the position array. Conveniently (and purposely), a Move is also defined as an Int, which allows this definition of legalMoves to be succinct. You can scan the rows, columns, and diagonals of a tic-tac-toe board in many ways to check for wins. The following implementation of the computed property isWin does it with a hard-coded seemingly endless amalgamation of &&, ||, and ==. It isn’t the prettiest code, but it does the job in a straightforward manner.

  
     var isWin: Bool {
         return
             position[0] == position[1] && position[0] == position[2] && position[0] != .E || // row 0
             position[3] == position[4] && position[3] == position[5] && position[3] != .E || // row 1
             position[6] == position[7] && position[6] == position[8] && position[6] != .E || // row 2
             position[0] == position[3] && position[0] == position[6] && position[0] != .E || // col 0
             position[1] == position[4] && position[1] == position[7] && position[1] != .E || // col 1
             position[2] == position[5] && position[2] == position[8] && position[2] != .E || // col 2
             position[0] == position[4] && position[0] == position[8] && position[0] != .E || // diag 0
             position[2] == position[4] && position[2] == position[6] && position[2] != .E // diag 1
  
     }
  

If all of a row, column, or diagonal’s squares aren’t empty and they contain the same piece, then the game has been won. A game is drawn if it hasn’t been won and there are no more legal moves left. The computed property isDraw closes out the implementation of Board.

  
     var isDraw: Bool {
         return !isWin && legalMoves.count == 0
     }
 }
  

Minimax

Minimax is a classic algorithm for finding the best move in a two-player zero-sum game with perfect information like tic-tac-toe, checkers, or chess. It’s been extended and modified for other types of games as well. Minimax is typically implemented using a recursive function in which each player is designated either the maximizing player or the minimizing player.

The maximizing player aims to find the move which leads to maximal gains, but the maximizing player must account for replies to his moves by his opponent. After each attempt to maximize the gains of the maximizing player, minimax is called recursively to find the opponent’s reply that minimizes the maximizing player’s gains. This continues back-and-forth (maximizing, minimizing, maximizing, etc.) until a base case in the recursive function is reached. The base case is a terminal position (a win or a draw).

Minimax returns an evaluation of the starting position for the maximizing player. If the best possible play by both sides result in a win for the maximizing player, then a score of 1 is returned (in our version; the exact number is arbitrary). If best play results in a loss, a -1 is returned. A zero is returned if best play is a draw. When a base case is reached these numbers get returned. They then “bubble-up” through all of the recursive calls that led to the base case. For each recursive call to maximize, the best evaluations one level further down bubble-up. For each recursive call to minimize, the worst evaluations one level further down bubble-up. In this way a decision tree is built.

Figure 2 illustrates this tree which facilitates bubbling-up for a game with two moves left.

Figure 2 This figure illustrates a minimax decision tree for a tic-tac-toe game with two moves left. The initial player, O, is trying to maximize his likelihood to win and he chooses to play O in the bottom center.

We now present minimax() in its entirety.

  
 // Find the best possible outcome for originalPlayer
 func minimax(_ board: Board, maximizing: Bool, originalPlayer: Piece) -> Int {
     // Base case - evaluate the position if it is a win or a draw
     if board.isWin && originalPlayer == board.turn.opposite { return 1 } // win
     else if board.isWin && originalPlayer != board.turn.opposite { return -1 } // loss
     else if board.isDraw { return 0 } // draw
  
     // Recursive case - maximize your gains or minimize the opponent's gains
     if maximizing {
         var bestEval = Int.min
         for move in board.legalMoves { // find the move with the highest evaluation
             let result = minimax(board.move(move), maximizing: false, originalPlayer: originalPlayer)
             bestEval = max(result, bestEval)
         }
         return bestEval
     } else { // minimizing
         var worstEval = Int.max
         for move in board.legalMoves {
             let result = minimax(board.move(move), maximizing: true, originalPlayer: originalPlayer)
             worstEval = min(result, worstEval)
         }
         return worstEval
     }
 }
  

In each recursive call, we need to keep track of the board position, whether we’re maximizing or minimizing, and who we’re trying to evaluate the position for (originalPlayer). The first few lines of minimax() deal with the base case – a terminal node (a win, loss, or draw). This could alternatively go inside of a separate “evaluation” function. The rest of the function is the recursive cases.

One recursive case is maximization. In this situation, we’re looking for a move that yields the highest possible evaluation. The other recursive case is minimization. In minimization, we’re looking for the move that results in the lowest possible evaluation. Either way, the two cases alternate until we reach a terminal state (base case).

Unfortunately, we can’t use our implementation of minimax() as-is to find the best move for a given position. It return an evaluation (an Int value). It doesn’t tell us what best first move led to that evaluation! Instead, we’ll create a helper function, findBestMove(), that loops through calls to minimax() for each legal move in a position to find the one that evaluates to the highest value. You can think of findBestMove() as the first maximizing call to minimax(), but with us keeping track of those initial moves.

  
 // Run minimax on every possible move to find the best one
 func findBestMove(_ board: Board) -> Move {
     var bestEval = Int.min
     var bestMove = -1
     for move in board.legalMoves {
         let result = minimax(board.move(move), maximizing: false, originalPlayer: board.turn)
         if result > bestEval {
             bestEval = result
             bestMove = move
         }
     }
     return bestMove
 }
  

Okay, we have everything ready to find the best possible move for any tic-tac-toe position. Let’s try a few examples. Let’s start with an easy win-in-one position.

  
 // win in 1 move
 let toWinEasyPosition: [Piece] = [.X, .O, .X,
                                   .X, .E, .O,
                                   .E, .E, .O]
 let testBoard1: Board = Board(position: toWinEasyPosition, turn: .X, lastMove: 8)
 let answer1 = findBestMove(testBoard1)
 print(answer1)
  

You should see 6 printed to the console, indicating X should play in location six to win, which is correct. Now, let’s try a position that requires the next move to be a block to stop the opponent from winning.

  
 // must block O's win
 let toBlockPosition: [Piece] = [.X, .E, .E,
                                 .E, .E, .O,
                                 .E, .X, .O]
 let testBoard2: Board = Board(position: toBlockPosition, turn: .X, lastMove: 8)
 let answer2 = findBestMove(testBoard2)
 print(answer2)
  

Again, the right answer, location two, should be printed to the console. Finally, a harder position that requires planning ahead.

  
 // find the best move to win in 2 moves
 let toWinHardPosition: [Piece] = [.X, .E, .E,
                                   .E, .E, .O,
                                   .O, .X, .E]
 let testBoard3: Board = Board(position: toWinHardPosition, turn: .X, lastMove: 6)
 let answer3 = findBestMove(testBoard3)
 print(answer3)
  

You should see location one being selected for the win. It doesn’t take much code to implement minimax and it works for many more games than tic-tac-toe. If you plan to implement minimax for another game, it’s important to set yourself up for success by creating data structures that work well for the way minimax is designed, like the Board struct. A common mistake for students learning minimax is using a modifiable data structure that gets changed by a recursive call to minimax and then can’t be rewound to its original state for additional calls.

That’s all for this article. Click here for more cybersecurity education resources.

For more on using Swift to solve some of the classic problems in computer science, download the free second chapter of Classic Computer Science Problems in Swift and see this slide deck.