我解决 Misere Nim 游戏的缺陷在哪里

Question

游戏是你有 N 堆石子，在每个玩家的回合中，他必须从一堆石子中至少移除 1 颗石子，移除最后一颗石子的玩家输。

我从基本案例开始，在十几个案例中写出了获胜者

/*
    stones             | winner  | N | ones 
    ========================================
    {1}                | Second  | 1 |  1   
    {i}, i>1           | First   | 1 |  0
    {1,1}              | First   | 2 |  2
    {1,i}, i>1         | First   | 2 |  1
    {i,j}, i,j>1       | Second  | 2 |  0
    {1,1,1}            | Second  | 3 |  3
    {1,1,i}, i>1       | First   | 3 |  2
    {1,i,j}, i,j>1     | First   | 3 |  1
    {i,j,k}, i,j,k>1   | First   | 3 |  0
    {1,1,1,1}          | First   | 4 |  4
    {1,1,1,i}          | First   | 4 |  3
    {1,1,i,j}, i,j>1   | Second  | 4 |  2
    {1,i,j,k}, i,j,k>1 | First   | 4 |  1
    {i,j,k,m}, ...     | Second  | 4 |  0
*/

从中我想我推导出了一个公式

static string GetWinner(int[] piles)
{
    int n = piles.Length, m = piles.Count(stones => stones == 1);
    if(m == n) // one stone per pile
        return n % 2 == 0 ? "First" : "Second";
    // if here, m < n
    return n % 2 == 0 ? (m % 2 == 0 ? "Second" : "First") : "First";
}

但这未通过测试用例 {2,1,3}，应该导致 "Second".

我尝试使用以下事实。

堆中任何数量大于 2 的石子都会得到与 2 相同的结果。原因是因为如果它大于 2 并且玩家在那个回合没有将牌堆缩减到 1 那么玩家基本上已经把回合交给了他的对手。

但是，我可能有一些错误..

Answer 1

我认为你的以下说法是错误的：

Any number of stones in a pile that is greater than 2 would give the same results if it were 2

如果状态为{1,2,2}，先手拿掉1颗棋子即可获胜。如果状态为 {1,2,3}，则第一个玩家无法获胜。所以石头的数量是2还是3是有区别的。

because if it's greater than 2 and the player doesn't shrink the pile to 1 on that turn then the player has basically give his opponent the turn.

这是正确的，除了有时 'desirable' 将回合交给其他玩家，即让出回合。

最佳策略与二进制表示中每堆中项目数的异或有关。有关最佳解决方案和详细信息，请参阅 https://en.wikipedia.org/wiki/Nim。

Answer 2

我无法深入理解答案背后的数学原理，但经过一些研究和优化，这是我为 python3 想出的解决方案：


from functools import reduce

def misereNim(s):
    if(max(s)==1):
        return "First" if (len(s) % 2 ==0) else "Second"
    else:
        xor = reduce((lambda x, y: x ^ y), s)
        return "Second" if xor == 0 else "First"

if __name__ == '__main__':

    s = [9, 8, 4, 4, 4, 7]

    result = misereNim(s)
    print(result)

我解决 Misere Nim 游戏的缺陷在哪里

Where is my flaw in solving the Misere Nim game

c#

algorithm

game-theory