Gomoku: tiempo limitado para buscar

Question

Estoy creando un programa en C para jugar gomoku . Utiliza Minimax buscar a decidir sobre el mejor movimiento. Sin embargo, sólo puede buscar el mejor movimiento durante 10 segundos. ¿Cómo puedo determinar cuando mi función de búsqueda ha gastado 10 segundos a buscar. Si usted me podría proporcionar, ya sea con un ejemplo o un enlace a la documentación que sería muy apreciada.

Answer 1

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

Es decir, lo que viene a la mente. No se prueba sin embargo.

Answer 2

Creo que su problema no es la función de tiempo mismo. Usted ha hablado de la Minmax algoritmo, que es recursivo. El criterio de parada de la Minmax algoritmo de búsqueda es la profundidad dada. Si te gusta tener un criterio basado en el tiempo de parada que debe ampliar su algoritmo con un marco iterativo Profundización y dejar que el retorno de la función recursiva Minmax un Sentinel Valor , si el tiempo ha terminado.

Answer 3

El tiempo de comprobación única no va a hacer el trabajo! El Minimax es un algoritmo de búsqueda en profundidad recursiva, lo que puede pasar, por ejemplo, 30 segundos que examinan se mueve muy mal cuando hay obviamente mucho mejores movimientos y justo en el último 1 segundo para encontrar un buen movimiento!

Hay que utilizar algún algoritmo que encuentra absolutamente un buen movimiento en corto tiempo y luego, con más y más tiempo disponible, se mejora la solución! Tiene que modificar su Minimax (o alfa-beta) algoritmo para búsqueda en anchura estrategia. A continuación, se puede cortar en cualquier momento tener bastante buenos movimientos.

Answer 4

Se podría utilizar la señal alarm. Basta con tener el manejador de la señal establece un indicador denominado okWereDoneNow mundial y tiene su inicio la búsqueda, comprobar, y reiniciarlo.

La ventaja de este sobre las funciones del temporizador es que requiere solamente una única comparación por iteración de la búsqueda. El trabajo de la señal es caro, pero sólo se ejecutan una vez. En una operación repetida intensiva, presumiblemente-CPU-bound, esto podría ser una ventaja significativa. Pero no tome mi palabra para ella - de prueba

Answer 5

Se puede usar la función de tiempo () en time.h. Generalmente, el valor devuelto es en cuestión de segundos. Incluso si no es así, usted podría simplemente utilizar difftime () de la misma cabecera.

Este es un recurso bien en las funciones necesarias.

El enlace anterior es de un sitio de referencia C ++, pero esa cabecera y ejemplos son todo el código C.