尼姆游戏,你玩过吗?

2023年11月2日11:27:4878

据说,遇到不可调解的分歧的时候,为了作出决定,人们的首选是猜拳,其次是抛硬币。

(一)尼姆游戏

既然说到银币,那么有一种游戏非常有名,叫“尼姆游戏”。这个游戏的玩法很简单,先将硬币分成几堆,然后两个人轮流取硬币,每次取硬币只能从同一堆中取出,枚数不限,但至少要取一枚,取走最后一枚硬币的就是赢家。其实,不过是银币,你也可以将其改变为任何东西,去走最后一件东西的就是赢家。

尼姆游戏是一种两个人玩的回合制数学战略游戏。游戏者轮流从一堆棋子(一共有好几堆,一次只能从其中一堆拿。)(或者任何道具)中取走一个或者多个,最后不能再取的就是输家。当指定相应数量时,一堆这样的棋子称作一个尼姆堆。

举个例子,比如说,甲乙二人玩这个游戏,开局有三堆硬币,分别有3、5、7枚。甲先取走第二堆中的4枚,每堆剩下3、1、7枚,接下来乙取走第三堆的所有硬币,剩下的就分别是3、1、0枚。

接下来甲只要取走第一堆中的2枚,留给乙的就是各自有一枚硬币的两堆。这时,乙只能取走其中一堆,而甲只需要拿走剩下的一堆就能获胜。

从这个例子能看出来,尼姆游戏中没有运气的成分,每位玩家都能看清整个局势,而玩家能采取的行动也是一样的,区别只是在于一位先攻而另一位后守。

在博弈论这一研究游戏取胜策略的数学分支中,这样的游戏被称为无偏博弈。也正是博弈论中的一个定理,赋予了尼姆游戏一个非常特殊的地位:任意给定一个无偏博弈,它都对应一个推广了的尼姆游戏的特例。

可以说,尼姆游戏中包含了所有的无偏博弈,比如象棋、围棋等,尽管这些更为复杂的游戏,它们对应的尼姆游戏特例中可能有很多堆硬币,每堆硬币可能会很多,甚至有无穷枚,需要用更为抽象的“序数”来描述。

(二)无偏博弈

在组合博弈论里,无偏博弈是一类任意局势对于游戏双方都是平等的回合制双人游戏。这里平等是指所有可行的走法仅仅依赖于当前的局势,而与现在正要行动的是那一方无关。换句话说,两个游戏者除了先后手之外毫无区别。

此外,它们还要满足一些组合游戏的基本条件:

①完全信息,所有游戏者都能看到整个局势。这排除了类似桥牌一类的游戏。

②无随机行动。所有行动都确定性地将目前局势转变到下一个局势。

③在有限步行动之后按照规则游戏必将终止,此时有唯一的一方成为赢家。

即使常见的游戏如象棋、围棋、五子棋等能符合以上三条规定(可能需要附加一些防止无限循环的规则),它们都不是无偏博弈,因为它们的棋子都有颜色,双方的走法因而要造成局势的不同变化。但是如果定义五子棋的一个变种:双方都采用同样颜色的棋子,先连成5子一线算胜利,那么这个变种是无偏博弈。

根据斯普莱格–格隆第定理,每个无偏博弈的特定局势都对应着一个尼姆数。这一定理是对无偏博弈进行分析的主要工具。

斯普莱格(R.P.Sprague)和格隆第(P.M.Grundy)独立地证明了一切无偏博弈(从任何一个局势出发,双方可以采取完全相同的行动,也就是说棋盘上没有颜色的区分)都等价于一个特定大小的尼姆堆。但这里的尼姆堆包含的棋子数量可以是无穷的。事实上,它可以是任何序数。游戏规则很简单,游戏双方轮流取 1 枚或多枚硬币(只能在同一行),谁拿到最后一枚就算赢。

  • 特别声明:本文由互联网用户自行发布,仅供参考,不作为投资建议。股市有风险,炒股需谨慎!
  • 本文链接:https://www.gpboke.com/34270.html