Alpha Beta 在 2048 游戏中存在的问题

Question

我将使用Python编写一个2048游戏的人工智能，但进展比我预期的要慢得多。我只将深度限制设置为5，但仍需要几秒钟才能获得答案。起初我认为所有函数的实现都很烂，但随后我发现了真正的原因。搜索树上的叶节点数量远远超过可能的数量。

以下是典型结果（我计算了叶子节点、分支和扩展数）：

111640 leaves, 543296 branches, 120936 expansions
Branching factor: 4.49242574585
Expected max leaves = 4.49242574585^5 = 1829.80385192 leaves

还有一个额外的内容：

99072 leaves, 488876 branches, 107292 expansions
Branching factor: 4.55650001864
Expected max leaves = 4.55650001864^5 = 1964.06963743 leaves

如您所见，搜索树上的叶子远比使用朴素极小化值算法时多得多。这是怎么回事？我的算法如下：

# Generate constants
import sys
posInfinity = sys.float_info.max
negInfinity = -sys.float_info.max

# Returns the direction of the best move given current state and depth limit
def bestMove(grid, depthLimit):
    global limit
    limit = depthLimit
    moveValues = {}
    # Match each move to its minimax value
    for move in Utils2048.validMoves(grid):
        gridCopy = [row[:] for row in grid]
        Utils2048.slide(gridCopy, move)
        moveValues[move] = minValue(grid, negInfinity, posInfinity, 1)
    # Return move that have maximum value
    return max(moveValues, key = moveValues.get)

# Returns the maximum utility when the player moves
def maxValue(grid, a, b, depth):
    successors = Utils2048.maxSuccessors(grid)
    if len(successors) == 0 or limit < depth:
        return Evaluator.evaluate(grid)
    value = negInfinity
    for successor in successors:
        value = max(value, minValue(successor, a, b, depth + 1))
        if value >= b:
            return value
        a = max(a, value)
    return value
# Returns the minimum utility when the computer moves
def minValue(grid, a, b, depth):
    successors = Utils2048.minSuccessors(grid)
    if len(successors) == 0 or limit < depth:
        return Evaluator.evaluate(grid)
    value = posInfinity
    for successor in successors:
        value = min(value, maxValue(successor, a, b, depth + 1))
        if value <= a:
            return value
        b = min(b, value)
    return value

有人能帮我一下吗？我已经多次检查了这段代码，但仍然无法确定问题所在。

- Occam's Blade

---

不用在意叶子节点的数量，如果在2048游戏中只有4个移动方式，分支因子怎么可能大于4呢？ - Lucas

请展示一下您如何计算叶子、分支和扩展，我们可以帮助您。 - Tony

这里有一篇论文讨论了游戏，也许会有用 http://www.cs.put.poznan.pl/mszubert/pub/szubert2014cig.pdf - edgarmtze

分支因子高于4，因为这是对抗性的，有一个玩家进行刷卡（4个分支），而另一个玩家则会在4个插槽中放置新的方块，这些方块可以具有值2或4（8个分支）。因此，对于1次前瞻（包括计算双方），分支因子为32。上述代码使用深度（半前瞻）为4，即32*32 = 1024，恰好如此。 - Anton Codes

@occams-blade，你在简单的已知单元测试中得到了什么输出？例如，如果你有一个矩阵，只有2个瓷砖，每个瓷砖的底部行上都有一个值为4，那么你的算法是否会产生正确的深度=1和深度=2的滑动？它是否具有正确的分支因子？如果你记录所有单元测试的移动+计数器移动，它实际上是否计算到了预期的深度，或者你是否off-by-one，因为也许limit < depth应该是limit <= depth。 - Anton Codes

Answer 1

显然，您正在将value与b（beta）和a（alpha）进行比较。 您代码中的比较如下：

def maxValue(grid, a, b, depth):
    .....
    .....
        if value >= b:
            return value
        a = max(a, value)
    return value

和

def minValue(grid, a, b, depth):
    .....
    .....
        if value <= a:
            return value
        b = min(b, value)
    return value

然而，alpha-beta剪枝的条件是，每当alpha增长超过beta，即alpha>beta时，我们就不需要遍历搜索树。

因此，应该是：

def maxValue(grid, a, b, depth):
    ....
    .....
        a = max(a, value)
        if a > b:
            return value

    return value

和

def minValue(grid, a, b, depth):
    .....
    .....
        b = min(b, value)
        if b < a:
            return value

    return value

这是你所缺少的边缘情况，因为a(alpha)和b(beta)并不总是等于value。

- Achint Sharma