Fixing a bug in Tic Tac Toe with TDD
I discovered a bug in the game I had written on Tic Tac Toe. When the board is in a certain state, the system did not take the obvious winning move. It still won the game, but with an extra move required. This article details how to write a failing unit test to reproduce the issue and how to update the minimax algorithm to address the issue.
Related articles on TDD in SwiftUI:
Game play to reproduce the issue
I developed a Tic Tac Toe game using TDD in Test Driven Development in SwiftUI - Part 3. The default for a one-player game is that the player has the X token and makes the first move.
Steps to reproduce the issue:
1. Place the "X-Token" in the top left corner.
2. The system places the O-Token in the center cell.
3. Place the "X-Token" in the top right corner.
4. The system places the "O-Token" in the top center cell to block "X".
5. Place the "X-Token" in the bottom left corner.
Expected Result:
The system places the `O-Token` in the bottom center cell.
Actual Result:
The system places the `O-Token` in the left center cell.
There is a winning move available to O-Player in the bottom center cell, however the system places the O-Token in the center cell in the right column. This does not lose the game, as the O-Player now has two winning options available and cannot be stopped by the X-Player. The result is that the O-Player wins the game, but it could have won the game with one less move.
System selects the first cell in the second row in Tic Tac Toe
Add a Unit Test for the scenario
Now that we know the steps to reproduce the issue, we can write a unit test against the model to test this scenario. Essentially, we set the board up with the tokens as outlined in the image above and assert that the system will place the O-Token in the bottom center cell (cell at index 7). A second assert is added that O-Player is the winning player when the token is placed in this cell. When we run the unit tests, all the existing tests pass, but this new unit test fails. Now we have a test to validate this scenario, we can investigate and fix the issue.
Failing Test added to TicGameModelTests
1 func test_oToWinInOneMove_ThreeBlankCells() {
2 // Arrange
3 var ticModel = TicGameModel()
4 let fullGrid: [Cell] = [.x, .o, .x,
5 .b, .o, .b,
6 .x, .b, .b]
7 for (i,c) in fullGrid.enumerated() {
8 ticModel.setCell(n: i, c: c)
9 }
10
11 // Act
12 let nextCell = ticModel.nextMove(player: .o)
13 ticModel.setCell(n: nextCell, c: .o)
14
15 // Assert
16 XCTAssertEqual(nextCell, 7)
17 XCTAssertEqual(ticModel.winner, .o)
18 }
Here is the TicGameModel for reference.
TicGameModel
1import Foundation
2
3enum Winner {
4 case o, x, none
5}
6
7struct TicGameModel {
8 private var _board: TicBoardModel
9 private var _winner: Winner
10 private var _playerXTurn: Bool
11 private var _winningLines: [Bool]
12 private var _boardDisabled: Bool
13 private var _twoPlayer: Bool
14
15 init(twoPlayer: Bool = true) {
16 _board = TicBoardModel(cells: [.b, .b, .b,
17 .b, .b, .b,
18 .b, .b, .b])
19 _winningLines = []
20 for _ in 0..<8 {
21 _winningLines.append(false)
22 }
23 _winner = .none
24 _playerXTurn = true
25 _boardDisabled = false
26 _twoPlayer = twoPlayer
27 }
28
29 var grid: [Cell] {
30 get { _board.grid }
31 }
32
33 var winner: Winner {
34 get { _winner }
35 }
36
37 var isGridFull: Bool {
38 get { _board.availableCells.count == 0 }
39 }
40
41 var isXTurn: Bool {
42 get { _playerXTurn }
43 }
44
45 var isTwoPlayer: Bool {
46 get { _twoPlayer }
47 }
48
49 var isBoardDisabled: Bool {
50 get { _boardDisabled }
51 }
52
53 var winningLines: [Bool] {
54 get { _winningLines }
55 }
56
57 func nextMove(player: Cell) -> Int {
58 // Select a random cell if the board is empty
59 if _board.availableCells.count == 9 {
60 return Int.random(in: 0..<9)
61 }
62
63 var bestMove = -1
64 // Maximising
65 if player == .x {
66 var maxScore = Int.min
67 for cell in _board.availableCells {
68 let score = minimax(board: _board,
69 cellNum: cell,
70 isMaximising: true)
71 if score > maxScore {
72 maxScore = score
73 bestMove = cell
74 }
75 }
76 } else { // player == .o - Minimising
77 var minScore = Int.max
78 for cell in _board.availableCells {
79 let score = minimax(board: _board,
80 cellNum: cell,
81 isMaximising: false)
82 if score < minScore {
83 minScore = score
84 bestMove = cell
85 }
86 }
87 }
88 return bestMove
89 }
90
91 mutating func setCell(n:Int, c: Cell) {
92 guard _board.grid.indices.contains(n) else {
93 return
94 }
95 guard _board.grid[n] == .b else {
96 return
97 }
98 _board = TicBoardModel(cells: _board.grid, n: n, c: c)
99 _winner = winningPlayer(board: _board)
100 _winningLines = winningLines(board: _board)
101 _playerXTurn.toggle()
102
103 // Disable the board if it is a one player game
104 if !_twoPlayer {
105 _boardDisabled = true
106 }
107 }
108
109 mutating func takeSystemTurn() {
110 guard !_twoPlayer else {
111 return
112 }
113 let cellIndex = nextMove(player: _playerXTurn ? .x : .o)
114 setCell(n: cellIndex, c: _playerXTurn ? .x : .o)
115
116 // Enable the board after the system has taken a turn
117 _boardDisabled = false
118 }
119
120 private func winningLines(board b: TicBoardModel) -> [Bool] {
121 var result = [false, false, false, false, false, false, false, false]
122 let winOptions: [Set<Int>] = [
123 [0,1,2], [3,4,5], [6,7,8],
124 [0,3,6], [1,4,7], [2,5,8],
125 [0,4,8], [2,4,6]]
126
127 let oCells: Set<Int> = Set(b.grid.indices.map { b.grid[$0] == Cell.o ? $0 : -1 })
128 let xCells: Set<Int> = Set(b.grid.indices.map { b.grid[$0] == Cell.x ? $0 : -1 })
129
130 for (i, win) in winOptions.enumerated() {
131 if win.intersection(xCells) == win {
132 result[i] = true
133 }
134 if win.intersection(oCells) == win {
135 result[i] = true
136 }
137 }
138 return result
139 }
140
141 private func winningPlayer(board b: TicBoardModel) -> Winner {
142 // There are 8 possible winning options in Tic Tac Toe
143 // The order of these options needs to match _winningLines
144 let winOptions: [Set<Int>] = [
145 [0,1,2], [3,4,5], [6,7,8],
146 [0,3,6], [1,4,7], [2,5,8],
147 [0,4,8], [2,4,6]]
148
149 let oCells: Set<Int> = Set(b.grid.indices.map { b.grid[$0] == Cell.o ? $0 : -1 })
150 let xCells: Set<Int> = Set(b.grid.indices.map { b.grid[$0] == Cell.x ? $0 : -1 })
151
152 for win in winOptions {
153 if win.intersection(xCells) == win {
154 return .x
155 }
156 if win.intersection(oCells) == win {
157 return .o
158 }
159 }
160 return .none
161 }
162
163 private func minimax(board: TicBoardModel, cellNum: Int, isMaximising: Bool) -> Int {
164 let b = TicBoardModel(cells: board.grid,
165 n: cellNum,
166 c: isMaximising ? .x : .o)
167
168 // Base case
169 if winningPlayer(board: b) == .x {
170 return 1
171 } else if winningPlayer(board: b) == .o {
172 return -1
173 } else if b.availableCells.count == 0 {
174 return 0
175 }
176
177 // Maximising
178 if isMaximising {
179 var minVal = Int.max
180 for nextMove in b.availableCells {
181 let score = minimax(board: b,
182 cellNum: nextMove,
183 isMaximising: false)
184 minVal = min(minVal, score)
185 }
186 return minVal
187 } else { // Minimising
188 var maxVal = Int.min
189 for nextMove in b.availableCells {
190 let score = minimax(board: b,
191 cellNum: nextMove,
192 isMaximising: true)
193 maxVal = max(maxVal, score)
194 }
195 return maxVal
196 }
197 }
198
199}
Explanation of why
There is an explanation for why the system selects the cell in the right center rather than the bottom center. We need to go back to look at the Minimax algorithm as explained in Understanding Minimax Algorithm with Tic Tac Toe. O-Player is set as the minimising player and X-Player the maximising. The diagram shows that there are 4 available cells where O-Player can place its token from the given starting state.
The diagram shows the options for alternate moves between O-Player and X-Player and the scores roll up to the original moves available to O-Player. It can be seen, from the image, that 2 of the 4 moves available to O-Player result in a score of -1, which is a win for O-Player. As there is no distinction between either of the winning plays, the system selects the first one, which places the token in the left center cell.
Change to Algorithm
The solution is to add some factor that gives some increased score for a win in less
moves. One way to do this is to multiply the score of -1 or +1 by the number of
remaining cells. In the TicGameModel the score is calculated for each available
cell by calling the minimax method.
The scores on the same initial state with O-Player as the minimising player are outlined below. There are two winning moves for O-Player from the starting state, but these now have scores of -2 and -4, rather than both having a score of -1. The move with the lower score (-4) will be selected resulting in an immediate win for O-Player.
Unit test passing
All unit tests on the model and viewmodel now pass, including the newly added tests. Inside the minimax method the available cells number needs to be adjusted by one, as the token has already been added to the cell to calculate the score. I missed this initially, and then added a unit test to test this scenario, before fixing the model code as outlined below.
Change to TicGameModel
1 private func minimax(board: TicBoardModel, cellNum: Int, isMaximising: Bool) -> Int {
2 let b = TicBoardModel(cells: board.grid,
3 n: cellNum,
4 c: isMaximising ? .x : .o)
5
6 let scoreFactor = b.availableCells.count + 1
7
8 // Base case
9 if winningPlayer(board: b) == .x {
10 return 1 * scoreFactor
11 } else if winningPlayer(board: b) == .o {
12 return -1 * scoreFactor
13 } else if b.availableCells.count == 0 {
14 return 0
15 }
16
17 // Maximising
18 if isMaximising {
19 var minVal = Int.max
20 for nextMove in b.availableCells {
21 let score = minimax(board: b,
22 cellNum: nextMove,
23 isMaximising: false)
24 minVal = min(minVal, score)
25 }
26 return minVal
27 } else { // Minimising
28 var maxVal = Int.min
29 for nextMove in b.availableCells {
30 let score = minimax(board: b,
31 cellNum: nextMove,
32 isMaximising: true)
33 maxVal = max(maxVal, score)
34 }
35 return maxVal
36 }
37 }
New Unit Test added to TicGameModelTests - passing
1 func test_oToWinInOneMove_ThreeBlankCells() {
2 // Arrange
3 var ticModel = TicGameModel()
4 let fullGrid: [Cell] = [.x, .o, .x,
5 .b, .o, .b,
6 .x, .b, .b]
7 for (i,c) in fullGrid.enumerated() {
8 ticModel.setCell(n: i, c: c)
9 }
10
11 // Act
12 let nextCell = ticModel.nextMove(player: .o)
13 ticModel.setCell(n: nextCell, c: .o)
14
15 // Assert
16 XCTAssertEqual(nextCell, 7)
17 XCTAssertEqual(ticModel.winner, .o)
18 }
19
20 func test_oToDraw_TwoBlankCells() {
21 // Arrange
22 var ticModel = TicGameModel()
23 let fullGrid: [Cell] = [.x, .o, .x,
24 .o, .o, .x,
25 .b, .x, .b]
26 for (i,c) in fullGrid.enumerated() {
27 ticModel.setCell(n: i, c: c)
28 }
29
30 // Act
31 let nextCell = ticModel.nextMove(player: .o)
32
33 // Assert
34 XCTAssertEqual(nextCell, 8)
35 }
Corrected game play
Here is the original game play behaving as expected with the system winning the game in as few moves as possible.
System selecting to win immediately in Tic Tac Toe
Conclusion
It is interesting that despite using TDD and having unit tests on Model and ViewModel, there was still a bug in the logic of the Tic Tac Toe game. The system still selected a winning move, it just seemed wrong to miss an immediate winning move. It turns out the minimax algorithm, as it was originally implemented, treated all wins equally, so the first cell that would lead to a winning move was selected. The change in the algorithm here was to add a factor to score a win in less moves higher than a win in more moves. All of the existing unit tests assure us that we have not broken anything else.