《博弈论.ppt.ppt》由会员分享，可在线阅读，更多相关《博弈论.ppt.ppt（116页珍藏版）》请在三一办公上搜索。
1、长春理工大学 赵小舟 2009.8,本期内容,博弈基本知识（博弈概念，纳什均衡）几个经典博弈问题组合游戏基础理论三类取石子游戏一些博弈题目博弈搜索简介,博弈论又被称为对策论（Game Theory)，它是现代数学的一个新分支，也是运筹学的一个重要组成内容。在博弈圣经中写到：博弈论是二人在平等的对局中各自利用对方的策略变换自己的对抗策略，达到取胜的意义。按照2005年因对博弈论的贡献而获得诺贝尔经济学奖的Robert Aumann教授的说法，博弈论就是研究互动决策的理论。所谓互动决策，即各行动方（即局中人（player）的决策是相互影响的，每个人在决策的时候必须将他人的决策纳入自己的决策考虑之中
2、，当然也需要把别人对于自己的考虑也要纳入考虑之中在如此迭代考虑情形进行决策，选择最有利于自己的战略(strategy)。,纳什均衡(Nash Equilibrium）,假设有n个局中人参与博弈，给定其他人策略的条件下，每个局中人选择自己的最优策略（个人最优策略可能依赖于也可能不依赖于他人的战略），从而使自己利益最大化。所有局中人策略构成一个策略组合（Strategy Profile）。纳什均衡指的是这样一种战略组合，这种策略组合由所有参与人最优策略组成。即在给定别人策略的情况下，没有人有足够理由打破这种均衡。纳什均衡，从实质上说，是一种非合作博弈状态。,约翰福布斯纳什(1928-)数学家、经济
3、学家，诺贝尔经济学奖获得者。,囚徒困境,假设有两个小偷A和B联合犯事、私入民宅被警察抓住。警方将两人分别置于不同的两个房间内进行审讯，对每一个犯罪嫌疑人，警方给出的政策是：如果一个犯罪嫌疑人坦白了罪行，交出了赃物，于是证据确凿，两人都被判有罪。如果另一个犯罪嫌疑人也作了坦白，则两人各被判刑3年；如果另一个犯罪嫌人没有坦白而是抵赖，则要被判10年。如果两人都抵赖，则警方因证据不足不能判两人的偷窃罪，将两人立即释放。,囚徒博弈的支付矩阵,我们发现对于每个人，坦白是他的最优策略。但两人都坦白时，整体的结果是各被判3年（3，3）。而整体的最优结果可以达到（0，0），显然纳什均衡没有达到整体最优。,问题
4、分析,两个囚犯符合自己利益的选择是坦白招供，原本对双方都有利的策略不招供从而均被释放就不会出现。这样两人都选择坦白的策略以及因此被判8年的结局，纳什均衡”首先对亚当斯密的“看不见的手”的原理提出挑战：按照斯密的理论，在市场经济中，每一个人都从利己的目的出发，而最终全社会达到利他的效果。但是我们可以从“纳什均衡”中引出“看不见的手”原理的一个悖论:从利己目的出发,结果损人不利己,既不利己也不利他。,经典博弈问题,孤岛土著海盗分金I之你争我夺海盗分金II之分金文明海盗分金III之要钱还是要命,孤岛土著,孤岛土著,在太平洋深处有一座孤岛，孤岛上住着三个人，分别住在岛的三个角落的洞穴里。他们太寂寞了，
5、都渴望着进入天堂。有一天有神仙下凡此岛，告诉他们：“现在给你们每人一个进入天堂的机会。你们的头发已经被我染成黑色或红色的，但你们只能看到其他二人头发的颜色，而不能看到自己头发的颜色，也不能从其他人口中得知自己的颜色。如果你们知道了自己头发的颜色，就在夕阳时分面对西方自杀，我会去接你上天堂。”三个人面面相觑，他们虽然都知道其他人头发的颜色，却始终无法得知自己头发的颜色。所以都不能去自杀，于是他们相安无事地生活了几年。但在一个清晨，这种情况被一个外来人的进入打破了。这个外来人来此得知了情况，对这三个人只说了一句话：“你们至少有一人头发是红色的。”然后就离开了小岛，一去无返了。这三个人又开始面面相觑
6、了，他们都回到自己的洞穴，陷入沉思。第二天清晨，他们来到岛中间集合，互相看了看，然后又都回到了自己的洞穴里。可是在第二天黄昏的时候，事情发生了。有两个人面西自杀，并成功升入天堂了。第三天清晨，最后的一个人来到了岛中间，发现其他二人没有来，他想了想，回去了。第三天夕阳西下的时候，最后一个人也面西自杀，并成功升入了天堂。那么，这究竟是怎么回事呢？他们的头发各是什么颜色的？,分析,根据外来人说的一句话，我们可以知道一共有3种情况：（1）有一人为红色，其他二人为黑色（2）有二人为红色，另一人为黑色（3）三个人都为红色,分析,如果是情况（1），1红2黑。那么第一天外来人说完话后，红头发的人看到其他二人都
7、为黑色，所以就可以直接判断出自己头发是红色的了，当于第一天黄昏自杀。其他二人会在第二天清晨发现他已自杀，所以会认定这是情况（1），并于第二天黄昏自杀。,分析,如果是情况（2），2红1黑那么在第一天，红头发的人会看到1红1黑，他会考虑如果自己头发颜色是黑的，那么为情况（1），他所见的红发人会在第一天黄昏自杀，如果他头发为红，为情况（2），他所见的红发人不会自杀。黑头发人看到2红，那么可排除情况（1），如果他头发为黑，则为情况（2），否则为情况（3）。到了第二天，没有人自杀。那么两个红发人都认定此为情况（2），知道自己头发为红，于第二天晚自杀。黑发人第三天发现这是情况（2），知道自己头发为黑，于当
8、晚自杀。,分析,如果是情况（3），3红那么第一天，三人都看到2红，那么他们会分析，如果自己头发为黑，则为情况（2），会有2人于第二天晚自杀，如果自己头发为红，则他们也会等待第二天的结果，在第二天不会自杀。而在第二天晚无人自杀，所以第三天三个人都判定此为情况（3），均于第三天晚自杀。,结论,如果为情况（1）则红色于第一天自杀，两黑色于第二天自杀如果为情况（2）两红色于第二天自杀，黑色于第三天自杀如果为情况（3）三红色于第三天自杀,海盗分金I之你争我夺,海盗分金I之你争我夺,有10个海盗抢了10个金币，在船上，他们准备开始分金。他们制定了这样一种分配制度，海盗编号的大小代表着他们的强壮程度，首先由
9、最强壮的10号海盗制定方案，然后所有海盗（包括方案制定者）进行投票表决，如果票数超过1/2，则方案通过；否则方案否决，此时要把制定方案的1号海盗扔海里喂鲨鱼，并继续由2号海盗制定方案。海盗们都狡猾、精明、冷静而残忍，他们都乐于看到其他海盗被扔到海里。但相比而言，他们更希望自己能多得到一些金币。那么作为1号海盗，该怎样制定方案呢？,分析,我们从1个海盗的情况开始讨论。（1）如果只有1个海盗，那么他显然会把10个金币都分给自己。此时最佳方案为10。,分析,（2）如果有2个海盗，那么2号来制定方案。但是他无论怎么制定，1号海盗都投反对票，根据规则2号海盗会被丢入大海，并且金币被1号海盗独享。最佳方案
10、为死，10。,2,1,分析,（3）如果有3个海盗，那么3号无论怎么制定方案，2号必同意（因为如果只剩2人了那么2号必死，他保命要紧），而1号必反对（因为如果只剩2人，他将独享10金币并搞死2号）。所以3号可以给自己分10个，依然能通过。最佳方案为10，0，0。,3,2,1,分析,（4）如果有4个海盗，那么4号除自己需要2票，此时3号必反对提议（因为如果到3海盗情况他将得10金币，就算现在给他10金币他也反对因为他还想搞死4号），那么此时需要1、2号各一票。如果到3海盗情况，那么1、2号会颗粒无收。若不给他们金币让他们同样颗粒无收，他们将反对（同样都一无所获那为什么不让你死），但若给他们1人1金
11、币，他们就会同意。所以最佳方案为8，0，1，1。,4,2,3,1,分析,（5）如果有5个海盗，那么5号除自己需要2票，此时需要给4号10金币才能收买他，显然不划算。所以应考虑收买1、2、3的2人。此时只要给3号一个金币他就同意了（因为4海盗情况时他得0个），而1、2号海盗在4海盗情况均得1个，如果想收买其中一人，就要给他们其中一人2个金币。所以最佳方案为7，0，1，2，0或7，0，1，0，2。,5,3,4,2,1,分析,（6）如果有6个海盗，那么6号除自己需要3票，此时应准备收买1-4号的3人。收买4号需一金币，收买3号需2金币，那么收买1、2号需几金币呢？我们考虑5海盗情况时1、2号均有得2
12、金币机会，但也可能一无所获。所以此时如果给他们1金币，他们就会同意（因为他们更相信到手的金币而不愿忍受继续受人摆布的命运）。所以此时最佳分配方案是7，0，1，0，1，1但是此时我们要小心5号和1、2号是否存在交易。如果5号对1号或2号说：“如果你这次投反票搞死6号，那么下次我给你2金币。”这个交易对双方都有利，如果达成则将颠覆1号的方案。但我们认为海盗是不相信其他人的，所以交易并不存在。,6,4,5,2,3,1,分析,（7-10）情况与上述类似。最佳方案为：7人：6，0，1，0，1，2，0或6，0，1，0，1，0，28人：6，0，1，0，1，0，1，19人：5，0，1，0，1，0，1，2，0或
13、5，0，1，0，1，0，1，0，210人：5，0，1，0，1，0，1，0，1，1,海盗分金II之分金文明,海盗分金II之分金文明,仍然是10海盗分10金币规则稍有改动。此时改为投票时，只需得到大于等于1/2的票数即可通过。,分析,从1海盗情况开始讨论：（1）1海盗时，显然最佳方案为10,分析,（2）2海盗时，2号自己票数已占有1/2，拥有通过权，所以最佳方案为10，0,分析,（3）3海盗时，除自己需1票，则需要收买1号，最佳方案为9，0，1,3,2,1,分析,（4）4海盗时，收买2号即可，最佳方案9，0，1，0,4,2,3,1,分析,（5）5海盗时，需额外2票，收买3、1号即可，最佳方案8，0
14、，1，0，1,5,3,4,1,2,分析,（6-10）与上述同理6人：8，0，1，0，1，0；7人：7，0，1，0，1，0，1；8人：7，0，1，0，1，0，1，0；9人：6，0，1，0，1，0，1，0，1；10人：6，0，1，0，1，0，1，0，1，0；,海盗分金III之要钱还是要命,海盗分金III之要钱还是要命,现在是200海盗分10金币。规则为II规则（投票时，只需得到大于等于1/2的票数即可通过）。,分析,1-20人情况与海盗分金II思路完全相同。1：102：10,03：9,0,14：9,0,1,05：8,0,1,0,16：8,0,1,0,1,0；7：7,0,1,0,1,0,1；8：7,
15、0,1,0,1,0,1,0；9：6,0,1,0,1,0,1,0,1；10:6,0,1,0,1,0,1,0,1,0；11:5,0,1,0,1,0,1,0,1,0,1;12:5,0,1,0,1,0,1,0,1,0,1,0;13:4,0,1,0,1,0,1,0,1,0,1,0,1;14:4,0,1,0,1,0,1,0,1,0,1,0,1,0;15:3,0,1,0,1,0,1,0,1,0,1,0,1,0,1;16:3,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0;17:2,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1;18:2,0,1,0,1,0,1,0,1,0,1,0
16、,1,0,1,0,1,0;19:1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1;20:1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0;,分析,20人之后的情况就比较惨烈了。（21）第21人，他为了得到额外10票，只能把10金币用来收买其他10人。21:0,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1;,分析,（22）第22人，他依然只需额外10票，所以钱数仍然够收买10人，有多种方案。22:0,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0;,分析,（23）第23人
17、，他需要额外11票，但他只有10金币，所以悲剧了。无论怎么分，他必死。23:必死无疑,分析,（24）第24人，他是个幸运的家伙。他虽然同样是需要11票而只有10金币，但由于此时第23人为了保命必然同意，所以他的方案可以通过（有多种）。24:0,0,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1;,分析,（25）第25人，和23一样悲剧了。他只有10金币但需要额外12票，而且他没有死党，所以他无论怎么收买，必死。,分析,（26-27）死党不足，必死,分析,（28）第28人，非常的幸运，他可以买来10票并有25，26，27三个死党，所以他可得14票而保住性命
18、。,分析,（29-35）由于死党不足，只能跳海喂鲨鱼了。（36）第36人，幸运者，拥有29-35的7个死党，加上自己一票及买来的10票，支持票可达半数而他可苟且偷生。（37-51）同上述不幸者，喂鲨鱼。（52）幸运者。.,结论,之后的幸运者为（84）（148），可以通过计算得到，幸运者编号为2*10+2n(n=0,1,2.)。所以有200个海盗时，在148之前的52个人都要跳海喂鲨鱼，直到148才能提出一个可通过的方案，他救了自己和自己之后的不幸者。,148的情况：,（Combinatorial Game）,定义,有两个玩家；游戏的操作状态是一个有限的集合（比如：限定大小的棋盘）；游戏双方轮流
19、操作；双方的每次操作必须符合游戏规定；当一方不能将游戏继续进行的时候，游戏结束，同时，对方为获胜方；无论如何操作，游戏总能在有限次操作后结束；,必败点和必胜点,必败点(P点):前一个选手(Previous player)将取胜的位置称为必败点。必胜点(N点):下一个选手(Next player)将取胜的位置称为必胜点。,必败(必胜)点属性,(1)所有终结点是必败点（P点）；(2)从任何必胜点（N点）操作，至少有一种方法可以进入必败点（P点）；(3)无论如何操作，从必败点（P点）都只能进入必胜点（N点）.这三点是组合游戏基本性质可用来判断一游戏是否是组合游戏,解决组合游戏问题的一般方法,步骤1:
20、将所有终结位置标记为必败点（P点）；步骤2:将所有一步操作能进入必败点（P点）的位置标记为必胜点（N点）步骤3:如果从某个点开始的所有一步操作都只能进入必胜点（N点），则将该点标记为必败点（P点）；步骤4:如果在步骤3未能找到新的必败（P点），则算法终止；否则，返回到步骤2。,第一类取石子（巴什博弈）第二类取石子（威佐夫博弈）第三类取石子（尼姆博弈）取火柴问题,只有一堆 n 个石子两个人轮流从这堆石子中取石子规定每次至少取一个，最多取m个最后取光者得胜。,策略：寻找P点,例：m=3。（即每次可取1、2、3个）得出规律：n%(m+1)=0时为P点，其他为N点,变形：减法游戏,只有一堆 n 个石子
21、两个人轮流从这堆石子中取物规定每次取的个数只能为一集合中的元素最后取光者得胜。,策略：寻找P点,例，减数集合为1，2，5寻找P点：(n=0为P)得出规律：n%3=0时为P点，其他为N点,Brave Game,题目大意：1、本游戏是一个二人游戏;2、有一堆石子一共有n个；3、两人轮流进行;4、每走一步可以取走1m个石子；5、最先取光石子的一方为胜；如果游戏的双方使用的都是最优策略，请输出哪个人能赢。,http:/,分析,最简单的第一类取石子（巴什博弈）从最终的P态(0)开始向上找出所有P点应用巴什博弈公式np%(m+1)=0来验证P点,Good Luck in CET-4 Everybody!,
22、题目大意：1、本游戏是一个二人游戏;2、总共n张牌;3、双方轮流抓牌；4、每人每次抓牌的个数只能是2的幂次（即：1，2，4，8，16）5、抓完牌，胜负结果也出来了：最后抓完牌的人为胜者；如果游戏的双方使用的都是最优策略，请输出哪个人能赢。,http:/,分析,属于第一类取石子给定减数集合的减法游戏由最终P态(0)向上构造所有P点即可得出规律：n%3=0为P点,类似习题,Public Salehttp:/,有两堆各若干个石子两个人轮流从某一堆或同时从两堆中取同样多的石子规定每次至少取一个，多者不限最后取光者得胜,策略：寻找奇异局势,我们用（ak，bk）（ak bk,k=0，1，2，.,n)表示两
23、堆石子的数量并称其为局势，如果甲面对（0，0），那么甲已经输了，这种局势我们称为奇异局势。前几个奇异局势是：（0，0）、（1，2）、（3，5）、（4，7）、（6，10）、（8，13）、（9，15）、（11，18）、（12，20）。,寻找奇异局势（P态）,奇异局势性质,1、任何自然数都包含在一个且仅有一个奇异局势中由于ak是未在前面出现过的最小自然数，所以有akak-1，而 bk=ak+k ak-1+k-1=bk-1 ak-1。所以性质1。成立。2、任意操作都可将奇异局势变为非奇异局势事实上，若只改变奇异局势（ak，bk）的某一个分量，那么另一个分量不可能在其他奇异局势中，所以必然是非奇异局势。
24、如果使（ak，bk）的两个分量同时减少，则由于其差不变，且不可能是其他奇异局势的差，因此也是非奇异局势。3、采用适当的方法，可以将非奇异局势变为奇异局势,奇异局势公式,那么任给一个局势（a，b），怎样判断它是不是奇异局势呢？我们有如下公式：ak=k（1+5）/2bk=ak+k（k=0，1，2，.,n）注:（1+5）/2 1.618，k、ak、bk满足黄金分割比所有奇异局势可组成若干Fibonacci数列,取石子游戏,题目大意：1、有两堆石子，数量任意。2、游戏开始由两个人轮流取石子。3、游戏规定，每次有两种不同的取法:(1)可以在任意的一堆中取走任意多的石子；(2)可以在两堆中同时取走相同数量
25、的石子。4、最后把石子全部取完者为胜者。现在给出初始的两堆石子的数目，如果轮到你先取，假设双方都采取最好的策略，问最后你是胜者还是败者。,http:/,分析,标准的第二类取石子，直接用公式验证即可给出初始数量(a,b)若ab，则交换a,b令ab若(b-a)(1+5)/2=a，则(a,b)为一组奇异局势,Euclids Game,题目大意：1、给出两个数a,b2、由两人轮流进行，可以将其中较大数减去较小数的任意倍如(25,7)-(25-72,7)3、最终将一数减为0者取胜 若双方都用最优策略且由你先手，请输出是否能取胜。,http:/,分析：建表,蓝色：N态红色：P态,分析,由P/N表得知，当a
26、b时，P点只出现在a+1与其后几个点中而威佐夫博弈的奇异局势(3,5)、(4,7)、(6,10)恰巧出现在P点之后验证其他P点之后的点满足威佐夫奇异局势关系ak=k(1+5)/2,ak=ak+k用公式验证给出的情况即可,类似习题,取(2堆)石子游戏 http:/思路：用公式进行判断，计算比较麻烦，需要解决取整问题,有三堆各若干个石子两个人轮流从某一堆取任意多的石子规定每次至少取一个，多者不限最后取光者得胜,策略,我们用（a，b，c）表示某种局势。首先（0，0，0）显然是奇异局势，无论谁面对奇异局势，都必然失败。第二种奇异局势是（0，n，n），只要与对手拿走一样多的物品，最后都将导致（0，0，0
27、）。仔细分析一下，（1，2，3）也是奇异局势，无论对手如何拿，接下来都可以变为（0，n，n）的情形。,方法：异或“”,任何奇异局势（a，b，c）都有abc=0。延伸：任何奇异局势(a1,a2,an)都满足 a1a2an=0,证明,欲证明此算法，只需证明3个命题：1、这个判断将所有终结点为P点2、这个判断的N点一定可以变换为P点3、这个判断的P点无法变换为另一P点通过二进制和异或的性质证（在此略，详细请参考doc文档）,异或(xor)性质,本质：二进制按位加后模2a0=aaa=0a+b=ab,Sprague-Grundy 函数,将组合游戏抽象为有向图每个位置为有向图的一个节点每种可行操作为有向图
28、的一条路径例：巴什博弈n=5,m=2,Sprague-Grundy 函数,我们就在有向图的顶点上定义SG函数首先定义mex(minimal excludant)运算，这是施加于一个集合的运算，表示最小的不属于这个集合的非负整数。例如mex0,1,2,4=3、mex2,3,5=0、mex=0。对于一个给定的有向无环图，定义关于图的每个顶点的Sprague-Garundy函数g如下：g(x)=mex g(y)|y是x的后继。,Sprague-Grundy函数性质,所有的终结点SG值为0（因为它的后继集合是空集）SG为0的顶点，它的所有后继y都满足SG不为0对于一个SG不为0的顶点，必定存在一个后继
29、满足SG为0满足组合游戏性质所有SG为0定点对应P点，SG大于0顶点对应N点,Sprague-Grundy函数意义,每个SG值对应Nim游戏每堆石子的初始数量将所有SG值异或，类同于将Nim游戏的所有初态异或SG定理（Sprague-Grundy Theorem）：g(G)=g(G1)g(G2)g(Gn)。游戏的和的SG函数值是它的所有子游戏的SG函数值的异或。,取(m堆)石子游戏,题目大意：1、m堆石子,两人轮流取2、只能在1堆中取任意个.取完者胜.先取者负输出No.先取者胜输出Yes.然后输出先取者第1次取子的所有方法.,http:/,分析,标准第三类取石子用异或进行判断，由异或基本性质（
30、aa=0）求出每个点的P点，依次比较即可,Fibonacci again and again,题目大意：1、这是一个二人游戏;2、一共有3堆石子，数量分别是m,n,p个；3、两人轮流走;4、每走一步可以选择任意一堆石子，然后取走f个；5、f只能是菲波那契数列中的元素（即每次只能取1，2，3，5，8等数量）；6、最先取光所有石子的人为胜者；假设双方都使用最优策略，请判断先手的人会赢还是后手的人会赢。,http:/,分析,求SG值的问题求SG算法：1.直接DFS 2.外加数组法（效率更高）,直接DFS算法,int k,a101;/k为节点数,a数组为减数集合int f10001;/f数组用来存储所
31、有节点的sg值,初值为-1int mex(int p)/mex为求sg的函数 int i,t;bool g101=0;/定义布尔数组，初值为0 for(i=0;ik;i+)t=p-ai;/t为p当前遍历的后继 if(t0)/后继最小是0 break;if(ft=-1)/如果这个点的sg还没被赋值过 ft=mex(t);/就去查找这个点的SG gft=1;/布尔数组中赋这个SG值为1 for(i=0;i+)/遍历布尔数组 从0开始 if(!gi)/当搜索到某点未赋sg值时，mex函数所求的sg值即为此点 return i;,外接数组法,int k,a101;/k为节点数，a为减数集合int f1
32、0001,num10001;/f存储sg值，num标记sg值是否存在 sg0=0;/0为终结点，sg0为0 for(i=1;i=0 numsgi-aj=i;/i-aj的sg值用num标记 for(j=0;j=i;j+)/遍历num数组 if(numj!=i)sgi=j;/查找到第一个未被标记为i的位置，即为i的sg值break;/一定要注意break不能丢 思考：为什么找下一个点时，num数组不用初始化？,Northcott Game,如图所示，游戏在一个n行m列（1 n 1000且2 m 100）的棋盘上进行，每行有一个黑子（黑方）和一个白子（白方）。执黑的一方先行，每次玩家可以移动己方的任
33、何一枚棋子到同一行的任何一个空格上，当然这过程中不许越过该行的敌方棋子。双方轮流移动，直到某一方无法行动为止，移动最后一步的玩家获胜。Tom总是先下（黑方）。图1是某个初始局面，图二是Tom移动一个棋子后的局面（第一行的黑子左移两步）问当前状态黑棋是否有必胜策略,http:/,分析,简单求SG值问题在P态时往自己方向走没有意义 对方只要跟着走这些步就行了如图情况，黑已必输，为P态黑若向左移动2步，则白可跟着走2步，情形没有变化，仍然为黑的P态,Stone Game,题目大意：1、有n个盒子，每个盒子都有它的容量s 2、在游戏开始时，每个盒子里都有一些石子3、双方轮流进行游戏，向一个盒子投入n个
34、石子，其中n不能大于当前盒子中石子数量的平方，投入后盒中石子数不能超过其容量例：如果现在盒中有3个石子，则可以向里投1-9个4、谁不能向任何盒中投石子为负给出n个盒子的初态，问在双方均为最优策略时先手者是否能取胜,http:/,分析,对每个盒子当前分别求SG再异或即可s=20的情况(k代表石子数）规律：k(k+1)s时k的最大值为sg=0的一点，其后的sg值从s-k-1开始递减。从大到小不断找k的最大值，并将其赋给s,不断与盒中初始石子数量比较即可,A Chess Game,题目大意：1、有N个位置和M个棋子2、同一位置可以有多个棋子3、棋盘的路径被连成一个有向无环图（即每个棋子都可向其有向路
35、径前进至下一位置）4、两位玩家轮流执棋5、当一方不能再走子时，为负给出棋盘初态，问在双方都为最优策略时，先行者是否能取胜,http:/,分析,任何组合游戏都可以抽象为有向图此题可化为求SG值问题通过有向图DFS+外加数组法找出所有点SG值,相关习题,Being a Good Boy in Spring Festivalhttp:/求SG，不过此题要求输出取胜方法数，这时依据异或原理，分别对所有堆求其P态值，再进行比较、计数A Simple Gamehttp:/第一类取石子+求SGRabbit and Grasshttp:/求SG，与上题相似S-Nimhttp:/给定不同减数集合的求SG问题，要
36、用求SG通法,今有若干堆火柴，两人依次从中拿取规定每次只能从一堆中取若干根可将一堆全取走，但不可不取题目1：最后取完者为胜题目2：最后取完者为负,分析,定义概念：孤单堆：只有一根火柴的堆充裕堆：有两根或两根以上火柴的堆T态：所有堆火柴数异或值为0S态：所有堆火柴数异或值大于0T0,S0：所有堆为孤单堆的T/S情形T1,S1：有一个充裕堆的T/S情形T2,S2：有两个或以上充裕堆的T/S情形,结论,先通过异或求出整体SG值SG=0时为T态，SG0为S态问题1：同Nim游戏，SG为0时为败问题2：败态：T2,S0胜态：T0,T1,S1,S2.证明：请参考doc文档：“取火柴游戏”,John,题目大
37、意：1、一个大盒子中有一些不同颜色的mm豆，每种颜色的都有若干2、John和他哥哥轮流吃豆。3、每人一次只能选一种颜色的豆吃若干个（至少吃1个）4、吃到最后一个豆的人为负如果John先吃，是否有必胜策略。,http:/,分析,一般的Nim游戏最终值为P态，此为N态由取火柴游戏结论，求出SG值后进行判断即可,Be the Winner,题目大意：1、m个苹果分成n组2、每一组有不超过100个苹果排成一行，你可以拿走连续排列的若干个苹果（至少取1个）例如3个苹果，可以变为、（变为2堆）3、两人轮流取苹果，取到最后一个的人为负问先取者是否有必胜策略。,http:/,分析,应用取火柴游戏的结论对于划分
38、为2堆的问题，由于异或中有ab=a+b，所以划分成2堆仅相当于从中取走了若干苹果，根据结论，这样做不会对结果产生影响,有两个玩家；游戏的操作状态是一个有限的集合；游戏双方轮流操作；双方的每次操作必须符合游戏规定；当一方不能将游戏继续进行的时候，游戏结束，同时，对方为获胜方；无论如何操作，游戏总能在有限次操作后结束；,kikis game,1、一个棋盘为n行，m列2、最开始棋子在棋盘右上角(1,m)3、每次棋子可以向左、向下或向左下移动一格4、双方轮流移动棋子5、一方不能移动棋子时判负如果kiki先行，那么她有必胜策略么？,http:/,分析,从棋盘最终P点开始，找出其他所有P点即可,A New
39、 Tetris Game,题目大意：1、一个n行m列棋盘2、在棋盘上有些格子是无效的3、双方轮流进行游戏，将22的方块放入棋盘（方块不能放在不可用的格子上，也不能放在已经放置方块的地方）4、谁不能再放方块，为负例如棋盘：0000 1100 1100 0010-1110-1110-P 0100 0100 0111 0000 0000 0011若双方都用最优策略，那么先行者是否有取胜方法。,http:/,游戏演示,分析,由于每组游戏只有一个棋盘，所以无需考虑时间问题直接DFS求SG即可,A New Tetris Game(2),题目大意：1、T个n行m列棋盘2、在棋盘上有些格子是无效的3、双方轮流
40、进行游戏，将22的方块放入任意棋盘（方块不能放在不可用的格子上，也不能放在已经放置方块的地方）4、谁不能再放方块，为负若双方都用最优策略，那么先行者是否有取胜方法。,http:/,分析,上题的加强版。由于每组都有多个棋盘，所以一定要考虑时间问题直接DFS求SG必然超时优化策略：1、将原棋盘划分为几个连通区域 分别求SG再异或2、由于是有向带环图，所以DFS时要判重3、利用哈希表进行优化,划分连通区域,相当于将一个棋盘划分为几个棋盘，分别求SG时，搜索空间大大减少，效率有所提升,Digital Deletions,题目大意：1、给出位数为1-6的数字字符串2、双方轮流对字符串进行变换3、有两种变
41、换策略：（1）可将1-9变为比它小的数字（2）可将0和0之后所有数字擦除例如：301可变为201、101、001、300或34、将最后一个数字擦除者为胜求先行者是否有必胜策略。,http:/,分析,一般组合游戏问题，方法就是找到1-1000000所有P点要注意0XXXXX和XXXXX并不同，但若首位为0则必胜，所以可以拿出去单独讨论。这样就可以将1-6位的所有状态存入一个1000000的数组中了此题求P点主要有两种思路，判断法和筛法（类似于求素数算法）判断法为从小到大依次判断当前值所能变换为的值是否存在P点，若存在则此点为N，否则为P。此方法要进行重复查找，效率较低，写起来也很复杂筛法是从小到
42、大依次查找，若找到一P点，则将该点所能反向变换出的所有点标记为N。继续查找时如遇N，则跳过，否则标记为P点并继续标记。相比而言筛法效率较高，写法也较简单。,相关习题,取石子游戏http:/Multiplication Gamehttp:/找规律即可Calendar Gamehttp:/找到一年的发现是个循环 而且与闰年无关 除9.30,11.30外 其他的都满足(m+d)%2=1时为败态,Game Tree Search,概念,局面估价函数：将每个局面（state）规定一个估价函数值f，评价它对己方的有利程度。胜利的局面估价函数值为+，失败的局面估价函数值为-Max局面：假设这个局面轮到己方走
43、，有多种对策可选，其中每种策略都导致一种局面（sub-state)。我们应选择估价函数值f最大的子局面。此时该局面的决策函数值为子局面f的最大值。把这样的局面称为Max局面。Min局面：假设这个局面轮到对方走。他也有多种决策可选。对手会选择导致估价函数f最小的子局面。此时局面的决策函数为子局面f的最小值。把这样的局面称为Min局面。终结局面：如果双方都不能走，即胜负已分，为终结局面。f按规定取值。极大极小过程：对于一个局面，递归计算它所有子局面的估价函数值。如果是Max层，转移到其中函数值最大的子局面，否则转移到函数值最小的子局面。最大递归深度：由于完整计算一个局面的f值计算量太大，所以规定一
44、个最大递归深度maxdepth。如果达到了某深度，f值就是按某种主观方法得到的估价值。,Alpha-beta剪枝,-剪枝技术的基本思想或算法是：边生成博弈树边计算评估各节点的倒推值，并且根据评估出的倒推值范围，及时停止扩展那些已无必要再扩展的子节点，即相当于剪去了博弈树上的一些分枝，从而节约了机器开销，提高了搜索效率。(1)对于一个与节点MIN，若能估计出其倒推值的上确界，并且这个值不大于 MIN的父节点(一定是或节点)的估计倒推值的下确界，即，则就不必再扩展该 MIN节点的其余子节点了(因为这些节点的估值对MIN父节点的倒推值已无任何影响 了)。这一过程称为剪枝。(2)对于一个或节点MAX，若能估计出其倒推值的下确界，并且这个值不小于 MAX的父节点(一定是与节点)的估计倒推值的上确界，即，则就不必再扩展该MAX节点的其余子节点了(因为这些节点的估值对MAX父节点的倒推值已无任何影响 了)。这一过程称为剪枝。”,Game Theory Thomas S.Ferguson 编著 算法艺术和信息学竞赛 刘汝佳 黄亮 编著 Poj,Hdoj Baidu&Wiki,
