Gomoku Heuristic

Question

I'm doing a Gomoku assignment which it can play with itself (computer) and human. The requirement is that there's time limit. Which means if you set the total game time to 2mins, then at the end of the 2min, the game should be over.

The prof suggested that the time can be equally assigned to each of the node of the game. The game should using pruning strategy. so suppose there're 20 node states to be visited, then the 2 mins are divided among these 20 nodes.

I'm confused since, how many states should be visited are depended on what move the human / computer take. Then how will I know how many nodes are to be visited and assign each an appropriate time?

Furthermore, I decided to apply "End of Four" or "Break three" heuristic strategy suggested by a research paper within the pruning search. But by this time limit requirement, at what point should I apply this strategy and at which point should I just apply the normal pruning?

Thanks for advice.

Answer 1

This is the classic Halting Problem: at what threshold should the program terminate computation? There's no one right answer, although one useful time management heuristic is: determine the number of nodes to search on a given turn based on both how much time you have remaining, and how much time your opponent has remaining.