全国统一热线:

400-123-4567

澳门金沙真人在线

news

  
澳门金沙真人在线

当前位置:主页 > 澳门金沙真人在线 >

捡石子游戏、 Wythoff 数表和一切的 Fibonacci 数列

2020-08-31 15:17

让我们来玩一个游戏。把某个国际象棋棋子放在棋盘上,两人遵循棋子的走法,轮流移动棋子,但只能将棋子往左方、下方或者左下方移动。谁先将棋子移动到棋盘的最左下角,谁就获胜。如果把棋子放在如图所示的位置,那么你愿意先走还是后走?显然,答案与我们放的是什么棋子有关。

这个游戏对于兵来说是没有意义的。在如图所示的地方放马或者放象,不管怎样都无法把它移动到棋盘的最左下角,所以我们也就不分析了。因此,我们只需要研究王、后、车三种情况。

在国际象棋中,车每次可以横着或竖着走任意多格。在上述游戏中,受到规则的限制,车每次只能向左或者向下走任意多格。如果问题中的棋子是车,答案就非常简单了:你应该选择先走。你应该直接把车移到棋盘对角线上的位置(如左图所示),然后不管对方怎么走,你都把它移回到棋盘的对角线上。这样,你就能保证必胜了。

在国际象棋中,王每次可以横着、竖着或者斜着走一格。在上述游戏中,受到规则的限制,王每次只能向左、向下或者向左下方走一格。如果问题中的棋子是王,分析出问题的答案也不算太难:你应该选择先走。你应该直接把王移到棋盘的“奇格”里(如右图所示),然后不管对方怎么走,你都可以把它再次移到某个“奇格”里。这样,你就能保证必胜了。

在国际象棋中,皇后每次可以横着、竖着或者斜着走任意多格。在上述游戏中,受到规则的限制,皇后每次只能向左、向下或者向左下方走任意多格。如果问题中的棋子是皇后,那么你应该选择先走还是后走呢?这次,问题就没那么简单了。

这个“挪动皇后”的游戏是由 Rufus Isaacs 在 1960 年左右提出来的。给定皇后在棋盘上的初始位置,如何判断出谁有必胜策略呢? Isaacs 给出了一个分析方法。

首先,第一行上的所有位置,第一列上的所有位置,以及对角线上的所有位置,都能一步直接走到棋盘的最左下角。我们可以从最左下角的位置出发,画出三条射线,把这些位置全都划掉。如果皇后位于被划掉的位置上,那么先走的人就会获胜。此时,棋盘上出现了两个死角。如果皇后在这两个地方,先走的人不得不把皇后挪到刚才被划掉的位置上,因而后走的人就必胜了。因而,从这两个地方出发,画出三条射线,被划掉的位置又是先走的人就会获胜的位置,先走的人只需要把皇后挪到这两个地方即可。此时,棋盘上又会出现两个新的死角,它们又是后走的人必胜的位置……不断这样递推下去,我们就能分析出,皇后在哪些地方时先走的人必胜,皇后在哪些地方时后走的人必胜。之前我们曾问,当皇后位于标有 × 的格子时你应该选择先走还是后走,现在我们就知道答案了:你应该后走才对。

那么,在“挪动皇后”的游戏中,哪些位置是后走的人必胜的位置呢?

画出更大的棋盘,将刚才的操作再多重复几次后,我们看见了一个非常明显的规律:这些位置大致形成了两条直线。再仔细观察,你会发现,每行每列里恰好有一个这样的位置。有没有什么公式不用递推就能找出这些位置呢?它们为什么会形成这么两条直线呢?为什么每行每列里有且仅有一个这样的位置呢?看来,这里面还有很深的水。

令 Isaacs 万万没有想到的是,这个游戏虽然是他发明的,但由此引申的问题却已经被前人解决了。 1907 年,荷兰数学家 Willem Abraham Wythoff 提出了一个双人对弈游戏,后来人们把它叫作 Wythoff 游戏。游戏规则是这样的。地上有两堆石子,其中一堆有 m 个石子,另外一堆有 n 个石子。两名玩家轮流取走石子,规定每次要么从其中一堆石子中取走任意多个石子,要么从两堆石子中取走相同数量的石子。等到谁没有石子可取了,谁就输了。也就是说,取到最后一个石子的玩家获胜。 Martin Gardner 认为, Wythoff 本人甚至也不是这个游戏最早的发明者——其实中国很早就有了这个游戏,人们把它叫作“捡石子”。

容易看出, Wythoff 游戏和“挪动皇后”是完全等价的。把棋盘从下到上各行依次标为 0, 1, 2, 3, …,把棋盘从左到右各列依次标为 0, 1, 2, 3, …,那么皇后移动时坐标变化的规则,正好与 Wythoff 游戏中两堆石子数量变化的规则是相同的。而两个游戏的目标也是相同的:谁先将游戏状态变为 (0, 0) ,谁就获得胜利。因此,这两个游戏完全等价。

全国统一热线

400-123-4567
+地址:广东省广州市天河区88号
+传真:+86-123-4567
+邮箱:admin@baidu.com
微信平台

微信平台

手机官网

手机官网