Gar*_*ees 20
我认为minimax不是点和盒算法的最佳选择.关于这个游戏的完整故事,你真的需要阅读Elwyn R. Berlekamp的书" The Dots and Boxes Game:Sophisticated Child's Play "一书,但我会在这里给你一个简短的总结.
Berlekamp做了许多有力的观察.第一个是双交叉策略,我假设你知道(它在游戏的维基百科页面中描述).
第二个是长链的平价规则.这是关于大多数精心打造的游戏的三个事实:
- 长链将在游戏结束时播放.
- 除了最后一个链外,每个链中都会有一个双十字.
- 首先必须在任何长链中进行比赛的球员都会输掉比赛.
加上你开始的点数加上双十字数的约束,等于游戏中的回合数.因此,如果有十六个点开始,并且有一个双十字,则将有十七个回合.(在大多数游戏中,这意味着第一个玩家将获胜.)
这极大地简化了对游戏中期位置的分析.例如,考虑这个位置有16个点和11个移动(问题3.3来自Berlekamp的书).这里最好的举动是什么？
好吧,如果有两个长链,那么将有一个双十字架,游戏将在另外六个动作(16 + 1 = 11 + 6)之后结束,并且移动的玩家将会失败.但是如果只有一条长链,则不会有双交叉,并且游戏将在另外五次移动后结束(16 + 0 = 11 + 5)并且移动的玩家将获胜.那么玩家怎样才能确保只有一条长链呢？唯一获胜的举动牺牲了两个盒子:
Minimax会发现这一举动,但需要做更多的工作.
第三个也是最有力的观察是点和盒子是一个公正的游戏:可用的移动是相同的,无论轮到谁发挥,以及在游戏过程中出现的典型位置(即包含长链的那些)盒子)它也是一个普通的游戏:最后一个获胜的玩家.这些属性的组合意味着可以使用Sprague-Grundy理论静态分析位置.
以下是使用Berlekamp的书中的图25来说明这种方法有多强大的例子.
这个位置有33个可能的动作,一个精心打造的游戏持续大约20个动作,所以如果minimax在合理的时间内完成分析是可行的,我会感到惊讶.但该位置有一条长链(上半部分的六个方块链),因此可以静态分析.该位置分为三个部分,其值为nimbers:
这些nimbers可以通过动态编程在时间O(2 n)中计算剩余n个移动的位置,并且您可能希望缓存许多常见小位置的结果.
Nimbers使用exclusive或者添加:**1 +*4 +*2 =*7.因此,唯一的获胜动作(将nim-sum减少到*0的动作)是将*4改变为*3(使得位置sum为*1 +*3 +*2 =*0).三个虚线红色动作中的任何一个都获胜:
编辑添加:我知道这个摘要并不真正构成一个算法,并留下了许多未回答的问题.对于一些答案,你可以阅读Berlekamp的书.但是在开幕式方面存在一些差距:链计数和Sprague-Grundy理论实际上只适用于中期和末期.对于开场你需要尝试新的东西:如果是我,我会尝试尝试蒙特卡罗树搜索,直到可以计算链.这项技术为Go游戏创造了奇迹,也可能在这里很有效率.
这个游戏是零和游戏,所以我建议使用min-max算法.这种算法被深蓝色用于在国际象棋中赢得卡斯帕罗夫.
创建启发式函数,评估游戏的每个状态,并将其用作min-max算法的评估函数.
您还可以使用alpha-beta prunning来提高min-max .
min-max的想法是穷尽地搜索所有可能的移动 [通常达到某个深度,因为你需要过去的状态是指数的深度],并选择最佳移动,假设你的对手也是做出最好的举动.
PS
赢得游戏是首要任务:算法效率并不重要.
它们紧密连接在一起,因为您的算法效率越高,您就能够检查可能的解决方案,直到更好的深度,并且您将获得更多的机会.请注意,在无限时间内,您可以浏览整个游戏树,并从每个游戏状态中获得一个获胜策略.然而 - 探索整个游戏树可能是不现实的.
- @CaseyPatton听起来很复杂,但它可以非常简单.您所需要的只是一个评估您在给定游戏配置中的位置的功能.它可以是你的盒子数量减去对应盒子的数量.然后从您的位置构建可能的移动并计算最大化您的位置质量的路径.然后走这条路.一旦你有一个简单的实现,你应该尝试改进状态评估函数,并尝试优化你的树,以避免计算无用的pathes. (3认同)
- @CaseyPatton:那么你将有100%的概率输给一个执行此操作的程序,除非这个游戏有一个已知的启发式方法,它完美地决定了最佳游戏.即使是强力搜索意味着这样做. (2认同)
- @CaseyPatton:这实际上是所有零和游戏中最好和最常用的算法.**现在代理之间的差异是使用的启发式方法,而不是使用或不使用**.另外,我相信你可以在python上找到它的现有实现,并且实现min-max算法并不是那么难. (2认同)
小智 5
我认为Gareth上面的答案非常好，但只是要补充（我没有任何声誉可以添加评论），根据以下内容，点和框已被证明（至少有草图）是 np-hard 的： arxiv。 org/pdf/cs/0106019v2.pdf
我写了一个 javascript 版本的点和框，试图结合上面提到的策略dotsandboxes.org。它不是最好的（尚未包含 Gareth 提到的所有技术）但图形很好，它击败了大多数人和其他实现:) 请随意查看代码，还有一些其他链接人的游戏版本，你可以训练你的游戏。
| 归档时间： |
|
| 查看次数： |
11031 次 |
| 最近记录： |