Gomoku：搜索时间有限

Question

我正在创建一个C程序 Gomoku. 。它用 minimax 搜索以决定最佳动作。但是，它只能在10秒内搜索最佳动作。如何确定搜索功能何时花了10秒钟的搜索。如果您可以为我提供一个示例或指向文档的链接，这将不胜感激。

Answer 1

#include <time.h>
time_t start_time = time(NULL);
while (((int)(time(NULL) - start_time)) < 10) {
  //search
}

也就是说，我想到的。不过没有测试。

Answer 2

我认为您的问题不是时间函数本身。您提到了Minmax算法，这是递归的。 Minmax算法的停止标准是给定的搜索深度。如果您想拥有基于时间的停止标准，则应使用A扩展算法 迭代加深 框架并让递归minmax函数返回 哨兵值, ，如果时间结束了。

Answer 3

唯一的时间检查将无法完成工作！ Minimax是一种递归深度优先的搜索算法，它可以花费30秒钟检查非常错误的动作，而显然有一些更好的动作，并且在最后一秒钟内就可以找到一些好的动作！

您必须使用一些算法，该算法在短时间内发现了一个很好的动作，然后随着越来越多的时间可用，它可以改善解决方案！您必须将minimax（或alpha-beta）算法修改为 广度首次搜索 战略。然后，您可以随时将其切开。

Answer 4

您可以使用 alarm 信号。只需让信号处理程序设置一个名为的全局标志 okWereDoneNow 并让您的搜索开始，检查并重置。

比计时器函数的优点在于，它仅需要根据搜索的迭代进行一次比较。信号工作很昂贵，但只能运行一次。在强化，大概是CPU结合的重复操作中，这可能是一个重要的优势。但是不要相信我的话 - 测试！

Answer 5

您可以使用time（）函数。通常，返回的值在几秒钟内。即使不是，您也可以简单地使用同一标头的difftime（）。

这个 是必要功能的好资源。

上面的链接来自C ++参考站点，但是标题和示例都是C代码。