Game

Posted on | Edited on | In | Views:

Game

只要找到一个子局面是P-position(先手必败)就能说明是N-position(后手必败)，反之为P-position。

SG函数(Sprague-Grund)

mex(minimal excludant)是定义在整数集合上的操作。它的自变量是任意整数集合，函数值是不属于该集合的最小自然数。

终止状态的SG值显然为0，并且SG值为0的状态就是P状态，SG值不为0的状态就是N状态.

Nim Game

有n堆石子，石子数目=分别为$a_1,a_2,a_3 · · · a_n$，A，B两人每次可以选一堆石子取走任意多个

P-position: $a_1\wedge a_2\wedge · · · \wedge a_n=0$

Wythoff’s Game

两堆石子，个数为$x_1,x_2$; A，B轮流取石子，规定要么只取一堆的任意多个，要么在两堆里取同样任意多个

P-position: (0,0)(1,2)(3,5)(4,7)

  • $a_k$是未在之前出现过的最小自然数
  • $b_k=a_k+k$
  • 由Beatty定理可得: $\frac 1\alpha+\frac 1 {\alpha+1}=1,\alpha=\frac {1+\sqrt5}2$

Beatty数列和Beatty定理

取正无理数α,β，使得$\frac 1\alpha+\frac 1 \beta=1$

构造两个数列a,b,它们的通项为$a_n=⌊αn⌋,b_n=⌊βn⌋$

那么这个数列显然是正整数序列，Beatty定理指出，两个数列都是严格递增的，并且每个正整数在两个数列中只出现一次

Fibonacci Nim

有一堆个数为n的石子，A，B轮流取石子，满足：

  • 先手不能在第一次把所有的石子取完；
  • 之后每次可以取的石子数介于1到对手刚取的石子数的2倍之间 (包含1和对手刚取的石子数的2倍)

P-position: 1,2,3,5,8,13,21,34,55,89,…(Fibonacci)

Zeckendorf定理

任何正整数可以表示为若干个不连续的Fibonacci数之和。

Staircase Nim

n堆石子，每堆石子的数量为$x_1,x_2,….x_n$，A，B轮流操作，每次可以选第k堆中的任意多个石子放到第k-1堆中，第1堆中的石子可以放到第0堆中.

P-position: $x_1 \wedge x_3\wedge x_5…\wedge x_{2*n+1}=0$

Anti Nim

有n堆石子，A，B两人每次可以选一堆石子取走任意多个,取到最后一个石子的人为输.

N-position: 所有堆石子数都为1且SG值为0 ; 至少有一堆石子数大于1且SG值不为0

Nim变形

两个人在一个1*N的格子内挪动棋子，刚开始在若干个位置上有若干个棋子，每一个选手可以进行的操作时选择一个棋子并把它向左方移动，当然不能越过其它的棋子，也不能超出边界。

按位置升序排列后，从后往前把他们两两绑定成一对。如果总个数是奇数，就把最前面一个和边界（位置为0）绑定。对手移动左,你移动相同步数;对手移动右,表示取相应的石子.

K倍动态减法

  • K=1 P-position: 2^k 先手的策略是取lowbit(n)

  • K=2 P-position: Fibonacci Nim

  • K>2 (K=1或K=2也可以用次方法构造)仿照斐波那契博弈的构造方法构造一个数列an b[]作为辅助数组表示前i个的a能够按规则构造出的最大的数

    1
    2
    3
    4
    a[i+1]=b[i]+1;
    //寻找最大的 t 使得 a[t] * K < a[i+1];
    b[i+1] = b[t] + a[i+1];
    P-position: a[]