组合博弈 取石子游戏.pdf

组合博弈 取石子游戏.pdf 组合博弈是一类需要策略和技巧的游戏，取石子游戏是其中的一种。游戏规则是两人轮流拿石子，规定谁取到最后一颗石子谁就胜出。在了解石子总数的情况下，如何快速预测谁将会胜出？我们可以通过分析小红和小蓝的取石子过程来解决这个问题。 小红和小蓝各取一次共有三种情况：①共取走 2 颗石子（1,1）、②共取走 4 颗石子（1,3）和③共取走 6 颗石子（3,3）。设方案①取了 N1 次，方案②取了 N2 次，方案③取了 N3 次后，还剩下 K（k<6）个石子。最后 K 的取值有三种情况：0、1、3。这是因为剩下的石子个数总共有 0、1、2、3、4、5 几种可能，2 可以再取一轮（1,1）剩下 0，4 可以再取一轮（1,3）或者两次（1,1）剩下 0，5 可以再取（1,1）、（1,3）等的组合剩下 1 或 3 个，所以综合是最终会剩下 0、1、3 三种可能。 设有石子 S，则 S=2*N1+4*N2+6*N3+K。其中 2*N1+4*N2+6*N3=(1+1)*N1+(1+3)*N2+(3+3)*N3，说明取的过程为偶数次，所以剩下 K 时该最先取石子的人取。K=1、3 则先取方胜。反之，另一方胜。又 2*N1+4*N2+6*N3=2*(N1+2*N2+3*N3) 为偶数，所以 S 的奇偶性取决于 K，当 K 为偶数时，后取方胜，反之，先取方胜。 因此，可以计算时可以先对 6 取余，如果余数为 0、2、4，则 K 为 0（偶数，后取者胜），如果余数为 1、3、5 则 K 为 1 或 3（奇数，先取者胜）。 此外，还有一种有趣的游戏，即巴什博奕（Bash Game）。游戏规则是两个人轮流从堆中取物体，规定最后取光物体者取胜。我们可以发现，如果 n=m+1，那么由于一次最多只能取 m 个，所以，无论先取者拿走多少个，后取者都能够一次拿走剩余的物品，后者取胜。因此，我们发现了如何取胜的法则：如果 n=(m+1)*r+s，（r 为任意自然数，s≤m），那么先取者要拿走 s 个物品，如果后取者拿走 k（k≤m）个，那么先取者再拿走 m+1-k 个，结果剩下（m+1）（r-1）个，以后保持这样的取法，那么先取者肯定获胜。 此外，还有威佐夫博奕（Wythoff Game），有两堆各若干个物品，两个人轮流从某一堆或同时从两堆中取同样多的物品，规定每次至少取一个，多者不限，最后取光者得胜。这种情况下是颇为复杂的。我们用（ak，bk）（ak ≤ bk，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）。我们可以知道，后面的奇异局势可以通过一轮特殊的取法变为更低的奇异局势！可以看出，a0=b0=0，ak 是未在前面出现过的最小自然数，而 bk=ak+k，奇异局势有如下三条性质： 1. 任何自然数都包含在一个且仅有一个奇异局势中。 2. 任意操作都可将奇异局势变为非奇异局势。 3. 采用适当的方法，可以将非奇异局势变为奇异局势。 组合博弈取石子游戏是一种需要策略和技巧的游戏，我们可以通过分析游戏规则和过程来解决问题，并且可以应用于其他类似的游戏中。