五子棋：搜索时间有限
我正在创建一个 C 程序来玩 Gomoku。它使用 Minimax 搜索来决定最佳移动。然而，它只能搜索 10 秒的最佳走法。如何确定我的搜索功能何时已花费 10 秒进行搜索。如果您能为我提供示例或文档链接，我将不胜感激。
I'm creating a C program to play Gomoku. It uses Minimax search to decide on the best move. However, it can only search for the best move for 10 seconds. How to I determine when my search function has spent 10 seconds searching. If you could provide me with either an example or a link to the documentation that would be much appreciated.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
这就是我想到的。但它还没有经过测试。
That is, what comes to my mind. It is not tested though.
我认为你的问题不是时间函数本身。您提到了最小最大算法，它是递归的。最小最大算法的停止标准是给定的搜索深度。如果您想要基于时间的停止标准，您应该使用迭代深化框架来扩展您的算法如果时间结束，让递归 Minmax 函数返回 Sentinel Value。
I think your problem is not the time function itself. You mentioned the Minmax Algorithm, which is recursive. The stopping criterion of the Minmax Algorithm is the given search-depth. If you like to have a time-based stopping criterion you should expand your Algorithm with a Iterative Deepening framework and let the recursive Minmax Function return a Sentinel Value, if time is over.
仅靠时间检查并不能完成这项工作！极小极大是一种递归深度优先搜索算法，当存在一些明显更好的走法并且恰好在最后1秒找到好招！
你必须使用某种算法，它可以在短时间内找到一个很好的移动，然后，随着越来越多的可用时间，它会改进解决方案！您必须将极小极大（或 alpha-beta）算法修改为广度优先搜索策略。然后你就可以随时砍掉它，动作相当好。
The sole time checking will not do the job! The minimax is a recursive depth-first search algorithm, which can spend e.g. 30 seconds examining very wrong moves when there are some obviously much better moves and just in the last 1 second to find some good move!
You have to use some algorithm which finds quite a good move in short time and then, with more and more time available, it improves the solution! You have to modify your minimax (or alpha-beta) algorithm to breadth first search strategy. Then you can cut it at any time having quite good moves.
您可以使用
警报信号。只需让信号处理程序设置一个名为 okWereDoneNow 的全局标志，然后开始搜索、检查并重置它。与计时器函数相比，它的优点是每次搜索迭代只需要一次比较。信号工作很昂贵，但只运行一次。在密集的、可能受 CPU 限制的重复操作中，这可能是一个显着的优势。但不要相信我的话——测试！
You could use the
alarmsignal. Simply have the signal handler set a global flag calledokWereDoneNowand have your search start, check for, and reset it.The advantage of this over the timer functions is that it requires only a single comparison per iteration of the search. The signal work is expensive, but only run once. In an intensive, presumably-CPU-bound repeated operation, this could be a significant advantage. But don't take my word for it - test!
您可以使用 time.h 中的 time() 函数。一般情况下，返回值以秒为单位。即使不是，您也可以简单地使用同一标头中的 difftime() 。
这是有关必要功能的良好资源。
上面的链接来自 C++ 参考站点，但该标头和示例都是 C 代码。
You could use the time() function in time.h. Generally, the returned value is in seconds. Even if it is not, you could simply use difftime() from the same header.
This is a good resource on the necessary functions.
The above link is from a C++ reference site, but that header and examples are all C code.