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算法的停止准则是给定的搜索深度。如果你想有一个基于时间的停止条件，你应该用Iterative Deepening框架扩展你的算法，如果时间到了，让递归的Minmax函数返回一个Sentinel Value。

Answer 3

minimax是一个递归的深度优先搜索算法，它可以花费30秒来检查非常错误的移动，当有一些明显更好的移动时，只需在最后1秒内找到一些好的移动！

你必须使用一些算法，在短时间内找到相当好的移动，然后，随着越来越多的时间可用，它改善了解决方案！您必须修改您的minimax (或alpha-beta)算法，以breadth first search策略。然后你可以在任何时候剪下它，有相当好的动作。