algorithm - 移除子集的博弈算法 [HW/Study]

Question

我们遇到了一个问题，我将其简化为以下内容:给你一个全为 1 的二进制数(例如 11111)和一组相同长度的二进制数(00101、10000、01100、00100、11100)。有两个玩家 A 和 B。在每一轮，玩家可以从主二进制数 (11111) 中减去任何一个较小的数字，使得 2 的二进制与是较小的数字。然后下一个玩家可以从结果中减去，依此类推。不能再减去的玩家输了。例如。

   A         B       
 11111     11010   // Now A cannot subtract 
-00101    -10000   // anymore in the next turn. 
-------   ------   // So B wins the game.
 11010     01010
-------   ------

如果两个玩家都玩得最好(为他们的胜利做出最佳选择)，我必须找出给定二进制数组合的玩家获胜。

我已经尝试了 O(n^2) 方法，但是有没有更快的方法？

编辑:O(n^2) :其中 n 是状态数。对于长度为 6 (111111) 的二进制数，将有 2^6 种可能的状态。所以我的复杂度是 O((2^6)^2)。

编辑:我生成所有可能状态的代码:

void makeAllStates() /* Bottom Up Approach. Starting from 00000 and going to 11111 */
{
    // bool states[i] : True if state[i] is a winning position.
    // bool isWord[i] : True if the given state matches a smaller number. (eg. If the main number has been reduced to 10110 and there is a smaller number 10110, then isWord[i] is true.
    // bool visited[i] : True If the given state has been visited  
    // int statecount : Total number of states
    int temp;
    for(int xx=1;xx<stateCount;xx++)
    {
        for(int yy=1;yy<stateCount;yy++)
        {
            if(xx&yy)
                continue;
            if(!(isWord[xx] || isWord[yy]))
                continue;
            if(!visited[yy])
                continue;
            temp = xx^yy;
            if(isWord[temp])
                continue;
            if(states[temp])
                continue;
            if(isWord[xx] && isWord[yy])
                states[temp] = false;
            else
            {
                if(isWord[xx])
                    states[temp] = !states[yy];
                else
                    states[temp] = !states[xx];
            }
            visited[temp] = true;
            if(temp == stateCount-1 && states[temp])
            {
                return;
            }

        }
    }
}

Answer 1

我不知道它是否对你有帮助(你讲了 O(n^2) 方法，但没有说 N 是什么意思)。尝试公平博弈的通用方法(Sprague-Grundy 理论):

• 游戏中的位置就是你的主号
• 找到所有“松动”的位置(你不能再减去任何东西的位置)
• 对于所有“松散”位置 x :Grundy 函数 g(x) = 0;
• 然后，如果您想计算位置 y 的 grundy 函数:找到所有位置 x_1...x_k，这样您就可以从位置 y 转到位置 x_i。 g(y) = mex(g(x_1),...,g(x_k))。 “mex”是“最小排他性”——除 g(x_1),...,g(x_k) 之外的所有整数中的最小非负整数。例如，mex(2, 3, 4) = 0，mex(0, 1, 2, 5) = 3，mex(0, 1) = 2 等。

请注意，您可以递归地考虑每个游戏位置，并且您将考虑位置 x 一次(同时计算 g(x))，因此该算法是 线性的可能位置的数量。 线性的位置之间可能的转弯次数，即 O(N*K)，其中 N 是状态数，K 是较小数字集的大小(您可以在游戏中进行转弯)

如果 g(START_POSITION) = 0，则起始位置为失败位置，第一个玩家失败(每一轮都会导致获胜位置)。如果 g(START_POSITION) > 0 则起始位置为获胜位置(存在到位置 x 的转弯使得 g(x) = 0)，因此第一个玩家获胜。

抱歉英语不好，希望对您有所帮助