游戏搜索树，我必须先建造树吗？

Question

在游戏搜索树中，有许多算法可以获取最佳解决方案，例如minimax算法。我开始学习如何使用Minimax算法（算法清晰）解决此问题。但是我对树本身感到困惑，在诸如tic tac toe节点数字之类的游戏中不是很大，但是在其他象棋等其他节点上，有很多节点。我认为这需要大量的内存空间。那么，是否有同一时间评估和构建树的算法？

Answer 1

游戏状态的树通常不是作为完整的数据结构构建的。取而代之的是，在创建的情况下对状态进行评估，并且大多数在此过程中被丢弃。通常，将评估回到游戏当前状态的状态的链接列表得到了维持。但是，如果证明一个举动比另一个举动要好得多，那么糟糕的举动的整个行将被丢弃，因此它不会占据内存中的空间。

像国际象棋一样搜索状态空间的一种简单方法是递归对给定的深度进行搜索。在这种情况下，实际上很少有游戏状态存在，而确实存在的游戏状态仅在呼叫堆上引用。更复杂的算法将创建一个较大的树，但是（尤其是对于国际象棋），没有一个将维护所有可能状态的树。对于国际象棋而言，使用队列而不是堆栈可能会更好，这只会维持树上的一定深度。更好的是将最佳状态存储以进行进一步评估的优先队列，并且最坏的状态被完全丢弃。