artificial-intelligence - 是否有可能解决点和盒游戏？

Question

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

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

这整个事情是递归的，基本逻辑是:
计算所有可能移动的整个树
如果轮到我的 AI，则为 AI 玩家选择具有最大点数的路线。如果轮到对手的 AI，则为我的 AI 选择点数最少的路线。也就是计算每个节点的保证点数。

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

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

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

Answer 1

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

有哪些解决方案？首先你可以看看作品Solving Dots-And-Boxes巴克和科尔夫。这是解决此类问题的最新技术(在 2012 年，也许现在，我不确定)。他们将经典的 Alpha-Beta 剪枝算法与一系列特定于问题的解决方案结合使用。

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