search - 走一棵巨大的游戏树

我有一个太大而无法完整行走的游戏树。

如何编写一个函数来评估树，直到达到时间限制或深度限制？

最佳答案

我认为，提供更多细节会有所帮助。此外，您提出了两个完全独立的问题——您是希望同时应用两个限制，还是在寻找如何独立完成每个限制？也就是说，粗略地说:

时间限制 :首先，如果不使用 IO ，这显然是不可能的。假设您的博弈树遍历函数在很大程度上是纯粹的，您可能不希望将它与一堆确定控制流的时间跟踪交织在一起。我认为这里最简单的事情可能是让遍历产生一系列逐渐更好的结果，将每个“迄今为止最好的结果”放入 MVar 等中，然后在单独的线程上运行它。如果达到时间限制，只需终止线程并从 MVar 中获取当前值。

深度限制 :最彻底的方法是简单地执行广度优先搜索，不是吗？如果这无论出于何种原因都不可行，我认为没有比简单地保留一个计数器来指示当前深度而不是在达到最大值时继续更深的明显解决方案更好的解决方案。请注意，在这种情况下，可以使用 Reader 样式的 monad 来整理代码，其中每个递归调用都包含在 local (subtract 1) 之类的东西中。