(HDUACM12)组合博弈入门_

ACM程序设计杭州电子科技大学刘春英[e-mail]2020/1/152周六月赛，你了吗？2020/1/153每周一星（11）：荒古劳神圣体2020/1/154第十二讲组合博弈入门（SimpleGameTheory）2020/1/155导引游戏(1)玩家：2人；(2)道具：23张扑克牌；(3)规则：游戏双方轮流取牌；每人每次仅限于取1张、2张或3张牌；扑克牌取光，则游戏结束；最后取牌的一方为胜者。2020/1/156基本思路？请陈述自己的观点2020/1/157第一部分简单取子游戏（组合游戏的一种）2020/1/158什么是组合游戏——(1)有两个玩家；(2)游戏的操作状态是一个有限的集合（比如：限定大小的棋盘）；(3)游戏双方轮流操作；(4)双方的每次操作必须符合游戏规定；(5)当一方不能将游戏继续进行的时候，游戏结束，同时，对方为获胜方；(6)无论如何操作，游戏总能在有限次操作后结束；2020/1/159概念:必败点和必胜点(P点&N点)必败点(P点):前一个选手(Previousplayer)将取胜的位置称为必败点。必胜点(N点):下一个选手(Nextplayer)将取胜的位置称为必胜点。2020/1/1510必败(必胜)点属性(1)所有终结点是必败点（P点）；(2)从任何必胜点（N点）操作，至少有一种方法可以进入必败点（P点）；(3)无论如何操作，从必败点（P点）都只能进入必胜点（N点）.2020/1/1511取子游戏算法实现——步骤1:将所有终结位置标记为必败点（P点）；步骤2:将所有一步操作能进入必败点（P点）的位置标记为必胜点（N点）步骤3:如果从某个点开始的所有一步操作都只能进入必胜点（N点），则将该点标记为必败点（P点）；步骤4:如果在步骤3未能找到新的必败（P点），则算法终止；否则，返回到步骤2。2020/1/1512课内练习:SubtractionGames:subtractionsetS={1,3,4}x:01234567891011121314…Pos:PNPNNNNPNPNNNNP…2020/1/1513实战练习…kiki'sgame2020/1/1514第二部分Nim游戏2020/1/1515Nim游戏简介(1)有两个玩家；(2)有三堆扑克牌（比如：可以分别是5，7，9张）；(3)游戏双方轮流操作；(4)玩家的每次操作是选择其中某一堆牌，然后从中取走任意张；(5)最后一次取牌的一方为获胜方；2020/1/15162020/1/1517初步分析(0,0,0)(0,0,x)(0,1,1)(0,k,k)P-positionP-positionP-positionN-position(14,35,46)???2020/1/1518引入概念：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）.2020/1/1519定理一：对于nim游戏的某个位置(x1,x2,x3),当且仅当它各部分的nim-sum等于0时（即x1⊕x2⊕x3=0），则当前位于必败点。定理一也适用于更多堆的情况～2020/1/1520定理一的证明……2020/1/1521思考（1）：有了定理一，如何判断某个游戏的先手是输还是赢？2020/1/1522思考（2）：对于必胜点，如何判断有几种可行的操作方案？2020/1/1523实例分析(HDOJ_1850)BeingaGoodBoyinSpringFestival2020/1/1524第三部分GraphGames&Sprague-GrundyFunction2020/1/1525Whatisthegraphgame?(1)PlayerImovesfirst,startingatx0.(2)Playersalternatemoves.(3)Atpositionx,theplayerwhoseturnitistomovechoosesapositiony∈F(x).(4)Theplayerwhoisconfrontedwithaterminalpositionathisturn,andthuscannotmove,loses.2020/1/1526Exampleaboutgraphgame:0,0,01,0,00,0,10,1,05,7,92,0,0……2020/1/1527TheSprague-GrundyFunction.Definition:TheSprague-Grundyfunctionofagraph,(X,F),isafunction,g,definedonXandtakingnon-negativeintegervalues,suchthatg(x)=min{n≥0:ng(y)fory∈F(x)}.(1)Inwords,g(x)thesmallestnon-negativeintegernotfoundamongtheSprague-Grundyvaluesofthefollowersofx.g(x)=mex{g(y):y∈F(x)}.(2)2020/1/1528UseoftheSprague-GrundyFunction:P-positions:Positionsxforwhichg(x)=0N-positions:Positionsxforwhichg(x)02020/1/1529Exercise:WhatistheSG-valueofthesubtractiongamewithsubtractionsetS={1,2,3}?x01234567891011121314...g(x)012301230123012...2020/1/1530Question:WhatcantheS-Gvaluedescribe?2020/1/1531Part4:SumsofCombinatorialGames2020/1/1532Whatisso-called——“SumsofCombinatorialGames”?2020/1/1533Theorem2.IfgiistheSprague-GrundyfunctionofGi,i=1,...,n,thenG=G1+···+GnhasSprague-Grundyfunctiong(x1,...,xn)=g1(x1)⊕···⊕gn(xn).2020/1/1534Applications:SumsofthreeSubtractionGames.Inthefirstgame:m=3andthepilehas9chips.Inthesecond:m=5andthepilehas10chips.Inthethird:m=7andthepilehas14chips.g(9,10,14)=?2020/1/1535附:参考源码(HDOJ-1536)#includestdio.h#includestring.h#includealgorithmusingnamespacestd;intk,a[100],f[10001];intmex(intp){inti,t;boolg[101]={0};for(i=0;ik;i++){t=p-a[i];if(t0)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;ik;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)printf(L);elseprintf(W);}printf(\n);}}2020/1/1536课后练习201403《ACM程序设计》作业（12）——刘春英老师2020/1/1537原来——学习也可以很快乐～2020/1/1538WelcometoHDOJThankYou~