解决 Dots and Boxes 游戏是否可行？
Is it feasible to solve Dots and Boxes game?
我试图证明其可计算性的游戏是 Dots and Boxes。
但是，我没有使用定理，而是尝试通过创建一个 AI 来做到这一点，该 AI 应该在该游戏中对玩家 1 或玩家 2 具有 100% 的胜率。
如果创造一个 100% 胜率的 AI 是不可能的，那么我的目标是创造一个至少比所有其他 AI 更好的 AI。截至目前，我正在用 PHP 编写所有内容，因为我正在与另一个也用脚本语言编写的 AI 竞争。
这整个事情是递归的，基本逻辑是：
计算所有可能移动的整棵树
如果轮到我的 AI，则为 AI 玩家选择点数最多的路线。如果轮到对手的AI，则为我的AI选择点数最少的路线。也就是计算每个节点的保证点数。
计算整棵树后，选择保证点数最多的路线。在偶数点上，随机选择。
在 15x15 板上计算整个计算过程大约需要永远，但是现在我要做的只是在 3x3 矩阵上计算它。我将在数据库中存储前 6-8 个动作的最佳可能动作，以便现在必须再次重新计算它们，这改变了每次计算的复杂性，从 24！到 18 岁！
这整件事可行吗？我计算动作的方式有问题吗？有更好的方法吗？
机器学习应该通过消除许多最初结果不好的分支来减少计算时间。它可能需要更多时间来解决诸如 3x3 电路板之类的小问题，但是当您开始在更大的电路板上测试您的算法时，它会（如果不写出这两种算法并尝试它们，我不能肯定地说）会更快，因为它应该是 t=log(n) 函数的一些变体。
例如，使用 Reinforcement Learning 它基本上会执行您的建议，计算一个巨大的决策树。然而，它会了解到某些动作（例如给对手一个盒子的动作）是不好的，并且不会浪费太多时间来计算接替这些动作的动作。
可行吗？取决于您有多少空闲处理时间。使用一个小网格，直到你编写了一个像样的 AI 算法，然后你可以 运行 一台机器并观察它自己学习。没有什么比看着你的创作学习一些东西更令人满足的了。这就像生了一个孩子......一个可以在点和框上打败你的孩子。
这个问题有一个非常大的搜索 space，对于 4x4 网格，我们有大约 40 条边，因此在搜索中有 2^40 个状态 space。因为这个原因是完全不可能解决整场比赛换一张更大的地图。
解决方法是什么？首先你可以看看 Barker 和 Korf 的工作Solving Dots-And-Boxes。这是解决这类问题的最先进技术（在 2012 年，也许现在也是，我不确定）。他们结合使用了经典的 Alpha-Beta 剪枝算法和一系列针对特定问题的解决方案。
您也可以尝试将Monte Carlo Tree Search应用于问题。我不知道这方面的工作，但 Monte Carlo 已被证明在围棋游戏中是成功的（这在某种意义上类似于你的问题）。
我试图证明其可计算性的游戏是 Dots and Boxes。
但是，我没有使用定理，而是尝试通过创建一个 AI 来做到这一点，该 AI 应该在该游戏中对玩家 1 或玩家 2 具有 100% 的胜率。 如果创造一个 100% 胜率的 AI 是不可能的，那么我的目标是创造一个至少比所有其他 AI 更好的 AI。截至目前，我正在用 PHP 编写所有内容，因为我正在与另一个也用脚本语言编写的 AI 竞争。
这整个事情是递归的，基本逻辑是： 计算所有可能移动的整棵树 如果轮到我的 AI，则为 AI 玩家选择点数最多的路线。如果轮到对手的AI，则为我的AI选择点数最少的路线。也就是计算每个节点的保证点数。
计算整棵树后，选择保证点数最多的路线。在偶数点上，随机选择。
在 15x15 板上计算整个计算过程大约需要永远，但是现在我要做的只是在 3x3 矩阵上计算它。我将在数据库中存储前 6-8 个动作的最佳可能动作，以便现在必须再次重新计算它们，这改变了每次计算的复杂性，从 24！到 18 岁！
这整件事可行吗？我计算动作的方式有问题吗？有更好的方法吗？
机器学习应该通过消除许多最初结果不好的分支来减少计算时间。它可能需要更多时间来解决诸如 3x3 电路板之类的小问题，但是当您开始在更大的电路板上测试您的算法时，它会（如果不写出这两种算法并尝试它们，我不能肯定地说）会更快，因为它应该是 t=log(n) 函数的一些变体。
例如，使用 Reinforcement Learning 它基本上会执行您的建议，计算一个巨大的决策树。然而，它会了解到某些动作（例如给对手一个盒子的动作）是不好的，并且不会浪费太多时间来计算接替这些动作的动作。
可行吗？取决于您有多少空闲处理时间。使用一个小网格，直到你编写了一个像样的 AI 算法，然后你可以 运行 一台机器并观察它自己学习。没有什么比看着你的创作学习一些东西更令人满足的了。这就像生了一个孩子......一个可以在点和框上打败你的孩子。
这个问题有一个非常大的搜索 space，对于 4x4 网格，我们有大约 40 条边，因此在搜索中有 2^40 个状态 space。因为这个原因是完全不可能解决整场比赛换一张更大的地图。
解决方法是什么？首先你可以看看 Barker 和 Korf 的工作Solving Dots-And-Boxes。这是解决这类问题的最先进技术（在 2012 年，也许现在也是，我不确定）。他们结合使用了经典的 Alpha-Beta 剪枝算法和一系列针对特定问题的解决方案。
您也可以尝试将Monte Carlo Tree Search应用于问题。我不知道这方面的工作，但 Monte Carlo 已被证明在围棋游戏中是成功的（这在某种意义上类似于你的问题）。