当前位置:   article > 正文

博弈论 总结_博弈算法停止的条件

博弈算法停止的条件

这几天接触了下博弈论,感觉算法在生活中的应用无处不在

1.组合博弈

条件:

1)两个玩家,双方轮流操作

2)博弈局面的状态是一个集合,通常是有限的

3)规则制定玩家从一个局面到另外一个局面的合法步骤

4)当无法操作时候,博弈结束,常规情况认为无法操作的一方输,但在misere规则下,无法操作的为赢(其实无多大影响,改变最后的输出条件即可)

5)博弈可以在有限步数结束

必败点(P点) :前一个选手(Previous player)将取胜的位置称为必败点。(当你走到此点的时候,如果你无论怎么都输,这个点就叫做必败点。)
必胜点(N点) :下一个选手(Next        player)将取胜的位置称为必胜点。(当你走到此点的时候,以聪明的走法去走,可以赢对方)



算法实现:
步骤1:将所有终结位置标记为必败点(P点);(终结位置指的是不能将游戏进行下去的位置)
步骤2:将所有一步操作能进入必败点(P点)的位置标记为必胜点(N点)
步骤3:如果从某个点开始的所有一步操作都只能进入必胜点(N点) ,则将该点标记为必败点(P点) ;
步骤4:如果在步骤3未能找到新的必败(P点),则算法终止;否则,返回到步骤2。

题目链接:
HDU 1517 http://blog.csdn.net/deepseazbw/article/details/76783359(模板题目)

POJ  2599http://blog.csdn.net/deepseazbw/article/details/77186290(记忆化搜索P N态)

POJ  2068http://blog.csdn.net/deepseazbw/article/details/77334045(记忆化搜索)



2.Nim博弈

Nim游戏是组合游戏(Combinatorial Games)的一种,准确来说,属于“Impartial Combinatorial Games”(以下简称ICG)。满足以下条件的游戏是ICG(可能不太严谨):

1、有两名选手;

2、两名选手交替对游戏进行移动(move),每次一步,选手可以在(一般而言)有限的合法移动集合中任选一种进行移动;

3、对于游戏的任何一种可能的局面,合法的移动集合只取决于这个局面本身,不取决于轮到哪名选手操作、以前的任何操作、骰子的点数或者其它什么因素;

 4、如果轮到某名选手移动,且这个局面的合法的移动集合为空(也就是说此时无法进行移动),则这名选手负。根据这个定义,很多日常的游戏并非ICG。例如象棋就不满足条件3,因为红方只能移动红子,黑方只能移动黑子,合法的移动集合取决于轮到哪名选手操作。


通常的Nim游戏的定义是这样的:有若干堆石子,每堆石子的数量都是有限的,合法的移动是“选择一堆石子并拿走若干颗(不能不拿)”,如果轮到某个人时所有的石子堆都已经被拿空了,则判负(因为他此刻没有任何合法的移动)。

这游戏看上去有点复杂,先从简单情况开始研究吧。如果轮到你的时候,只剩下一堆石子,那么此时的必胜策略肯定是把这堆石子全部拿完一颗也不给对手剩,然后对手就输了。如果剩下两堆不相等的石子,必胜策略是通过取多的一堆的石子将两堆石子变得相等,以后如果对手在某一堆里拿若干颗,你就可以在另一堆中拿同样多的颗数,直至胜利。如果你面对的是两堆相等的石子,那么此时你是没有任何必胜策略的,反而对手可以遵循上面的策略保证必胜。如果是三堆石子……好像已经很难分析了,看来我们必须要借助一些其它好用的(最好是程式化的)分析方法了,或者说,我们最好能够设计出一种在有必胜策略时就能找到必胜策略的算法




2道Nim博弈的题目:

HDU 1730  http://blog.csdn.net/deepseazbw/article/details/77046444(Nim博弈的分析转化)

HDU 1907http://blog.csdn.net/deepseazbw/article/details/76982719(模板题目)

3.威佐夫博弈

有两堆各若干个物品,两个人轮流从某一堆或同时从两堆中取同样多的物品,规定每次至少取一个,多者不限,最后取光者得胜。
这种情况下是颇为复杂的。我们用(a[k],b[k])(a[k] ≤ b[k] ,k=0,1,2,...,n)( a[k] 其中 k 为下标 )表示两堆物品的数量并称其为局势,如果甲面对(0,0),那么甲已经输了,这种局势我们称为奇异局势。前几个奇异局势是:(0,0)、(1,2)、(3,5)、(4,7)、(6,10)、(8,13)、(9,15)、(11,18)、(12,20)。
奇异局势:针对最后去光者胜利,先手必输。
判断一个局势是否为奇异局势?公式如下:
a[k] = [k(1+√5)/2](a[k]这个方括号为下标运算符,[k(1+√5)/2]这个方括号为取整运算符),b[k] = a[k] + k 。奇妙的是其中出现了黄金分割数(1+√5)/2 = 1.618...因此,由a[k],b[k]组成的矩形近似为黄金矩形,由于2/(1+√5)=(√5-1)/2,可以先求出 j = [a(√5-1)/2],若 a = [ j(1+√5)/2],那么a = a[j],b[j] = a[j] + j,若不等于,那么a = a[j]+1,b = a[j] + j + 1,若都不是,那么就不是奇异局势。然后再按照上述法则进行,一定会遇到奇异局势。
判断方法:min(a,b)与a[k]是否相等,若相等则为奇异局势,先手输(k=|a-b|,a[k] =  [ k(1+√5)/2],) 
题目:

http://blog.csdn.net/deepseazbw/article/details/77160818 (威佐夫模板题)
4.阶梯博弈
阶梯的序号如图所示,地面表示第0号阶梯。每次都可以将一个阶梯上的石子向其左侧移动任意个石子,没有可以移动的空间时(及所有石子都位于地面时)输。
阶梯博弈可以看成奇数阶梯的Nim博弈。
原因:假设我是先手,第一次移动按照Nim博弈的规则移动,如果对手移动奇数阶梯的石头,我们接着按照Nim博弈的规则移动奇数阶梯的石头,如果对手移动的是偶数阶梯的石头(到达了下一个奇数阶梯的石头),我则将对手移动的石头接着往下移动到下一个偶数阶梯。

题目:
POJ 1704 http://blog.csdn.net/deepseazbw/article/details/77245590(阶梯博弈的模板题)

5.联合组合博弈
n个组合博弈联合起来的博弈
例:POJ 2599是一个棋子在有向无环树上判断输赢(组合博弈), POJ 2425确实多个棋子在无向无环树上判断输赢(联合组合博弈)。
组合博弈可以直接得到SG值,而联合组合博弈由于数据量较大,maybe很多数据要重复利用,所以会打表存储SG值。
著名的SG定理:(很多的博弈论题目都会用到它)





题目:

POJ 2599http://blog.csdn.net/deepseazbw/article/details/77186290(理解组合博弈)

POJ 2425http://blog.csdn.net/deepseazbw/article/details/77189612(理解联合组合博弈)

HDU 1848http://blog.csdn.net/deepseazbw/article/details/77148400(SG定理的模板题目)

6.直接总结规律

对于部分题目,直接总结规律,要比利用上述方法简单暴力

题目:

抢n游戏 http://blog.csdn.net/deepseazbw/article/details/56485339

三子连 http://blog.csdn.net/deepseazbw/article/details/75807701

POJ 1740http://blog.csdn.net/deepseazbw/article/details/77258057

POJ 2484http://blog.csdn.net/deepseazbw/article/details/77161112





声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/小蓝xlanll/article/detail/471377
推荐阅读
相关标签
  

闽ICP备14008679号