组合游戏系列2: 井字棋Leetcode系列题解和Minimax最佳策略实现

7月 12 2020 Tech Blog 32 分钟读完 (约 4735 字)

继上一篇介绍了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占据了第一行。

{linenos

# 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过程中不会产生输赢结果，因此我们直接检查最后一个棋子向外的八个方向，若任意方向有三连子，则此玩家获胜。这种解法主要是为后续井字棋扩展到五子棋时判断每个落子是否产生输赢做代码准备。

{linenos

# 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多一个。其关键在于需要找到判断状态合法的充要条件，就可以在\(O(1)\) 时间复杂度完成判断。此外，这道题给了我们井字棋所有可能状态数量的启示。

{linenos

# 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解法一的方法：保存八个关键变量，每次落子后更新这个子所关联的某几个变量。

{linenos

# 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方法用于撤销最后一个落子，方便在后续寻找最佳策略时回溯。

ConnectNGame

{linenos

class 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）。

{linenos

class Strategy(ABC):

    def __init__(self):
        super().__init__()

    @abstractmethod
    def action(self, game: ConnectNGame) -> Tuple[int, Tuple[int, int]]:
        pass

MinimaxStrategy 的逻辑和之前的minimax模版算法大致相同，多了保存最佳move对应的动作，用于最后返回。

{linenos

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个位置，排除对称位置后只有三种，分别为角落，边上和正中。但无论哪一个位置作为先手，最好的结局都是被对方逼平，不存在必赢的开局。所以井字棋的结局是：如果两个玩家都采用最优策略（无失误），游戏结果为双方逼平。

下面分别画出三种开局后进一步的游戏结局。

井字棋游戏状态数和解

有趣的是井字棋游戏的状态数量，简单的上限估算是\(3^9=19683\)。这显然是个较宽泛的上限，因为很多状态在游戏结束后无法达到。这篇文章 Tic-Tac-Toe (Naughts and Crosses, Cheese and Crackers, etc 中列出了每一步的状态数，合计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

我们已经实现了井字棋的minimax策略，算法本质上遍历了所有情况，稍加改造后增加dp数组，就可以确认上面的总状态数。

{linenos


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，下面是一些极小规模时代码运行结果：

	3x3	4x4
k=3	5478 （Draw)	6035992 （Win）
k=4		9722011 （Draw）
k=5

根据 Wikipedia M,n,k-game, 列出了一些小规模下的游戏解：

	3x3	4x4	5x5	6x6
k=3	Draw	Win	Win	Win
k=4		Draw	Draw	Win
k=5			Draw	Draw

值得一提的是，五子棋（棋盘15x15或以上）被 L. Victor Allis证明是先手赢。

Alpha-Beta剪枝策略

Alpha Beta 剪枝策略的代码如下（和之前代码比较类似，不再赘述）：

{linenos

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, bestMove

Alpha Beta 的DP版本中，由于lru_cache无法指定cache的有效参数，递归函数并没有传入alpha, beta。因此我们将alpha，beta参数隐式放入自己维护的栈中，并保证栈的状态和alpha_beta_dp函数调用状态一致。

{linenos

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

组合游戏系列1: Leetcode中的Minimax 和 Alpha Beta剪枝

6月 27 2020 Tech Blog 31 分钟读完 (约 4610 字)

本系列，我们来看看在一种常见的组合游戏——回合制棋盘类游戏中，如何用算法来解决问题。首先，我们会介绍并解决搜索空间较小的问题，引入经典的博弈算法和相关理论，最终实现在大搜索空间中的Deep RL近似算法。在此基础上可以理解AlphaGo的原理和工作方式。本系列的第一篇，我们介绍3个Leetcode中的零和回合制游戏，从最初的暴力解法，到动态规划最终演变成博弈论里的经典算法： minimax 以及 alpha beta 剪枝。

Leetcode 292 Nim Game (简单)

简单题 Leetcode 292 Nim Game。

你和你的朋友，两个人一起玩 Nim游戏：桌子上有一堆石头，每次你们轮流拿掉 1 - 3 块石头。拿掉最后一块石头的人就是获胜者。你作为先手。
你们是聪明人，每一步都是最优解。编写一个函数，来判断你是否可以在给定石头数量的情况下赢得游戏。

示例:
输入: 4
输出: false
解释: 如果堆中有 4 块石头，那么你永远不会赢得比赛；因为无论你拿走 1 块、2 块还是 3 块石头，最后一块石头总是会被你的朋友拿走。

定义 \(f(n)\) 为有\(n\)个石头并采取最优策略的游戏结果， \(f(n)\)的值只有可能是赢或者输。考察前几个结果：\(f(1) = f(2) = f(3) = Win\)，然后来计算\(f(4)\)。因为玩家采取最优策略（只要有一种走法让对方必输，玩家获胜），对于4来说，玩家能走的可能是拿掉1块、2块或3块，但是无论剩余何种局面，对方都是必赢，因此，4就是必输。总的说来，递归关系如下： \[ f(n) = \neg (f(n-1) \land f(n-2) \land f(n-3)) \]

这个递归式可以直接翻译成Python 3代码

{linenos

# TLE
# Time Complexity: O(exponential)
class Solution_BruteForce:

    def canWinNim(self, n: int) -> bool:
        if n <= 3:
            return True
        for i in range(1, 4):
            if not self.canWinNim(n - i):
                return True
        return False

以上的递归公式和代码很像fibonacci数的递归定义和暴力解法，因此对应的时间复杂度也是指数级的，提交代码以后会TLE。下图画出了当n=7时的递归调用，注意 5 被扩展向下重复执行了两次，4重复了4次。

我们采用和fibonacci一样的方式来优化算法：缓存较小n的结果以此来计算较大n的结果。 Python 中，我们可以只加一行lru_cache decorator，来取得这种动态规划效果，下面的代码将复杂度降到了 \(O(N)\)。

{linenos

# RecursionError: maximum recursion depth exceeded in comparison n=1348820612
# Time Complexity: O(N)
class Solution_DP:
    from functools import lru_cache
    @lru_cache(maxsize=None)
    def canWinNim(self, n: int) -> bool:
        if n <= 3:
            return True
        for i in range(1, 4):
            if not self.canWinNim(n - i):
                return True
        return False

再来画出调用图：这次5和4就不再被展开重复计算，图中绿色的节点表示缓存命中。

但还是没有AC，因为当n=1348820612时，这种方式会导致栈溢出。再改成下面的循环版本，可惜还是TLE。

{linenos

# TLE for 1348820612
# Time Complexity: O(N)
class Solution:
    def canWinNim(self, n: int) -> bool:
        if n <= 3:
            return True
        last3, last2, last1 = True, True, True
        for i in range(4, n+1):
            this = not (last3 and last2 and last1)
            last3, last2, last1 = last2, last1, this
        return last1

由此看来，AC 版本需要低于\(O(n)\)的算法复杂度。上面的写法似乎暗示输赢有周期性的规律。事实上，如果将输赢按照顺序画出来，就马上得出规律了：只要\(n \mod 4 = 0\) 就是输，否则赢。原因如下：当面临不能被4整除的数量时 \(4k+i (i=1,2,3)\) ，一方总是可以拿走 \(i\) 个，将\(4k\) 留给对手，而对方下轮又将返回不能被4整除的数，如此循环往复，直到这一方有1, 2, 3 个，最终获胜。

最终AC版本，只有一句语句。

{linenos

# AC
# Time Complexity: O(1)
class Solution:
    def canWinNim(self, n: int) -> bool:
        return not (n % 4 == 0)

Leetcode 486 Predict the Winner (中等)

中等难度题目： Leetcode 486 Predict the Winner.

给定一个表示分数的非负整数数组。玩家1从数组任意一端拿取一个分数，随后玩家2继续从剩余数组任意一端拿取分数，然后玩家1拿，……。每次一个玩家只能拿取一个分数，分数被拿取之后不再可取。直到没有剩余分数可取时游戏结束。最终获得分数总和最多的玩家获胜。
给定一个表示分数的数组，预测玩家1是否会成为赢家。你可以假设每个玩家的玩法都会使他的分数最大化。

示例 1:
输入: [1, 5, 2]
输出: False
解释: 一开始，玩家1可以从1和2中进行选择。
如果他选择2（或者1），那么玩家2可以从1（或者2）和5中进行选择。如果玩家2选择了5，那么玩家1则只剩下1（或者2）可选。
所以，玩家1的最终分数为 1 + 2 = 3，而玩家2为 5。
因此，玩家1永远不会成为赢家，返回 False。

示例 2:
输入: [1, 5, 233, 7]
输出: True
解释: 玩家1一开始选择1。然后玩家2必须从5和7中进行选择。无论玩家2选择了哪个，玩家1都可以选择233。
最终，玩家1（234分）比玩家2（12分）获得更多的分数，所以返回 True，表示玩家1可以成为赢家。

对于当前玩家，他有两种选择：左边或者右边的数。定义 maxDiff(l, r) 为剩余子数组\([l,r]\)时，当前玩家能取得的最大分差，那么

\[ \begin{equation*} \operatorname{maxDiff}(l, r) = \max \begin{cases} nums[l] - \operatorname{maxDiff}(l + 1, r)\\\\ nums[r] - \operatorname{maxDiff}(l, r - 1) \end{cases} \end{equation*} \]

对应的时间复杂度可以写出递归式，显然是指数级的： \[ f(n) = 2f(n-1) = O(2^n) \]

采用暴力解法可以AC，但运算时间很长，接近TLE边缘 (6300ms)。

{linenos

# AC
# Time Complexity: O(2^N)
# Slow: 6300ms
from typing import List

class Solution:

    def maxDiff(self, l: int, r:int) -> int:
        if l == r:
            return self.nums[l]
        return max(self.nums[l] - self.maxDiff(l + 1, r), self.nums[r] - self.maxDiff(l, r - 1))

    def PredictTheWinner(self, nums: List[int]) -> bool:
        self.nums = nums
        return self.maxDiff(0, len(nums) - 1) >= 0

从调用图也很容易看出是指数级的复杂度

上图中我们有重复计算的节点，例如[1-2]节点被计算了两次。使用 lru_cache 大法，在maxDiff 上仅加了一句，就能以复杂度 \(O(n^2)\)和运行时间 43ms AC。

{linenos

# AC
# Time Complexity: O(N^2)
# Fast: 43ms
from functools import lru_cache
from typing import List

class Solution:

    @lru_cache(maxsize=None)
    def maxDiff(self, l: int, r:int) -> int:
        if l == r:
            return self.nums[l]
        return max(self.nums[l] - self.maxDiff(l + 1, r), self.nums[r] - self.maxDiff(l, r - 1))

    def PredictTheWinner(self, nums: List[int]) -> bool:
        self.nums = nums
        return self.maxDiff(0, len(nums) - 1) >= 0

动态规划解法调用图可以看出节点 [1-2] 这次没有被计算两次。

Leetcode 464 Can I Win (中等)

类似但稍有难度的题目 Leetcode 464 Can I Win。难点在于使用了位的状态压缩。

在 "100 game" 这个游戏中，两名玩家轮流选择从 1 到 10 的任意整数，累计整数和，先使得累计整数和达到 100 的玩家，即为胜者。
如果我们将游戏规则改为 “玩家不能重复使用整数” 呢？
例如，两个玩家可以轮流从公共整数池中抽取从 1 到 15 的整数（不放回），直到累计整数和 >= 100。
给定一个整数 maxChoosableInteger （整数池中可选择的最大数）和另一个整数 desiredTotal（累计和），判断先出手的玩家是否能稳赢（假设两位玩家游戏时都表现最佳）？
你可以假设 maxChoosableInteger 不会大于 20， desiredTotal 不会大于 300。

示例：
输入：
maxChoosableInteger = 10
desiredTotal = 11
输出：
false
解释：
无论第一个玩家选择哪个整数，他都会失败。
第一个玩家可以选择从 1 到 10 的整数。
如果第一个玩家选择 1，那么第二个玩家只能选择从 2 到 10 的整数。
第二个玩家可以通过选择整数 10（那么累积和为 11 >= desiredTotal），从而取得胜利.
同样地，第一个玩家选择任意其他整数，第二个玩家都会赢。

{linenos

# AC
# Time Complexity: O:(2^m*m), m: maxChoosableInteger
class Solution:
    from functools import lru_cache
    @lru_cache(maxsize=None)
    def recurse(self, status: int, currentTotal: int) -> bool:
        for i in range(1, self.maxChoosableInteger + 1):
            if not (status >> i & 1):
                new_status = 1 << i | status
                if currentTotal + i >= self.desiredTotal:
                    return True
                if not self.recurse(new_status, currentTotal + i):
                    return True
        return False


    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:
        self.maxChoosableInteger = maxChoosableInteger
        self.desiredTotal = desiredTotal

        sum = maxChoosableInteger * (maxChoosableInteger + 1) / 2
        if sum < desiredTotal:
            return False
        return self.recurse(0, 0)

上面的代码算法复杂度为\(O(m 2^m)\)，m是maxChoosableInteger。由于所有状态的数量是\(2^m\)，对于每个状态，最多会尝试 \(m\) 走法。

Minimax 算法

至此，我们AC了leetcode中的几道零和回合制博弈游戏。事实上，在这个领域有通用的算法：回合制博弈下的minimax。算法背景如下，两个玩家轮流玩，第一个玩家max的目的是将游戏的效用最大化，第二个玩家min则是最小化效用。比如，下面的节点表示玩家选取节点后游戏的效用，当两个玩家都能采取最优策略，Minimax 算法从底层节点来计算，游戏的结果是最终max 玩家会得到-7。

Minimax Python 3伪代码如下。

{linenos

def minimax(node: Node, depth: int, maximizingPlayer: bool) -> int:
    if depth == 0 or is_terminal(node):
        return evaluate_terminal(node)
    if maximizingPlayer:
        value:int = −∞
        for child in node:
            value = max(value, minimax(child, depth − 1, False))
        return value
    else: # minimizing player
        value := +∞
        for child in node:
            value = min(value, minimax(child, depth − 1, True))
        return value

Minimax: 486 Predict the Winner

我们知道486 Predict the Winner 是有minimax解法的，但如何具体实现，其难点在于如何定义合适的游戏价值或者效用。之前的解法中，我们定义maxDiff(l, r) 来表示当前玩家面临子区间 \([l, r]\) 时能取得的最大分差。对于minimax算法，max 玩家要最大化游戏价值，min玩家要最小化游戏价值。先考虑最简单情况即只有一个数x时，若定义max玩家在此局面下得到这个数时游戏价值为 +x，则min玩家为-x，即max玩家得到的所有数为正（\(+a_1 + a_2 + ... = A\)），min玩家得到的所有数为负（\(-b_1 - b_2 - ... = -B\)）。至此，max玩家的目标就是 \(max(A-B)\) ，min玩家是 \(min(A-B)\)。有了精确的定义和优化目标，代码只需要套一下上面的模版。

{linenos

# AC
from functools import lru_cache
from typing import List

class Solution:
    # max_player: max(A - B)
    # min_player: min(A - B)
    @lru_cache(maxsize=None)
    def minimax(self, l: int, r: int, isMaxPlayer: bool) -> int:
        if l == r:
            return self.nums[l] * (1 if isMaxPlayer else -1)

        if isMaxPlayer:
            return max(
                self.nums[l] + self.minimax(l + 1, r, not isMaxPlayer),
                self.nums[r] + self.minimax(l, r - 1, not isMaxPlayer))
        else:
            return min(
                -self.nums[l] + self.minimax(l + 1, r, not isMaxPlayer),
                -self.nums[r] + self.minimax(l, r - 1, not isMaxPlayer))

    def PredictTheWinner(self, nums: List[int]) -> bool:
        self.nums = nums
        v = self.minimax(0, len(nums) - 1, True)
        return v >= 0

Minimax: 464 Can I Win

该题目是很典型的此类游戏，即结果为赢输平，但是中间的状态没有直接对应的游戏价值。对于这样的问题，一般定义为，max玩家胜，价值 +1，min玩家胜，价值-1，平则0。下面的AC代码实现了 Minimax 算法。算法中针对两个玩家都有剪枝（没有剪枝无法AC）。具体来说，max玩家一旦在某一节点取得胜利(value=1)，就停止继续向下搜索，因为这是他能取得的最好分数。同理，min玩家一旦取得-1也直接返回上层节点。这个剪枝可以泛化成 alpha beta剪枝算法。

{linenos

# AC
class Solution:
    from functools import lru_cache
    @lru_cache(maxsize=None)
    # currentTotal < desiredTotal
    def minimax(self, status: int, currentTotal: int, isMaxPlayer: bool) -> int:
        import math
        if status == self.allUsed:
            return 0  # draw: no winner

        if isMaxPlayer:
            value = -math.inf
            for i in range(1, self.maxChoosableInteger + 1):
                if not (status >> i & 1):
                    new_status = 1 << i | status
                    if currentTotal + i >= self.desiredTotal:
                        return 1  # shortcut
                    value = max(value, self.minimax(new_status, currentTotal + i, not isMaxPlayer))
                    if value == 1:
                        return 1
            return value
        else:
            value = math.inf
            for i in range(1, self.maxChoosableInteger + 1):
                if not (status >> i & 1):
                    new_status = 1 << i | status
                    if currentTotal + i >= self.desiredTotal:
                        return -1  # shortcut
                    value = min(value, self.minimax(new_status, currentTotal + i, not isMaxPlayer))
                    if value == -1:
                        return -1
            return value

Alpha-Beta 剪枝

在464 Can I Win minimax 算法代码实现中，我们发现有剪枝优化空间。对于每个节点，定义两个值alpha 和 beta，表示从根节点到目前局面时，max玩家保证能取得的最小值以及min玩家能保证取得的最大值。初始时，根节点alpha = −∞ ， beta = +∞，表示游戏最终的价值在区间 [−∞, +∞]中。在向下遍历的过程中，子节点先继承父节点的 alpha beta 值进而继承区间 [alpha, beta]。当子节点在向下遍历的时候同步更新alpha 或者 beta，一旦区间[alpha, beta]非法就立即向上返回。举个Wikimedia的例子来进一步说明：

根节点初始时： alpha = −∞, beta = +∞
根节点，最左边子节点返回4后： alpha = 4, beta = +∞
根节点，中间子节点返回5后： alpha = 5, beta = +∞
最右Min节点（标1节点），初始时： alpha = 5, beta = +∞
最右Min节点（标1节点），第一个子节点返回1后： alpha = 5, beta = 1

此时，最右Min节点的alpha, beta形成了无效区间[5, 1]，满足了剪枝条件，因此可以不用计算它的第二个和第三个子节点。如果剩余子节点返回值 > 1，比如2，由于这是个min节点，将会被已经到手的1替换。若其他子节点返回值 < 1，但由于min的父节点有效区间是[5, +∞]，已经保证了>=5，小于5的值也会被忽略。

Alpha Beta 剪枝 Python 3伪代码如下

{linenos

def alpha_beta(node: Node, depth: int, α: int, β: int, maximizingPlayer: bool) -> int:
    if depth == 0 or is_terminal(node):
        return evaluate_terminal(node)
    if maximizingPlayer:
        value: int = −∞
        for child in node:
            value = max(value, alphabeta(child, depth − 1, α, β, False))
            α = max(α, value)
            if α >= β:
                break # β cut-off
        return value
    else:
        value: int = +∞
        for child in node:
            value = min(value, alphabeta(child, depth − 1, α, β, True))
            β = min(β, value)
            if β <= α:
                break # α cut-off
        return value

Alpha-Beta Pruning: 486 Predict the Winner

用 Alpha-Beta 剪枝再次AC 486。

{linenos

# AC
import math
from functools import lru_cache
from typing import List

class Solution:
    def alpha_beta(self, l: int, r: int, curr: int, isMaxPlayer: bool, alpha: int, beta: int) -> int:
        if l == r:
            return curr + self.nums[l] * (1 if isMaxPlayer else -1)

        if isMaxPlayer:
            ret = self.alpha_beta(l + 1, r, curr + self.nums[l], not isMaxPlayer, alpha, beta)
            alpha = max(alpha, ret)
            if alpha >= beta:
                return alpha
            ret = max(ret, self.alpha_beta(l, r - 1, curr + self.nums[r], not isMaxPlayer, alpha, beta))
            return ret
        else:
            ret = self.alpha_beta(l + 1, r, curr - self.nums[l], not isMaxPlayer, alpha, beta)
            beta = min(beta, ret)
            if alpha >= beta:
                return beta
            ret = min(ret, self.alpha_beta(l, r - 1, curr - self.nums[r], not isMaxPlayer, alpha, beta))
            return ret

    def PredictTheWinner(self, nums: List[int]) -> bool:
        self.nums = nums
        v = self.alpha_beta(0, len(nums) - 1, 0, True, -math.inf, math.inf)
        return v >= 0

Alpha-Beta Pruning: 464 Can I Win

464 Alpha-Beta 剪枝版本。

{linenos

# AC
class Solution:
    from functools import lru_cache
    @lru_cache(maxsize=None)
    # currentTotal < desiredTotal
    def alpha_beta(self, status: int, currentTotal: int, isMaxPlayer: bool, alpha: int, beta: int) -> int:
        import math
        if status == self.allUsed:
            return 0  # draw: no winner

        if isMaxPlayer:
            value = -math.inf
            for i in range(1, self.maxChoosableInteger + 1):
                if not (status >> i & 1):
                    new_status = 1 << i | status
                    if currentTotal + i >= self.desiredTotal:
                        return 1  # shortcut
                    value = max(value, self.alpha_beta(new_status, currentTotal + i, not isMaxPlayer, alpha, beta))
                    alpha = max(alpha, value)
                    if alpha >= beta:
                        return value
            return value
        else:
            value = math.inf
            for i in range(1, self.maxChoosableInteger + 1):
                if not (status >> i & 1):
                    new_status = 1 << i | status
                    if currentTotal + i >= self.desiredTotal:
                        return -1  # shortcut
                    value = min(value, self.alpha_beta(new_status, currentTotal + i, not isMaxPlayer, alpha, beta))
                    beta = min(beta, value)
                    if alpha >= beta:
                        return value
            return value

C++, Java, Javascript AC 486 Predict the Winner

最后介绍一种不同的DP实现：用C++, Java, Javascript 实现自底向上的DP解法来AC leetcode 486，当然其他语言没有Python的lru_cache大法。以下实现中，注意DP解的构建顺序，先解决小规模的问题，并在此基础上计算稍大的问题。值得一提的是，以下的循环写法严格保证了 \(n^2\) 次循环，但是自顶向下的计划递归可能会少于 \(n^2\)次循环。

Java AC Code

{linenos

// AC
class Solution {
    public boolean PredictTheWinner(int[] nums) {
        int n = nums.length;
        int[][] dp = new int[n][n];
        for (int i = 0; i < n; i++) {
            dp[i][i] = nums[i];
        }

        for (int l = n - 1; l >= 0; l--) {
            for (int r = l + 1; r < n; r++) {
                dp[l][r] = Math.max(
                        nums[l] - dp[l + 1][r],
                        nums[r] - dp[l][r - 1]);
            }
        }
        return dp[0][n - 1] >= 0;
    }
}

C++ AC Code

{linenos

// AC
class Solution {
public:
    bool PredictTheWinner(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> dp(n, vector<int>(n, 0));
        for (int i = 0; i < n; i++) {
          dp[i][i] = nums[i];
        }
        for (int l = n - 1; l >= 0; l--) {
            for (int r = l + 1; r < n; r++) {
                dp[l][r] = max(nums[l] - dp[l + 1][r], nums[r] - dp[l][r - 1]);
            }
        }
        return dp[0][n - 1] >= 0;
    }
};

Javascript AC Code

{linenos

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var PredictTheWinner = function(nums) {
    const n = nums.length;
    const dp = new Array(n).fill().map(() => new Array(n));

    for (let i = 0; i < n; i++) {
      dp[i][i] = nums[i];
    }
  
    for (let l = n - 1; l >=0; l--) {
        for (let r = i + 1; r < n; r++) {
            dp[l][r] = Math.max(nums[l] - dp[l + 1][r],nums[r] - dp[l][r - 1]);
        }
    }
  
    return dp[0][n-1] >=0;
};

#LeetCode

组合游戏系列2: 井字棋Leetcode系列题解和Minimax最佳策略实现

Leetcode 上的井字棋系列

Leetcode 1275. 找出井字棋的获胜者 (简单)

Leetcode 794. 有效的井字游戏 (中等)

Leetcode 348. 判定井字棋胜负 (中等，加锁)

井字棋最佳策略

ConnectNGame

Minimax 算法

井字棋游戏状态数和解

Alpha-Beta剪枝策略

组合游戏系列1: Leetcode中的Minimax 和 Alpha Beta剪枝

Leetcode 292 Nim Game (简单)

Leetcode 486 Predict the Winner (中等)

Leetcode 464 Can I Win (中等)

Minimax 算法

Minimax: 486 Predict the Winner

Minimax: 464 Can I Win

Alpha-Beta 剪枝

Alpha-Beta Pruning: 486 Predict the Winner

Alpha-Beta Pruning: 464 Can I Win

C++, Java, Javascript AC 486 Predict the Winner

Java AC Code

C++ AC Code

Javascript AC Code

Your browser is out-of-date!