三大博弈游戏

参考:ACM BOOK

巴什博弈

问题

只有一堆n个物品,两个人轮流从这堆物品中取物, 规定每次至少取一个,最多取m个。最后取光者得胜。

分析

  1. 如果 n=m+1 ,那么由于一次最多只能取 m 个,所以,无论先手拿走多少个,后手都能够一次拿走剩余的物品,后者取胜。
  2. 如果 n=(m+1)∗r+s ,(r为任意自然数, s≤m ),先手要拿走s个物品,如果后手拿走 k(k≤m) 个,那么先手再拿走 m+1−k 个,结果剩下 (m+1)∗(r−1) 个,以后保持这样的取法,那么先取者肯定获胜。我们得到如下结论:要保持给对手留下 (m+1) 的倍数,就能最后获胜。

拓展

如果我们规定最后取光者输,那么又会如何呢?

(n−1) % (m+1)==0 则后手胜利 先手会重新决定策略,所以不是简单的相反的。

例如 n=15,m=3

后手 先手 剩余
0 2 13
1 3 9
2 2 5
3 1 1
1 0 0

先手胜利 输的人最后必定只抓走一个,如果>1个,则必定会留一个给对手

威佐夫博弈

问题

有两堆各若干个物品,两个人轮流从某一堆或同时从两堆中取同样多的物品,规定每次至少取一个,多者不限,最后取光者得胜。

分析

我们用$(a_k,b_k)$,$(a_k≤b_k,k=0,1,2,…,n)$表示两堆物品的数量并称其为局势,如果甲面对 (0,0) ,那么甲已经输了,这种局势我们称为奇异局势。前几个奇异局势是: (0,0) 、 (1,2) 、 (3,5) 、 (4,7) 、 (6,10) 、 (8,13) 、 (9,15) 、 (11,18) 、 (12,20) 。 可以看出: $a_0=b_0=0$ , $a_k$ 是未在前面出现过的最小自然数,而$b_k=a_k+k$ 。

满足$a_k=k\times (1+\sqrt 5)/2,b_k=a_k+k$后手必胜,否则先手必胜。

Nim博弈

问题

有若干堆石子,每堆石子的数量都是有限的,合法的移动是“选择一堆石子并拿走若干颗(不能不拿)”,如果轮到某个人时所有的石子堆都已经被拿空了,则判负(因为他此刻没有任何合法的移动)。

分析

假设n堆石子,每堆石子的数量为$a_i$

若$a_1\bigoplus a_2…\bigoplus a_n = 0$ 则先手必败

证明: 若$a_1\bigoplus a_2…\bigoplus a_n \neq 0$ 那么一定可以通过从其中一堆拿一定数量的石子使得$a_1\bigoplus a_2…\bigoplus a_n = 0$

若$a_1\bigoplus a_2…\bigoplus a_n = 0$,则不管怎么拿,拿完之后$a_1\bigoplus a_2…\bigoplus a_n \neq 0$

若想不明白可以考虑 数字的每一位

Thank you for your support!