導引游戲
(1)玩家：2人；
(2)道具：23張撲克牌；
(3)規則：
·游戲雙方輪流取牌
·每人每次僅限于取1張、2張或3張牌；
·撲克牌取光，則游戲結束；
·最后取牌的一方為勝者，
一、簡單取子游戲（組合游戲的一種）
組合游戲——
1）有兩個玩家；
2）游戲的操作狀態是一個有限的集合（比如：限定大小的棋盤）；
3）游戲雙方輪流操作；
4）雙方的每次操作必須符合游戲規定；
5）當一方不能將游戲繼續進行的時候，游戲結束，同時，對方為獲勝方；
6）無論如何操作，游戲總能在有限次操作后結束；
必敗點（P點）：前一個選手（Previous player）將取勝的位置稱為必敗點，
必勝點（N點）：下一個選手（Next player）將取勝的位置稱為必勝點，
必勝點屬性
（1）所有終結點是必敗點（P點）；
（2）從任何必勝點（N點）操作，至少有一種方法可以進入必敗點（P點）；
（3）無論如何操作，從必敗點（P點）都只能進入必勝點（N點），
取子游戲演算法實作——
1）將所有終結位置標記為必敗點（P點）；
2）將所有一步操作能進入必敗點（P點）的位置標記為必勝點（N點）
3）如果從某個點開始的所有一步操作都只能進入必勝點（N點），則將該點標記為必敗點（P點）；
4）如果在步驟3未能找到新的必敗點（P點），則演算法終止；否則，回傳到步驟2，
二、Nim 游戲
1）有兩個玩家；
2）有三堆撲克牌（比如：分別是5，7，9張）；
3）游戲雙方輪流操作；
4）玩家的每次操作是選擇其中某一堆牌，然后從中取走任意張；
5）最后一次取牌的一方為獲勝方，
引入概念：Nim-Sum
定理1：對于nim游戲的某個位置（x1,x2,x3），當且僅當它各部分的nim-sum等于0時（即x1異或x2異或x3=0），則當前位于必敗點，
證明：
三、Graph Games & Sprague-Grundy Function
NIM游戲的狀態轉移圖：
SG函式
X節點的SG值是去除X的后繼節點的SG值后的最小的非負整數，
四、組合游戲的并
定理2：
例2：
Sample Input
2 2 5
3
2 5 12
3 2 4 7
4 2 3 7 12
5 1 2 3 4 5
3
2 5 12
3 2 4 7
4 2 3 7 12
0
Sample Output
LWW
WWL
解題代碼
#include<bits/stdc++.h>
using namespace std;
int k,a[100],f[10001];
int sg(int p)
{
int i,t;
bool g[101]={0};
for(i=0;i<k;i++)
{
t=p-a[i];
if(t<0)
break;
if(f[t]==-1)
f[t]=sg(t);
g[f[t]]=1;
}
for(i=0;;i++)
{
if(!g[i])
return i;
}
}
int main()
{
int n,i,m,t,s;
while(scanf("%d",&k),k)
{
for(i=0;i<k;i++)
scanf("%d",&a[i]);
sort(a,a+k);
memset(f,-1,sizeof(f));
f[0]=0;
scanf("%d",&n);
while(n--)
{
scanf("%d",&m);
s=0;
while(m--)
{
scanf("%d",&t);
if(f[t]==-1)
f[t]=sg(t);
s=s^f[t];
}
if(s==0)
printf("L");
else
printf("W");
}
printf("\n");
}
}運行結果
總結
組合博弈的定義
必敗點、必勝點的屬性
簡單取子游戲的演算法（根據必敗點、必勝點屬性）
Nim游戲
SG函式的含義和實作
圖游戲的SG函式求解方案
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/325839.html
標籤：其他
上一篇：如何用電腦自帶的軟體錄屏