Gomoku: periodo di tempo limitato per la ricerca

Question

Sto creando un programma in C per giocare Gomoku . Esso utilizza Minimax cercare di decidere la mossa migliore. Tuttavia, può solo cercare la mossa migliore per 10 secondi. Come determino quando la mia funzione di ricerca ha trascorso 10 secondi la ricerca. Se si potesse fornirmi sia un esempio o un link alla documentazione che sarebbe molto apprezzato.

Answer 1

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

Questo è, ciò che mi viene in mente. Non è testato però.

Answer 2

Credo che il problema non è la funzione il tempo stesso. Lei ha citato l'algoritmo Minmax, che è ricorsiva. Il criterio di arresto del Algorithm Minmax è la data ricerca approfondita. Se ti piace avere un criterio basato sul tempo di arresto si dovrebbe espandere il vostro algoritmo con un quadro iterativo Approfondimento e lasciare che il ricorsiva Minmax ritorno funzione un Sentinel Valore , se il tempo è finito.

Answer 3

Il tempo di verifica suola non farà il lavoro! Il Minimax è un algoritmo di ricerca ricorsiva in profondità, che può spendere per esempio 30 secondi esame si muove molto sbagliato quando ci sono alcune mosse, ovviamente, molto meglio e solo negli ultimi 1 secondo per trovare qualche buona mossa!

Devi usare qualche algoritmo che trova piuttosto una buona mossa in breve tempo e poi, con sempre più tempo a disposizione, si migliora la soluzione! È necessario modificare la Minimax (o alfa-beta) algoritmo per ricerca in ampiezza di strategia. Poi si può tagliare in qualsiasi momento avendo abbastanza buone mosse.

Answer 4

Si potrebbe utilizzare il segnale alarm. Basta avere il gestore di segnale impostato un flag chiamato okWereDoneNow globale e avere il vostro inizio di ricerca, verificare la presenza di, e ripristinarlo.

Il vantaggio di questo le funzioni di timer è che richiede solo un singolo confronto per ogni iterazione della ricerca. Il lavoro del segnale è costoso, ma solo eseguito una volta. In un intenso, presumibilmente-CPU-bound funzionamento ripetuto, questo potrebbe essere un vantaggio significativo. Ma non prendere la mia parola per esso - test

Answer 5

Si potrebbe utilizzare la funzione time () in time.h. In generale, il valore restituito è espresso in secondi. Anche se non lo è, si può semplicemente utilizzare difftime () dalla stessa intestazione.

Questa è una buona risorsa per le funzioni necessarie.

il collegamento precedente è da un sito di riferimento C ++, ma che intestazione e gli esempi sono tutto il codice C.