如何在递归函数中实现一个值？

Question

我尝试用 Python 编写 minimax nim 游戏。我几乎完成了代码。但是，我无法解决一个非常棘手的问题。我无法达到算法的 'best movement'。我从 (5, Max) 位置开始，算法输出应该是 (4, Min)。我的算法解决了具有效用值的整棵树，但无法 return 达到最佳运动。

def startposition():
    return 5, 'max'


def terminalstate(state):
    if state == (0, 'min') or state == (0, 'max'):
        return True
    else:
        return False


def minimax(state):
    turn,heap=state
    if terminalstate(state):
        return utilitystatic(state)
    else:
        if heap == 'min':
            value = 250
            for x in successorsgenerator(state):
                value = min(value, minimax(x))
            result = state, value
        elif heap == 'max':
            value = -250
            for x in successorsgenerator(state):
                value = max(value, minimax(x))
            result = state, value

        print(result)
    return value


def utilitystatic(state):
    turn, heap = state
    assert terminalstate(state)
    if state[1] == 'max':
        return -100
    elif state[1] == 'min':
        return 100
    assert False


def successorsgenerator(state):
    successors = []
    state = toggle(state)
    newstate = decrease(state)
    i = 0
    while newstate[0] >= 0 and i < 3:
        successors.append(newstate)
        i += 1
        newstate = decrease(newstate)
    print('successors:', successors)
    return successors


def toggle(state):
    state = list(state)
    state[1] = 'min' if state[1] == 'max' else 'max'
    state = tuple(state)
    return state


def decrease(state):
    state = state[:0] + (state[0] - 1,) + state[1:2]
    return state


stick = startposition()
result = minimax(stick)
print('result:', result)

Answer 1

在 minimax() 中，您目前只能找到后继状态的最佳值（最小值或最大值取决于玩家），但还不能准确记住每个深度级别的最佳后继状态。如果您不将该信息存储在内存中，您将无法判断哪一步是最好的。所以，你会想尝试这样的事情：

def minimax(state):
    turn,heap=state
    if terminalstate(state):
        return utilitystatic(state), _
    else:
        if heap == 'min':
            value = 250
            best_succ = None
            for x in successorsgenerator(state):
                val, _ = minimax(x)
                if val < value:
                    value = val
                    best_succ = x
            result = state, value
        elif heap == 'max':
            value = -250
            best_succ = None
            for x in successorsgenerator(state):
                val, _ = minimax(x)
                if val > value:
                    value = val
                    best_succ = x
            result = state, value

        print(result)
    return value, best_succ

经过一些小改动，我们现在将导致最佳值的继任者 x 存储在 best_succ 中，因此也能够准确判断哪个继任者是最好的（而不是只能说出它的价值）

Answer 2

如果您不想将整个移动序列存储在内存中（often/usually 不必要），只需从生成当前游戏状态的可能子项开始。不要运行极小化你当前的状态，只是找到可能的下一步。假设从您所在的位置（A、B、C）有 3 种可能的移动。现在运行 A 上的 minimax 算法并将结果与移动 A 的描述一起存储。对 B 和 C 重复。现在你应该有类似的东西：

A: 3.5
B: 1.2
C: -7.1

请记住，这些不是采取这些行动后立即产生的游戏状态的启发式值。从最大化玩家的角度来看，它们代表了当前玩家选择该着法后，其他玩家在未来可以迫使当前玩家获得的最小值。

在此示例中，着法 A 最适合最大化玩家，而着法 C 最适合最小化玩家。

如何在递归函数中实现一个值？

How to achieve a value in recursion function?

python

recursion

minimax

nim-game