资源描述：
《(lecture_11)组合博弈入门》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、ACM程序设计杭州电子科技大学刘春英acm@hdu.edu.cn8/25/20211今天，你了吗？AC8/25/20212每周一星（10）：Lin21448/25/20213第十一讲组合博弈入门（SimpleGameTheory）8/25/20214导引游戏(1)玩家：2人；(2)道具：23张扑克牌；(3)规则：游戏双方轮流取牌；每人每次仅限于取1张、2张或3张牌；扑克牌取光，则游戏结束；最后取牌的一方为胜者。8/25/20215基本思路？请陈述自己的观点8/25/20216第一部分简单取子游戏（组合游戏的一种）8/25/20217什么是组合游戏
2、——有两个玩家；游戏的操作状态是一个有限的集合（比如：限定大小的棋盘）；游戏双方轮流操作；双方的每次操作必须符合游戏规定；当一方不能将游戏继续进行的时候，游戏结束，同时，对方为获胜方；无论如何操作，游戏总能在有限次操作后结束；8/25/20218概念:必败点和必胜点(P点&N点)必败点(P点):前一个选手(Previousplayer)将取胜的位置称为必败点。必胜点(N点):下一个选手(Nextplayer)将取胜的位置称为必胜点。8/25/20219必败(必胜)点属性(1)所有终结点是必败点（P点）；(2)从任何必胜点（N点）操作，至少有一种方
3、法可以进入必败点（P点）；(3)无论如何操作，从必败点（P点）都只能进入必胜点（N点）.8/25/202110取子游戏算法实现——步骤1:将所有终结位置标记为必败点（P点）；步骤2:将所有一步操作能进入必败点（P点）的位置标记为必胜点（N点）步骤3:如果从某个点开始的所有一步操作都只能进入必胜点（N点），则将该点标记为必败点（P点）；步骤4:如果在步骤3未能找到新的必败（P点），则算法终止；否则，返回到步骤2。8/25/202111课内练习:SubtractionGames:subtractionsetS={1,3,4}x:01234567891
4、011121314…Pos:PNPNNNNPNPNNNNP…8/25/202112实战练习…kiki'sgame8/25/202113第二部分Nim游戏8/25/202114Nim游戏简介有两个玩家；有三堆扑克牌（比如：可以分别是5，7，9张）；游戏双方轮流操作；玩家的每次操作是选择其中某一堆牌，然后从中取走任意张；最后一次取牌的一方为获胜方；8/25/2021158/25/202116初步分析(0,0,0)(0,0,x)(0,1,1)(0,k,k)P-positionP-positionP-positionN-position(14,35,46
5、)???8/25/202117引入概念：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）.8/25/202118定理一：对于nim游戏的某个位置(x1,x2,x3),当且仅当它各部分的nim-sum等于0时（即x1⊕x2⊕x3=0），则当前位于必败点。定理一也适用于更多堆的情况～8/25/202119定理一的证明……8/25/202120思考（1）：有了定理一，如果
6、判断某个游戏的先手是输还是赢？8/25/202121思考（2）：对于必胜点，如何判断有几种可行的操作方案？8/25/202122实例分析(HDOJ_1850)BeingaGoodBoyinSpringFestival8/25/202123第三部分GraphGames&Sprague-GrundyFunction8/25/202124Whatisthegraphgame?(1)PlayerImovesfirst,startingatx0.(2)Playersalternatemoves.(3)Atpositionx,theplayerwhosetu
7、rnitistomovechoosesapositiony∈F(x).(4)Theplayerwhoisconfrontedwithaterminalpositionathisturn,andthuscannotmove,loses.8/25/202125Exampleaboutgraphgame:0,0,01,0,00,0,10,1,05,7,92,0,0……8/25/202126TheSprague-GrundyFunction.Definition:TheSprague-Grundyfunctionofagraph,(X,F),isafun
8、ction,g,definedonXandtakingnon-negativeintegervalues,suchthatg(x)=mi
