Ingenio y Rapidez: Resolución De Juegos Mediante El Algoritmo Minimax y Poda Alpha Beta
Páginas: 7 (1606 palabras)
Publicado: 3 de octubre de 2011
Ingenio y Rapidez: Resolución de juegos mediante el algoritmo Minimax y Poda Alpha Beta
Bogotá, Colombia
@hotmail.com
@gmail.com
Introducción
Los algoritmos de búsqueda han sido bastante utilizados desde hace tiempo para la resolución de problemas matemáticos o de lógica, esto nos ha llevado incluso a implementarlos en el desarrollo de juegos (ya sea de un solo jugador o concontrincante) de Inteligencia Artificial.
Algunos algoritmos bastante conocidos son el Minimax y el Poda Alfa Beta, usados para minimizar la perdida máxima aplicada en dichos juegos de adversarios.
En este articulo, podremos ver como se implementa el algoritmo Minimax y Poda Alfa Beta para resolver un problema entre dos adversarios, planteado del libro “Inteligencia Artificial: Un Enfoque Moderno” de losautores Stuart J. Russell y Peter Norving.
Abstract
A basic game between two players, there are two chips (A & B) located on a board of four squares numbered 1 to 4.
The two players move in turn and each player must move his piece to an adjacent empty space in a different direction. The game ends when one player reaches the opposite end of the board.
Resumen
I. Definición delproblema
Un juego básico entre dos jugadores, se tienen dos fichas (A y B) ubicadas en un tablero de cuatro casillas enumeradas del 1 al 4:
A
| | | B
|
1 2 3 4
Los dos jugadores mueven por turno, y cada jugador debe mover su ficha a un espacio vacío adyacente en diferente dirección. El juego termina cuando un jugador alcanza elextremo opuesto del tablero.
El algoritmo Minimax
Este algoritmo analiza la mejor decisión del estado actual. Usa un simple cálculo recurrente de los valores minimax de los anteriores estados sucesores. En un árbol, la recursión avanza hacia las hojas del árbol, y los valores minimax retroceden por el árbol cuando la recursión va desapareciendo o deshaciendo. Este algoritmo, en otras palabras,realizar una exploración en profundidad completa del árbol indicado de juego.
He aquí el algoritmo planteado para el cálculo de decisiones minimax planteado por el libro:
Función DECISION-MINIMAX (estado) devuelve una acción
variables de entrada: estado, estado actual del juego
Otra definición de Minimax
Es un esquema genérico de búsqueda para situaciones en las que el objetivo es ganaruna partida en la que participan dos adversarios que realizan movimientos alternos en el juego. La efectividad de esta estrategia reside en la profundidad aplicada.
Características:
* Algoritmo de decisión para minimizar la pérdida máxima aplicada en juegos de adversarios.
* Información completa (cada jugador conoce el estado del otro).
* Elección del mejor movimiento para cadajugador, suponiendo que el contrincante escogerá el peor.
Representación de los juegos:
* Posición inicial.
* Conjunto de operadores o reglas del juego (definen movimientos legales).
* Estado terminal.
* Función de utilidad (Ej: Gana, pierde, empata).
Poda Alfa Beta (Poda Alpha-Beta)
Este algoritmo es el más utilizado en las aplicaciones referidas a juegos, dada su excepcionalutilidad en el aumento de la velocidad de la búsqueda sin producir pérdida de la información.
Es una extensión en particular del algoritmo de Búsqueda Minimax en juegos de dos contrincantes. Cada vez que se evalúa un nodo u hoja, el algoritmo determina s los nuevos hijos generados pueden generar una mejor utilidad de la que ya posee el nodo estudiado y si afecta al nodo padre. De no ser así,eso significa que seguir analizando esa rama es desperdiciara recursos como tiempo y espacio, por lo cual no se sigue generando y simplemente se le poda, de allí el nombre.
En el algoritmo, se detalla las entradas. Para ingresar al algoritmo, se necesita ingresar el nodo a ser evaluado, del que se obtendrá su utilidad, así como la utilidad del padre para evaluar si es que la nueva utilidad...
Bogotá, Colombia
@hotmail.com
@gmail.com
Introducción
Los algoritmos de búsqueda han sido bastante utilizados desde hace tiempo para la resolución de problemas matemáticos o de lógica, esto nos ha llevado incluso a implementarlos en el desarrollo de juegos (ya sea de un solo jugador o concontrincante) de Inteligencia Artificial.
Algunos algoritmos bastante conocidos son el Minimax y el Poda Alfa Beta, usados para minimizar la perdida máxima aplicada en dichos juegos de adversarios.
En este articulo, podremos ver como se implementa el algoritmo Minimax y Poda Alfa Beta para resolver un problema entre dos adversarios, planteado del libro “Inteligencia Artificial: Un Enfoque Moderno” de losautores Stuart J. Russell y Peter Norving.
Abstract
A basic game between two players, there are two chips (A & B) located on a board of four squares numbered 1 to 4.
The two players move in turn and each player must move his piece to an adjacent empty space in a different direction. The game ends when one player reaches the opposite end of the board.
Resumen
I. Definición delproblema
Un juego básico entre dos jugadores, se tienen dos fichas (A y B) ubicadas en un tablero de cuatro casillas enumeradas del 1 al 4:
A
| | | B
|
1 2 3 4
Los dos jugadores mueven por turno, y cada jugador debe mover su ficha a un espacio vacío adyacente en diferente dirección. El juego termina cuando un jugador alcanza elextremo opuesto del tablero.
El algoritmo Minimax
Este algoritmo analiza la mejor decisión del estado actual. Usa un simple cálculo recurrente de los valores minimax de los anteriores estados sucesores. En un árbol, la recursión avanza hacia las hojas del árbol, y los valores minimax retroceden por el árbol cuando la recursión va desapareciendo o deshaciendo. Este algoritmo, en otras palabras,realizar una exploración en profundidad completa del árbol indicado de juego.
He aquí el algoritmo planteado para el cálculo de decisiones minimax planteado por el libro:
Función DECISION-MINIMAX (estado) devuelve una acción
variables de entrada: estado, estado actual del juego
Otra definición de Minimax
Es un esquema genérico de búsqueda para situaciones en las que el objetivo es ganaruna partida en la que participan dos adversarios que realizan movimientos alternos en el juego. La efectividad de esta estrategia reside en la profundidad aplicada.
Características:
* Algoritmo de decisión para minimizar la pérdida máxima aplicada en juegos de adversarios.
* Información completa (cada jugador conoce el estado del otro).
* Elección del mejor movimiento para cadajugador, suponiendo que el contrincante escogerá el peor.
Representación de los juegos:
* Posición inicial.
* Conjunto de operadores o reglas del juego (definen movimientos legales).
* Estado terminal.
* Función de utilidad (Ej: Gana, pierde, empata).
Poda Alfa Beta (Poda Alpha-Beta)
Este algoritmo es el más utilizado en las aplicaciones referidas a juegos, dada su excepcionalutilidad en el aumento de la velocidad de la búsqueda sin producir pérdida de la información.
Es una extensión en particular del algoritmo de Búsqueda Minimax en juegos de dos contrincantes. Cada vez que se evalúa un nodo u hoja, el algoritmo determina s los nuevos hijos generados pueden generar una mejor utilidad de la que ya posee el nodo estudiado y si afecta al nodo padre. De no ser así,eso significa que seguir analizando esa rama es desperdiciara recursos como tiempo y espacio, por lo cual no se sigue generando y simplemente se le poda, de allí el nombre.
En el algoritmo, se detalla las entradas. Para ingresar al algoritmo, se necesita ingresar el nodo a ser evaluado, del que se obtendrá su utilidad, así como la utilidad del padre para evaluar si es que la nueva utilidad...
Leer documento completo
Regístrate para leer el documento completo.