Gomoku: limited time to search

Question

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.

Answer 1

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

That is, what comes to my mind. It is not tested though.

Answer 2

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.

Answer 3

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.

Answer 4

You could use the alarm signal. Simply have the signal handler set a global flag called okWereDoneNow and 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!

Answer 5

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.