Nim游戏问题

Question

好的，我必须制作一个nim游戏，并尝试找到在以下nim游戏中始终获胜的策略：

21场比赛，玩家1和2每回合进行1、2、3、4或5场比赛，并且不能与前一名玩家进行相同数量的比赛。如果/当他们参加最后一场比赛时，这个玩家就赢了。

我必须为此编写一些程序，但我甚至不知道该如何开始。如何找到这种类型的nim游戏的制胜策略？

编辑：

所以我想当你有7场比赛还在中间的时候你总是会赢的。另一个可以取2-5，最后一个可以加到7。当另一个取1时，你取3(另一个不能取3)，并且必须选择1或2，在这种情况下，你将得到最后一个并且也赢了。

然而，从21岁到7岁对我来说是一个难题，我不明白为什么你总是那个到7岁的人。

编辑2:好的，如果没有你不能和之前的玩家一样的规则，我想这很简单。

你可以使k=5+1= 6。然后你应该进行第一步，这样匹配就会离开，然后%6= 0。所以在这种情况下，先取3，然后将其他玩家的步数加到6，但是，在这种情况下，这是行不通的，因为其他玩家可以取3，之后你不能将3加到6，这就是我的问题。有什么想法吗？

EDIT3：

好的，所以你说我可以强制7个匹配。然而，假设我对14-7匹配步骤采取同样的想法。(然后轮到另一个人)

然后有两种情况: 1:他拿了2-5，我把它填满了7，让7在那里，我赢了。2:他拿了1个，所以还剩下13个。当我拿到3分，就像我在(7-0)-step中做的那样，它变成了10分，然后他拿了5分，我不能再拿5分了，我就输了。

这就是问题所在，场景2在现在的(7-0)-step中是没有问题的。我该如何解决这个问题？

是的，解决方案是：

顺便说一句，na拼写器1的意思是:在玩家1轮到之后等(我是荷兰人)。

​

​

好的，我尝试了一些方法，我想我有解决方案了。你必须先作为第一个玩家参加一场比赛。然后其他人可以拿到2-5场比赛。你匹配(双关语)他的金额到7，所以你将有(21-1-7=) 13个匹配总是在中间。然后又轮到2号玩家了，有两种情况:2号玩家1,2,4场比赛，or5比赛，在这种情况下，左边有7场比赛。(正如前面所说的，当你只剩下7场比赛时，你总是会赢)。第二种情况是，玩家2需要3场比赛，在这种情况下，当轮到你时，中间有10场比赛。你不能取3等于7，因为你不能取相同数量的2倍。所以你拿了5个，剩下5个。然后玩家2不能拿5来赢，而必须选择1-4，然后你可以拿剩下的来赢。

我想这就是解决方案。不知何故，我找到了它，因为我注意到了：

具有模数等的普通Nim游戏：

P2  1  2  3  4  5  
P1  5  4  3  2  1  
------------------
    6  6  6  6  6 

但你不能在这里做3,3，所以它就像这样：

p2 1  2  3  4  5 
p1    5  4  3  2  1
---------------------
      7  7  7  7 

所以你每次都可以做7，1是一个特例。我不知道为什么，但我直觉上把1作为起点，因为感觉你需要采取主动才能控制对方的移动。(一个人不能做两次乘以1，所以另一个人必须做2-5，这使你处于控制之中)

无论如何，非常感谢你的帮助。对于整个编写的程序也是如此。我不能使用它，因为它不能编译为缺乏良好的java技能:)，我也想自己解决它。

无论如何，我看到这是一个维基，祝未来试图解决这个问题的人好运！

Answer 1

使用Minimax algorithm，如果您需要减少运行时间，可以使用alpha-beta修剪。

从本质上讲，您可以详尽地搜索可能的移动树，然后向上工作以确定最佳结果。

编辑：这里有一些代码向您展示了创建一个完美的代理是多么容易。编写代码花了大约5分钟。

public class MinimaxNim {

    public static int getBestMove(int matchesLeft, int lastVal) {
        int max = Integer.MIN_VALUE;
        int bestMove = matchesLeft > 0 ? 1 : 0;
        for ( int move = 1; move <= 5 && move <= matchesLeft; move++ ) {
            if ( move == lastVal )
                continue;
            int val = minValue(matchesLeft - move, move);
            if ( val > max ) {
                bestMove = move;
                max = val;
            }
        }
        return bestMove;
    }

    private static int maxValue(int matchesLeft, int lastVal) {
        if ( matchesLeft == 0 ) 
            return -1; //min has won

        int max = Integer.MIN_VALUE;
        for ( int toTake = 1; toTake <= 5 && toTake <= matchesLeft; toTake++) {
            if ( toTake == lastVal ) 
                continue;
            int val = minValue(matchesLeft - toTake, toTake);
            if ( val > max ) {
                max = val;
            }
        }
        return max;
    }

    private static int minValue(int matchesLeft, int lastVal) {
        if ( matchesLeft == 0 ) 
            return 1; //max has won

        int min = Integer.MAX_VALUE;
        for ( int toTake = 1; toTake <= 5 && toTake <= matchesLeft; toTake++) {
            if ( toTake == lastVal ) 
                continue;
            int val = maxValue(matchesLeft - toTake, toTake);
            if ( val < min ) {
                min = val;
            }
        }
        return min;
    }
}

您可以使用以下命令进行测试：

public static void main(String[] args) {
    int count = 21;
    int move = -1;
    for ( ;; ) {
        move = getBestMove(count, move);
        System.out.println("Player 1 takes " + move);
        count -= move;
        if ( count == 0 ) {
            System.out.println("Player 1 has won");
            break;
        }
        move = getBestMove(count, move);
        System.out.println("Player 2 takes " + move);
        count -= move;
        if ( count == 0 ) {
            System.out.println("Player 2 has won");
            break;
        }
    }
}

但是我建议将玩家1或玩家2替换为你自己，或者一个随机的代理，这样你就可以检查一个完美的玩家所做的动作。

再说一次，这不会向你展示最好的策略，但它将展示对任何对手的最佳发挥(尽管未经测试)。

编辑2

如果你很好奇，从初始状态开始，只有26705个终端状态(玩家赢了)需要检查。随着你的动作越来越多，这一点会越来越少。最小极大的完美之处在于，进度总是made...once，你不能回到17，例如在国际象棋这样的游戏中，你可以在搜索树中得到循环，因为玩家可以在棋盘周围跳舞，返回到以前的状态，等等。

Answer 2

正如要考虑的更多数据一样，我将我的代理运行在游戏中可能出现的每一个可能的场景中(1-21根棍子乘以5个可能的最后一步)。其中一些状态是不可能的(例如，20，最后一步是2)。我从表中删除了其中的大部分，但更可能的是留了下来。

如果这种组合有价值，这意味着在这一点上玩那个动作肯定会导致胜利(假设继续完美的游戏)。

那些标有x的人表示，处于这种状态肯定会导致失败，而不管移动(假设对手的完美发挥)。

   0 1 2 3 4 5
21 1           
20   x         
19     3       
18   5 5 5     
17   4   4 5   
16   3 3 x 3 3 
15   2 1 1 1 1 
14   x 1 1 1 1 
13   x x x x x 
12   5 5 5 5 x 
11   4 4 4 x 4 
10   3 3 5 3 3 
 9   2 3 2 2 2 
 8   4 1 1 1 1 
 7   x x x x x 
 6   3 3 x 3 3 
 5   5 5 5 5 x 
 4   4 4 4 x 4 
 3   3 3 x 3 3 
 2   2 1 1 1 1 
 1   x 1 1 1 1 

所以如果你一直在做分析，你可以在这个表中查找在特定状态下的最佳移动是什么(或者，如果有多个最佳移动)。

到目前为止，有一件事与你的分析完全一致:如果是你的行动，还剩7根棍子，你就完蛋了！但也请注意13。