解决点和盒子游戏是否可行？

Question

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

但是，我试图通过创建一个应该在玩家1或玩家2中在该游戏中具有100％胜率的AI来实现这一点。 如果创建100％winrate AI是不可能的，那么我的目标就是创造一个至少比所有其他AI更好的人。截至目前，我正在使用PHP编写所有内容，因为我正在与另一种用脚本语言编写的AI进行竞争。

这整个事情是递归的，其基本逻辑是： 计算所有可能移动的整个树木 如果是我的AI轮到，那么选择最大AI点数的路线。如果是轮到对手的AI，那么选择AI数量最少的路线。 Aka计算每个节点的保证点数。

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

这整个计算过程大概需要永远在15x15板上进行计算，但是现在我要做的就是在3x3矩阵上进行计算。为了现在必须重新计算它们，我将为数据库中的前6-8次移动存储最佳移动，这将改变每个计算从24开始的复杂度！到18 !.

这整个事情是可行的吗？我的计算方式有问题吗？有一个更好的方法吗？

Answer 1

这个问题有一个非常大的搜索空间，对于一个4x4的网格，我们在搜索空间中有40个边缘和2^40个状态。由于这个原因，完全不可能为整个游戏解决更大的地图。

有什么解决方案？首先你可以看看Barker和Korf的作品Solving Dots-And-Boxes。这是这种问题的最先进的状态（2012年，也许现在，我不知道）。他们将经典的Alpha-Beta修剪算法与一组问题特定解决方案结合使用。

您也可以尝试将Monte Carlo Tree Search应用于该问题。我不知道在这个方向上的作品，但蒙特卡洛已经被证明在围棋游戏中取得了成功（这在某种程度上类似于你的问题）。

Answer 2

机器学习应该通过消除许多最初具有不良结果的分支来减少计算时间。它可能需要更多的时间来解决像3x3板这样的小问题，但是当你在更大的板上开始测试你的算法时，它会（我不能肯定地说没有写出算法和尝试它们）会更快，因为它应该是at = log（n）函数的一些变量。

例如，使用Reinforcement Learning它将基本上做你的建议，计算一个大规模的决策树。但是，它会知道一些举措（例如那些给对手一个盒子的举动）是不好的，它不会浪费尽可能多的时间计算移动成功。

它可行吗？取决于你有多少免费处理时间。使用一个小网格，直到你有一个体面的人工智能算法编写，然后你可以运行一台机器，看着它自己学习。没有什么比看着你的创造学习更令人满意的了。这就像有一个婴儿......一个可以在Dots and Boxes打败你的人。