行走一棵巨大的游戏树
我有一棵游戏树太大了，无法完整行走。
如何编写一个函数来评估树，直到达到时间限制或深度限制？
I have a game tree that is too big to walk in its entirety.
How can I write a function that will evaluate the tree until a time limit or depth limit is reached?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
我认为提供更多细节会有所帮助。另外，您提出了两个完全独立的问题 - 您是否希望同时应用这两个限制，或者您是否正在寻找如何独立地执行每个限制？也就是说，粗略地说：
时间限制：如果不使用
IO，这显然是不可能的。假设您的游戏树遍历函数很大程度上是纯粹的，您可能不希望将其与一堆确定控制流的时间跟踪交织在一起。我认为这里最简单的事情可能是让遍历产生一个逐渐更好的结果流，将每个“迄今为止最好的结果”放入MVar等中，并在单独的线程上运行它。如果达到时间限制，只需终止线程并从MVar中获取当前值。深度限制：最彻底的方法就是简单地执行广度优先搜索，不是吗？如果无论出于何种原因这都不可行，我认为没有比简单地保留一个计数器来指示当前深度并且在达到最大值时不继续更深的显而易见的解决方案更好的解决方案了。请注意，在这种情况下，可以使用 Reader 样式的 monad 来整理代码，其中每个递归调用都包含在
local (subtract 1)之类的内容中。It would help to have a bit more detail, I think. Also, you raise two entirely separate issues--do you want both limits applied simultaneously, or are you looking for how to do each independently? That said, in rough terms:
Time limit: This is clearly impossible without using
IO, to start with. Assuming your game tree traversal function is largely pure you'd probably prefer not to intertwine it with a bunch of time-tracking that determines control flow. I think the simplest thing here is probably to have the traversal produce a stream of progressively better results, place each "best result so far" into anMVaror such, and run it on a separate thread. If the time limit is reached, just kill the thread and take the current value from theMVar.Depth limit: The most thorough way to do this would be to simply perform a breadth-first search, wouldn't it? If that's not viable for whatever reason, I don't think there's any better solution than the obvious one of simply keeping a counter to indicate the current depth and not continuing deeper when the maximum is reached. Note that this is a case where the code can potentially be tidied up using a Reader-style monad, where each recursive call is wrapped in something like
local (subtract 1).超时基础包中的 函数允许您在一段时间后终止计算。将timeout与越来越深入的结果流交错，以便将最新结果存储在MVar中，这是 Haskell 中搜索问题的一个相对常见的技巧。The
timeoutfunction in the base package allows you to kill a computation after a certain period. Interleavingtimeoutwith a stream of increasingly deeper results, such that the most recent result is stored in anMVaris a relatively common trick for search problems in Haskell.您还可以使用惰性编写器 monad 进行遍历，生成改进答案的列表。现在您已经在某种程度上简化了您的问题，只需按照某些标准从列表中获取第一个“足够好”或“迄今为止最好”的结果。最重要的是，您可以使用所描述的超时技巧，或您认为合适的任何其他方法......
You can also use a lazy writer monad for your traversal, generating a list of improving answers. Now you've simplified your problem somewhat, to just taking the first "good enough" or "best so far" result from the list by some criteria. On top of that you can use the
timeouttrick that dons described, or any other approach you think appropriate...