From Classic Computer Science Problems in Swift by David Kopec This article will teach you how to use the minimax algorithm to create a Tic-Tac-Toe AI that plays the game flawlessly.

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

 NOTE This article assumes that you are familiar with the game called Tic-Tac-Toe. In the event that you are not, a simple Google search will inform you.

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.

 TIP For games that have too deep a search space to reach a terminal position (checkers, chess) minimax is stopped after a certain depth (number of moves deep to search, sometimes called ply). Then an evaluation function kicks-in that uses heuristics to score the state of the game. The better the game is for the originating player, the higher the score that is awarded.

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)

```

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)

```

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)
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.