Gomoku: temps limité à la recherche

Question

Je crée un programme C pour jouer Gomoku . Il utilise Minimax recherche pour décider de la meilleure décision. Cependant, il ne peut rechercher le meilleur mouvement pendant 10 secondes. Comment je déterminer quand ma fonction de recherche a passé 10 secondes de recherche. Si vous pouviez me fournir soit un exemple ou un lien vers la documentation qui serait très apprécié.

Answer 1

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

C'est, ce qui me vient à l'esprit. Il n'a pas été testé cependant.

Answer 2

Je pense que votre problème n'est pas la fonction du temps lui-même. Vous avez mentionné l'algorithme minmax, qui est récursive. Le critère d'arrêt de l'algorithme minmax est la recherche de profondeur donnée. Si vous avez un critère d'arrêt en fonction du temps que vous devez développer votre algorithme avec un cadre itératives Approfondir et laisser le minmax retour de fonction récursive Sentinel Value , si le temps est terminé.

Answer 3

La vérification unique de temps ne fera pas le travail! Le minimax est un algorithme de recherche en profondeur d'abord récursive, ce qui peut passer par exemple 30 secondes examinant très mauvais coups quand il y a des mouvements évidemment beaucoup mieux et juste dans la dernière 1 seconde pour trouver une bonne chose!

Vous devez utiliser un algorithme qui trouve un très bon coup en peu de temps, puis, avec de plus en plus de temps disponible, il améliore la solution! Vous devez modifier votre Minimax (ou alpha-bêta) algorithme première recherche étendue Stratégie. Ensuite, vous pouvez le couper à tout moment avoir assez bons coups.

Answer 4

Vous pouvez utiliser le signal alarm. tout simplement le gestionnaire de signal défini un indicateur global appelé okWereDoneNow et votre début de recherche, vérifier et réinitialiser.

L'avantage de ce sur les fonctions de la minuterie est qu'il ne nécessite qu'une seule comparaison par itération de la recherche. Le travail du signal est cher, mais seulement une fois exécuté. Lors d'une opération intensive, répétée sans doute CPU-limite, cela pourrait être un avantage significatif. Mais ne prenez pas ma parole - test

Answer 5

Vous pouvez utiliser la fonction time () dans time.h. En général, la valeur retournée est exprimée en secondes. Même si ce n'est pas, vous pouvez simplement utiliser difftime () de la même tête.

Cette est une bonne ressource sur les fonctions nécessaires.

Le lien ci-dessus est d'un site de référence C ++, mais en-tête et des exemples sont tout le code C.