0

我是人工智能的新手。我的任务要求我用 Python 编写一个程序，以最佳方式玩 Nim 游戏（使用NegaMax算法）。

如果您对游戏不熟悉，这里有一个简短的说明：

Nim 是一款简单的两人游戏。我们从一堆 n 匹配开始，其中n ≥ 3。

两个玩家，Max 和 Min，轮流从堆中移除 k 个匹配项，其中k = 1, k = 2, or k = 3。拿下最后一场比赛的玩家输了。

这是我已经写的：

def NegaMax(state, turn, bestmove): 
    max = -100000000000  
    if state == 1:
        if turn == 0:
            return (-1,bestmove)
        else:
            return (1,bestmove)       
    for move in range(1, 4):
        if state-move > 0:
            m = NegaMax(state-move, 1-turn, bestmove)
            m1 = -m[0]
            if m1 > max:
                max = m1
                bestmove = move
    return (max,bestmove)

def play_nim(state):
    turn = 0
    bestmove = 0
    while state != 1:
        [evaluation,move] = NegaMax(state, turn, bestmove)
        print(str(state) + ": " + ("MAX" if not turn else "MIN") + " takes " + str(move))
        state -= move
        turn = 1 - turn
    print("1: " + ("MAX" if not turn else "MIN") + " loses")

无论state我投入多少，Min 和 Max 总是在每一轮中进行 1 场比赛。

我认为问题在于评估是错误的，但我看不出我在哪里做错了。任何帮助，将不胜感激！谢谢！

4

1 回答 1

0

检查您的停止条件。

你需要 ：

if state == 1:
    return (-1,1)

然后一切顺利。

为了清楚起见，我还将更改函数签名，因为它只需要state：

def NegaMax(state):
    max = -100000000000
    if state == 1:
        return (-1,1)
    for move in range(1, 4):
        if state-move > 0:
            m = NegaMax(state-move)
            m1 = -m[0]
            if m1 > max:
                max = m1
                bestmove = move
    return (max,bestmove)

def play_nim(state):
    turn = 0
    while state != 1:
        [evaluation,move] = NegaMax(state)
        print(str(state) + ": " + ("MAX" if not turn else "MIN") + " takes " + str(move))
        state -= move
        turn = 1 - turn
    print("1: " + ("MAX" if not turn else "MIN") + " loses")

它发挥最佳。

您可以观察到最佳游戏下的结果，即 MAX 在状态 1+4k（1、5、9、13、17 等）下输，而在其他所有状态下都赢。

play_nim(5)
5: MAX takes 1
4: MIN takes 3
1: MAX loses

play_nim(11)
11: MAX takes 2
9: MIN takes 1
8: MAX takes 3
5: MIN takes 1
4: MAX takes 3
1: MIN loses
于 2019-05-14T11:14:06.417 回答