了解minimax算法

Question

我很难理解minimax算法的递归部分。

def minimax(state, depth, player):
    if player == MAX:
        best = [-1, -1, -infinity]
    else:
        best = [-1, -1, +infinity]

    if depth == 0 or game_over(state):
        score = evaluate(state)
        return [-1, -1, score]

    for cell in empty_cells(state):
        x, y = cell[0], cell[1]
        state[x][y] = player
        score = minimax(state, depth - 1, -player)
        state[x][y] = 0
        score[0], score[1] = x, y

        if player == MAX:
            if score[2] > best[2]:
                best = score
        else:
            if score[2] < best[2]:
                best = score

    return best

例如此代码。当函数在循环内调用自身时，循环会继续进行到state[x][y] = 0？什么弯腰的功能？或函数的递归部分会执行哪些操作？tnx

Answer 1

您具有递归函数，该函数使用（希望）不同的参数进行调用。问题是：我们如何证明这种功能曾经停止过？通用证明是归纳证明：让n是函数f的自变量。如果可以显示：

• f(0)被定义
• f(n)内部的递归调用始终为f(k)类型，其中0 <= k < n

您有一个归纳证明（强版本），每个f(n)都定义了n >= 0。

在您的职能中，depth是n的理想人选。但是len(empty_cells(state))也是。查看围绕递归调用的两个语句：

state[x][y] = player
...
state[x][y] = 0

这是一种常见的技术：您在调用之前更新状态，并在调用之后恢复状态（假设：如果(x, y)，则单元格state[x][y] == 0为空）。因此，递归调用的空单元格数小于当前的空单元格数。

并且您可能处于game_over状态。

[没有其他信息，无法说出什么将停止递归调用：depth到达0，存在game_over或没有空单元格。

[请注意，depth开头可能是负数，game_over可能永远不会出现，但是可以确定，当空单元格的数量为0时，该函数将停止（如果之前没有停止）。] >

---

我认为您很难理解这段代码，因为score变量有时是一个数字，有时是一个3个元素的列表（在这种情况下，可能应该是一个元组）。此外，停止条件可以在函数的开头。

此版本应该更清晰，因为它隐藏了由+/-player引起的行为变化：

def minimax(state, depth, player):
    if depth == 0 or game_over(state):
        score = evaluate(state)
        return [-1, -1, score]

    best = [-1, -1, initial_score(player)]
    for x, y in empty_cells(state):
        state[x][y] = player # fill this cell
        _, _, score = minimax(state, depth - 1, -player) # extract the score
        cur = [x, y, score]
        state[x][y] = 0 # restore state

        if is_better(player, cur, best):
            best = cur

    return best

def initial_score(player):
    if player == MAX:
        return -infinity
    else 
        return +infinity

def is_better(player, first, second):
    if player == MAX:
        return first[2] > second[2]
    else:
        return first[2] < second[2]
可以重写很多，但我们不是https://codereview.stackexchange.com ...