A fin de comprender el funcionamiento del algoritmo alfa-beta para la búsqueda en juegos dejaré un ejemplo de una implemetación de dicho algoritmo en una próxima entrada de mi blog. El ejemplo que dejaré publicado fue implementado para calcular la mejor jugada para un juego de origen africano, como no, bipersonal llamado OWARE ó wari.
En juegos bipersonales el algoritmo más usado es el denominado Minimax. El procedimiento de búsqueda Minimax es una búsqueda en profundidad (DFS) de profundidad limitada. Este algoritmo es bastante costoso en cuanto a complejidad temporal. Para acotar el espacio de búsqueda de la mejor jugada, encontramos otros algoritmos como: Alpha Beta, SSS*o Scout.
Vamos a explicar el principio de como funcionan todos estos algoritmo de busqueda mencionados aplicados a juegos, sin entrar en los detalles de complejidades espaciales y temporales de los mismos, pues los dejaremos para proximos Posts. Partiendo de un estado del juego, por ejemplo un tablero, que representará el nodo raíz de nuestro arbol de busqueda, bifurcamos todas las posibles jugadas, obtenemos N estados nuevos de tablero en el nivel 1, luego volvemos a bifurcar todas las posibles jugadas que puede hacer nuestro adversario, volveremos a obtener N estados nuevos para el nivel 2, y así sucesivamente, hasta llegar al ultimo nivel (que fijáremos dependiendo de las limitaciones tiempo y memoria) donde evaluaremos los tableros, ventajas y desventajas de cada uno. Para evaluar los estados del tablero finales, los que corresponden a los nodos hoja de nuestro arbol, llamamos a una fución de evaluación, que tendrá como propósito, para un estado dado de un tablero, analizar y ponderar de forma óptima y eficiente el estado de este último según los criterios que se hayan tomado en consideración. Es obio que la función de evaluación desempeña un papel muy importante en la búsqueda y obtención de la mejor jugada.
Esta función nos devuelve el mejor resultado obtenido, vuelta atrás, y ya tenemos la mejor jugada.
En juegos bipersonales el algoritmo más usado es el denominado Minimax. El procedimiento de búsqueda Minimax es una búsqueda en profundidad (DFS) de profundidad limitada. Este algoritmo es bastante costoso en cuanto a complejidad temporal. Para acotar el espacio de búsqueda de la mejor jugada, encontramos otros algoritmos como: Alpha Beta, SSS*o Scout.
Vamos a explicar el principio de como funcionan todos estos algoritmo de busqueda mencionados aplicados a juegos, sin entrar en los detalles de complejidades espaciales y temporales de los mismos, pues los dejaremos para proximos Posts. Partiendo de un estado del juego, por ejemplo un tablero, que representará el nodo raíz de nuestro arbol de busqueda, bifurcamos todas las posibles jugadas, obtenemos N estados nuevos de tablero en el nivel 1, luego volvemos a bifurcar todas las posibles jugadas que puede hacer nuestro adversario, volveremos a obtener N estados nuevos para el nivel 2, y así sucesivamente, hasta llegar al ultimo nivel (que fijáremos dependiendo de las limitaciones tiempo y memoria) donde evaluaremos los tableros, ventajas y desventajas de cada uno. Para evaluar los estados del tablero finales, los que corresponden a los nodos hoja de nuestro arbol, llamamos a una fución de evaluación, que tendrá como propósito, para un estado dado de un tablero, analizar y ponderar de forma óptima y eficiente el estado de este último según los criterios que se hayan tomado en consideración. Es obio que la función de evaluación desempeña un papel muy importante en la búsqueda y obtención de la mejor jugada.
Esta función nos devuelve el mejor resultado obtenido, vuelta atrás, y ya tenemos la mejor jugada.
Ahora bien, el MiniMax es el algoritmo más costoso en cuanto a complejidad temporal y espacial, su mejora es el alpha-beta, introduce poda teniendo en cuenta cotas superiores e inferiores de los espacios de búsqueda, limitando así el espacio de la solución. SSS* es más eficiente en caunto a complejidad temporal, sin embargo consume bastante recursos de memoria. Scout reduce las complejidades temporales y espaciales de forma espectacular en algunos casos.
Si otpaís por implementar alguno tenerlo en consideración.
Comentarios
Publicar un comentario