简单的组合博弈游戏.ppt

《简单的组合博弈游戏.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、算法与程序设计实训组合博弈游戏湖南涉外经济学院计算机科学与技术学部邹竞组合博弈游戏的概念和特点组合博弈游戏应满足以下性质：1.有两个游戏者。2.有一个可能的游戏状态集。这个状态集通常是有限的。3.游戏规则指定了在任何状态下双方的可能的走步和对应的后继状态集。如果在任意状态下双方的走步集合是相同的，那么说游戏是公平的(impartial)，否则是不公平的(partizan)。象棋是不公平的，因为每个人只能移动自己的子。4.两个游戏者轮流走步。5.当到达一个没有后继状态的状态后，游戏结束。在普通游戏规则(normalplayrule)下，最后一个走步

2、的游戏者胜；在misµere游戏规则下，最后一个走步的游戏者输。如果游戏无限进行下去，我们认为双方打平，但通常我们会附加规定：6.不管双方怎么走步，游戏总能在有限步后结束。其他规则包括：不允许随机走步（不能扔色子或者随机洗牌），且必须信息完全的（如隐藏走步是不允许的），有限步结束时不能产生平局。在本节中，我们只考虑公平游戏，并且通常只考虑普通游戏规则（最后走步的胜）。和一般的双人零和博弈不同的是，这里的博弈游戏是特殊的：它们很好的数学特性，使得我们能够找到可判定输赢的数学策略，而不需要进行状态空间的搜索。P状态和N状态：假设双方都采取最明智的策略

3、，则对于一些状态，刚完成走步的游戏者(PreviousPlayer)一定胜利，而对于其他状态，下一个走步的游戏者(NextPlayer)一定胜利。把两种状态称为P状态(Pposition)和N状态(Nposition)，且有以下关系：1.所有终止状态是P状态2.能一步到达P状态的状态为N状态3.每一步都将到达N状态的状态为P状态我们也可以把P状态称为必败态，N状态称为必胜态，含义是直观的。以上关系实际上给出了一个递推计算所有状态的P-N标号的算法。只要状态集构成一个n个结点m条边的有向无环图(directedacyclicgraph,DAG)，则

4、可以按照拓扑顺序在O(m)时间内计算所有状态的标号。可问题在于这样的状态往往有很多，能否通过数学方法直接判断一个状态是P状态还是N状态呢？常见的组合博弈模型，有若干种，但也有很多情况，不能套用这些模型，要具体情况具体分析。博弈树模型假设甲乙双方在进行这种二人游戏，从唯一的一个初始局面开始，如果轮到甲方走棋，甲方有很多种着法，但只能选择一个着法进行走棋。甲方走棋后，局面发生了变化，轮到乙方走棋，乙方也有很多种着法，但也只能选择一个着法。从初始局面开始，甲乙两方交替走棋，局面的变化可以表示成一个树形结构，这就是博弈树（game-tree）。一种井字棋

5、的博弈树，如图所示。每个局面可以用博弈树的一个结点来表示，某方获胜、失败或双方平局的结点构成了叶子结点。甲乙双方在选择着法时，不仅要考虑己方每一种着法的好坏，同时也要考虑对方会针对自己的每一种着法采取怎样的着法来应对。显然，博弈树是一种特殊的与或树，“或”结点和“与”结点是逐层交替出现的。己方扩展的结点之间是“或”关系，对方扩展的结点之间是“与”关系。Bash'sGame（巴什博弈）所谓巴什博弈，是ACM题中最简单的组合游戏，大致上是这样的：只有一堆n个物品，两个人轮流从这堆物品中取物，规定每次至少取1个，最多取m个，最后取光者得胜。显然，如果n

6、=m+1，那么由于一次最多只能取m个，所以，无论先取者拿走多少个，后取者都能够一次拿走剩余的物品，后者取胜。因此我们发现了如何取胜的法则：如果n=(m+1)*r+s，(r为任意自然数，s≤m)，即n%(m+1)!=0，则先取者肯定获胜。巴什博弈还是很好理解的，以你是先手的角度考虑。你想把对手给弄垮，那么每一局，你都必须构建一个局势，这个局势就是每次都留给对手m+1的倍数个物品。因为，如果n=(m+1)r+s，(r为任意自然数，s≤m),那么先取者要拿走s个物品，如果后取者拿走k(≤m)个，那么先取者再拿走m+1-k个，结果剩下(m+1)(r-1)

7、个,以后保持这样的取法，那么先取者肯定获胜。总之，要保持给对手留下(m+1)的倍数，就能最后获胜。这个游戏还可以有一种变相的玩法：两个人轮流报数，每次至少报1个，最多报10个，谁能报到100者胜。好运！该死的英语四级！ProblemDescription大学英语四级考试就要来临了，Kiki和Cici在紧张的复习之余喜欢打牌放松。“升级”？“斗地主”？那多俗啊！作为计算机学院的学生，Kiki和Cici打牌的时候可没忘记专业，她们打牌的规则是这样的：1、总共n张牌；2、双方轮流抓牌；3、每人每次抓牌的个数只能是2的幂次（即：1，2，4，8，16…）4

8、、抓完牌，胜负结果也出来了：最后抓完牌的人为胜者；假设Kiki和Cici都是足够聪明并且每次都是Kiki先抓牌，请问谁能赢呢？Inpu