3

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.

Tomas
  • 57,621
  • 49
  • 238
  • 373
Spencer
  • 4,018
  • 10
  • 33
  • 43

5 Answers5

5
#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.

imbaer
  • 554
  • 3
  • 21
  • While not note for note what I would do, that is the basic approach I would take. Obviously you would need to place more constraints inside the while loop, such as `while(!foundOptimalMove && ... time stuff ...)` – corsiKa Oct 16 '10 at 21:10
  • 2
    this is no good! The problem is in the depth search, not in time checking! – Tomas Aug 09 '11 at 11:24
  • still an answer to the question? – imbaer Aug 09 '11 at 14:14
3

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.

Christian Ammer
  • 7,464
  • 6
  • 51
  • 108
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.

Tomas
  • 57,621
  • 49
  • 238
  • 373
  • @Christian thanks, it was a revenge from the other answerers, because I downvoted their wrong answers... currently I have +2/-2 => 0 – Tomas Aug 12 '11 at 21:02
1

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!

Thom Smith
  • 13,916
  • 6
  • 45
  • 91
  • The sole time checking will not do the job in the recursive depth-first search minimax algorithm! – Tomas Aug 09 '11 at 11:33
  • The question was about timeouts. The answer was about timeouts. If you want to post an answer that is not about timeouts, go right ahead, but why on earth would you downvote people for answering the question given? – Thom Smith Aug 09 '11 at 16:34
  • 1
    Thom Smith, the question was not about timeouting in general, it was about timeouting in minimax algorithm. The question was put this way. Your answer is wrong, because without changing the algorithm it would not produce the expected result.... that's why I downvoted your answer. Why you downvoted mine? Pure revenge? – Tomas Aug 09 '11 at 16:40
0

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.

Kizaru
  • 2,443
  • 3
  • 24
  • 39
  • 1
    The sole time checking will not do the job in the recursive depth-first search minimax algorithm! – Tomas Aug 09 '11 at 11:32
  • Sure, BFS would be better than DFS, but the question is about time and not the algorithm itself. The user was solely asking how to check the time, not if the algorithm is solid. – Kizaru Aug 09 '11 at 20:30
  • 1
    The question was about time limiting the minimax algorithm. Using your answer, the asker will not obtain the expected result. – Tomas Aug 09 '11 at 20:36
  • "If you could provide me with either an example or a link to the documentation that would be much appreciated." Does my answer not answer the question? – Kizaru Aug 09 '11 at 23:25