博弈论总结

什么是博弈论：

多人进行博弈，假设每个人都采取最优策略，一定有一个人胜出，在知道初态及规则的情况下，求解出

何人胜出的一类问题的理论及方法。

博弈论的一些性质

P点：必败点，N点：必胜点

（1）无法进行任何移动的局面（也就是terminal position）是P-position；

（2）可以移动到P-position的局面是N-position；

（3）所有移动都导致N-position的局面是P-position。

巴什博奕：

介绍：只有一堆n个物品，两个人轮流从中取物，规定每次最少取一个，最多取m个，最后取光者为

胜。

必定可以写成该式子 n=k*(m+1)+r；

结论：若r=0，则先手必败，否则先手必胜。

  

   

    

     

    
    

     

      if(n % (m + 1) == 0)
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 cout<<"后手必胜"<<endl;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      else
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 cout<<"先手必胜"<<endl;
     
    
  
 

威佐夫博弈：

介绍：有两堆各若干的物品，两人轮流从其中一堆取至少一件物品，至多不限，或从两堆中同时取相同

件物品，规定最后取完者胜利。

结论：若两堆物品的初始值为（x，y），且x<y，则另z=y-x；

记w=（int）[（（sqrt（5）+1）/2）*z ]；（中间为熟知的黄金分割比）

若w=x，则先手必败，否则先手必胜。

  

   

    

     

    
    

     

      if(x > y)
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

       swap(x, y);
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int c = floor((y - x) * (sqrt(5) + 1) / 2);
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      if(c == x)
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 cout<<0<<endl;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      else
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 cout<<1<<endl;
     
    
  
 

尼姆博奕：

介绍：有三堆各若干个物品,两个人轮流从某一堆取任意多的物品,规定每次至少取一个,多者不限,最后取

光者得胜.

结论：n堆石子全部做异或运算，结果为0则为必败结果

SG函数：

首先定义mex(minimal excludant)运算，这是施加于一个集合的运算，表示最小的不属于这个集合的非

负整数。例如mex{0,1,2,4}=3、mex{2,3,5}=0、mex{}=0。

对于任意状态 x ， 定义 SG(x) = mex(F)，其中F 是 x 后继状态的SG函数值的集合（就是上述mex中的数

值）。最后返回值（也就是SG(X)）为0为必败点，不为零必胜点。

进一步解释一下F，就是题意中给出的可以移动的次数。举个例子来说，一堆石子，每次只能拿1，3，

5，7个，那么S数组就是1，3，5，7。

假如说是在一个游戏中有多个石子堆该怎么办了。我们只需要把对每个石子堆进行sg函数的调用，将得

到的所有的值进行异或。得出来的结果为0则该情形为必败态。否则为必胜态。

  

   

    

     

    
    

     

      int sg[MAXN];
     
    
   

    

     

    
    

     

      int f[MAXM]; //可以取走的石子个数
     
    
   

    

     

    
    

     

      bool Hash[MAXN];
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      void getSG(int m)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 memset(sg, 0, sizeof(sg));
     
    
   

    

     

    
    

     
 for (int i = 1; i < MAXN; i++) {//枚举石子的个数
     
    
   

    

     

    
    

     
 memset(Hash, false, sizeof(Hash));
     
    
   

    

     

    
    

     
 for (int j = 0; j < m && f[j] <= i; j++)
     
    
   

    

     

    
    

     

       Hash[sg[i-f[j]]] = true;//枚举每次拿走的个数并标记
     
    
   

    

     

    
    

     
 for (int j = 0; j < MAXN; j++) {
     
    
   

    

     

    
    

     
 if (!Hash[j]) {
     
    
   

    

     

    
    

     

       sg[i] = j; //找到这个F[](该状态可以达到的状态)中不存在的最小的数
     
    
   

    

     

    
    

     
 break;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      } 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      //例题：hdu1847
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int n, num = 1;
     
    
   

    

     

    
    

     
 for (int i = 0; i < MAXM; num <<= 1, i++)
     
    
   

    

     

    
    

     

       f[i] = num;//这里的F数组就是可以移动的步数，每次都是2的幂次
     
    
   

    

     

    
    

     

       getSG(MAXM);
     
    
   

    

     

    
    

     
 while (cin >> n)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 if (sg[n])
     
    
   

    

     

    
    

     
 cout << "Kiki" << endl;
     
    
   

    

     

    
    

     
 else
     
    
   

    

     

    
    

     
 cout << "Cici" << endl;
     
    
   

    

     

    
    

     

       } 
     
    
   

    

     

    
    

     
 return 0;
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: fantianzuo.blog.csdn.net，作者：兔老大RabbitMQ，版权归原作者所有，如需转载，请联系作者。

原文链接：fantianzuo.blog.csdn.net/article/details/102688773