首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >问答首页 >解决点盒游戏可行吗?

解决点盒游戏可行吗?
EN

Stack Overflow用户
提问于 2015-02-06 14:17:34
回答 2查看 2.7K关注 0票数 3

我试图证明的游戏是点和盒

然而,我没有使用定理,而是尝试创建一个AI,它应该在游戏中为玩家1或玩家2拥有100%的成功率。如果创建一个100%的winrate AI是不可能的,那么我的目标是创建一个至少比其他人工智能更好的AI。到目前为止,我正在用PHP编写所有的东西,因为我也在与用脚本语言编写的另一个AI竞争。

这整件事是递归的,基本的逻辑是:如果是我的AI回合,计算出所有可能移动的整个树,然后为AI玩家选择具有最大点数的路径。如果这是对手的人工智能,然后选择最小的点数为我的人工智能路线。也就是计算每个节点上的保证点数。

在计算完整个树之后,选择具有最高保证点数的路由。在偶数点上,随机挑选。

整个计算过程大概要花费很长时间才能在15x15板上计算,但是现在我要做的就是在3x3矩阵上计算它。我将存储最好的移动前6-8移动在数据库中,以便现在必须重新计算他们,这改变了每次计算的复杂性从24!到18点!

这整件事可行吗?我计算移动的方式有问题吗?有更好的方法吗?

EN

回答 2

Stack Overflow用户

回答已采纳

发布于 2015-02-06 16:56:32

这个问题有一个很大的搜索空间,对于一个4x4网格,我们在搜索空间中有大约40条边和2^40个状态。因此,要解决整个游戏中更大的地图是完全不可能的。

解决办法是什么?首先,您可以查看Barker和Korf的工作解点与盒。对于这类问题,这是最先进的(2012年,也许现在,我也不确定)。他们将经典的Alpha-Beta剪枝算法与一系列特定于问题的解决方案结合起来。

您还可以尝试将蒙特卡罗树搜索应用于此问题。我不知道在这个方向上的工作,但蒙特卡罗已经证明成功的围棋游戏(这是类似于你的问题在某种意义上)。

票数 7
EN

Stack Overflow用户

发布于 2015-02-06 14:36:17

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

例如,使用强化学习,它基本上会执行您建议的操作,计算一个庞大的决策树。然而,它会发现一些动作(比如那些给对手一个盒子的动作)是不好的,它不会浪费大量的时间来计算那些动作。

是可行的吗?取决于您有多少自由处理时间。使用一个小的网格,直到你有一个像样的人工智能算法,然后你可以运行一台机器,并观察它自己学习。没有什么比看到你的创造学到什么更让人满意的了。就像有了孩子..。一个能在点和盒子里打败你的人。

票数 4
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/28367756

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档