博弈論學習筆記

決定近段時間復習一下博弈論順便寫點筆記。

大佬博客：幾種常見博弈模型https://blog.csdn.net/wr132/article/details/51213331

SG函數與SG定理https://www.cnblogs.com/ECJTUACM-873284962/p/6921829.html

無敵的博弈總結https://blog.csdn.net/acm_cxlove/article/details/7854526

常見博弈模型

首先要清楚博弈論的基礎知識概念(必勝必敗態，多堆游戲，公平組合游戲，有向圖游戲)，然后了解幾種常見的博弈模型，其中中比較常見的應該就是巴什博弈和尼姆博弈了。把一些題目轉換為經典的博弈論模型能夠快速地找到規律解決問題。

巴什博弈：只有一堆n個物品，兩個人輪流從這堆物品中取物，規定每次至少取一個，最多取m個，最后取光者得勝。n%(m+1)=0，是必先手敗的局勢。

威佐夫博奕：有兩堆各若干個物品，兩個人輪流從某一堆或同時從兩堆中取同樣多的物品，規定每次至少取一個，多者不限，最后取光者得勝。奇異局勢：ak?=[k（1+√5）/2]，bk=?ak?+?k先手必敗。

尼姆博弈：有三堆各若干個物品，兩個人輪流從某一堆取任意多的物品，規定每次至少取一個，多者不限，最后取光者得勝。(a,b,c)是必敗態等價于a^b^c=0。

?HDU-2149

巴什博弈裸題，問是否先手必勝，是的話輸出先手第一次出手的必勝策略。m%(n+1)不為0先手必勝，必勝策略分兩種如果m<=n那么先手就可以一次勝利，否則就第一次就要出m%(n+1)。

#include<bits/stdc++.h>
using namespace std;int main()
{int m,n;while (scanf("%d%d",&m,&n)==2) {if (m%(n+1)==0) {puts("none"); continue;}if (m<=n) {printf("%d",m); for (int i=m+1;i<=n;i++) printf(" %d",i);} else {printf("%d",m%(n+1));}puts("");}return 0;
}

View Code

POJ-1067

威佐夫博奕裸題，只有奇異局勢的時候是必敗態，奇異局勢的公式為 ak?=[k（1+√5）/2]，bk=?ak?+?k 。我們怎么判斷呢？用bk-ak得到k，然后用這個k計算得到ak看看和原ak是否相等。

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;int main()
{int n,m;while (scanf("%d%d",&n,&m)==2) {if (m>n) swap(n,m);int k=n-m;int tmp=floor(k*(1.0+sqrt(5.0))/2);if (tmp==m) puts("0"); else puts("1");}return 0;
}

View Code

HDU-1847

巴什博弈變形。我們觀察到3是一個先手必敗點，所以大家都避免走到3，但是只要有一個人避免了必敗點他就可以通過對方出的數湊成3的倍數讓對方必敗。所以n是3的倍數時候先手必敗否則先手必勝。

#include<bits/stdc++.h>
using namespace std;int main()
{int n;while (scanf("%d",&n)==1) {if (n%3) puts("Kiki"); else puts("Cici");}return 0;
}

View Code

?SG函數與SG定理

但是對于一些非常見博弈模型或者是模型變形規律不明顯的，我們有一個大殺器：SG函數。通過SG函數我們能夠快速直到某個點是必勝/必敗態從而找到規律。

做了HDU-1848當作求SG函數的模板：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int N=1e3+10;
 4 int f[30],S[N],SG[N]; 
 5 
 6 void getSG(int n) {
 7     memset(SG,0,sizeof(SG));
 8     for (int i=1;i<=n;i++) {
 9         memset(S,0,sizeof(S));  //后繼SG狀態函數集合 
10         for (int j=0;j<=20&&f[j]<=i;j++) S[SG[i-f[j]]]=1;  //標記后繼狀態SG函數 
11         for (int j=0;;j++) 
12             if (!S[j]) {  //mex:后繼SG第一個沒出現的 
13                 SG[i]=j; break;
14             }
15     }
16 }
17 
18 int main()
19 {
20     int n,m,k;
21     f[0]=f[1]=1;
22     for (int i=2;i<=20;i++) f[i]=f[i-1]+f[i-2];  //求出可操作集 
23     getSG(1000);  //計算前1000的SG函數 
24     while (scanf("%d%d%d",&n,&m,&k) && (n||m||k)) {
25         if (SG[n]^SG[m]^SG[k]) printf("Fibo\n");  //多堆游戲XOR和 
26         else printf("Nacci\n");
27     }
28     return 0;
29 }

View Code

?HDU-1536

SG函數直接應用。要注意這題輸入的操作集合不是升序的要先排序才行。

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10;
int k,n,m,f[110],S[N],SG[N]; void getSG(int n) {memset(SG,0,sizeof(SG));memset(S,-1,sizeof(S));for (int i=1;i<=n;i++) {for (int j=1;j<=k&&f[j]<=i;j++) S[SG[i-f[j]]]=i;  for (int j=0;;j++) if (S[j]!=i) {  SG[i]=j; break;}}
}int main()
{while (scanf("%d",&k) && k) {for (int i=1;i<=k;i++) scanf("%d",&f[i]);sort(f+1,f+k+1);getSG(10000);scanf("%d",&n);for (int i=1;i<=n;i++) {int m,tmp=0; scanf("%d",&m);for (int j=1;j<=m;j++) {int x; scanf("%d",&x);tmp^=SG[x];}if (tmp==0) printf("L"); else printf("W"); }puts("");}return 0;
}

View Code

HDU-3980

這道題會難一些。首先原來是一個環不好處理，但是我們注意到只要第一步下手后就會變成鏈，所以我們一開始從n-m這條鏈開始求SG函數。那么假設此時是一條長度為n的鏈，我們在當前選手在上面選擇了長度為m的區間染色，之后這條鏈就會分割成兩段分別是i和n-i-m的后繼狀態，于是此時就會變成兩個游戲，然后根據多堆Nim博弈異或和的結論，后繼狀態的SG函數就是SG[i]^SG[n-i-m]，所以我們就能標記所有后繼的SG函數得到當前狀態的SG函數。

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int n,m,SG[N],S[N];int getSG(int n) {if (n<m) return 0;if (SG[n]!=-1) return SG[n];for (int i=0;n-i-m>=0;i++) S[getSG(i)^getSG(n-i-m)]=n;  //Nim博弈 for (int i=0;;i++)if (S[i]!=n) {SG[n]=i; break;} return SG[n];    
}int main()
{int T,Case=0; cin>>T;while (T--) {scanf("%d%d",&n,&m);memset(SG,-1,sizeof(SG));memset(S,-1,sizeof(-1));SG[0]=0;if (n<m || getSG(n-m)) printf("Case #%d: abcdxyzk\n",++Case);else printf("Case #%d: aekdycoin\n",++Case);}return 0;
}

View Code

?POJ-2505

SG函數應該很容易求。但是此題的數字非常大數組決定存不下，可以考慮用map計算SG函數可以獲得AC。

#include<cstdio>
#include<iostream>
#include<map>
using namespace std;
typedef long long LL;
LL n;
map<LL,LL> SG;LL getSG(LL x) {if (x>=n) return 0;if (SG.count(x)) return SG[x];map<LL,int> S;for (int i=2;i<=9;i++) S[getSG(x*i)]=1;for (int i=0;;i++)if (!S.count(i)) return SG[x]=i;
}int main()
{while (scanf("%lld",&n)==1) {SG.clear();if (getSG(1)) printf("Stan wins.\n"); else printf("Ollie wins.\n");}return 0;
}

View Code

其他題目練習：

POJ-2484

很經典的一道題。給n個連成環的硬幣，每次每人可以取一個或者相鄰的兩個硬幣，最后取不到硬幣的人輸掉。這題要運用一種平均分然后不斷模仿對方決策得到必勝的思想。首先如果硬幣個數<=2先手必勝，大于3的時候第一個人取完之后環會變成一條鏈，然后無論第一個人取的是一個還是兩個第二個人都可以根據第一個人取的數量和位置做出“把剩下硬幣取成完全相同的兩條鏈”(這里要重點理解)。然后通過模仿對方達到不敗之地。所以硬幣數量>=3時候先手必敗。

#include<iostream>
#include<cstdio>
using namespace std;
const int N=1e6+10;
int n,m;int main()
{while (scanf("%d",&n)==1 && n) {if (n<=2) puts("Alice");else puts("Bob");}return 0;
}

View Code

POJ-2425

圖上的博弈：一個n個點的有向無環圖，有某些點有硬幣，每次沒人只可以把一個棋子往前推一步(當然是沿著邊的方向推)，最后不能推的人輸掉。盡管是在DAG上的博弈，但是SG函數的求法還是那樣，標記所有后繼狀態之后mex。然后有幾個棋子就是XOR和即可。

#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
const int N=1e3+10;
int n,m,q,SG[N];
vector<int> G[N];int getSG(int x) {if (SG[x]!=-1) return SG[x];int S[N]={0};for (int i=0;i<G[x].size();i++) {int y=G[x][i];S[getSG(y)]=1;}for (int i=0;;i++)if (S[i]!=1) return SG[x]=i;
}int main()
{while (scanf("%d",&n)==1) {for (int i=1;i<=n;i++) {G[i].clear();int t; scanf("%d",&t);for (int j=1;j<=t;j++) {int x; scanf("%d",&x); x++;G[i].push_back(x);}}memset(SG,-1,sizeof(SG));while (scanf("%d",&q) && q) {int ans=0;for (int j=1;j<=q;j++) {int x; scanf("%d",&x); x++;ans^=getSG(x);}printf("%s\n",ans?"WIN":"LOSE");}}return 0;
}

View Code

POJ 1704 Georgia and Bob

一列格子上有n個棋子，每次沒人可以選擇一個棋子往左移動若干步，棋子不能越過1格子，棋子也不能越過其他棋子移動，不能移動的人輸掉。這題真的挺巧妙的，聽大佬說這是一種叫階梯博弈的博弈模型。我們先考慮對于一組相鄰的棋子，這種情況肯定是先手必敗，因為先手移動x格同時后手可以用后面那個棋子移動相同格。那么我們把棋子兩兩配對，那么兩兩配對的時候前面棋子的移動其實是沒有意義的，因為與其配對的后面棋子可以做一模一樣的操作。所以唯一的變數變成了兩兩配對的一組棋子間的間隙。

所以解法就是把棋子兩兩匹配，奇數時候第一個棋子和格子1匹配，然后對于每一組格子間的間隙當成一堆Nim游戲，求出所有Nim游戲的和就是答案。

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1e3+10;
int n,a[N];int main()
{int T; cin>>T;while (T--) {scanf("%d",&n);for (int i=1;i<=n;i++) scanf("%d",&a[i]);sort(a+1,a+n+1);int ans=0;for (int i=n;i>0;i-=2) ans^=a[i]-a[i-1]-1;printf("%s\n",ans?"Georgia will win":"Bob will win");}return 0;
}