博弈論五大模型

前四大模型的深入理解

Bash博弈模型

有一堆數量為n的石頭，雙方輪流每次從堆中取至少1個石頭最多m個石頭，誰先取完誰贏。

設存在整數k和r使方程**n=k*(m+1)+r**成立,當r==0時先手必敗，否則先手必贏。

結論：n%(m+1) == 0, 先手必敗

Wythoff博弈模型

有兩堆數量分別為x、y(x <= y)的石頭，每次可以從一堆中取至少一個石頭或者從兩堆中取同等數量的石頭，誰先取完誰贏。

結論：x == floor( (sqrt(5)+1)/2 )*(y-x), 滿足等式時先手必敗

Nim博弈模型

有任意m堆、數量任意的石頭，每次只能從一堆中獲取至少1個石頭，誰先取完誰贏

設石頭堆Di，Di的異或和k = D1^D2^...^Di，當且僅當k == 0時先手必敗，否則先手必贏

結論：D1^D2^...^Di == 0, 先手必敗

Fibonacci博弈模型

有一堆數量為n的石頭，雙方輪流從石頭堆里取k[i]個石頭(1≤k[i]≤2*k[i-1])，先取完的人獲勝

當且僅當n不是斐波那契數時，先手必勝，否則先手必敗

結論：Fib(n) == false, 先手必勝

SG函數

對sg函數的深入理解

定義： P點：必敗點，換而言之，就是誰處于此位置，則在雙方操作正確的情況下必敗。
______ N點：必勝點，處于此情況下，雙方操作均正確的情況下必勝。
定義：設mex{S}為集合S中第一個不存在的正整數
定義：設sg(x)為x狀態的sg值，sg(x)=mex{S}，其中S為x的后繼狀態的sg值的集合
當sg(x) == 0時， 沒有獲勝局面，此時處于P點
性質：1、所有終結點的sg值都為0，即sg(0) == 0
______2、無論在N點如何操作，都至少存在一種情況進入P點
______3、無論如何，P節點的后繼節點一定是N節點
______4、無論如何只能進入N點的點一定是P點

例題：HDU 1848：Fibonacci again and again

題解：假設只有一堆數量為n的石子

定義sg(x)函數為當前石子數量的sg函數，每次只能取Fib[]數列的數

sg[0] = 0, Fib[] = {1,2,3,5...}

當x == 1時，可以取Fib[1]個石子，剩余0個石子，sg[1] = mex{sg[0]} = mex{0} = 1;

當x == 2時，可以取Fib[2]、Fib[1]個石子，剩余1、0個石子sg[2] = mex{sg[1],sg[0]} = mex{0,1} = 2;

當x == 3時，可以取Fib[3]、Fib[2]、Fib[1]個石子，剩余2、1、0個石子，sg[3] = mex{sg[2],sg[1],sg[0]} = mex{2,1,0} = 3;

當x == 4時，可以取Fib[3]、Fib[2]、Fib[1]個石子，剩余3、2、1個石子，sg[4] = mex{sg[3],sg[2],sg[1]} = mex{3,2,1} = 0;

......

當x == n時，若sg[n] != 0，先手必勝

對于多堆石子，類比Nim游戲：

sg[n]^sg[m]^sg[k] == 0, 先手必敗

#include<iostream> #include<vector> #include<map> #include<set> #include<algorithm> #include<cmath> #include<string> #include<string.h> #include<queue> using namespace std; #define fi first #define se second #define mp make_pair #define pb push_back #define rep(i, a, b) for(int i=(a); i<(b); i++) #define sz(a) (int)a.size() #define de(a) cout<<#a<<" = "<<a<<endl #define dd(a) cout<<#a<<" = "<<a<<" " #define be begin #define en end typedef long long ll; typedef pair<int, int> pii; typedef vector<int> vi; const int N = 1005; vi f; void fib(){f.pb(1), f.pb(1);for(int i = 1;f[i] < N;i++){f.pb(f[i]+f[i-1]);}f.erase(f.begin()); } int sg[N]; void SG(){vi::iterator it;sg[0] = 0;for(int i = 1;i < N;i++){set<int> q;for(it = f.begin();it != f.end() && *it <= i;it++){q.insert( sg[i-(*it)] );}set<int>::iterator sit = q.begin();int t = 0;for(;sit != q.end();sit++){if(t < *sit) {break;}elset = *sit+1;}sg[i] = t;} } int main() {std::ios::sync_with_stdio(false);std::cin.tie(0);fib();SG();int m,n,p;while(cin >> m >> n >> p){if(m == 0) break;if((sg[m]^sg[n]^sg[p]) == 0) cout << "Nacci" << endl;else cout << "Fibo" << endl;}return 0; }

轉載于:https://www.cnblogs.com/Ace-Monster/p/9415889.html

總結

以上是生活随笔為你收集整理的博弈论模型总结的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。