尼姆博弈为什么要用二进制

JavaScript021

尼姆博弈为什么要用二进制,第1张

由于物品的数量总在严格减小,此博弈是有限的。尼姆博弈是一个两人博弈,2名玩家轮流从数堆物品中拿取一定数量的物品,每次拿取时先选择某一堆,再从中拿取任意数量个物品,至少拿1个,至多将这一堆物品全部拿走,不能不拿。尼姆博弈由于物品的数量总在严格减小,此博弈是有限的,所以用二进制。且玩家可以知晓对手的行动,双方均具有完全信息;且博弈中不含运气成分;那么由策梅洛定理可知,先手方或后手方有必胜策略。

抢21游戏规则必赢方法:

让别人先开始喊,并且你每次都报到3的倍数。

别人先喊,别人喊一个数字,你喊两个。

两个人轮流说,谁先说出21谁就输,后手是必赢的奥秘如下:

只要看明白了,后手必赢。先手只能有三种说法,也就是1,1 2,1 2 3,对应的后手只要说2 3 4,3 4,4即可。只要自己说的最后一个数字是4的倍数,那就一定可以由自己说出20,所以后手是必赢的。

抢21其实就是巴什博弈的一个玩法,类似的还有威佐夫博弈和尼姆博弈等博弈玩法。

巴什博弈(Bash game)是一个双人博弈:有一堆总数为n的物品,2名玩家轮流从中拿取物品。每次至少拿1件,至多拿m件,不能不拿,最终将物品拿完者获胜。

巴什博弈除了两人轮流按一定数量拿物品,先拿完者胜的规则,还有一种更加常见易操作的等价形式:两人轮流报数,先报数的必须报1到m之间的正整数(包含1或m),后面所报数则必须比前一个人所报数大1到m(包含1或m),先说出n者获胜。

此时可以想象我们将n个物品编号1至n,每人的报数相当于取走该编号以下(含该编号)的未被取走的所有物品,先报到n者相当于先取完物品者。由此可知,这两种形式是等价的。

巴什博弈是一种较为简单的减法博弈(Subtraction game),减法博弈的共同特征为玩家轮流从某一总数(对应n件物品)中减去某个数值(对应拿取物品),所减去的数值限定在某个集合中(对应1到m),先将数值减为0者(先拿完物品者)获胜。

由于物品的数量总在严格减小,此博弈是有限的;且玩家可以知晓对手的报数,双方均具有完全信息;且博弈中不含运气成分;那么由策梅洛定理可知,先手方或后手方有必胜策略。