1.3 Niveles Min y Max [Inteligencia Artificial]

Árbol de Juego de aislamiento con valores de hoja

Link:

No tienes permitido ver los links. Registrarse o Entrar a mi cuenta

Tome un tiempo para analizar el árbol de juego y luego continuar.
Observe el segundo sub árbol del nivel 1 (donde "O" escoge la parte superior, celula media) – conduce a un montón de perdidas (valores -1).


¿Puede pensar en una manera de marcar este subárbol entero cono una mala elección?

En la mayoría de situaciones en este árbol de juego por ordenador nuestro "O" gana, Sin embargo en algunas situaciones, el juego termina con nuestro oponente "X" ganador a nivel cinco.
Si nuestro jugador de la computadora hace una mala elección para su primer movimiento, "X" puede ganar, no importa lo que "O" haga.

Está claro que no queremos que nuestro jugador de la computadora haga mal este primer movimiento. Para evitar esta situación podemos mantener una tabla de mejores primeros movimientos de esta configuración de tablero.

Esta tabla llamara a un libro de aperturas, tablas similares se pueden mantener durante juego finales.
¿Pero cómo podemos descubrir las malas jugadas automáticamente?
¿Mejor aún, Como descubrimos los mejores movimientos para un jugador?
La respuesta es el algoritmo Minimax, unan versión de la que veremos a continuación.

Niveles Min y Max

Con nodo terminal en nuestro árbol de juego, con un 1 nuestro jugador gana y un -1 pierde.
Hemos utilizado los cuadrados para indicar los nodos terminales y poner sus indicaciones en su interior.
Vamos a suponer que nuestro oponente X es muy inteligente y siempre juega para ganar. En otras palabras, vamos a suponer que X siempre minimiza las calificaciones de S.

Mientras que nuestro jugador de la computadora siempre tratara de maximizar sus resultados.
Para mostrar esta idea, vamos a marcar el árbol de juego con un triángulo que apunta para indicar giros cuando nuestro jugador está tratando de maximizar la puntuación.
El triángulo apuntando hacia abajo cuando el componente está tratando de reducir al mínimo el marcador.




Dado que nuestro jugador de la computadora va primero, Empezamos con el nivel de maximización.
En general, ya que estamos buscando únicamente desde la perspectiva de nuestro jugador de la computadora, que solo puede afectar el juego cuando se trata a su vez, la parte superior de un árbol Minimax siempre va a ser un nivel máximo.


Propagando valores arriba del árbol

Con el fin de propagar las ganancias y pérdidas de el árbol de juego, hasta el punto que un jugador de la computadora pueda tomar una decisión, tenemos que empezar en la parte inferior del árbol.
Vamos a empezar con el lado izquierdo del árbol.

En la rama más a la izquierda, "O" gana.
En la siguiente más. "O" nunca utiliza la última casilla del tablero de juego y pierde.
Dado que nuestro oponente "X" juega para ganar y reduce al mínimo la puntuación de "O", nunca va a elegir la rama de la izquierda. En su lugar, va a elegir esta rama que está garantizado para darle al equipo jugador una puntuación de -1.

Sin embargo nuestro jugador de la computadora puede evitar esta situación haciendo una sabia elección de un nivel superior.


Ambas ramas de este árbol conducen a la victoria, por lo tanto, las puntuaciones de 1.
Podemos mantener la propagación de estas puntuaciones en el árbol, alternando en los niveles máximos hasta llegar a la cima.

Este proceso de los valores de cálculo para cada parte inferior del nodo al principio es conocido como el algoritmo Minimax.

Para cada nodo Max, escoge el valor máximo entre sus nodos secundarios.
Si hay por lo menos una ramificación más, el computador puede escogerlo siempre para ganar. De lo contrario, nunca podría ganar a partir de ese momento, suponiendo un oponente perfecto.
Por su puesto, a través de representar el oponente, en cada nodo mediano, escogemos el valor mínimo.

Ejercicio
Puede practicar con la siguiente parte del árbol de juego colocando el +1 o -1 dependiendo el caso de cada movimiento.

---