Gomoku: temps de recherche limité

Question

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

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'est pas testé cependant.

Answer 2

Vous pouvez utiliser la fonction time() dans time.h. Généralement, la valeur renvoyée est en secondes. Même si ce n'est pas le cas, vous pouvez simplement utiliser difftime() depuis le même en-tête.

This est une bonne ressource sur les fonctions nécessaires. Le lien ci-dessus provient d'un site de référence C++, mais cet en-tête et ces exemples sont tous du code C.

Answer 3

Vous pouvez utiliser le signal alarm. Faites en sorte que le gestionnaire de signal définisse un indicateur global appelé okWereDoneNow et lancez votre recherche, vérifiez et réinitialisez-la. L'avantage de ceci sur les fonctions de minuterie est qu'il ne nécessite qu'une seule comparaison par itération de la recherche. Le travail de signal est cher, mais seulement courir une fois. Dans une opération répétée intensive, vraisemblablement liée au CPU, cela pourrait être un avantage significatif. Mais ne me croyez pas sur parole - test!

Answer 4

Je pense que votre problème n'est pas la fonction de temps elle-même. Vous avez mentionné l'algorithme Minmax, qui est récursif. Le critère d'arrêt de l'algorithme Minmax est la profondeur de recherche donnée. Si vous souhaitez avoir un critère d'arrêt basé sur le temps, vous devez développer votre algorithme avec un cadre et laisser la fonction Minmax récursive retourner un Sentinel Value, si le temps est écoulé.

Answer 5

La seule vérification du temps ne fera pas l'affaire! Le minimax est un algorithme de recherche en profondeur récursif en premier, qui peut dépenser par ex. 30 secondes examinant de très mauvais mouvements quand il y a des mouvements évidemment bien meilleurs et juste dans la dernière seconde pour trouver du bon mouvement!

Vous devez utiliser un algorithme qui trouve un bon mouvement en peu de temps et ensuite, avec de plus en plus de temps disponible, il améliore la solution! Vous devez modifier votre algorithme minimax (ou alpha-beta) à en largeur la première recherche stratégie. Ensuite, vous pouvez le couper à tout moment en ayant de très bons mouvements.