组合游戏1: 详解Minimax 和 Alpha Beta剪枝算法

2020-09-02 00:00:00 算法 节点 整数 玩家 剪枝

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

获得好的阅读体验,请点击下方 阅读原文,并在电脑上打开

  • 篇 [Leetcode中的Minimax 和 Alpha Beta剪枝]

  • 第二篇: 一些组合游戏的理论

  • 第三篇: 连接N个点 的OpenAI Gym GUI环境

  • 第四篇: 蒙特卡洛树搜索(MCTS)和时间差分学习(TD learning)

Leetcode 292 Nim Game (简单)

简单题 Leetcode 292 Nim Game。

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

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

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

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

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

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

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


292 Nim Game 暴力解法调用图  n=7

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

# 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(14):
            if not self.canWinNim(n - i):
                return True
        return False

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

 
292 Nim Game 动归解法调用图 n=7
但还是没有AC,因为当n=1348820612时,这种方式会导致栈溢出。再改成下面的循环版本,可惜还是TLE。
# TLE for 1348820612
# Time Complexity: O(N)
class Solution:
    def canWinNim(self, n: int) -> bool:
        if n <= 3:
            return True
        last3, last2, last1 = TrueTrueTrue
        for i in range(4, n+1):
            this = not (last3 and last2 and last1)
            last3, last2, last1 = last2, last1, this
        return last1

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

 
输赢分布

终AC版本,只有一句语句。

AC
Time ComplexityO(1)
class Solution:
    def canWinNim(self, n: int) -bool:
        return not (n % 4 == )

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) 为剩余子数组时,当前玩家能取得的大分差,那么

对应的时间复杂度可以写出递归式,显然是指数级的:

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

# 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(len(nums) - 1) >= 

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

 
486 Predict the Winner 暴力解法调用图 n=4

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

# 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(len(nums) - 1) >= 

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

 
486 Predict the Winner 动归解法调用图 n=4

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),从而取得胜利.
同样地,个玩家选择任意其他整数,第二个玩家都会赢。

# 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()

上面的代码算法复杂度为,m是maxChoosableInteger。由于所有状态的数量是,对于每个状态,多会尝试 走法。

Minimax 算法

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

 
Wikipedia Minimax 例子

Minimax Python 3伪代码如下。

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

Minimax: 486 Predict the Winner

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

# 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 - 1not isMaxPlayer))
        else:
            return min(
                -self.nums[l] + self.minimax(l + 1, r, not isMaxPlayer),
                -self.nums[r] + self.minimax(l, r - 1not isMaxPlayer))

    def PredictTheWinner(self, nums: List[int]) -> bool:
        self.nums = nums
        v = self.minimax(len(nums) - 1True)
        return v >= 
 
Minimax 486 调用图 nums=[1, 5, 2, 4]

Minimax: 464 Can I Win

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

# 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   # 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的例子来进一步说明:

  1. 根节点初始时:alpha = −∞, beta = +∞

  2. 根节点,左边子节点返回4后:alpha = 4, beta = +∞

  3. 根节点,中间子节点返回5后:alpha = 5, beta = +∞

  4. 右Min节点(标1节点),初始时:alpha = 5, beta = +∞

  5. 右Min节点(标1节点),个子节点返回1后:alpha = 5, beta = 1

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

 
Wikimedia Alpha Beta 剪枝例子
Minimax Python 3伪代码如下
def alpha_beta(node: Node, depth: int, α: int, β: int, maximizingPlayer: bool) -> int:
    if depth ==  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

# 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(len(nums) - 1True, -math.inf, math.inf)
        return v >= 

Alpha-Beta Pruning: 464 Can I Win

# 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   # 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解的构建顺序,先解决小规模的问题,并在此基础上计算稍大的问题。值得一提的是,以下的循环写法严格保证了 次循环,但是自顶向下的计划递归可能会少于 次循环。

Java AC Code

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

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

C++ AC Code

// AC
class Solution {
public:
    bool PredictTheWinner(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> dp(n, vector<int>(n, ));
        for (int i = ; i < n; i++) {
          dp[i][i] = nums[i];
        }
        for (int l = n - 1; l >= ; 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[][n - 1] >= ;
    }
};

Javascript AC Code

/**
 * @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 = ; i < n; i++) {
      dp[i][i] = nums[i];
    }
  
    for (let l = n - 1; l >=; 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[][n-1] >=;
};

著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。


相关文章