博弈论.ppt.ppt

长春理工大学赵小舟2009.8,本期内容,博弈基本知识（博弈概念，纳什均衡）几个经典博弈问题组合游戏基础理论三类取石子游戏一些博弈题目博弈搜索简介,博弈论又被称为对策论（gametheory)，它是现代数学的一个新分支，也是运筹学的一个重要组成内容。在博弈圣经中写到：博弈论是二人在平等的对局中各自利用对方的策略变换自己的对抗策略，达到取胜的意义。按照2005年因对博弈论的贡献而获得诺贝尔经济学奖的robertaumann教授的说法，博弈论就是研究互动决策的理论。所谓互动决策，即各行动方（即局中人（player）的决策是相互影响的，每个人在决策的时候必须将他人的决策纳入自己的决策考虑之中，当然也需要把别人对于自己的考虑也要纳入考虑之中在如此迭代考虑情形进行决策，选择最有利于自己的战略(strategy)。,纳什均衡(nashequilibrium）,假设有n个局中人参与博弈，给定其他人策略的条件下，每个局中人选择自己的最优策略（个人最优策略可能依赖于也可能不依赖于他人的战略），从而使自己利益最大化。所有局中人策略构成一个策略组合（strategyprofile）。纳什均衡指的是这样一种战略组合，这种策略组合由所有参与人最优策略组成。即在给定别人策略的情况下，没有人有足够理由打破这种均衡。纳什均衡，从实质上说，是一种非合作博弈状态。,约翰福布斯纳什(1928-)数学家、经济学家，诺贝尔经济学奖获得者。,囚徒困境,假设有两个小偷a和b联合犯事、私入民宅被警察抓住。警方将两人分别置于不同的两个房间内进行审讯，对每一个犯罪嫌疑人，警方给出的政策是：如果一个犯罪嫌疑人坦白了罪行，交出了赃物，于是证据确凿，两人都被判有罪。如果另一个犯罪嫌疑人也作了坦白，则两人各被判刑3年；如果另一个犯罪嫌人没有坦白而是抵赖，则要被判10年。如果两人都抵赖，则警方因证据不足不能判两人的偷窃罪，将两人立即释放。,囚徒博弈的支付矩阵,我们发现对于每个人，坦白是他的最优策略。但两人都坦白时，整体的结果是各被判3年（3，3）。而整体的最优结果可以达到（0，0），显然纳什均衡没有达到整体最优。,问题分析,两个囚犯符合自己利益的选择是坦白招供，原本对双方都有利的策略不招供从而均被释放就不会出现。这样两人都选择坦白的策略以及因此被判8年的结局，纳什均衡”首先对亚当斯密的“看不见的手”的原理提出挑战：按照斯密的理论，在市场经济中，每一个人都从利己的目的出发，而最终全社会达到利他的效果。但是我们可以从“纳什均衡”中引出“看不见的手”原理的一个悖论:从利己目的出发,结果损人不利己,既不利己也不利他。,经典博弈问题,孤岛土著海盗分金i之你争我夺海盗分金ii之分金文明海盗分金iii之要钱还是要命,孤岛土著,孤岛土著,在太平洋深处有一座孤岛，孤岛上住着三个人，分别住在岛的三个角落的洞穴里。他们太寂寞了，都渴望着进入天堂。有一天有神仙下凡此岛，告诉他们：“现在给你们每人一个进入天堂的机会。你们的头发已经被我染成黑色或红色的，但你们只能看到其他二人头发的颜色，而不能看到自己头发的颜色，也不能从其他人口中得知自己的颜色。如果你们知道了自己头发的颜色，就在夕阳时分面对西方自杀，我会去接你上天堂。”三个人面面相觑，他们虽然都知道其他人头发的颜色，却始终无法得知自己头发的颜色。所以都不能去自杀，于是他们相安无事地生活了几年。但在一个清晨，这种情况被一个外来人的进入打破了。这个外来人来此得知了情况，对这三个人只说了一句话：“你们至少有一人头发是红色的。”然后就离开了小岛，一去无返了。这三个人又开始面面相觑了，他们都回到自己的洞穴，陷入沉思。第二天清晨，他们来到岛中间集合，互相看了看，然后又都回到了自己的洞穴里。可是在第二天黄昏的时候，事情发生了。有两个人面西自杀，并成功升入天堂了。第三天清晨，最后的一个人来到了岛中间，发现其他二人没有来，他想了想，回去了。第三天夕阳西下的时候，最后一个人也面西自杀，并成功升入了天堂。那么，这究竟是怎么回事呢？他们的头发各是什么颜色的？,分析,根据外来人说的一句话，我们可以知道一共有3种情况：（1）有一人为红色，其他二人为黑色（2）有二人为红色，另一人为黑色（3）三个人都为红色,分析,如果是情况（1），1红2黑。那么第一天外来人说完话后，红头发的人看到其他二人都为黑色，所以就可以直接判断出自己头发是红色的了，当于第一天黄昏自杀。其他二人会在第二天清晨发现他已自杀，所以会认定这是情况（1），并于第二天黄昏自杀。,分析,如果是情况（2），2红1黑那么在第一天，红头发的人会看到1红1黑，他会考虑如果自己头发颜色是黑的，那么为情况（1），他所见的红发人会在第一天黄昏自杀，如果他头发为红，为情况（2），他所见的红发人不会自杀。黑头发人看到2红，那么可排除情况（1），如果他头发为黑，则为情况（2），否则为情况（3）。到了第二天，没有人自杀。那么两个红发人都认定此为情况（2），知道自己头发为红，于第二天晚自杀。黑发人第三天发现这是情况（2），知道自己头发为黑，于当晚自杀。,分析,如果是情况（3），3红那么第一天，三人都看到2红，那么他们会分析，如果自己头发为黑，则为情况（2），会有2人于第二天晚自杀，如果自己头发为红，则他们也会等待第二天的结果，在第二天不会自杀。而在第二天晚无人自杀，所以第三天三个人都判定此为情况（3），均于第三天晚自杀。,结论,如果为情况（1）则红色于第一天自杀，两黑色于第二天自杀如果为情况（2）两红色于第二天自杀，黑色于第三天自杀如果为情况（3）三红色于第三天自杀,海盗分金i之你争我夺,海盗分金i之你争我夺,有10个海盗抢了10个金币，在船上，他们准备开始分金。他们制定了这样一种分配制度，海盗编号的大小代表着他们的强壮程度，首先由最强壮的10号海盗制定方案，然后所有海盗（包括方案制定者）进行投票表决，如果票数超过1/2，则方案通过；否则方案否决，此时要把制定方案的1号海盗扔海里喂鲨鱼，并继续由2号海盗制定方案。海盗们都狡猾、精明、冷静而残忍，他们都乐于看到其他海盗被扔到海里。但相比而言，他们更希望自己能多得到一些金币。那么作为1号海盗，该怎样制定方案呢？,分析,我们从1个海盗的情况开始讨论。（1）如果只有1个海盗，那么他显然会把10个金币都分给自己。此时最佳方案为10。,分析,（2）如果有2个海盗，那么2号来制定方案。但是他无论怎么制定，1号海盗都投反对票，根据规则2号海盗会被丢入大海，并且金币被1号海盗独享。最佳方案为死，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金币，他们就会同意。所以最佳方案为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金币机会，但也可能一无所获。所以此时如果给他们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或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，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,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,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人，他需要额外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票而保住性命。,分析,（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的情况：,（combinatorialgame）,定义,有两个玩家；游戏的操作状态是一个有限的集合（比如：限定大小的棋盘）；游戏双方轮流操作；双方的每次操作必须符合游戏规定；当一方不能将游戏继续进行的时候，游戏结束，同时，对方为获胜方；无论如何操作，游戏总能在有限次操作后结束；,必败点和必胜点,必败点(p点):前一个选手(previousplayer)将取胜的位置称为必败点。必胜点(n点):下一个选手(nextplayer)将取胜的位置称为必胜点。,必败(必胜)点属性,(1)所有终结点是必败点（p点）；(2)从任何必胜点（n点）操作，至少有一种方法可以进入必败点（p点）；(3)无论如何操作，从必败点（p点）都只能进入必胜点（n点）.这三点是组合游戏基本性质可用来判断一游戏是否是组合游戏,解决组合游戏问题的一般方法,步骤1:将所有终结位置标记为必败点（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个石子两个人轮流从这堆石子中取物规定每次取的个数只能为一集合中的元素最后取光者得胜。,策略：寻找p点,例，减数集合为1，2，5寻找p点：(n=0为p)得出规律：n%3=0时为p点，其他为n点,bravegame,题目大意：1、本游戏是一个二人游戏;2、有一堆石子一共有n个；3、两人轮流进行;4、每走一步可以取走1m个石子；5、最先取光石子的一方为胜；如果游戏的双方使用的都是最优策略，请输出哪个人能赢。,分析,最简单的第一类取石子（巴什博弈）从最终的p态(0)开始向上找出所有p点应用巴什博弈公式np%(m+1)=0来验证p点,goodluckincet-4everybody!,题目大意：1、本游戏是一个二人游戏;2、总共n张牌;3、双方轮流抓牌；4、每人每次抓牌的个数只能是2的幂次（即：1，2，4，8，16）5、抓完牌，胜负结果也出来了：最后抓完牌的人为胜者；如果游戏的双方使用的都是最优策略，请输出哪个人能赢。,分析,属于第一类取石子给定减数集合的减法游戏由最终p态(0)向上构造所有p点即可得出规律：n%3=0为p点,类似习题,publicsale,有两堆各若干个石子两个人轮流从某一堆或同时从两堆中取同样多的石子规定每次至少取一个，多者不限最后取光者得胜,策略：寻找奇异局势,我们用（ak，bk）（akbk,k=0，1，2，.,n)表示两堆石子的数量并称其为局势，如果甲面对（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+kak-1+k-1=bk-1ak-1。所以性质1。成立。2、任意操作都可将奇异局势变为非奇异局势事实上，若只改变奇异局势（ak，bk）的某一个分量，那么另一个分量不可能在其他奇异局势中，所以必然是非奇异局势。如果使（ak，bk）的两个分量同时减少，则由于其差不变，且不可能是其他奇异局势的差，因此也是非奇异局势。3、采用适当的方法，可以将非奇异局势变为奇异局势,奇异局势公式,那么任给一个局势（a，b），怎样判断它是不是奇异局势呢？我们有如下公式：ak=k（1+5）/2bk=ak+k（k=0，1，2，.,n）注:（1+5）/21.618，k、ak、bk满足黄金分割比所有奇异局势可组成若干fibonacci数列,取石子游戏,题目大意：1、有两堆石子，数量任意。2、游戏开始由两个人轮流取石子。3、游戏规定，每次有两种不同的取法:(1)可以在任意的一堆中取走任意多的石子；(2)可以在两堆中同时取走相同数量的石子。4、最后把石子全部取完者为胜者。现在给出初始的两堆石子的数目，如果轮到你先取，假设双方都采取最好的策略，问最后你是胜者还是败者。,分析,标准的第二类取石子，直接用公式验证即可给出初始数量(a,b)若ab，则交换a,b令a(25-72,7)3、最终将一数减为0者取胜若双方都用最优策略且由你先手，请输出是否能取胜。,分析：建表,蓝色：n态红色：p态,分析,由p/n表得知，当ab时，p点只出现在a+1与其后几个点中而威佐夫博弈的奇异局势(3,5)、(4,7)、(6,10)恰巧出现在p点之后验证其他p点之后的点满足威佐夫奇异局势关系ak=k(1+5)/2,ak=ak+k用公式验证给出的情况即可,类似习题,取(2堆)石子游戏,有三堆各若干个石子两个人轮流从某一堆取任意多的石子规定每次至少取一个，多者不限最后取光者得胜,策略,我们用（a，b，c）表示某种局势。首先（0，0，0）显然是奇异局势，无论谁面对奇异局势，都必然失败。第二种奇异局势是（0，n，n），只要与对手拿走一样多的物品，最后都将导致（0，0，0）。仔细分析一下，（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函数,将组合游戏抽象为有向图每个位置为有向图的一个节点每种可行操作为有向图的一条路径例：巴什博弈n=5,m=2,sprague-grundy函数,我们就在有向图的顶点上定义sg函数首先定义mex(minimalexcludant)运算，这是施加于一个集合的运算，表示最小的不属于这个集合的非负整数。例如mex0,1,2,4=3、mex2,3,5=0、mex=0。对于一个给定的有向无环图，定义关于图的每个顶点的sprague-garundy函数g如下：g(x)=mexg(y)|y是x的后继。,sprague-grundy函数性质,所有的终结点sg值为0（因为它的后继集合是空集）sg为0的顶点，它的所有后继y都满足sg不为0对于一个sg不为0的顶点，必定存在一个后继满足sg为0满足组合游戏性质所有sg为0定点对应p点，sg大于0顶点对应n点,sprague-grundy函数意义,每个sg值对应nim游戏每堆石子的初始数量将所有sg值异或，类同于将nim游戏的所有初态异或sg定理（sprague-grundytheorem）：g(g)=g(g1)g(g2)g(gn)。游戏的和的sg函数值是它的所有子游戏的sg函数值的异或。,取(m堆)石子游戏,题目大意：1、m堆石子,两人轮流取2、只能在1堆中取任意个.取完者胜.先取者负输出no.先取者胜输出yes.然后输出先取者第1次取子的所有方法.,分析,标准第三类取石子用异或进行判断，由异或基本性质（aa=0）求出每个点的p点，依次比较即可,fibonacciagainandagain,题目大意：1、这是一个二人游戏;2、一共有3堆石子，数量分别是m,n,p个；3、两人轮流走;4、每走一步可以选择任意一堆石子，然后取走f个；5、f只能是菲波那契数列中的元素（即每次只能取1，2，3，5，8等数量）；6、最先取光所有石子的人为胜者；假设双方都使用最优策略，请判断先手的人会赢还是后手的人会赢。,分析,求sg值的问题求sg算法：1.直接dfs2.外加数组法（效率更高）,直接dfs算法,intk,a101;/k为节点数,a数组为减数集合intf10001;/f数组用来存储所有节点的sg值,初值为-1intmex(intp)/mex为求sg的函数inti,t;boolg101=0;/定义布尔数组，初值为0for(i=0;ik;i+)t=p-ai;/t为p当前遍历的后继if(t0)/后继最小是0break;if(ft=-1)/如果这个点的sg还没被赋值过ft=mex(t);/就去查找这个点的sggft=1;/布尔数组中赋这个sg值为1for(i=0;i+)/遍历布尔数组从0开始if(!gi)/当搜索到某点未赋sg值时，mex函数所求的sg值即为此点returni;,外接数组法,intk,a101;/k为节点数，a为减数集合intf10001,num10001;/f存储sg值，num标记sg值是否存在sg0=0;/0为终结点，sg0为0for(i=1;i=0numsgi-aj=i;/i-aj的sg值用num标记for(j=0;j1110-p010001000111000000000011若双方都用最优策略，那么先行者是否有取胜方法。,游戏演示,分析,由于每组游戏只有一个棋盘，所以无需考虑时间问题直接dfs求sg即可,anewtetrisgame(2),题目大意：1、t个n行m列棋盘2、在棋盘上有些格子是无效的3、双方轮流进行游戏，将22的方块放入任意棋盘（方块不能放在不可用的格子上，也不能放在已经放置方块的地方）4、谁不能再放方块，为负若双方都用最优策略，那么先行者是否有取胜方法。,分析,上题的加强版。由于每组都有多个棋盘，所以一定要考虑时间问题直接dfs求sg必然超时优化策略：1、将原棋盘划分为几个连通区域分别求sg再异或2、由于是有向带环图，所以dfs时要判重3、利用哈希表进行优化,划分连通区域,相当于将一个棋盘划分为几个棋盘，分别求sg时，搜索空间大大减少，效率有所提升,digitaldeletions,题目大意：1、给出位数为1-6的数字字符串2、双方轮流对字符串进行变换3、有两种变换策略：（1）可将1-9变为比它小的数字（2）可将0和0之后所有数字擦除例如：301可变为201、101、001、300或34、将最后一个数字擦除者为胜求先行者是否有必胜策略。,分析,一般组合游戏问题，方法就是找到1-1000000所有p点要注意0xxxxx和xxxxx并不同，但若首位为0则必胜，所以可以拿出去单独讨论。这样就可以将1-6位的所有状态存入一个1000000的数组中了此题求p点主要有两种思路，判断法和筛法（类似于求素数算法）判断法为从小到大依次判断当前值所能变换为的值是否存在p点，若存在则此点为n，否则为p。此方法要进行重复查找，效率较低，写起来也