Google的“+-游戏”最优策略下的O(N^2) DP解法

原题：


给定一个仅由+和-组成的字符串，如“++++-----+++++-----++-+”，两名玩家轮流地将“相邻的两个++flip为--”，直至轮到一方时，如果他不能继续flip，则这名玩家输。问对于给定的字符串，如何判断（在双方都使用最优策略的情况下）先手玩家是否一定能赢？


此题的面经请点这里。


------------------------------


这种解法需要了解博弈论的知识，一般面试应该是不做要求的。只是放在这里供大家参考：

首先，这种游戏属于“无偏博弈”(impartial game)，意思是：“棋盘”上的棋子，即"+"号，双方都可以公平地使用；而且胜利的最终判定方法对二者来说是一样的。而象棋就不是无偏博弈，因为双方各有不同的棋子和胜利条件。其次这种游戏的终结条件是“正常终结条件”的，即最后无法move的那个人输。与之相对的还有一种叫做“misere终结条件”，即无法move的人赢。

以下将要谈到的所有定理和推理过程，都是仅适用于“无偏博弈”和“正常终结条件”的情况。

------------------------------

因为我们只能把连着的两个+号变为-号，所以对我们来说，“棋盘”状态可以由一组“连续的+的个数来表示”，比如“+++----+-++----++++”可以表示为(3, 1, 2, 4)。 因为其中那个单独的+号对结果没有影响，而且3和2出现的顺序也无关紧要，所以我们扔掉“1”，然后将这个序列排序，即得较简的表达方式：(2,3,4)。

所以，这个游戏其实就是从某个初始状态开始，不断进入下一个状态，直至无法改变状态为止。如果以每一个可能的状态做为一个节点，那么整个游戏中能出现的所有状态和这些状态直接的转移方式共同构成了一个有向无环图。之所以无环，是因为我们没法将-号变回+号，所以我们永远不可能回到之前的状态。

比如，从状态(2, 3, 4)开始，我们能进入的可能状态是
(2-2, 3, 4) => (3,4)
(2, 3-1, 4) => (2,4)
(2, 3, 4-2) => (2,2,3)
(2, 3, 2, 2) => (2,2,2,3)

由于游戏结束时序列中必然没有连续的两个+号，所以按照我们的简化记法，此时的状态为().

接下来是两个重要概念，第一是Sprague-Grundy（SG）函数g(x)，其中x是“游戏图”中的一个节点（状态），如果我们用{y1, y2, ..., yn}表示x的所有子节点（即下一步状态）。那么SG函数的定义是：

g(x) = FirstMissingNumber(g(y1), g(y2), ... g(y3))

这是个递归定义的函数。如果x没有子节点，那么定义g(x) = 0；如果x有n个子节点，比如有3个子节点，g值分别为{0,1,3}，那么g(x)的值是这个列表中第一个没有出现的>=0的值，此时g(x) = 2。

为什么需要引入这样一个函数？此处给出一个定理，各位暂时承认他即可：

------------

定理1：如果一个节点x的g(x)=0，那么x状态一定是“先手必输”的状态；否则一定是“先手必赢”。

------------

因此，我们如果能递归算出g(字符串初始状态)的值，那么我们就可以立即判断输赢。


但是，递归计算这个式子会比较繁琐。因为，一个连续序列经常会被分割成两个不连续的序列，这样递归计算的复杂度会比较高。所以我们引入第二个定理，即著名的Sprague-Grundy定理：

------------

定理2：如果一个游戏G由许多相同规则的子游戏G1,G2,..., Gk组成，那么对于游戏G的一个状态x = {x1,x2,...,xn}，SG函数g(x) = g(x1) ^ g(x2) ^ ... ^ g(xn)。其中^表示“异或”。

------------

在我们这个游戏里，多个不相邻的+++子序列，就可以看做多个子游戏。所以，我们就可以用DP来代替递归了，比如当前状态为(10)，它的后继状态可能是(8), (7), (2,6), (3,5), (4,4)。这里，我们就没有必要再次递归去算(2,6), (3,5)和(4,4)，因为根据SG定理, g((2,6)) = g(2) ^ g(6), g((3,5)) = g(3) ^ g(5) ....一般地，对于各种可能状态，我们有如下的计算公式：

g(0) = 0;        // 一个+都没有，先手必输

g(1) = 0;        // 只有一个+，先手必输

g(2) = FirstMissingNumber(g(0)) = 1     // 两个+，先手必赢

g(3) = FirstMissingNumber(g(1))        = 1            // 先手必赢

g(4) = FMN(g(2), g(1) XOR g(1)) = 2    // 两种情况：A 1111->0011 OR 1100，也就是状态2，B 1111-> 1001  

...

g(9) = FMN(g(0)^g(7), g(1)^g(6), g(2)^g(5), g(3)^(4)).

...

g(x) = FMN(g(0)^g(x-2), g(1)^g(x-3), g(2)^g(x-4), ... g(x/2)^g(x/2)).

因为计算每一个g(x)都要进行x/2次异或，且FirstMissingNumber也是一个O(x)的操作，所以计算g(1)~g(x)共需要O(x^2)时间。在长为N的“棋盘”上，最大的连续+串的长也为N，所以最差时间复杂度是O(N^2)。需要额外空间保存[0, 1,2,3,4,5...N]状态下的g值，因此空间复杂度是O(N)。

另外，如果最初的状态不是一个连续的+号序列，而是几个不连续的+号序列，比如x = (2,3,8)。 那么我们只要分别算x1 = (2), x2 = (3), x3 = (8)三种情况的g值，然后三者取异或即可，对时间空间复杂度没有影响。

-----------------------------------
补充下这个问题的SG函数的图。这看起来是个分形，说不定利用这个性质，能得到更优的解法：

PS：这题要是有人能在不知道SG定理的情况下现场给出多项式时间的解法，绝对是神……

本文由stellari首发于1point3acres.com论坛，图文均为原创，转载请注明。

UmassJin 发表于 2015-7-14 01:00
感谢楼主分享！ 请教楼主，定理一里面说 “如果一个节点x的g(x)=0，那么x状态一定是“先手必输”的状态；否 ...

是的，大部分局面都是有可能赢，也有可能输的。但是咱们这里讨论问题的前提都是指“在最优策略下”。所以“先手必赢”的意思是：在双方都采用最优策略的情况下，先手必赢。换句话说：只要先手想赢，先手就一定能赢，不管对手有多么聪明。

抱歉，我的博弈论知识仅限于原帖中提到的那些。minmax我并不了解，容我再补习一下。

感谢楼主分享！ 请教楼主，定理一里面说 “如果一个节点x的g(x)=0，那么x状态一定是“先手必输”的状态；否则一定是“先手必赢”。”  可是对于这个情况，先手有可能赢（如果是1111->0110）也有可能输(1111->0011)，“g(4) = FMN(g(2), g(1) XOR g(1)) = 2    // 两种情况：A 1111->0011 OR 1100，也就是状态2，B 1111-> 1001” ，但是g(4)=2，这里一定表示先手必赢的状态吗？ 另外这个算法和minmax那些算法有什么不同的地方呢？

膜拜，楼主太神啦。
从状态(2, 3, 4)开始，我们能进入的可能状态是  // 挑出其中一个数减去2，如果结果小于2，删除
(2-2, 3, 4) => (3,4)
(2, 3-1, 4) => (2,4)
(2, 3, 4-2) => (2,2,3)
(2, 3, 2, 2) => (2,2,2,3)
为什么 (2, 3, 2, 2) => (2,2,2,3) 这个可以，不是至少要flip不？why 可以一把4 拆成两个2呢？
(2, 3-1, 4) => (2,4) 这个楼主是不是笔误，应该为 (2, 3-2, 4) => (2,4) 呢？
还是我的理解有误？

....code呢.....

象棋就不是无偏博弈，因为双方各有不同的棋子和胜利条件 <---这个有歧义, 应该说是因为双方各执颜色不同的子

膜拜大神 顺便八卦下可是LC上的stellari?

glaciersilent 发表于 2015-7-13 13:11
膜拜大神 顺便八卦下可是LC上的stellari?

见笑见笑，大神绝不敢称，但确实是LC上的同名人士。

楼主，求交流！！带我飞！

楼主牛逼

stellari 发表于 2015-7-14 08:03
是的，大部分局面都是有可能赢，也有可能输的。但是咱们这里讨论问题的前提都是指“在最优策略下”。所以 ...

好的，多谢楼主详细解答！一直都特别纠结于游戏design或者是algorithm之类的问题，再细细研读一下。