minimax算法理解
我很难理解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
回答 1
Stack Overflow用户
发布于 2020-06-12 03:44:37
你有一个递归函数，这是一个用(希望)不同的参数调用自己的函数。问题是:我们如何证明这样的函数会停止？一般的证明是通过归纳来证明的:设n是函数f的一个参数。如果你能证明这点：
f(0)是defined- recursive
0 <= k < n
中f(n)内的调用始终是f(k)类型
您可以通过归纳(强版本)证明，每个n >= 0都定义了f(n)。
在您的函数中，depth是n的一个很好的候选者。但len(empty_cells(state))也是。看看围绕递归调用的两个语句：
state[x][y] = player
...
state[x][y] = 0这是一种常见的技术:您在调用之前更新状态，并在调用之后恢复状态(假设:如果为state[x][y] == 0，则单元(x, y)为空)。因此，递归调用的空单元格数量低于当前的空单元格数量。
你可能会有一个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...
https://stackoverflow.com/questions/62319164
复制相似问题
腾讯云开发者
