(HDUACM)組合博弈入門(mén)報(bào)告

ACM程序設(shè)計(jì)杭州電子科技大學(xué)劉春英acm@8/16/20241今天，你

了嗎？AC8/16/20242每周一星（9）：Hugo8/16/20243第十講組合博弈入門(mén)（SimpleGameTheory）8/16/20244導(dǎo)引游戲(1)玩家：2人；(2)道具：23張撲克牌；(3)規(guī)則：游戲雙方輪流取牌；每人每次僅限于取1張、2張或3張牌；撲克牌取光，則游戲結(jié)束；最后取牌的一方為勝者。8/16/20245基本思路？請(qǐng)陳述自己的觀點(diǎn)8/16/20246第一部分簡(jiǎn)單取子游戲（組合游戲的一種）8/16/20247什么是組合游戲——有兩個(gè)玩家；游戲的操作狀態(tài)是一個(gè)有限的集合（比如：限定大小的棋盤(pán)）；游戲雙方輪流操作；雙方的每次操作必須符合游戲規(guī)定；當(dāng)一方不能將游戲繼續(xù)進(jìn)行的時(shí)候，游戲結(jié)束，同時(shí)，對(duì)方為獲勝方；無(wú)論如何操作，游戲總能在有限次操作后結(jié)束；8/16/20248概念:必?cái)↑c(diǎn)和必勝點(diǎn)(P點(diǎn)&N點(diǎn))必?cái)↑c(diǎn)(P點(diǎn)):前一個(gè)選手(Previousplayer)將取勝的位置稱為必?cái)↑c(diǎn)。必勝點(diǎn)(N點(diǎn)):下一個(gè)選手(Nextplayer)將取勝的位置稱為必勝點(diǎn)。

8/16/20249必?cái)?必勝)點(diǎn)屬性(1)所有終結(jié)點(diǎn)是必?cái)↑c(diǎn)（P點(diǎn)）；(2)從任何必勝點(diǎn)（N點(diǎn)）操作，至少有一種方法可以進(jìn)入必?cái)↑c(diǎn)（P點(diǎn)）；(3)無(wú)論如何操作，從必?cái)↑c(diǎn)（P點(diǎn)）都只能進(jìn)入必勝點(diǎn)（N點(diǎn)）.8/16/202410取子游戲算法實(shí)現(xiàn)——

步驟1:將所有終結(jié)位置標(biāo)記為必?cái)↑c(diǎn)（P點(diǎn)）；步驟2:將所有一步操作能進(jìn)入必?cái)↑c(diǎn)（P點(diǎn)）的位置標(biāo)記為必勝點(diǎn)（N點(diǎn)）步驟3:如果從某個(gè)點(diǎn)開(kāi)始的所有一步操作都只能進(jìn)入必勝點(diǎn)（N點(diǎn)），則將該點(diǎn)標(biāo)記為必?cái)↑c(diǎn)（P點(diǎn)）；步驟4:如果在步驟3未能找到新的必?cái)。≒點(diǎn)），則算法終止；否則，返回到步驟2。8/16/202411課內(nèi)練習(xí):SubtractionGames: subtractionsetS={1,3,4}x:01

234

5678

91011121314…Pos:PNPNNNNPNP

N

N

N

N

P…8/16/202412實(shí)戰(zhàn)練習(xí)…kiki'sgame

8/16/202413第二部分Nim游戲8/16/202414Nim游戲簡(jiǎn)介有兩個(gè)玩家；有三堆撲克牌（比如：可以分別是5，7，9張）；游戲雙方輪流操作；玩家的每次操作是選擇其中某一堆牌，然后從中取走任意張；最后一次取牌的一方為獲勝方；8/16/2024158/16/202416初步分析(0,0,0)(0,0,x)(0,1,1)(0,k,k)P-positionP-positionP-positionN-position(14,35,46)???8/16/202417引入概念：Nim-Sum定義:假設(shè)

(xm···x0)2和(ym···y0)2的nim-sum是(zm

···z0)2,則我們表示成

(xm···x0)2⊕(ym···y0)2=(zm

···z0)2,這里，zk=xk+yk(mod2)（k=0…m）.8/16/202418定理一：

對(duì)于nim游戲的某個(gè)位置(x1,x2,x3),當(dāng)且僅當(dāng)它各部分的nim-sum等于0時(shí)（即x1⊕x2⊕x3=0），則當(dāng)前位于必?cái)↑c(diǎn)。定理一也適用于更多堆的情況～8/16/202419定理一的證明……

8/16/202420思考（1）：有了定理一，如何判斷某個(gè)游戲的先手是輸還是贏？8/16/202421思考（2）：對(duì)于必勝點(diǎn)，如何判斷有幾種可行的操作方案？8/16/202422實(shí)例分析(HDOJ_1850)BeingaGoodBoyinSpringFestival

8/16/202423第三部分GraphGames&Sprague-GrundyFunction8/16/202424Whatisthegraphgame?(1)PlayerImovesfirst,startingatx0.(2)Playersalternatemoves.(3)Atpositionx,theplayerwhoseturnitistomovechoosesapositiony∈F(x).(4)Theplayerwhoisconfrontedwithaterminalpositionathisturn,andthuscannotmove,loses.8/16/202425Exampleaboutgraphgame:0,0,01,0,00,0,10,1,05,7,92,0,0……8/16/202426TheSprague-GrundyFunction.Definition:

TheSprague-Grundyfunctionofagraph,(X,F),isafunction,g,definedonXandtakingnon-negativeintegervalues,suchthat

g(x)=min{n≥0:n<>g(y)fory∈F(x)}.(1)

Inwords,g(x)thesmallestnon-negativeintegernotfoundamongtheSprague-Grundyvaluesofthefollowersofx.

g(x)=mex{g(y):y∈F(x)}.(2)8/16/202427Useof

theSprague-GrundyFunction:

P-positions:Positionsxforwhichg(x)=0

N-positions:Positionsxforwhichg(x)>0

8/16/202428Exercise:WhatistheSG-valueofthesubtractiongamewithsubtractionsetS={1,2,3}?x01234567891011121314...g(x)012301230123012...8/16/202429Question:

WhatcantheS-Gvaluedescribe?8/16/202430Part4:SumsofCombinatorialGames8/16/202431What

isso-called——

“SumsofCombinatorialGames”?8/16/202432Theorem2.

Ifgi

istheSprague-GrundyfunctionofGi

, i=1,...,n,then G=G1+···+GnhasSprague-Grundyfunction g(x1,...,xn)=g1(x1)⊕···⊕gn(xn).8/16/202433Applications:SumsofthreeSubtractionGames.Inthefirstgame:m=3andthepilehas9chips.Inthesecond:m=5andthepilehas10chips.Inthethird:m=7andthepilehas14chips.g(9,10,14)=?8/16/202434附:參考源碼(HDOJ-1536)#include<stdio.h>

#include<string.h>

#include<algorithm>

usingnamespacestd;

intk,a[100],f[10001];

int

mex(intp)

{

int

i,t;

boolg[101]={0};

for(i=0;i<k;i++)

{

t=p-a[i];

if(t<0)

break;

if(f[t]==-1)

f[t]=mex(t);

g[f[t]]=1;

}

for(i=0;;i++)

{

if(!g[i])

returni;

}

}

intmain()

{

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]=mex(t);

s=s^f[t];

}

if(s==0)