算法12組合博弈入門

ACM程序設(shè)計杭州電子科技大學(xué)劉春英

2023/4/202期末考試，你了嗎？準備好2023/4/203卓越群星：南立浩陳欽況劉紫賢王海光楊博睿......2023/4/204第十二講組合博弈入門（SimpleGameTheory）2023/4/205導(dǎo)引游戲(1)玩家：2人；(2)道具：23張撲克牌；(3)規(guī)則：游戲雙方輪流取牌；每人每次僅限于取1張、2張或3張牌；撲克牌取光，則游戲結(jié)束；最后取牌的一方為勝者。2023/4/206基本思路？請陳述自己的觀點2023/4/207第一部分簡單取子游戲（組合游戲的一種）2023/4/208什么是組合游戲——有兩個玩家；游戲的操作狀態(tài)是一個有限的集合（比如：限定大小的棋盤）；游戲雙方輪流操作；雙方的每次操作必須符合游戲規(guī)定；當(dāng)一方不能將游戲繼續(xù)進行的時候，游戲結(jié)束，同時，對方為獲勝方；無論如何操作，游戲總能在有限次操作后結(jié)束；2023/4/209概念:必敗點和必勝點(P點&N點)必敗點(P點):前一個選手(Previousplayer)將取勝的位置稱為必敗點。必勝點(N點):下一個選手(Nextplayer)將取勝的位置稱為必勝點。

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

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

234

5678

91011121314…Pos:PNPNNNNPNP

N

N

N

N

P…2023/4/2013實戰(zhàn)練習(xí)…kiki'sgame

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

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

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

2023/4/2024第三部分GraphGames&Sprague-GrundyFunction2023/4/2025Whatisthegraphgame?(1)PlayerImovesfirst,startingatx0.(2)Playersalternatemoves.(3)Atpositionx,theplayerwhoseturnitistomovechoosesapositiony∈F(x).(4)Theplayerwhoisconfrontedwithaterminalpositionathisturn,andthuscannotmove,loses.2023/4/2026Exampleaboutgraphgame:0,0,01,0,00,0,10,1,05,7,92,0,0……2023/4/2027TheSprague-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)2023/4/2028Useof

theSprague-GrundyFunction:

P-positions:Positionsxforwhichg(x)=0

N-positions:Positionsxforwhichg(x)>0

2023/4/2029Exercise:WhatistheSG-valueofthesubtractiongamewithsubtractionsetS={1,2,3}?x01234567891011121314...g(x)012301230123012...2023/4/2030Question:

WhatcantheS-Gvaluedescribe?2023/4/2031Part4:SumsofCombinatorialGames2023/4/2032What

isso-called——

“SumsofCombinatorialGames”?2023/4/2033Theorem2.

IfgiistheSprague-GrundyfunctionofGi, i=1,...,n,then G=G1+·

·

·

+GnhasSprague-Grundyfunction g(x1,...,xn)=g1(x1)⊕·

·

·⊕gn(xn).2023/4/2034Applications:SumsofthreeSubtractionGames.Inthefirstgame:m=3andthepilehas9chips.Inthesecond:m=5andthepilehas10chips.Inthethird:m=7andthepilehas14chips.g(9,10,14)=?2023/4/2035附:參考源碼(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)

print