組合博弈問題（巴什博弈，威佐夫博弈，尼姆博弈）

文章目錄

• 組合博弈
• 一、巴什博弈
• • 1.引例——取石子
  • 2.分析
  • 3.提高題
• 二、威佐夫博弈
• • 1.引例——取石子
  • 2.分析
  • 3.推廣
• 二、尼姆博弈
• • 1.引例——Matches Game
  • 2.分析
  • 3.異或和處理的正确性證明
  • • 1.終止狀态下，滿足異或和為0的平衡态
    • 2.由非平衡态存在一種方式可以變為平衡态（先手必勝分析）
    • 3.由平衡态隻能變為非平衡态（先手必敗分析）
    • 4.小結
  • 4.例題——如何在非平衡态下進行第一次選擇使得變為平衡态

組合博弈

兩名玩家交替行動，均采取最優操作，但有一方不能繼續操作時判定為輸。

具體的遊戲形式是取石子，兩個玩家輪流對石子堆進行操作，直至有玩家無法繼續操作時遊戲結束。

一、巴什博弈

1.引例——取石子

經典取石子

在這道題裡面，總共有n顆石頭，每次至少取一顆，最多取m顆，在雙方均采取最優解的情況下，問先手勝負情況

2.分析

思路一（直接判斷）：

先手必輸：

隻要石子個數為（m+1）的倍數，先手無法在一次操作内取盡，若先手拿了k顆石子（1<=K<=m），而對方卻可以拿（m+1-k）枚石子，将石子個數重新構造為（m+1）的倍數，故此時先手必輸。

先手必勝：

當石子總數為（m+1）*r+s，先手拿了s顆石子後，剩餘（m+1)*r顆石子，而此時也輪到了後手操作，根據上方的結論，可知此時後手必輸，即先手必勝。

思路二（遞推）：

必勝狀态：

先手進行操作後，石子數将發生變化，根據操作的不同，石子數的變化也不同，若變化後的石子數有一種可能對于後手來說為必敗，那麼此時可視為必勝狀态；

必敗狀态：

此時已經無法操作，或者經過操作後隻有必勝狀态，那麼此時即為必敗狀态；

由此，我們通過已知推未知，可以對每個狀态都進行判斷，直至得出結果，對于這道題來說其實還是有點浪費的。

//思路一————直接判斷
#include<bits/stdc++.h> 
using namespace std; 
int t;
int m,n;
int main(){
    cin>>t;
    while(t--){
        cin>>n>>m;
        int s=n%(m+1);
        if(s==0)cout<<"second"<<endl;
        else cout<<"first"<<endl;
    }
}
           

//思路二————遞推
#include<bits/stdc++.h> 
using namespace std; 
int t;
int m,n;
int a[1005];
int main(){
    cin>>t;
    while(t--){
        cin>>n>>m;
       for(int i=1;i<=m;i++)a[i]=1;
       for(int i=m+1;i<=n;i++){
    	int ans=1;
       	for(int j=1;j<=m;j++){
       		ans=(ans&&a[i-j]);
		   }
		a[i]=!ans;
	   }
	   if(a[n])cout<<"first"<<endl;
	   else cout<<"second"<<endl;
    }
}
           

3.提高題

Public Sale

注意空格，注意題目要求還要輸出必勝時第一次出價

#include<bits/stdc++.h> 
using namespace std; 
int m,n;
int main(){
    while(cin>>m>>n){
        if(n>=m){
            for(int i=m;i<=n;i++){
                cout<<i;
                (i<n)?cout<<" ":cout<<endl;
            }
        }
        else if(m%(n+1)==0)cout<<"none"<<endl;
        else{
            cout<<(m%(n+1))<<endl;
        }
    }
}
           

Good Luck in CET-4 Everybody!

//思路一
#include<bits/stdc++.h>
using namespace std;
int main() {
	int n;
	while(cin>>n) {
		if(n%3==0)
			cout<<"Cici"<<endl;
		else
    		cout<<"Kiki"<<endl;
 	}
 	return 0;
}
           

//思路二————遞推
#include<bits/stdc++.h> 
using namespace std; 
int a[1025];
int n;
int main(){
    for(int i=0;i<=10;i++){
        a[(int)(pow(2,i))]=1;//必勝狀态 
    }
    for(int i=1;i<=1000;i++){
        if(!a[i]){
            int ans=1;
            for(int j=0;pow(2,j)<i;j++){
                ans=(ans&&a[i-(int)(pow(2,j))]);
            }
            a[i]=!ans;
        }
    }
    while(cin>>n&&n){
        if(a[n])cout<<"Kiki"<<endl;
        else cout<<"Cici"<<endl;
    }
}
           

二、威佐夫博弈

1.引例——取石子

取石子

這道題中，仍然是兩方交替操作，不過此時的差別為：

1.初始有兩堆石子；

2.兩種操作，要麼選擇一堆從中取任意顆石子，或者從兩堆中取出相同石子個數的石子，要求石子個數要大于等于1，不設上限；

2.分析

先手必輸：

若為（0，0），此時先手無法操作，為輸；

若為（1，2），先手有四種操作：

左側取一枚石子，後手可取完右側，先手輸；

右側取一枚石子，後手可兩堆各取一個，先手輸；

右側取兩枚石子，後手可取完左側，先手輸；

兩側各取一枚石子，後手可取完右側，先手輸；

故此時先手必輸。

通過模拟，可以發現先手必輸的情況為：

（0，0）

（1，2）

（3，5）

（4，7）

（6，10）

（8，13）

（9，15）·········

我們将先手必輸的情況叫做奇異局勢，而且在其中有一個規律，以（a，b）為例，

若min（a，b）==(int)(abs(a-b)*(sqrt(5)+1)/2)，則此時為一個奇異局勢，即先手必輸。

至于具體的了解，還可以借助一個二維棋盤，一開始位于右下角，此時操作為沿一個方向走任意格，或者沿對角線移動，直至走到左上角判定為獲勝。

#include<iostream>
#include<math.h>
#include<stdlib.h>
using namespace std;
int n,m;
double tmp=(sqrt(5)+1)/2;
int main(){
	while(cin>>n>>m){
		if(min(n,m)==(int)(abs(n-m)*tmp))cout<<0<<endl;
		else cout<<1<<endl;
	}
}
           

3.推廣

有時我們不止需要判斷先手勝負情況，我們還需要輸出在先手必勝的前提下，先手可以進行的操作，我覺得隻需要依次枚舉操作，隻有操作結束，後手進行操作時處于奇異局勢下即後手必輸，說明該操作可使得先手必勝。

二、尼姆博弈

1.引例——Matches Game

Matches Game

兩方交替操作，均采取最優政策，無法操作即為失敗，有n堆石子，每次操作需要選擇一堆石子，并且從中拿出任意顆石子，可以一次性拿光。

2.分析

若為一堆：直接取完，先手必勝。

若為兩堆：相等則先手必敗；否則先手必勝。

當兩堆石子個數相同時，先手必敗，因為先手隻能對一堆石子進行操作，要麼取完，後手直接取另外一堆，即先手失敗，；要麼選擇一堆不取完，而後手可令另外一堆減少相同數目石子，此時先手重新面臨了兩堆個數相同的石子。

若石子個數不等，反過來說即可通過操作使後手面臨以上局面，即先手必勝。

若為三堆：若其中存在兩堆石子個數相等，則先手必勝。

若三堆石子個數分别為a，b和c，且a==b，那麼當先手拿光第三堆石子c時，後手面臨着上方必敗的情況。

如果三堆石子數均不相等，那麼又需要怎麼判斷呢？

與二進制的聯系（向n堆石子的推廣）：

子堆劃分：以石子數為7的一堆石子為例，我們根據它的二進制（111）視其為三個子堆，個數分别為4、2、1。

資料處理：對于三堆石子，分别為4（100），6（110），7（111），

可劃分為石子個數為1的堆數為1，石子個數為2的堆數為2，石子個數為4的堆數為3.

結果判定：4（100）^ 6（110）^ 7（111）！=0；

若n個數異或和結果為0，則被稱為平衡态，平衡态下先手必敗；

若不為0，則為非平衡态，此時先手必勝。

#include<iostream>
using namespace std;
int p;
int n;
int main(){
	while(cin>>n&&n){
		int tmp=0;
		for(int i=0;i<n;i++){
			cin>>p;
			tmp^=p;
		}
		if(!tmp)cout<<"No"<<endl;
		else cout<<"Yes"<<endl;
	}
}
           

3.異或和處理的正确性證明

1.終止狀态下，滿足異或和為0的平衡态

當選手面臨無法操作的情況，就判定為失敗，也就是所有堆都為0，異或和為0，滿足平衡态。

2.由非平衡态存在一種方式可以變為平衡态（先手必勝分析）

以 a 1 a_1 a1​、 a 2 a_2 a2​… a n a_n an​表示所有堆的石子數，以sum表示 a 1 a_1 a1​^ a 2 a_2 a2​^ …^ a n a_n an​，分析sum二進制中的最高位的1，設其為第k位，這個1意味着在 a 1 a_1 a1​、 a 2 a_2 a2​… a n a_n an​中，至少存在一個數在這一位的值同樣為1，不妨令這個數為 a i a_i ai​。

此時必定存在關系：sum ^ a i a_i ai​ < a i a_i ai​

sum ^ a i a_i ai​ 将 a i a_i ai​中的第k位置為0，對更高位無影響，那麼可知此時的 a i a_i ai​必定小于原來的值。

根據異或的知識，sum ^ a i a_i ai​ 的結果其實就是原來所有元素除去 a i a_i ai​的異或和，若此時 a i a_i ai​變為了sum ^ a i a_i ai​（一個小于 a i a_i ai​的數，可以通過操作來實作），那麼接下來所有元素的異或和就是：sum ^ a i a_i ai​ ^ sum ^ a i a_i ai​，即0.

由上可知，由非平衡态存在一種方式可以變為平衡态。

3.由平衡态隻能變為非平衡态（先手必敗分析）

反證：若由平衡态可以變為平衡态，此時仍然對 a i a_i ai​進行處理，此時sum為0，tmp = sum ^ a i a_i ai​

處理之後，tmp不發生變化，而sum仍然為0，那麼 a i a_i ai​= tmp^sum，可知 a i a_i ai​其實沒有發生變化，然而這是不滿足題目要求的，是以不成立。

由上可知，由平衡态隻能變為非平衡态

4.小結

由上可知，掌握着非平衡态的選手總有辦法使對方陷入平衡态，一步一步下去，對方也無法擺脫這種身份，隻會最終走向終止狀态。

故證明了異或和方法的正确性。

4.例題——如何在非平衡态下進行第一次選擇使得變為平衡态

此時隻能選擇一堆進行操作，我們的目标是通過修改這一堆的值（隻能減少）使結果變成平衡态。

事實上先不管我們選擇的這一堆，而将其餘的堆之間進行異或和處理，我們設這個異或和為tmp,而我們令選擇的那一堆為A，我們需要确定有無一個值a（a<A，因為a要是A通過減少石子可以變為的狀态）可以使得a^tmp結果為0。

我們可以得知其實在tmp确定的前提下，其實這個a值其實是确定的，是以我們隻需要判斷這個a與A的大小關系，就可以得知該操作是否合法。

a的确定也隻需要借助異或操作的性質，一開始我們會用sum來存所有數的異或和，而sum^A即tmp，因為tmp=tmp ^ A ^ A= sum ^ A; 而a^tmp等于0，說明了a==tmp

是以我們隻要比較sum^A跟A的大小關系

例題：Being a Good Boy in Spring Festival

#include<iostream>
using namespace std;
int p[105];
int n;
int main(){
	while(cin>>n&&n){
		int tmp=0;
		for(int i=0;i<n;i++){
			cin>>p[i];
			tmp^=p[i];
		}
		if(!tmp)cout<<0<<endl;
		else {
			int cnt=0;
			for(int i=0;i<n;i++){
				if(p[i]>(tmp^p[i]))cnt++;
			}
			cout<<cnt<<endl;
		}
	}
}