网页游戏盒子源码:解决点和盒子游戏是否可行 (dots boxes)

关于网页游戏盒子源码的问题,在dots boxes中经常遇到, 我试图证明可计算性的游戏是Dots and Boxes。

我试图证明可计算性的游戏是Dots and Boxes

但是,我没有使用定理,而是试图通过创建一个 AI 来做到这一点,该 AI 应该在该游戏中为玩家 1 或玩家 2 提供 100 % 的 winrate。如果不可能创建 100 % winrate AI,那么我的目标是创建一个至少比所有其他 AI 更好的 AI。截至目前,我正在用 PHP 编写所有内容,因为我正在与另一个用脚本语言编写的 AI 竞争。

整个过程是递归的,基本逻辑是:计算所有可能动作的整棵树如果轮到我的 AI,则为 AI 玩家选择最大点数的路线。如果轮到对手的 AI,则为我的 AI 选择最小点数的路线。Aka 计算每个节点的保证点数。

计算完整棵树后,选择保证点数最多的路线。在偶数点上,随机选择。

整个计算过程将花费大约永远在 15x15 板上进行计算,但是现在我要做的是在 3x3 矩阵上进行计算。我将在数据库中存储前 6-8 个移动的最佳移动,以便现在必须再次重新计算它们,这将每个计算的复杂性从 24!更改为 18!。

这整件事可行吗?我计算我的动作的方式有问题吗?有没有更好的方法来做到这一点?

7

这个问题有一个非常大的搜索空间,对于一个 4x4 网格,我们在搜索空间中有 40 个边缘,所以 2 ^ 40 个状态。

解决方案是什么?首先你可以看看 Barker 和 Korf 的工作Solving Dots-And-Boxes。这是这类问题的最新技术(在 2012 年,也许现在,我不确定)。他们使用了经典的 Alpha-Beta 修剪算法和一堆特定问题的解决方案的组合。

您也可以尝试将Monte Carlo Tree Search应用于问题。我不知道这方面的工作,但蒙特卡洛已被证明是成功的围棋游戏(在某种意义上类似于您的问题)。

4

机器学习应该通过消除许多最初结果不好的分支来减少计算时间,它可能需要更多的时间来解决诸如 3x3 板之类的小问题,但是当你开始在更大的板上测试你的算法时,它会更快(我不能肯定地说没有写出两个算法并尝试它们),因为它应该是 t = log(n)函数的一些变体。

例如,使用Reinforcement Learning,它基本上会按照你的建议去做,计算一个巨大的决策树。然而,它会知道一些动作(比如给对手一个盒子的动作)是不好的,它不会浪费太多的时间来计算这些动作。

这是可行的吗?取决于你有多少空闲处理时间。使用一个小网格,直到你写了一个像样的人工智能算法,然后你就可以运行一台机器,看着它自己学习。没有什么比看着你的创作学到一些东西更令人满意的了。这就像生了一个孩子...一个可以在点和盒子上打败你的人。

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

(255)
怎么清楚cookie:JavaScript我怎么能做一个 cookie/+ 1动画
上一篇
编程基本:基本的面向对象编程(object oriented programming java course)
下一篇

相关推荐

发表评论

登录 后才能评论

评论列表(9条)