解决点盒游戏可行吗？
我试图证明的游戏是点和盒。
然而，我没有使用定理，而是尝试创建一个AI，它应该在游戏中为玩家1或玩家2拥有100%的成功率。如果创建一个100%的winrate AI是不可能的，那么我的目标是创建一个至少比其他人工智能更好的AI。到目前为止，我正在用PHP编写所有的东西，因为我也在与用脚本语言编写的另一个AI竞争。
这整件事是递归的，基本的逻辑是:如果是我的AI回合，计算出所有可能移动的整个树，然后为AI玩家选择具有最大点数的路径。如果这是对手的人工智能，然后选择最小的点数为我的人工智能路线。也就是计算每个节点上的保证点数。
在计算完整个树之后，选择具有最高保证点数的路由。在偶数点上，随机挑选。
整个计算过程大概要花费很长时间才能在15x15板上计算，但是现在我要做的就是在3x3矩阵上计算它。我将存储最好的移动前6-8移动在数据库中，以便现在必须重新计算他们，这改变了每次计算的复杂性从24！到18点！
这整件事可行吗？我计算移动的方式有问题吗？有更好的方法吗？
回答 2
Stack Overflow用户
发布于 2015-02-06 16:56:32
这个问题有一个很大的搜索空间，对于一个4x4网格，我们在搜索空间中有大约40条边和2^40个状态。因此，要解决整个游戏中更大的地图是完全不可能的。
解决办法是什么？首先，您可以查看Barker和Korf的工作解点与盒。对于这类问题，这是最先进的(2012年，也许现在，我也不确定)。他们将经典的Alpha-Beta剪枝算法与一系列特定于问题的解决方案结合起来。
您还可以尝试将蒙特卡罗树搜索应用于此问题。我不知道在这个方向上的工作，但蒙特卡罗已经证明成功的围棋游戏(这是类似于你的问题在某种意义上)。
Stack Overflow用户
发布于 2015-02-06 14:36:17
机器学习应该减少计算时间的一个好的一点，消除许多分支的坏结果一开始。解决诸如3x3板这样的小问题可能需要更多的时间，但当您开始在更大的板上测试算法时(我不能肯定地说，如果不同时写出算法并尝试它们)会更快，因为它应该是t=log(n)函数的一些变量。
例如，使用强化学习，它基本上会执行您建议的操作，计算一个庞大的决策树。然而，它会发现一些动作(比如那些给对手一个盒子的动作)是不好的，它不会浪费大量的时间来计算那些动作。
是可行的吗？取决于您有多少自由处理时间。使用一个小的网格，直到你有一个像样的人工智能算法，然后你可以运行一台机器，并观察它自己学习。没有什么比看到你的创造学到什么更让人满意的了。就像有了孩子..。一个能在点和盒子里打败你的人。
https://stackoverflow.com/questions/28367756
复制相似问题
腾讯云开发者
