Expectiminimax

EXPECTIMINIMAX

El algoritmo expectiminimax es una derivación del algoritmo minimax con la diferencia que se ingresa un nuevo elemento en el árbol que es un nodo al azar llamado nodo chance que permite la elección del mínimo o máximo de pendiendo el nivel donde se esté haciendo la búsqueda sin afectar la decisión final de elección. Este juego es de suma cero, bipersonal, información incompleta, y no determinísticos  además de utilizar una función de evaluación para poder limitar las ramas del árbol. Vale recordar que utiliza la búsqueda en profundidad

Dichos nodos “CHANCE” se intercalan con los nodos MIN y MAX. En dichos nodos, en lugar de tomar el máximo o el mínimo de los valores de utilidad de sus hijos, como se hace en el Minimax, se toma una media ponderada de los valores de sus hijos, en la cual los pesos serán las probabilidades de los sucesores. La forma de intercalar dichos nodos depende de cada juego. Cada turno del juego se evalúa como un nodo “MAX”, que representa el turno del jugador, un nodo “MIN”, que representa al adversario, o un nodo “CHANCE”, que representa un jugador o efecto aleatorio. Por ejemplo, consideremos un juego en el que cada ronda consta de un solo tiro de dados y, a continuación, las decisiones tomadas por el primer jugador de la IA, y luego otro oponente inteligente. El orden de los nodos en este juego se alterna entre ” CHANCE “, ” MAX ” y ” MIN “.

Seudocódigo

función expectiminimax (nodo, profundidad)

si el nodo es un nodo terminal o profundidad = 0

retorno el valor heurístico de nodo

si el adversario es jugar en el nodo

// Valor de retorno de nodo de valor mínimo niño

dejar α: = + ∞

foreach hijo del nodo

α: = min (α, expectiminimax (niño, profundidad-1))

más si vamos a jugar en el nodo

// Valor de retorno de nodo de máxima valioso niño

dejar α: = -∞

foreach hijo del nodo

α: = max (α, expectiminimax (niño, profundidad-1))

else if evento aleatorio en el nodo

// Devuelve la media ponderada de los valores de todos los nodos hijos

dejar α: = 0

foreach hijo del nodo

α: = α + (Probabilidad [niño] * expectiminimax (niño, profundidad-1))

retorno α

34.png

Explicaremos cómo funciona el algoritmo mediante el ejemplo anterior.

  1. En primer lugar, se genera el árbol, al igual que en el algoritmo Minimax. Mediante una función de utilidad se da valor a las hojas de este, situadas en el nivel 4.
  2. En el nivel 3 tenemos nodos MIN, por lo que cada nodo seleccionará el menor valor de los valores de sus hijos, siendo 2,4,0 y -2 los valores escogidos.
  3. En el nivel 2, los nodos son de tipo CHANCE. ¿Cómo se calculará su valor?

Situémonos en el nodo de la izquierda de nivel dos. Calcularemos su valor de la siguiente manera:

𝑒𝑥𝑝𝑒𝑐𝑡𝑒𝑑_𝑣𝑎𝑙𝑢𝑒 = 0.5 ∗ 2 + 0.5 ∗ 4 = 1 + 2 = 3

Por tanto, su valor esperado será 3. Para el nodo de la derecha tendremos:

𝑒𝑥𝑝𝑒𝑐𝑡𝑒𝑑_𝑣𝑎𝑙𝑢𝑒 = 0.5 ∗ 0 + 0.5 ∗ (−2) = −1

Por lo que su valor será -1.

  1. El nodo de nivel 1, la raíz, es de tipo MAX, por lo que seleccionará el mayor valor de ambos, el 3.

Este ejemplo es bastante sencillo y, además las probabilidades son las mismas para todos los hijos, lo que correspondería a una media simple, sin embargo, no siempre es así, pues la probabilidad dependerá del juego en concreto.

 

Referencia del ejemplo

https://riuma.uma.es/xmlui/bitstream/handle/10630/12713/CristinaGomezGomezMemoriaTFG.pdf?sequence=1

 

Anuncios

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión /  Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión /  Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión /  Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión /  Cambiar )

Conectando a %s