Dim*_*tri 2 artificial-intelligence scripting-language
我试图证明可计算性的游戏是Dots和Boxes.
然而,我没有使用定理,而是试图通过创建一个AI,该游戏应该在该游戏中为玩家1或玩家2赢得100%的胜利.如果创造100%的胜利AI是不可能的,那么我的目标是创造一个至少比所有其他AI更好的.截至目前,我正在用PHP编写所有内容,因为我正在与另一个用脚本语言编写的AI竞争.
整个事情是递归的,基本逻辑是:计算所有可能移动的整个树如果是我的AI,那么为AI玩家选择具有最大点数的路线.如果是对手的AI,那么选择我的AI点数最少的路线.Aka计算每个节点的保证点数.
计算完整棵树后,选择保证点数最多的路线.在偶数点,随机挑选.
整个计算过程将大致永远地计算在15x15板上,但是现在我想要的是在3x3矩阵上计算它.我将为数据库中的前6-8个移动存储最佳移动,以便现在必须再次重新计算它们,这将每个计算的复杂性从24改变!到18!
这一切都可行吗？我计算动作的方式有问题吗？有一个更好的方法吗？
该问题具有非常大的搜索空间,对于4x4网格,我们在搜索空间中有40个边缘,因此有2 ^ 40个状态.因此,对于更大的地图,完全不可能解决整个游戏.
有什么解决方案？首先,您可以看看解决 Barker和Korf的Dots-And-Boxes的工作.这种问题是最先进的(2012年,也许现在,我不确定).他们结合使用经典的Alpha-Beta修剪算法和一系列特定问题的解决方案.
您还可以尝试将蒙特卡罗树搜索应用于该问题.我不知道这方面的作品,但蒙特卡洛已被证明是Go游戏的成功(在某种意义上类似于你的问题).
机器学习应该通过消除许多最初结果不好的分支来大大减少计算时间。它可能需要更多的时间来解决像 3x3 板这样的小问题，但是当你开始在更大的板上测试你的算法时，它会更快（如果没有写出两种算法并尝试它们，我不能肯定地说），因为它应该是 at=log(n) 函数的某种变体。
例如，使用强化学习，它基本上会按照您的建议进行操作，计算大量决策树。然而，它会了解到某些动作（例如给对手一个盒子的动作）是不好的，并且它不会浪费那么多时间来计算这些动作的后续动作。
可行吗？取决于您有多少免费处理时间。使用一个小网格，直到你编写了一个像样的人工智能算法，然后你可以运行一台机器并观察它自己学习。没有什么比看着你的创作学习一些东西更令人满足的了。这就像生了一个孩子……一个可以在点和盒子上击败你的孩子。