This episode extends last one, where Minimax and Alpha Beta Pruning algorithms are introduced. We will solve several tic-tac-toe problems in leetcode, gathering intuition and building blocks for tic-tac-toe game logic, which can be naturally extended to Connect-N game or Gomoku (N=5). Then we solve tic-tac-toe using Minimax and Alpha Beta pruning for small N and analyze their state space. In the following episodes, based on building blocks here, we will implement a Connect-N Open Gym GUI Environment, where we can play against computer visually or compare different computer algorithms. Finally, we demonstrate how to implement a Monte Carlo Tree Search for Connect-N Game.
Tic-tac-toe is played by two players A and B on a 3 x 3 grid.
Here are the rules of Tic-Tac-Toe:
Players take turns placing characters into empty squares (” “).
The first player A always places “X” characters, while the second player B always places “O” characters.
“X” and “O” characters are always placed into empty squares, never on filled ones.
The game ends when there are 3 of the same (non-empty) character filling any row, column, or diagonal.
The game also ends if all squares are non-empty.
No more moves can be played if the game is over.
Given an array moves where each element is another array of size 2 corresponding to the row and column of the grid where they mark their respective character in the order in which A and B play.
Return the winner of the game if it exists (A or B), in case the game ends in a draw return “Draw”, if there are still movements to play return “Pending”.
You can assume that moves is valid (It follows the rules of Tic-Tac-Toe), the grid is initially empty and A will play first.
Example 1:
Input: moves = [[0,0],[2,0],[1,1],[2,1],[2,2]]
Output: “A"
Explanation: “A” wins, he always plays first.
“X " “X " “X " “X " “X “
" " -> " " -> " X " -> " X " -> " X “
" " “O " “O " “OO " “OOX"
Example 3:
Input: moves = [[0,0],[1,1],[2,0],[1,0],[1,2],[2,1],[0,1],[0,2],[2,2]]
Output: “Draw"
Explanation: The game ends in a draw since there are no moves to make.
“XXO"
“OOX"
“XOX"
Example 4:
Input: moves = [[0,0],[1,1]]
Output: “Pending"
Explanation: The game has not finished yet.
“X “
" O “
" “
The intuitive solution is to permute all 8 possible winning conditions: 3 vertical lines, 3 horizontal lines and 2 diagonal lines. We keep 8 variables representing each winning condition and a simple trick is converting board state to a 3x3 2d array, whose cell has value -1, 1, and 0. In this way, we can traverse the board state exactly once and in the process determine all 8 variables value by summing corresponding cell value. For example, row[0] is for first line winning condition, summed by all 3 cells in first row during board traveral. It indicates win for first player only when it’s equal to 3 and win for second player when it’s -3.
# ACfrom typing import List
classSolution:
deftictactoe(self, moves: List[List[int]]) -> str:
board = [[0] *3for _ in range(3)]
for idx, xy in enumerate(moves):
player =1if idx %2==0else-1
board[xy[0]][xy[1]] = player
turn =0
row, col = [0, 0, 0], [0, 0, 0]
diag1, diag2 = False, False
for r in range(3):
for c in range(3):
turn += board[r][c]
row[r] += board[r][c]
col[c] += board[r][c]
if r == c:
diag1 += board[r][c]
if r + c ==2:
diag2 += board[r][c]
oWin = any(row[r] ==3for r in range(3)) or any(col[c] ==3for c in range(3)) or diag1 ==3or diag2 ==3
xWin = any(row[r] ==-3for r in range(3)) or any(col[c] ==-3for c in range(3)) or diag1 ==-3or diag2 ==-3return"A"if oWin else"B"if xWin else"Draw"if len(moves) ==9else"Pending"
Below we give another AC solution. Despite more code, it’s more efficient than previous one because for a given game state, it does not need to visit each cell on the board. How is it achieved? The problem guarentees each move is valid, so what’s sufficent to examine is to check neighbours of the final move and see if any line including final move creates a winning condition. Later we will reuse the code in this solution to create tic-tac-toe game logic.
A Tic-Tac-Toe board is given as a string array board. Return True if and only if it is possible to reach this board position during the course of a valid tic-tac-toe game.
The board is a 3 x 3 array, and consists of characters " “, “X”, and “O”. The " " character represents an empty square.
Here are the rules of Tic-Tac-Toe:
Players take turns placing characters into empty squares (” “).
The first player A always places “X” characters, while the second player B always places “O” characters.
“X” and “O” characters are always placed into empty squares, never on filled ones.
The game ends when there are 3 of the same (non-empty) character filling any row, column, or diagonal.
The game also ends if all squares are non-empty.
No more moves can be played if the game is over.
Example 1:
Input: board = [“O “, " “, " “]
Output: false
Explanation: The first player always plays “X”.
Example 2:
Input: board = [“XOX”, " X “, " “]
Output: false
Explanation: Players take turns making moves.
Note:
board is a length-3 array of strings, where each string board[i] has length 3.
Each board[i][j] is a character in the set {” “, “X”, “O”}.
Surely, it can be solved using DFS, checking if the state given would be reached from initial state. However, this involves lots of states to search. Could we do better? There are obvious properties we can rely on. For example, the number of X is either equal to the number of O or one more. If we can enumerate a combination of necessary and sufficient conditions of checking its reachability, we can solve it in O(1) time complexity.
# ACfrom typing import List
classSolution:
defconvertCell(self, c:str):
return1if c =='X'else-1if c =='O'else0defvalidTicTacToe(self, board: List[str]) -> bool:
turn =0
row, col = [0, 0, 0], [0, 0, 0]
diag1, diag2 = False, False
for r in range(3):
for c in range(3):
turn += self.convertCell(board[r][c])
row[r] += self.convertCell(board[r][c])
col[c] += self.convertCell(board[r][c])
if r == c:
diag1 += self.convertCell(board[r][c])
if r + c ==2:
diag2 += self.convertCell(board[r][c])
xWin = any(row[r] ==3for r in range(3)) or any(col[c] ==3for c in range(3)) or diag1 ==3or diag2 ==3
oWin = any(row[r] ==-3for r in range(3)) or any(col[c] ==-3for c in range(3)) or diag1 ==-3or diag2 ==-3if (xWin and turn ==0) or (oWin and turn ==1):
return False
return (turn ==0or turn ==1) and (not xWin ornot oWin)
Design a Tic-tac-toe game that is played between two players on a n x n grid.
You may assume the following rules:
A move is guaranteed to be valid and is placed on an empty block.
Once a winning condition is reached, no more moves is allowed.
A player who succeeds in placing n of their marks in a horizontal, vertical, or diagonal row wins the game.
Example:
Given n = 3, assume that player 1 is “X” and player 2 is “O” in the board.
TicTacToe toe = new TicTacToe(3);
toe.move(0, 0, 1); -> Returns 0 (no one wins)
|X| | |
| | | | // Player 1 makes a move at (0, 0).
| | | |
toe.move(0, 2, 2); -> Returns 0 (no one wins)
|X| |O|
| | | | // Player 2 makes a move at (0, 2).
| | | |
toe.move(2, 2, 1); -> Returns 0 (no one wins)
|X| |O|
| | | | // Player 1 makes a move at (2, 2).
| | |X|
toe.move(1, 1, 2); -> Returns 0 (no one wins)
|X| |O|
| |O| | // Player 2 makes a move at (1, 1).
| | |X|
toe.move(2, 0, 1); -> Returns 0 (no one wins)
|X| |O|
| |O| | // Player 1 makes a move at (2, 0).
|X| |X|
toe.move(1, 0, 2); -> Returns 0 (no one wins)
|X| |O|
|O|O| | // Player 2 makes a move at (1, 0).
|X| |X|
toe.move(2, 1, 1); -> Returns 1 (player 1 wins)
|X| |O|
|O|O| | // Player 1 makes a move at (2, 1).
|X|X|X|
Follow up:
Could you do better than O(n2) per move() operation?
348 is a locked problem. For each player’s move, we can resort to checkWin function in second solution for 1275. We show another solution based on first solution of 1275, where 8 winning condition flags are kept and each move only touches associated several flag variables.
# ACclassTicTacToe:
def __init__(self, n:int):
""" Initialize your data structure here. :type n: int"""
self.row, self.col, self.diag1, self.diag2, self.n = [0] * n, [0] * n, 0, 0, n
defmove(self, row:int, col:int, player:int) -> int:
""" Player {player} makes a move at ({row}, {col}). @param row The row of the board. @param col The column of the board. @param player The player, can be either 1 or 2. @return The current winning condition, can be either: 0: No one wins. 1: Player 1 wins. 2: Player 2 wins."""if player ==2:
player =-1
self.row[row] += player
self.col[col] += player
if row == col:
self.diag1 += player
if row + col == self.n -1:
self.diag2 += player
if self.n in [self.row[row], self.col[col], self.diag1, self.diag2]:
return1if-self.n in [self.row[row], self.col[col], self.diag1, self.diag2]:
return2return0
Optimal Strategy of Tic-Tac-Toe
Tic-tac-toe and Gomoku (Connect Five in a Row) share the same rules and are generally considered as
M,n,k-game
, where board size range to M x N and winning condition changes to k.
ConnectNGame class implements M,n,k-game of MxM board size. It encapsulates the logic of checking each move and also is able to undo last move to facilitate backtrack in game search algorithm later.
classConnectNGame:
PLAYER_A =1
PLAYER_B =-1
AVAILABLE =0
RESULT_TIE =0
RESULT_A_WIN =1
RESULT_B_WIN =-1def __init__(self, N:int =3, board_size:int =3):
assert N <= board_size
self.N = N
self.board_size = board_size
self.board = [[ConnectNGame.AVAILABLE] * board_size for _ in range(board_size)]
self.gameOver = False
self.gameResult = None
self.currentPlayer = ConnectNGame.PLAYER_A
self.remainingPosNum = board_size * board_size
self.actionStack = []
defmove(self, r: int, c: int) -> int:
""" :param r: :param c: :return: None: game ongoing"""assert self.board[r][c] == ConnectNGame.AVAILABLE
self.board[r][c] = self.currentPlayer
self.actionStack.append((r, c))
self.remainingPosNum -=1if self.checkWin(r, c):
self.gameOver = True
self.gameResult = self.currentPlayer
return self.currentPlayer
if self.remainingPosNum ==0:
self.gameOver = True
self.gameResult = ConnectNGame.RESULT_TIE
return ConnectNGame.RESULT_TIE
self.currentPlayer *=-1defundo(self):
if len(self.actionStack) >0:
lastAction = self.actionStack.pop()
r, c = lastAction
self.board[r][c] = ConnectNGame.AVAILABLE
self.currentPlayer = ConnectNGame.PLAYER_A if len(self.actionStack) %2==0else ConnectNGame.PLAYER_B
self.remainingPosNum +=1
self.gameOver = False
self.gameResult = None
else:
raiseException('No lastAction')
defgetAvailablePositions(self) -> List[Tuple[int, int]]:
return [(i,j) for i in range(self.board_size) for j in range(self.board_size) if self.board[i][j] == ConnectNGame.AVAILABLE]
defgetStatus(self) -> Tuple[Tuple[int, ...]]:
return tuple([tuple(self.board[i]) for i in range(self.board_size)])
Note that checkWin code is identical to second solution in 1275.
Minimax Strategy
Now we have Connect-N game logic, let’s finish its minimax algorithm to solve the game.
Define a generic strategy base class, where action method needs to be overridden. Action method expects ConnectNGame class telling current game state and returns a tuple of 2 elements, the first element is the estimated or exact game result after taking action specified by second element. The second element is of form Tuple[int, int], denoting the position of the move, for instance, (1，1).
classMinimaxStrategy(Strategy):
defaction(self, game: ConnectNGame) -> Tuple[int, Tuple[int, int]]:
self.game = copy.deepcopy(game)
result, move = self.minimax()
return result, move
defminimax(self) -> Tuple[int, Tuple[int, int]]:
game = self.game
bestMove = None
assertnot game.gameOver
if game.currentPlayer == ConnectNGame.PLAYER_A:
ret =-math.inf
for pos in game.getAvailablePositions():
move = pos
result = game.move(*pos)
if result is None:
assertnot game.gameOver
result, oppMove = self.minimax()
game.undo()
ret = max(ret, result)
bestMove = move if ret == result else bestMove
if ret ==1:
return1, move
return ret, bestMove
else:
ret = math.inf
for pos in game.getAvailablePositions():
move = pos
result = game.move(*pos)
if result is None:
assertnot game.gameOver
result, oppMove = self.minimax()
game.undo()
ret = min(ret, result)
bestMove = move if ret == result else bestMove
if ret ==-1:
return-1, move
return ret, bestMove
We plot up to first 2 moves with code above. For first player O, there are possibly 9 positions, where due to symmetry, only 3 kinds of moves, which we call corner, edge and center, respectively. The following graph shows whatever 9 positions the first player takes, the best result is draw. So solution of tic-tac-toe is draw.
Plot first step of 3 kinds of moves one by one below.
Tic-tac-toe Solution and Number of States
An interesting question is the number of game states of tic-tac-toe. A loosely upper bound can be derived by $3^9=19683$, which includes lots of inreachable states. This article
Tic-Tac-Toe (Naughts and Crosses, Cheese and Crackers, etc
lists number of states after each move. The total number is 5478.
Moves
Positions
Terminal Positions
0
1
1
9
2
72
3
252
4
756
5
1260
120
6
1520
148
7
1140
444
8
390
168
9
78
78
Total
5478
958
We can verify the number if we change a little of existing code to code below.
classAlphaBetaStrategy(Strategy):
defaction(self, game: ConnectNGame) -> Tuple[int, Tuple[int, int]]:
self.game = game
result, move = self.alpha_beta(self.game.getStatus(), -math.inf, math.inf)
return result, move
defalpha_beta(self, gameStatus: Tuple[Tuple[int, ...]], alpha:int=None, beta:int=None) -> Tuple[int, Tuple[int, int]]:
game = self.game
bestMove = None
assertnot game.gameOver
if game.currentPlayer == ConnectNGame.PLAYER_A:
ret =-math.inf
for pos in game.getAvailablePositions():
move = pos
result = game.move(*pos)
if result is None:
assertnot game.gameOver
result, oppMove = self.alpha_beta(game.getStatus(), alpha, beta)
game.undo()
alpha = max(alpha, result)
ret = max(ret, result)
bestMove = move if ret == result else bestMove
if alpha >= beta or ret ==1:
return ret, move
return ret, bestMove
else:
ret = math.inf
for pos in game.getAvailablePositions():
move = pos
result = game.move(*pos)
if result is None:
assertnot game.gameOver
result, oppMove = self.alpha_beta(game.getStatus(), alpha, beta)
game.undo()
beta = min(beta, result)
ret = min(ret, result)
bestMove = move if ret == result else bestMove
if alpha >= beta or ret ==-1:
return ret, move
return ret, bestMove
Rewrite alpha beta pruning with DP, where we omit alpha and beta parameters in alpha_beta_dp because lru_cache cannot specify effective parameters. Instead, we keep alpha and beta in a stack variable and maintain the stack according to alpha_bate_dp calling stack.