深入理解 Nim 博弈

定义P-position和N-position,其中P代表Previous,N代表Next。直观的说,上一次move的人有必胜策略的局面是P-position,也就是“后手可保证必胜”或者“先手必败”,现在轮到move的人有必胜策略的局面是N-position,也就是“先手可保证必胜”。更严谨的定义是:1.无法进行任何移动的局面(也就是terminal position)是P-position;2.可以移动到P-position的局面是N-position;3.所有移动都导致N-position的局面是P-position。

注意:对于游戏的任何一种可能的局面,合法的移动集合只取决于这个局面本身,不取决于轮到哪名选手操作、以前的任何操作、骰子的点数或者其它什么因素; 

归纳为3点: 

1) terminal position(终态)为P_position. (先手输)

2)N_Position (先手赢)---存在某个移动----->P_Position(当前局势的先手输)

3)P_Position(先手输)-----任何移动----->N_Position(当前局势的先手赢)。

当只有两堆石子且两堆石子数量相等时后手有必胜策略,也就是这是一个P-position。我们可以用定义证明:

(2,2)局面是一个 P_Position.

(2,2) ---可以移动的子局面-->(1,2),(0,2)

(1,2) ----可以移动--->(1,1)---唯一移动--->(1,0)---唯一移动--->(0,0)

     N_position<--可以--- P_position < --任意 ------  N_ position  <--- 因为(0.0)是P_position

(0,2) ---可以移动-->(0,0)

N_position<---可以--P_position

因此, 由于(2,2)的子局面(1,2),(0,2)都是N_position,  故(2,2)是 P_position。

由归纳法 , 同理可得出, 当两堆有相同石子 的 堆, 该局面为P_position.(即先手输)。

上面是引子,引出下面的定理(Bouton's Theorem):对于一个Nim游戏的局面(a1,a2,...,an),它是P-position当且仅当a1^a2^...^an=0,其中^表示异或(xor)运算。

申明:

根据定义,证明一种判断position 性质方法的正确性,只需证明下面三个命题。

1)这个 判断  一定是将所有的terminal position判断为 P_Position.

2) 根据这个 判断  被判为 N_position的局面   一定     可以移动    到某个 P_Position.

3)根据这个 判断  被判为 P_position 的局面   无法移动    到 某个 P_position.

证明:  bouton's Theorem ,  中 的判断是      如果a1^a2^...^an=0   ,则(a1,a2,...,an) 是 P_position

第一个命题:  显然成立。 terminal  只有一个 就是 (0,0,……,0) , 根据判断 a1^a2^...^an===0,  是P_position.

第二个命题:  如果 对于某个局面(a1,a2,...,an) 是 N_position,  则 a1^a2^...^an   !=  0,    一定 存在某个 合法的移动,将 ai 改变成ai' 后使得 a1^a2^...^ai'^...^an=0.

不妨设  a1^a2^...^an = k,  则 一定存在某个 ai  它的二进制表示在k的最高位上是1(否则k的最高位那个1是怎么得到的)。 这时令  ai' = ai^k   < ai(满足取石头要求)   。

 则 移动后的局面 是  (a1,a2,  ....ai',...,an), 有a1^a2^...^ai'^...^an = a1^a2^...^ai^...^an^k = 0,  为 P_position。命题得证。

第三个命题:  对于某个局面(a1,a2,...,an) 是 P_position,  则 a1^a2^...^an   =  0。  假设可以通过合法的移动, 将 ai 改变成ai' 后 使得a1^a2^...^ai'^...^an   =  0

因为 异或满足 消除律, 则有 ai = ai',  这不满足至少取一个石子,不是合法移动,  故 被判为 P_position 的局面 无法移动到 某个 P_position.

证毕。

原文地址:https://www.cnblogs.com/zn505119020/p/3611642.html