繼上一篇介紹了Minimax 和Alpha Beta 剪枝算法之後，本篇選擇了Leetcode中的井字棋遊戲題目，積累相關代碼後實現井字棋遊戲並擴展到五子棋和N子棋（戰略井字棋），隨後用Minimax和Alpha Beta剪枝算法解得小規模下N子棋的遊戲結局，並分析其狀態數量和每一步的最佳策略。後續篇章中，我們基於本篇代碼完成一個N子棋的OpenAI Gym 圖形環境，可用於人機對戰或機器對戰，並最終實現棋盤規模稍大的五子棋或者N子棋中的蒙特卡洛樹搜索（MCTS）算法。
Leetcode 上的井字棋系列Leetcode 1275. 找出井字棋的獲勝者 (簡單)A 和 B 在一個 3 x 3 的網格上玩井字棋。
井字棋遊戲的規則如下：
玩家輪流將棋子放在空方格 (" ") 上。
第一個玩家 A 總是用 "X" 作為棋子，而第二個玩家 B 總是用 "O" 作為棋子。
"X" 和 "O" 只能放在空方格中，而不能放在已經被佔用的方格上。
只要有 3 個相同的（非空）棋子排成一條直線（行、列、對角線）時，遊戲結束。
如果所有方塊都放滿棋子（不為空），遊戲也會結束。
遊戲結束後，棋子無法再進行任何移動。
給你一個數組 moves，其中每個元素是大小為 2 的另一個數組（元素分別對應網格的行和列），它按照 A 和 B 的行動順序（先 A 後 B）記錄了兩人各自的棋子位置。
如果遊戲存在獲勝者（A 或 B），就返回該遊戲的獲勝者；如果遊戲以平局結束，則返回 "Draw"；如果仍會有行動（遊戲未結束），則返回 "Pending"。
你可以假設 moves 都 有效（遵循井字棋規則），網格最初是空的，A 將先行動。
示例 1：
輸入：moves = [[0,0],[2,0],[1,1],[2,1],[2,2]]
輸出："A"
解釋："A" 獲勝，他總是先走。
"X " "X " "X " "X " "X "
" " -> " " -> " X " -> " X " -> " X "
" " "O " "O " "OO " "OOX"
示例 2：輸入：moves = [[0,0],[1,1],[0,1],[0,2],[1,0],[2,0]]
輸出："B"
解釋："B" 獲勝。
"X " "X " "XX " "XXO" "XXO" "XXO"
" " -> " O " -> " O " -> " O " -> "XO " -> "XO "
" " " " " " " " " " "O "
第一種解法，檢查A或者B贏的所有可能情況：某玩家佔據8種連線的任意一種情況則勝利，我們使用八個變量來保存所有情況。下面的代碼使用了一個小技巧，將moves轉換成3x3的棋盤狀態數組，元素的值為1，-1和0。1，-1代表兩個玩家，0代表空的棋盤格子，其優勢在於後續我們只需累加棋盤的值到八個變量中關聯的若干個，再檢查這八個變量是否滿足取勝條件。例如，row[0]表示第一行的狀態，當遍歷一次所有棋盤格局後，row[0]為第一行的3個格子的總和，只有當row[0] == 3 才表明玩家A佔據了第一行，-3表明玩家B佔據了第一行。
# AC
from typing import List
class Solution:
def tictactoe(self, moves: List[List[int]]) -> str:
board = [[0] * 3 for _ in range(3)]
for idx, xy in enumerate(moves):
player = 1 if idx % 2 == 0 else -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] == 3 for r in range(3)) or any(col[c] == 3 for c in range(3)) or diag1 == 3 or diag2 == 3
xWin = any(row[r] == -3 for r in range(3)) or any(col[c] == -3 for c in range(3)) or diag1 == -3 or diag2 == -3
return "A" if oWin else "B" if xWin else "Draw" if len(moves) == 9 else "Pending"下面我們給出另一種解法，這種解法雖然代碼較多，但可以不必遍歷棋盤每個格子，比上一種嚴格遍歷一次棋盤的解法略為高效。原理如下，題目保證了moves過程中不會產生輸贏結果，因此我們直接檢查最後一個棋子向外的八個方向，若任意方向有三連子，則此玩家獲勝。這種解法主要是為後續井字棋擴展到五子棋時判斷每個落子是否產生輸贏做代碼準備。
# AC
from typing import List
class Solution:
def checkWin(self, r: int, c: int) -> bool:
north = self.getConnectedNum(r, c, -1, 0)
south = self.getConnectedNum(r, c, 1, 0)
east = self.getConnectedNum(r, c, 0, 1)
west = self.getConnectedNum(r, c, 0, -1)
south_east = self.getConnectedNum(r, c, 1, 1)
north_west = self.getConnectedNum(r, c, -1, -1)
north_east = self.getConnectedNum(r, c, -1, 1)
south_west = self.getConnectedNum(r, c, 1, -1)
if (north + south + 1 >= 3) or (east + west + 1 >= 3) or \
(south_east + north_west + 1 >= 3) or (north_east + south_west + 1 >= 3):
return True
return False
def getConnectedNum(self, r: int, c: int, dr: int, dc: int) -> int:
player = self.board[r][c]
result = 0
i = 1
while True:
new_r = r + dr * i
new_c = c + dc * i
if 0 <= new_r < 3 and 0 <= new_c < 3:
if self.board[new_r][new_c] == player:
result += 1
else:
break
else:
break
i += 1
return result
def tictactoe(self, moves: List[List[int]]) -> str:
self.board = [[0] * 3 for _ in range(3)]
for idx, xy in enumerate(moves):
player = 1 if idx % 2 == 0 else -1
self.board[xy[0]][xy[1]] = player
# only check last move
r, c = moves[-1]
win = self.checkWin(r, c)
if win:
return "A" if len(moves) % 2 == 1 else "B"
return "Draw" if len(moves) == 9 else "Pending"
Leetcode 794. 有效的井字遊戲 (中等)用字符串數組作為井字遊戲的遊戲板 board。若且唯若在井字遊戲過程中，玩家有可能將字符放置成遊戲板所顯示的狀態時，才返回 true。
該遊戲板是一個 3 x 3 數組，由字符 " "，"X" 和 "O" 組成。字符 " " 代表一個空位。
以下是井字遊戲的規則：
玩家輪流將字符放入空位（" "）中。
第一個玩家總是放字符 「X」，且第二個玩家總是放字符 「O」。
「X」 和 「O」 只允許放置在空位中，不允許對已放有字符的位置進行填充。
當有 3 個相同（且非空）的字符填充任何行、列或對角線時，遊戲結束。
當所有位置非空時，也算為遊戲結束。
如果遊戲結束，玩家不允許再放置字符。示例 1:
輸入: board = ["O ", " ", " "]
輸出: false
解釋: 第一個玩家總是放置「X」。示例 2:
輸入: board = ["XOX", " X ", " "]
輸出: false
解釋: 玩家應該是輪流放置的。示例 3:
輸入: board = ["XXX", " ", "OOO"]
輸出: false示例 4:
輸入: board = ["XOX", "O O", "XOX"]
輸出: true
說明:遊戲板 board 是長度為 3 的字符串數組，其中每個字符串 board[i] 的長度為 3。board[i][j] 是集合 {" ", "X", "O"} 中的一個字符。
這道題第一反應是需要DFS來判斷給定狀態是否可達，但其實可以用上面1275的思路，即通過檢驗最終棋盤的一些特點來判斷給定狀態是否合法。比如，X和O的數量只有可能相同，或X比O多一個。其關鍵在於需要找到判斷狀態合法的充要條件，就可以在
# AC
from typing import List
class Solution:
def convertCell(self, c:str):
return 1 if c == 'X' else -1 if c == 'O' else 0
def validTicTacToe(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] == 3 for r in range(3)) or any(col[c] == 3 for c in range(3)) or diag1 == 3 or diag2 == 3
oWin = any(row[r] == -3 for r in range(3)) or any(col[c] == -3 for c in range(3)) or diag1 == -3 or diag2 == -3
if (xWin and turn == 0) or (oWin and turn == 1):
return False
return (turn == 0 or turn == 1) and (not xWin or not oWin)
Leetcode 348. 判定井字棋勝負 (中等，加鎖)請在 n × n 的棋盤上，實現一個判定井字棋（Tic-Tac-Toe）勝負的神器，判斷每一次玩家落子後，是否有勝出的玩家。
在這個井字棋遊戲中，會有 2 名玩家，他們將輪流在棋盤上放置自己的棋子。
在實現這個判定器的過程中，你可以假設以下這些規則一定成立：
每一步棋都是在棋盤內的，並且只能被放置在一個空的格子裡；
一旦遊戲中有一名玩家勝出的話，遊戲將不能再繼續；
一個玩家如果在同一行、同一列或者同一斜對角線上都放置了自己的棋子，那麼他便獲得勝利。示例：給定棋盤邊長 n = 3, 玩家 1 的棋子符號是 "X"，玩家 2 的棋子符號是 "O"。
TicTacToe toe = new TicTacToe(3);
toe.move(0, 0, 1); -> 函數返回 0 (此時，暫時沒有玩家贏得這場對決)
|X| | |
| | | | // 玩家 1 在 (0, 0) 落子。
| | | |
toe.move(0, 2, 2); -> 函數返回 0 (暫時沒有玩家贏得本場比賽)
|X| |O|
| | | | // 玩家 2 在 (0, 2) 落子。
| | | |
toe.move(2, 2, 1); -> 函數返回 0 (暫時沒有玩家贏得比賽)
|X| |O|
| | | | // 玩家 1 在 (2, 2) 落子。
| | |X|
toe.move(1, 1, 2); -> 函數返回 0 (暫沒有玩家贏得比賽)
|X| |O|
| |O| | // 玩家 2 在 (1, 1) 落子。
| | |X|
toe.move(2, 0, 1); -> 函數返回 0 (暫無玩家贏得比賽)
|X| |O|
| |O| | // 玩家 1 在 (2, 0) 落子。
|X| |X|
toe.move(1, 0, 2); -> 函數返回 0 (沒有玩家贏得比賽)
|X| |O|
|O|O| | // 玩家 2 在 (1, 0) 落子.
|X| |X|
toe.move(2, 1, 1); -> 函數返回 1 (此時，玩家 1 贏得了該場比賽)
|X| |O|
|O|O| | // 玩家 1 在 (2, 1) 落子。
|X|X|X|348 是道加鎖題，對於每次玩家的move，可以用1275第二種解法中的checkWin 函數。下面代碼給出了另一種基於1275解法一的方法：保存八個關鍵變量，每次落子後更新這個子所關聯的某幾個變量。
# AC
class TicTacToe:
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
def move(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]:
return 1
if -self.n in [self.row[row], self.col[col], self.diag1, self.diag2]:
return 2
return 0
井字棋最佳策略井字棋的規模可以很自然的擴展成四子棋或五子棋等，區別在於棋盤大小和勝利時的連子數量。這類遊戲最一般的形式為 M,n,k-game，中文可能翻譯為戰略井字遊戲，表示棋盤大小為M x N，當k連子時獲勝。下面的ConnectNGame類實現了戰略井字遊戲（M=N）中，兩個玩家輪流下子、更新棋盤狀態和判斷每次落子輸贏等邏輯封裝。其中undo方法用於撤銷最後一個落子，方便在後續尋找最佳策略時回溯。
ConnectNGameclass ConnectNGame:
PLAYER_A = 1
PLAYER_B = -1
AVAILABLE = 0
RESULT_TIE = 0
RESULT_A_WIN = 1
RESULT_B_WIN = -1
def __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 = []
def move(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 -= 1
if 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 *= -1
def undo(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 == 0 else ConnectNGame.PLAYER_B
self.remainingPosNum += 1
self.gameOver = False
self.gameResult = None
else:
raise Exception('No lastAction')
def getAvailablePositions(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]
def getStatus(self) -> Tuple[Tuple[int, ...]]:
return tuple([tuple(self.board[i]) for i in range(self.board_size)])其中checkWin和1275解法二中的邏輯一致。
Minimax 算法此戰略井字遊戲的邏輯代碼，結合之前的minimax算法，可以實現遊戲最佳策略。
先定義一個通用的策略基類和抽象方法 action。action表示給定一個棋盤狀態，返回一個動作決定。返回Tuple的第一個int值表示估計走這一步的結局，第二個值類型是Tuple[int, int]，表示這次落子的位置，例如（1，1）。
class Strategy(ABC):
def __init__(self):
super().__init__()
@abstractmethod
def action(self, game: ConnectNGame) -> Tuple[int, Tuple[int, int]]:
passMinimaxStrategy 的邏輯和之前的minimax模版算法大致相同，多了保存最佳move對應的動作，用於最後返回。
class MinimaxStrategy(Strategy):
def action(self, game: ConnectNGame) -> Tuple[int, Tuple[int, int]]:
self.game = copy.deepcopy(game)
result, move = self.minimax()
return result, move
def minimax(self) -> Tuple[int, Tuple[int, int]]:
game = self.game
bestMove = None
assert not 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:
assert not game.gameOver
result, oppMove = self.minimax()
game.undo()
ret = max(ret, result)
bestMove = move if ret == result else bestMove
if ret == 1:
return 1, move
return ret, bestMove
else:
ret = math.inf
for pos in game.getAvailablePositions():
move = pos
result = game.move(*pos)
if result is None:
assert not 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通過上面的代碼可以畫出初始兩步的井字棋最終結局。對於先手O來說可以落9個位置，排除對稱位置後只有三種，分別為角落，邊上和正中。但無論哪一個位置作為先手，最好的結局都是被對方逼平，不存在必贏的開局。所以井字棋的結局是：如果兩個玩家都採用最優策略（無失誤），遊戲結果為雙方逼平。
井字棋第一步結局下面分別畫出三種開局後進一步的遊戲結局。 井字棋角落開局 井字棋邊上開局 井字棋中間開局井字棋遊戲狀態數和解有趣的是井字棋遊戲的狀態數量，簡單的上限估算是
MovesPositionsTerminal Positions01
19
272
3252
4756
51260120615201512071140444839016897878Total5478958我們已經實現了井字棋的minimax策略，算法本質上遍歷了所有情況，稍加改造後增加dp數組，就可以確認上面的總狀態數。
class CountingMinimaxStrategy(Strategy):
def action(self, game: ConnectNGame) -> Tuple[int, Tuple[int, int]]:
self.game = copy.deepcopy(game)
self.dpMap = {}
result, move = self.minimax(game.getStatus())
return result, move
def minimax(self, gameStatus: Tuple[Tuple[int, ...]]) -> Tuple[int, Tuple[int, int]]:
# print(f'Current {len(strategy.dpMap)}')
if gameStatus in self.dpMap:
return self.dpMap[gameStatus]
game = self.game
bestMove = None
assert not 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:
assert not game.gameOver
result, oppMove = self.minimax(game.getStatus())
self.dpMap[game.getStatus()] = result, oppMove
else:
self.dpMap[game.getStatus()] = result, move
game.undo()
ret = max(ret, result)
bestMove = move if ret == result else bestMove
self.dpMap[gameStatus] = ret, bestMove
return ret, bestMove
else:
ret = math.inf
for pos in game.getAvailablePositions():
move = pos
result = game.move(*pos)
if result is None:
assert not game.gameOver
result, oppMove = self.minimax(game.getStatus())
self.dpMap[game.getStatus()] = result, oppMove
else:
self.dpMap[game.getStatus()] = result, move
game.undo()
ret = min(ret, result)
bestMove = move if ret == result else bestMove
self.dpMap[gameStatus] = ret, bestMove
return ret, bestMove
if __name__ == '__main__':
tic_tac_toe = ConnectNGame(N=3, board_size=3)
strategy = CountingMinimaxStrategy()
strategy.action(tic_tac_toe)
print(f'Game States Number {len(strategy.dpMap)}')運行程序證實了井字棋狀態數為5478，下面是一些極小規模時代碼運行結果：
3x34x4k=35478 （Draw)6035992 （Win）k=4
9722011 （Draw）根據 Wikipedia M,n,k-game, 列出了一些小規模下的遊戲解：
3x34x45x56x6k=3DrawWinWinWink=4
DrawDrawWink=5
DrawDraw值得一提的是，五子棋（棋盤15x15或以上）被 L. Victor Allis證明是先手贏。
Alpha-Beta剪枝策略Alpha Beta 剪枝策略的代碼如下（和之前代碼比較類似，不再贅述）：
class AlphaBetaStrategy(Strategy):
def action(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
def alpha_beta(self, gameStatus: Tuple[Tuple[int, ...]], alpha:int=None, beta:int=None) -> Tuple[int, Tuple[int, int]]:
game = self.game
bestMove = None
assert not 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:
assert not 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:
assert not 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, bestMoveAlpha Beta 的DP版本中，由於lru_cache無法指定cache的有效參數，遞歸函數並沒有傳入alpha, beta。因此我們將alpha，beta參數隱式放入自己維護的棧中，並保證棧的狀態和alpha_beta_dp函數調用狀態一致。
class AlphaBetaDPStrategy(Strategy):
def action(self, game: ConnectNGame) -> Tuple[int, Tuple[int, int]]:
self.game = game
self.alphaBetaStack = [(-math.inf, math.inf)]
result, move = self.alpha_beta_dp(self.game.getStatus())
return result, move
@lru_cache(maxsize=None)
def alpha_beta_dp(self, gameStatus: Tuple[Tuple[int, ...]]) -> Tuple[int, Tuple[int, int]]:
alpha, beta = self.alphaBetaStack[-1]
game = self.game
bestMove = None
assert not 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:
assert not game.gameOver
self.alphaBetaStack.append((alpha, beta))
result, oppMove = self.alpha_beta_dp(game.getStatus())
self.alphaBetaStack.pop()
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:
assert not game.gameOver
self.alphaBetaStack.append((alpha, beta))
result, oppMove = self.alpha_beta_dp(game.getStatus())
self.alphaBetaStack.pop()
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