如果不是所有的分支都被探索到相同的深度，Expectimax AI是否仍然像预期的那样工作？

Question

我正在做一个预期的最大AI，这个游戏的分支因子是不可预测的，从6到20。我目前在每个回合中探索游戏树1秒，然后确保整个游戏树被探索到相同的深度，但偶尔这会导致非常大的减速，如果特定回合的分支因子急剧上升的话。当游戏树的某些部分没有被深入探索时，如果我切断探索，可以吗？这会影响expectimax的数学属性吗？

Answer 1

简而言之:我非常肯定你失去了数学上的保证，但这对你程序性能的影响程度可能取决于游戏和你的棋盘评估函数。

这里有一个抽象的场景，让你直观地知道在哪里有不同的分支长度可能会产生最多的问题:假设，对于玩家1，最好的走法是需要几轮设置的东西。假设这种设置不是您的董事会评估函数可以识别的。在这种情况下，无论玩家2同时做什么，在未来的几步棋中都会有一个点，棋盘的分数将朝着有利于玩家1的方向摆动。如果一个分支走得足够远，而另一个分支没有看到，那么对于玩家2来说，第一个选择看起来更糟糕，尽管同样的事情也会发生在另一个分支上。如果玩家2在第一个分支中的移动实际上比它在第二个分支中的移动更好，这将导致次优的选择。

另一方面，一个完美的棋盘评估器将使这变得不可能(它将识别玩家1设置他们的走法)。也有一些游戏不可能像这样提前设置走法。但这种情况的存在是一个危险信号。

从根本上说，没有得到评估的分支在评估移动有多好时有更大的不确定性。这有时会导致它们在不应该被选中的时候被选中，而另一些时候会导致它们在应该被选中的时候没有被选中。因此，我强烈怀疑这样做会失去数学上的保证。也就是说，这个问题对性能的实际影响可能很大，也可能不是很大。

如果您将当前的回合数合并到棋盘评估函数中并相应地进行调整，则可能会有一些方法绕过这一问题。至少，这将允许您显式地说明较短分支中添加的不确定性。