玩Gomoku的好AI策略是什么

我正在写一个游戏,它是Gomoku的一个变体。

我正在写一个游戏,它是Gomoku的一个变体。

想知道是否有人知道游戏的良好 AI 策略。我目前的实现非常愚蠢,需要很长时间 (O (n ^ 3),大约 1-2 秒才能做出动作):

-(void) moveAI {
    //check if the enemy is trying to make a line horizontally, vertically, or diagonally
    //O(n^3 * 3)
    [self checkEnemies];
    //check if we can make a line horizontally, vertically, or diagonally
    //O(n^3 * 3)
    [self checkIfWeCanMakeALine];
    //otherwise just put the piece randomly
    [self put randomly];
}
23

对于 gomoku,已经找到了获胜策略。请参阅本文:L. Victor Allis, H. J. van den Herik, M. P. H. Huntjens, 1993. Go-Moku and Threat-Space Search。当我编写自己的程序时,它对我有很大帮助。这样,您将能够编写非常擅长攻击对手并找到获胜组合的程序。

15

为此类游戏编写 AI 的传统且相当有效的策略是典型的树搜索策略。也就是说,每个板状态在图中形成一个节点,并且在每个节点和状态之间放置一个有向边,这可以通过一次移动来产生。这样,就可以构建一棵树,而根板是一个空节点。然后,以某种巧妙的方式遍历该树,以找到您想要的“好”状态。显然,“好”状态通常是通过函数评估来

您可以添加一个预先计算的早期游戏和最终游戏来加快这些场景,然后依靠一个优化的树遍历启发式游戏。

这样的树遍历算法的实际名称是“Minimax”算法。在 Wikipedia 上查找它,您会看到很多相当不错的材料。有一些提高算法效率的方法,其中最值得注意的是 alpha-beta 修剪,因此请确保您对此有所了解。您可能想看看 connect-four 启发式算法,并决定如何将其应用于游戏中。

另一种优化策略是开发一种启发式方法,该方法优先考虑 minimax 算法应在何处进行更多搜索-通常是通过估计董事会评估函数的某种确定性。

使用此策略,您应该能够在相同的时间内获得不那么愚蠢的 AI。但是,即使在这些“简单”的游戏中,真正真正好的 AI 也需要花费大量精力来构建,并且仍然可能需要 10 秒或更长时间才能使智能动作摆脱困境。另一方面,还有一些聪明的编程技巧,例如在人类对手忙于思考的同时预先计算遍历树!

7

我一直在尝试为同一个程序创建一个算法。

你当然是正确的,你的程序应该做的第一件事,就是检查是否有办法形成 5 并获胜。如果没有,下一步应该是检查你的对手是否可以做到这一点,如果是,那么防御。

您自己玩了多少 gomoku?您对基础知识的掌握程度如何?

好吧,下一步是思考:我们如何到达可以获胜的位置?显然,要赢得胜利,我们必须连续四个。但是我们只是这样连续形成四个:

__________
____XOOOO_
__________

然后对手可以关闭它。

但是如果我们形成“开放四”,就像这样:

__________
____OOOO__
__________

那么对手不能两边都合拢,你就能赢。所以形成一个开放的四是一种获胜的方法。现在问题来了:我们如何形成一个开放的四?当然,如果我们形成“开放的三”,就像这样:

__________
____OOO___
__________

然后对手可以阻止我们:

___________
____XOOO___
___________

我们又回到了起点.

为了获胜,我们可以同时形成两个开放的三人组:

____________
____OOO_____
_____O______
____O_______

现在,如果对手阻止其中一个,我们可以使用另一个来形成一个开放的四个:

____________
_______O____
___XOOO_____
_____O______
____O_______
____________

并赢得:

________O___
_______O____
___XOOO_____
_____O______
____O_______
___X________

在 gomoku 术语中,这被称为 3x3,如果你同时做两个开放的三。

请注意,这三个必须是开放的:你能理解为什么吗?

还有其他获胜的方法:

4x3:您看到获胜的举动以及为什么获胜吗?

____________
__XOOO______
__XXXO______
____OX______
____________

4x4:看到获胜的举动了吗?

____________
__XOOO______
__XXXO______
__OXOX______
___O________
__X_________

这些只是游戏的基础。了解战术可以帮助您思考如何构建 AI,因此您可以对原则进行硬编码。

当然,这只是一个开始。如果你能尝试实现这一点,然后给我反馈,我将不胜感激。

我一直在尝试用 Java 编写程序。你想看看我所做的代码,以便你可以 playtest?它还不是很好,但是你可以从那里得到新的想法。尽管注释和变量名是用爱沙尼亚语编写的..可能很难理解。:(

7

Gomoku 解决了,但是当它在开放位置和有限资源的情况下播放时,它没有解决。

我是Hewer gomoku程序和Gomocup组织者的作者,我可以告诉你,编写好的 Gomoku AI 需要很长时间。Renju 要复杂得多。您可以使用Gomocup接口简化工作并编写“仅”AI。

本站系公益性非盈利分享网址,本文来自用户投稿,不代表码文网立场,如若转载,请注明出处

(921)
如何在Google应用程序脚本中将时间戳“newDate()”格式化为新加坡时区
上一篇
如何在 Google电子表格中添加印度卢比货币符号
下一篇

相关推荐

发表评论

登录 后才能评论

评论列表(67条)