天天看點

組合博弈問題(巴什博弈,威佐夫博弈,尼姆博弈)組合博弈一、巴什博弈二、威佐夫博弈二、尼姆博弈

文章目錄

  • 組合博弈
  • 一、巴什博弈
    • 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;
		}
	}
}
           

繼續閱讀