árbol de búsqueda juego, ¿Tengo que construir el árbol en primer lugar?

Question

en el árbol de búsqueda juego hay muchos algoritmos para obtener la solución óptima, al igual que el algoritmo minimax. Empiezo a aprender cómo resolver este problema con el algoritmo minimax, el algoritmo de borrar. pero yo estoy confundido acerca del propio árbol, en juegos como el número tres en raya de nodo no muy grande, pero en otros como el ajedrez hay muchos nodos. Creo que este gran espacio necesario en la memoria. Entonces, ¿hay alguna algoritmos para evaluar y árbol de construcción en el mismo tiempo?

Answer 1

Un árbol de estados de juego normalmente no es construido como una estructura de datos completa. En cambio, los estados se evalúan como se crean, y la mayoría son descartados en el proceso. Vuelve a menudo, una lista enlazada desde el estado que se evalúa el estado actual del juego se mantiene. Pero si se demuestra que un movimiento a ser mucho mejor que otro, entonces la línea completa para el movimiento pobre será descartado, por lo que no ocupan espacio en la memoria.

Una forma sencilla de buscar el espacio de estados para un juego como el ajedrez es hacer la búsqueda de forma recursiva a una profundidad determinada. En ese caso, muy pocos estados juego realmente existen a la vez, y los que existen son simplemente hace referencia en la pila de llamadas. Más sofisticados algoritmos crearán un árbol grande, pero (especialmente para el ajedrez) ninguno mantendrán un árbol de todos los estados posibles. Para el ajedrez, una búsqueda en amplitud puede ser mejor, utilizando una cola en lugar de una pila, y esto mantendrá sólo los estados a una cierta profundidad en el árbol. Aún mejor sería una cola de prioridad en la que los mejores estados se almacenan para su posterior evaluación, y los peores estados se descartan por completo.