Support Lasker Morris rules #221
Labels
enhancement
New feature or request
Comments
|
摘要：我们描述了一种用于解决拉斯克-莫里斯（Lasker Morris）游戏的回溯算法，并展示了最重要的博弈论结果。该游戏由埃马努埃尔·拉斯克（Emanuel Lasker）发明，源于“九子棋”（Nine Men’s Morris）游戏。它试图为其前身赋予更多的战略潜力，以避免平淡无味的游戏玩法，同时不对游戏规则进行过于剧烈的改动。
近年来，一些重要的战略游戏已经完全得到解决。例如，Awari游戏由John W. Romein和Henri E. Bal解决[J.W. Romein, H.E. Bal, 2002]。Qubic由Victor Allis解决[V. Allis, 92]，Connect Four则由Victor Allis [V. Allis, 88]和James Allen [J. Allen, 89]分别解决。有趣的是，这两种解决Connect Four的方法采用了互补的方法：Allis采用了基于知识的方法，而Allen则使用了暴力深度优先搜索。Nine Men’s Morris游戏由Ralph Gasser使用狭窄的alpha-beta数据库进行开局，以及完整的DTC（depth to conversation）数据库进行中局和残局解决[R. Gasser, 1994]。在其他游戏中，如国际象棋[K. Thompson, 1986]和跳棋游戏[J. Schaeffer, 1997]，数据库方法被应用于解决重要的残局。 我们描述了一种回溯算法的开发，该算法用于创建一个完整的DTW（depth to win）拉斯克-莫里斯（Lasker Morris）数据库，包含136,476,472,674个位置。
Nine Men’s Morris是一种规则简单的双人桌游。它在14世纪很受欢迎，但更早的版本可以追溯到公元前1400年，棋子少于九个。与其他中世纪游戏一样，多年来演变出了许多不同的规则。拉斯克-莫里斯（Lasker Morris）是由国际象棋世界冠军埃马努埃尔·拉斯克（Emanuel Lasker）（1894年至1921年）发明的。它基于Nine Men’s Morris的规则。他在1931年的著作《Brettspiele der Völker》中描述了他新变体的规则如下（作者翻译）： “一步棋包括在空位上放置一个棋子或将已放置的棋子滑动到相邻的空位，玩家可以做这两者中的任何一个。游戏开始时，手中的棋子数量可以是九个，或者更好是十个。” 图Morris：轮到白方下棋，他手中有两个棋子，黑方还剩下三个棋子。 Nine Men’s Morris（九子棋）游戏在一块方形棋盘上进行，如图1所示。棋盘上有24个点（交叉点），棋子只能沿着标记的线在这些点之间移动。每个点上只能放置一个棋子。玩家开始时各有九个棋子，每位玩家的棋子颜色不同。通常，一个玩家使用白色棋子，另一个玩家使用黑色棋子。与其他游戏不同，棋盘最初是空的。执白棋的玩家先手。在开局阶段，玩家交替在空位上放置棋子。每个玩家都试图让自己的三个棋子连成一条直线，同时防止对手这样做。当玩家有三个棋子连成一条直线时——这被称为“关磨坊”——他可以从棋盘上拿走对手的一个不在磨坊内的棋子。当两位玩家都将所有棋子放在棋盘上后，就可以通过将其从一个方格滑动到相邻的空方格来移动棋子。玩家们不断尝试让自己的三个棋子连成一条直线，这样他们就可以拿走对手的一个不在磨坊内的棋子。一旦一个玩家只剩下三个棋子，他就可以将自己的一个棋子跳到棋盘上的任何空位。 游戏可能以下列方式结束：
还有两个问题需要讨论：
在我们的实现中，我们根据世界九子棋协会的规则，对第一个问题的回答是肯定的，对第二个问题的回答是否定的。九子棋（NMM）和拉斯克-莫里斯（Lasker Morris）之间的区别在于，在拉斯克-莫里斯中，并非所有棋子都必须在最初的几步中放置。放置棋子和滑动棋子的操作可以按任意顺序执行。
图2. 黑方先手。g7xb4、f4（!）是唯一不会输掉游戏的走法。 图3. 白方先手，不允许只进行跳跃。
状态空间 无法到达的位置 对称位置 每个子空间都包含很多对称位置。我们有五条对称轴，但其中一条是多余的，因此我们可以预期状态空间的大小最多可以减少到原来的1/16。构建一个完美解决“对称”问题的函数可能很困难。因此，由于快速计算至关重要，我们只提供了一个半完美的解决方案，该方案将状态空间的大小减少了15.66倍，而不是16倍。计算子空间大小的公式是：24! / [(24-nw)! * nw! * nb!]。考虑到对称位置，我们可以将所有子空间的状态空间从大约2136亿个位置减少到1364亿个位置。 哈希函数 数据库 计算 图7. 当q是输棋时，我们可以将所有尚未评估的q的前驱标记为白方先手n+1步获胜。 这个算法听起来很简单——事实上，对于所有状态空间较小且可以轻松装入当今计算机主内存的游戏来说，计算这样的数据库是一项轻松的工作。拉斯克-莫里斯的状态空间有2134亿个元素。考虑到所有对称性，我们可以将状态空间减少到大约1360亿个不同的位置。为了加快数据库的计算速度，我们必须避免随机磁盘访问。即使每个位置只有一次磁盘访问，也会将计算时间增加到40年以上！（1360亿 * 10毫秒）。在我们的实现中，我们利用数据库由3600个文件组成的事实。这些文件使我们能够使用下面描述的一种非常有效的缓存方法： 在我们的迭代算法中，我们安排了一个遍历所有子空间的循环，以分别查找每个子空间的所有白方先手n+1步获胜的位置。这给了我们一个机会，将受影响的少数子空间完全加载到计算机的主内存中，以避免许多磁盘访问。 接下来，我们将详细描述我们用于计算整个拉斯克-莫里斯数据库的迭代算法。 解决拉斯克-莫里斯（Lasker Morris） 但我们如何确定软件没有错误呢？目前，我们没有正式的证明表明我们创建所有数据库的程序没有错误。但另一方面，在过去三年的测试工作中，我们也没有发现任何异常。这些测试工作包括最近使用Morris-GUI进行的数百场比赛。这个GUI总是应用一层或两层的极小极大搜索来确定每个可能移动的价值。在搜索过程中，它会执行深度检查，以比较存储的原始位置值与每次移动后位置的值。当然，如果游戏能由独立的数据库程序重新计算，那将是非常令人安心的。
迄今为止，拉斯克-莫里斯是一款相对未知的游戏。因此，我们将我们的结果与众所周知的母游戏九子棋（Nine Men’s Morris）进行比较。如果双方都正确地下棋，拉斯克-莫里斯的初始位置是和棋。 图9. 拉斯克-莫里斯中的最大位置。白方先手，171步获胜。 拉斯克-莫里斯是和棋。因此，看看一个错误能有多早发生是很有趣的。图11（12）显示了黑色方早期错误后，棋盘上只有两枚（四枚）棋子时最长的获胜距离。这两个位置在九子棋中是和棋。九子棋中可能出现的最早错误是白方的第二步，即1.c3 f4 2.f2? 图11. 开局位置，白方先手，72步获胜。 图13. 拉斯克-莫里斯获胜距离的分布。 |
|
Crash when exit macOS Edition: |
|
blur issue: d1-d2 可复现 b2 可复现。 |
|
no bestmove |
Move now |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
The difference between NMM and Lasker Morris is that in Lasker Morris not all pieces have to be placed in the very first moves. Placing moves and sliding moves may be executed in arbitrary order.
[ ]The text was updated successfully, but these errors were encountered: