我试图证明的游戏是点和盒。
然而,我没有使用定理,而是尝试创建一个AI,它应该在游戏中为玩家1或玩家2拥有100%的成功率。如果创建一个100%的winrate AI是不可能的,那么我的目标是创建一个至少比其他人工智能更好的AI。到目前为止,我正在用PHP编写所有的东西,因为我也在与用脚本语言编写的另一个AI竞争。
这整件事是递归的,基本的逻辑是:如果是我的AI回合,计算出所有可能移动的整个树,然后为AI玩家选择具有最大点数的路径。如果这是对手的人工智能,然后选择最小的点数为我的人工智能路线。也就是计算每个节点上的保证点数。
在计算完整个树之后,选择具有最高保证点数的路由。在偶数点上,随机挑选。
整个计算过程大概要花费很长时间才能在15x15板上计算,但是现在我要做的就是在3x3矩阵上计算它。我将存储最好的移动前6-8移动在数据库中,以便现在必须重新计算他们,这改变了每次计算的复杂性从24!到18点!
这整件事可行吗?我计算移动的方式有问题吗?有更好的方法吗?
发布于 2015-02-06 16:56:32
这个问题有一个很大的搜索空间,对于一个4x4网格,我们在搜索空间中有大约40条边和2^40个状态。因此,要解决整个游戏中更大的地图是完全不可能的。
解决办法是什么?首先,您可以查看Barker和Korf的工作解点与盒。对于这类问题,这是最先进的(2012年,也许现在,我也不确定)。他们将经典的Alpha-Beta剪枝算法与一系列特定于问题的解决方案结合起来。
您还可以尝试将蒙特卡罗树搜索应用于此问题。我不知道在这个方向上的工作,但蒙特卡罗已经证明成功的围棋游戏(这是类似于你的问题在某种意义上)。
发布于 2015-02-06 14:36:17
机器学习应该减少计算时间的一个好的一点,消除许多分支的坏结果一开始。解决诸如3x3板这样的小问题可能需要更多的时间,但当您开始在更大的板上测试算法时(我不能肯定地说,如果不同时写出算法并尝试它们)会更快,因为它应该是t=log(n)函数的一些变量。
例如,使用强化学习,它基本上会执行您建议的操作,计算一个庞大的决策树。然而,它会发现一些动作(比如那些给对手一个盒子的动作)是不好的,它不会浪费大量的时间来计算那些动作。
是可行的吗?取决于您有多少自由处理时间。使用一个小的网格,直到你有一个像样的人工智能算法,然后你可以运行一台机器,并观察它自己学习。没有什么比看到你的创造学到什么更让人满意的了。就像有了孩子..。一个能在点和盒子里打败你的人。
https://stackoverflow.com/questions/28367756
复制相似问题