主题

主题

 
   

Nim游戏

全部抄的百度百科。自己做一些笔记……

我觉得百度百科这一篇文章写的挺好的,只是最后一段不得不涉及到学术内容。前面的一部分都是可以给不做学术的人看懂的。比百度百科其它某些文章,看上去高大上实际上有没有用的东西高到不知道哪里去了。

链接

  • Nim游戏

有若干堆石子,每堆石子的数量都是有限的。游戏双方在操作的时候,可以选择一堆石子,并拿走若干石子(但是不能不拿)。直到一方无法操作(即全部被拿完)。无法操作的一方为败。

  • 必胜策略

假设现在我们操作,讨论我们面临的局面,看我们是否有必胜策略。

先看看一种必胜的方法:

如果只有一堆石子,显然我们直接拿走这一堆石子就可以取胜。

如果有两堆石子,我们先拿走较大的那一堆多出来的石子。之后对方从第一堆石子拿走多少,我们就从第二堆石子拿走多少。这样我们也是必胜的。

(当然,如果两堆石子相等,对方有必胜策略)

如果有三堆……

感觉有点头疼。那么我们从另一个角度来看此问题。

  • 局面分析

假设我们现在面临的是(3,3)这样一个局面。

(3,3)可以通过我们移动一次得到的局面有(0,3) (1,3) (2,3)。

接下来对方通过移动一次,从(0,3)会达到(0,0) (0,1) (0,2)。由于(0,0)是我方必败,因此如果对方面临的局面是(0,3),那么我方必败。

同理可以得到(1,3)与(2,3)都是我方必败的局面,因此(3,3)是我方必败的局面。

我们把(3,3),(0,0)这样的局面称之为先手必败局面,简称为必败局面。把(0,1) (0,2)这样的局面称之为先手必胜局面,简称为必胜局面

那么我们也理论分析出了(3,3)是必败局面。同样,我们可以归纳得到,对于任何a=b,局面(a,b)为必败局面。

  • 第一种方法

我们发现,对于一个局面的分析——

  1. 如果可以推导出的局面全部是必胜局面,那么此局面为必败局面。

  2. 如果推导出了有一个局面是必败局面,此局面就是必胜局面。

那么很显然我们可以使用递归来计算。

由于大量状态的重复,我们可以通过记忆化搜索或者DP来处理这个问题。

对于一个(a[1],a[2]……a[k])的局面,我们需要一个O(a[1]*a[2]*……*a[k])的时间复杂度来求解。

  • 一些相关内容

  1. 局面的转移是一个拓扑图(大概也算作一个偏序集?不太懂)。这个通过它可以DP得到是很容易理解的。

  2. 基于上面的理论,一个局面要么是必胜局面,要么是必败局面。

    因为每一个局面都可以通过拓扑排序得到。而这个拓扑排序中只有这两种局面。

  • 位运算

我们发现这个递归式十分有趣,有点像或运算(如果有一个是1,那么答案就是1,如果全部是0,那么答案就是0)。

虽然和或运算关系不大。毕竟这是递归式……

首先,全部是0的局面是必败局面。

我们把(a[1],a[2]……a[n])变为二进制。

10100101001

01001100010

正如上面一样。

接下来我们发现,一次移动就是选择一个数字,把二进制数上面的某一个1变为0,把后面的所有的数字任意变化。

  • 先考虑1位的情况:

如果末位只有1个1,那么显然这个局面是必胜局面。

如果末位有2个1,那么显然这个局面是必败局面。

……

  1. 如果末位有奇数个1,那么下一步一定是偶数个1,此局面为必胜局面。

  2. 如果末位有偶数个1,那么下一步一定是奇数个1,此局面为必败局面。

这个通过归纳法我们可以得到。

  • 接下来考虑两位的情况:

如果第二位上只有1个1,那么这个局面显然可以推导出一个必败局面。因为我们可以选择把第2位上这个1删去,在对应的第一位上选择0或者1,达到末位有偶数个1的局面。那么,“第二位只有1个1”就是一个必胜局面。

如果第二位上有2个1:

 如果先手选择移动第二位上的1,那么就会移动到第二位上只有一个1的局面,即移动到一个必胜局面。(所以先手不会移动第二位上的1)

 如果先手选择移动第一位上的1,那么我们讨论:

  如果第一位上只有1个1。那么先手移动一次之后,后手面临的局面就是“第二位上2个1,末位没有1”的局面(显然这是一个必败局面)。那么这个局面推导出了一个必败局面,所以这个局面就是必胜局面。

  如果第一位上有2个1,那么先手移动一次之后,后手面临的就是一个必胜局面。那么我们发现,这个“第二位上2个1,末位2个1”的局面推导出的所有局面都是必胜局面,这个局面就是一个必败局面。

通过归纳,我们不难发现,如果第二位上有2个1的时候,

  1. 对于第一位上奇数个1,此局面为必胜局面;

  2. 对于第一位上偶数个1,此局面为必败局面。

如果第二位上有3个1:

显然,我们可以通过删去第二位上的一个1,让这一位对应的第一位变为0或者1,达到一个“第二位上有2个1,第一位上有偶数个1的局面”,即可以推导出一个必败局面,那么,“第二位上有3个1”就是一个必胜局面。

如果第二位上有4个1,不难发现它是与“第二位上有2个1”的局面是一样的。如果第二位上有5个1,不难发现他是与“第二位上有3个1”是一样的。

……

于是对于第二位的分析,我们可以得出:

  1. 如果第二位上有奇数个1,那么此局面为必胜局面

  2. 如果第二位上有偶数个1,那么需要考虑第一位:

    如果第一位上有奇数个1,那么此局面为必胜局面;如果第一位上有偶数个1,那么此局面为必败局面。

这个通过归纳法亦可得到。

  • 接下来我们考虑三位的情况

  • 接下来我们考虑更高位的情况……

其实最后不难分析出来:

如果某一位上有奇数个1,那么此局面为必胜局面。否则为必败局面。

那么这就是异或运算:

如果a[1]^a[2]^……^a[n]=0,那么此局面为必败局面。否则为必胜局面。

 
 
评论
 
 
热度(1)