ACM程序設計杭州電子科技大學劉春英acm@6/5/20241周六月賽，你

了嗎？準備好6/5/20242每周一星（11）：荒古勞神圣體6/5/20243第十二講組合博弈入門（SimpleGameTheory）6/5/20244導引游戲(1)玩家：2人；(2)道具：23張撲克牌；(3)規則：游戲雙方輪流取牌；每人每次僅限于取1張、2張或3張牌；撲克牌取光，則游戲結束；最后取牌的一方為勝者。6/5/20245基本思路？請陳述自己的觀點6/5/20246第一部分簡單取子游戲（組合游戲的一種）6/5/20247什么是組合游戲——有兩個玩家；游戲的操作狀態是一個有限的集合（比如：限定大小的棋盤）；游戲雙方輪流操作；雙方的每次操作必須符合游戲規定；當一方不能將游戲繼續進行的時候，游戲結束，同時，對方為獲勝方；無論如何操作，游戲總能在有限次操作后結束；6/5/20248概念:必敗點和必勝點(P點&N點)必敗點(P點):前一個選手(Previousplayer)將取勝的位置稱為必敗點。必勝點(N點):下一個選手(Nextplayer)將取勝的位置稱為必勝點。

6/5/20249必敗(必勝)點屬性(1)所有終結點是必敗點（P點）；(2)從任何必勝點（N點）操作，至少有一種方法可以進入必敗點（P點）；(3)無論如何操作，從必敗點（P點）都只能進入必勝點（N點）.6/5/202410取子游戲算法實現——

步驟1:將所有終結位置標記為必敗點（P點）；步驟2:將所有一步操作能進入必敗點（P點）的位置標記為必勝點（N點）步驟3:如果從某個點開始的所有一步操作都只能進入必勝點（N點），則將該點標記為必敗點（P點）；步驟4:如果在步驟3未能找到新的必敗（P點），則算法終止；否則，返回到步驟2。6/5/202411課內練習:SubtractionGames: subtractionsetS={1,3,4}x:01

234

5678

91011121314…Pos:PNPNNNNPNP

N

N

N

N

P…6/5/202412實戰練習…kiki'sgame

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

對于nim游戲的某個位置(x1,x2,x3),當且僅當它各部分的nim-sum等于0時（即x1⊕x2⊕x3=0），則當前位于必敗點。定理一也適用于更多堆的情況～6/5/202419定理一的證明……

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

6/5/202423第三部分GraphGames&Sprague-GrundyFunction6/5/202424Whatisthegraphgame?(1)PlayerImovesfirst,startingatx0.(2)Playersalternatemoves.(3)Atpositionx,theplayerwhoseturnitistomovechoosesapositiony∈F(x).(4)Theplayerwhoisconfrontedwithaterminalpositionathisturn,andthuscannotmove,loses.6/5/202425Exampleaboutgraphgame:0,0,01,0,00,0,10,1,05,7,92,0,0……6/5/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)6/5/202427Useof

theSprague-GrundyFunction:

P-positions:Positionsxforwhichg(x)=0

N-positions:Positionsxforwhichg(x)>0

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

WhatcantheS-Gvaluedescribe?6/5/202430Part4:SumsofCombinatorialGames6/5/202431What

isso-called——

“SumsofCombinatorialGames”?6/5/202432Theorem2.

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

#include<string.h>

#include<algorithm>

usingnamespacestd;

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

intmex(intp)

{

inti,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()

{

intn,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)