簡單描述
組合博弈定義
①有兩個玩家
②游戲的操作狀態是一個有限集合（比如：限定的總的牌的數量
③游戲雙方輪流操作
④雙方每次運算子合游戲規定（按規定取牌數量取牌
⑤當一方不能繼續進行的時候，游戲結束，同時，對方為獲勝方
⑥無論如何操作，游戲總能在有限次數操作后結束
必敗點、必勝點
定義：
必敗點（P點）：前一個選手（Previous player）將取勝的位置稱為必敗點（即將要在這個點操作的玩家，一定會輸）
必勝點（N點）：下一個選手（Next player）將取勝的位置稱為必勝點（在必勝點的玩家不一定贏，是要在不犯錯誤的情況下，整個游戲才會贏）
屬性：
一、所有終結點是必敗點（P點）；（終結點有限且易標記）
（終結狀態：是游戲進行不下去的點；而必敗點是游戲可能還能進行下去，改變不了要輸的命運）
舉個例子：每次取牌規則是兩張或三張；則終結點為 剩0張 或 剩1張
所以：必敗點不一定是終結點，但終結點一定是必敗點
二、從任何必勝點（N點）操作，至少有一種方式可以進入必敗點（P點）；
因為必勝點不一定怎么走都贏，一定至少一種方式進入必敗點
舉個例子：剩三張牌，取牌規則（1，2，3），若取了兩張或一張，一定是對方贏自己輸
Nim游戲
游戲簡介：
①有兩個玩家
②有三堆撲克牌（比如;5,7,9
③游戲雙方輪流操作
④玩家每次操作是選擇其中某一堆牌，然后從中取走任意張
⑤最后一次取牌的一方為獲勝方
由題引入：
Nim-Sum：按位的異或運算
SG函式的含義以及實作
sg函式的定義：
X節點的sg值是除去后繼點的sg值得最小非負整數，
sg函式的使用：
必敗點：節點sg值等于0
必勝點：節點sg值大于0
解決的問題：組合游戲
引入定理：
如果圖游戲G有若干個子圖游戲Gi組成，即：G=G1+G2+···+Gn，假設gi是Gi（i=1，，，n）的SG函式值，那么，圖游戲的SG值計算如下：
g（x1···xn）=g1（x1）^···gn（xn）
例
多個組合游戲的并
給定若干個組合游戲，可以按照下面的規則將它們并成一個新的游戲，
l 對每個游戲給定初始狀態，
l 兩人輪流走步，從A開始，
l 每一輪，選擇一個未到達終止狀態的游戲，在這個游戲中按照規則走一步，其他游戲的狀態不變，
l 最后一個走步者獲勝，即走完之后所有游戲都到達終止狀態，
我們稱這個新的游戲為“多個組合游戲的并”，我們要來看如何用每一個游戲的SG函式來求這個新的組合游戲的SG函式，
g（x1···xn）=g1（x1）^···gn（xn）
簡單例題
題述
題目大意
有n堆蘋果，每堆有mi個
兩人輪流取，每次可以從一堆蘋果中取任意連續個蘋果
最后取光者為輸
Fra先下，問是否可以獲勝
輸入輸出
代碼
#include<iostream>
#include<cstring>
#include<string>
#include<iomanip>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<stack>
#include<set>
#include<cstdio>
#include<map>
//#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,m,a,sum,i;
while(cin>>n)
{
m=0;//判斷是否是孤單堆
sum=0;
for(i=0;i<n;i++)
{
cin>>a;
if(a>1)//如果a=1即是孤單堆
m=1;
sum^=a;
}
if(m==0)
{
if(n%2==0)
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
}
else
{
if(sum==0)
cout<<"No"<<endl;//等于0，后手必勝
else
cout<<"Yes"<<endl;
}
}
return 0;
}
所以我們只要判斷孤單堆和富裕堆然后用尼姆博弈公式（nimm game)即可
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/310657.html
標籤：其他
上一篇：大一學習Python的第二天