玩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。

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

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

相关推荐

  • django网站实例:使用Django构建功能强大的网站

    Django网站实例是一个简单的网站,它使用Django框架来构建,并且可以让用户在网站上进行注册、登录、浏览、搜索等操作。以下是一个Django网站实例的代码示例:…

    2024-03-16 13:15:46
    0 64 93
  • golang 编译构建高效可靠的应用程序

    Golang 编译是指将源代码编译成可执行文件的过程。Golang 使用 go tool 来完成编译,它可以将源代码编译成二进制文件,也可以将源代码编译成共享库文件。…

    2024-04-24 15:46:11
    0 58 21
  • To goo:跟随鼠标指针的 Goo球(gooball)

    关于To goo的问题,在gooball中经常遇到,你知道这个网站上显示的鼠标跟随效果是如何制作的吗?https://pygar.co/en…

    2022-11-28 12:26:51
    0 83 18
  • 验证码接口程序:django简单验证码一直说“无效验证码”

    关于验证码接口程序的问题,在jetleech中经常遇到,我已经按照文档给出的步骤,首先,它工作得很好,但是,我不知道任何错误,它使invalid Captcha。…

    2022-12-09 15:07:39
    0 63 55
  • 旺旺代码生成器:XSD代码生成器(asheesh goja)

    关于旺旺代码生成器的问题,在asheesh goja中经常遇到,是否有任何代码生成器将采用格式良好的 XML 文档,并根据 XML 文档的结构写出 XSD 模式?…

    2022-11-30 13:28:32
    0 91 18
  • Goo s:跟随鼠标指针的 Goo球(gooball)

    关于Goo s的问题,在gooball中经常遇到,你知道这个网站上显示的鼠标跟随效果是如何制作的吗?https://pygar.co/en…

    2022-11-29 07:08:35
    0 34 48
  • 证据保全的程序:证据 Argos-在报告之前执行一个程序

    关于证据保全的程序的问题,在evisions argos中经常遇到,我们正在将一些报表从 Oracle Reports 迁移到 Evisions Argos。在 Oracle 报表中,有一个“Before Report”触发器,该触发器将在报表查询实际运行之前被触发。这使我们能够在查询之前填充一些表,并将整个业务逻辑保留在报表本身中。是否可以在 Argos 中执行类似的操作?在运行报表查询之前,您可以在哪里执行 PL / SQL 代码?…

    2022-12-03 07:27:05
    0 74 63
  • 如何在 Mandango中创建自动增量字段

    我在我的项目中使用 mandago ODM for mongodb。…

    2022-11-23 07:05:46
    0 22 83

发表评论

登录 后才能评论

评论列表(35条)