我正在尝试证明可计算性的游戏是点与框。
然而，我不是通过使用定理来证明，而是通过创建一个AI，期望它在该游戏中对玩家1或玩家2有100%的胜率。如果创建一个100%胜率的AI是不可能的，那么我的目标是创建一个至少比其他所有AI都要好的AI。目前，我正在用PHP编写所有代码，因为我正在与其他使用脚本语言编写的AI竞争。
整个过程是递归的，基本逻辑是：计算所有可能移动的整个树。如果是我的AI的回合，则选择AI玩家得分最高的路线。如果是对手的AI的回合，则选择我的AI得分最低的路线。也就是说，计算每个节点的保证得分数。
计算完整个树后，选择保证得分最高的路线。在得分相同时，随机选择。
整个计算过程在15×15的棋盘上计算将花费很长时间，但目前我只尝试在3×3的矩阵上进行计算。我将把前6-8步的最佳可能移动存储在数据库中，以便不再需要重新计算，从而将每次计算的复杂度从24!降低到18!。
这整个事情可行吗？我计算移动的方式有问题吗？有没有更好的方法来做这件事？
回答：
这个问题有一个非常大的搜索空间，对于4×4的网格，我们有大约40条边，因此搜索空间中有2^40个状态。因此，对于更大的地图，完全不可能解决整个游戏。
解决方案是什么？首先，你可以参考Barker和Korf的作品Solving Dots-And-Boxes。这是这类问题的最新技术（在2012年，也许现在也是，我不确定）。他们使用了经典的Alpha-Beta剪枝算法与一系列特定问题的解决方案的组合。
你也可以尝试将蒙特卡洛树搜索应用到这个问题上。我不知道在这方面有哪些工作，但蒙特卡洛在围棋游戏中已被证明是成功的（在某种意义上与你的问题相似）。
