尼姆的游戏，极大极小

Question

有3桩(1桩-7火柴，2桩-5火柴，3桩-3火柴)你可以采取任何数目的火柴，但只有从一堆，谁采取了最后一场比赛失败。https://en.wikipedia.org/wiki/Nim

有一个代码可以生成所有可能的移动并将它们存储在字典中(“当前位置”：“可能的位置”)。

def get_moves(initialstate):
    memo = {}
    memo[initialstate] = [move for move in move_list(initialstate)]
    return memo

def move_list(state):
    for i in range(state[0]):
        yield (i, state[1], state[2])
    for i in range(state[1]):
        yield (state[0], i, state[2])
    for i in range(state[2]):
        yield (state[0], state[1], i)

print(get_moves((7,5,3)))

如何将这本字典转换成一棵树，以及如何实现最小值？

我想要这样的东西：

function  minimax(node, depth, maximizingPlayer) is
    if depth = 0 or node is a terminal node then
        return the heuristic value of node
    if maximizingPlayer then
        value := −∞
        for each child of node do
            value := max(value, minimax(child, depth − 1, FALSE))
        return value
    else (* minimizing player *)
        value := +∞
        for each child of node do
            value := min(value, minimax(child, depth − 1, TRUE))
        return value

我改变了启发式的功能，但是电脑还是选择了错误的动作，为什么？从状态0,1,3有获胜状态0,1,0，为什么计算机不选择此选项？

def minimax(position, depth, max_player):
    print(position, evaluate(position))
    if depth == 0:
        return evaluate(position), position
    
    if max_player:
        maxEval = float('-inf')
        best_move = None
        for move in get_moves(position):
            evaluation = minimax(move, depth-1, False)[0]
            maxEval = max(maxEval, evaluation)
            if maxEval == evaluation:
                best_move = move
        
        return maxEval, best_move
    else:
        minEval = float('inf')
        best_move = None
        for move in get_moves(position):
            evaluation = minimax(move, depth-1, True)[0]
            minEval = min(minEval, evaluation)
            if minEval == evaluation:
                best_move = move
        
        return minEval, best_move

def evaluate(position):
    if position == (0,0,0):
        return -100
    if position == (0,0,1) or position == (1,0,0) or position == (0,1,0):
        return 100
    return 1 if (position[0] ^ position[1] ^ position[2]) == 0 else 0

def get_moves(initialstate):
    memo = [move for move in move_list(initialstate)]
    return memo

def move_list(state):
    for i in range(state[0]):
        yield (i, state[1], state[2])
    for i in range(state[1]):
        yield (state[0], i, state[2])
    for i in range(state[2]):
        yield (state[0], state[1], i)
        
print(list(minimax((0,1,3),12,True)[1]))

Answer 1

这与任何其他的minimax实现没有什么不同，例如对于抽搐脚趾。对于每一个回合，你都会经历所有可能的移动(从任何一堆中抽出一根棍子)，并查看相应的游戏状态(赢/输/平局)。在这种情况下，平局是在所有的堆中还剩下棍子，赢的是对手在一堆中抽最后一根棍子，而输的是你在一堆里画最后一根棍子。

你不需要把它储存在一个白痴里。你可以有一个通用的“棋盘”，它可以保存当前的游戏状态(在每一堆中坚持)。然后，在每次极小极大迭代中，从当前的板状态得到所有可能的移动(例如，get_possible_moves(板))。

Answer 2

以下几个问题：

• 当没有可能的移动时(即当状态为minimax )时，None函数将返回作为值的None。相反，在这种情况下应该运行evaluate函数，就像运行depth == 0时一样。
• 当您使用最大化和最小化玩家的概念时，基本情况是不正确的：return -100表示这是最小化玩家的胜利，而实际上取决于是谁做了最后一步。下一个return 100也是如此。 因此，我建议不要使用最大化/最小化玩家的概念，而是将双方都视为最大化，并切换返回值的符号。
• 在XOR部分中，我将返回-1而不是0，因此它实际上是相反的值1。
• 由于尼姆游戏的这种味道是"misère“版本(见维基百科)，因此大小写应该包括最大的一堆大小为1的任何情况。因此，不仅是(1,0,0)，而且还有(1, 1, 1)和(1, 0, 1) .等。

以下是一项更正：

def minimax(position, depth):
    val = evaluate(position)
    # Use heuristic when depth is reached OR when no more moves possible
    if depth == 0 or val == -100:  
        return -val, None  # No move associated with this value
    
    maxEval = -1000
    best_move = None
    for move in get_moves(position):
        # Negate returned value to make it relevant for current player
        evaluation = -minimax(move, depth-1)[0]
        maxEval = max(maxEval, evaluation)
        if maxEval == evaluation:
            best_move = move
    return maxEval, best_move

def evaluate(position):
    # Evaluate the board in the view of 
    #     the player that last moved
    if max(position) <= 1:  # Largest pile size is at most 1?
        # Must leave odd number of non-empty piles to win
        return 100 if sum(position) % 2 else -100
    # Must leave a XOR sum of zero. Use 1 or -1.
    return 1 if (position[0] ^ position[1] ^ position[2]) == 0 else -1

最后，由于这种“启发式”不是真正的启发式，而是对状态的完美评估，我在这里看不到使用minimax，因为在深度为1的情况下，最佳移动将被找到。通过更高的depth值不会导致更好的移动。如果您想让玩家在放松位置时做出最有希望的动作，那么您需要添加一个真正的启发式，它表达了“最有希望”的确切含义；比如：

• “选择另一名球员有最少的机会进行获胜移动的移动”，或
• “选择尽可能拖延损失的移动”，或
• “选择一个能最大限度地增加非空堆数量的动作”(理由是，当一个人的非空堆较少时，这个游戏更容易正确地玩)。