EXPECTIMINIMAX

ALGORITMO EXPECTIMINIMAX

El algoritmo expectiminimax es otra variante del algoritmo minimax para búsquedas en arboles con adversario con azar, en donde los hijos de cada nodo son todos los resultados al azar que pueden presentarse en el juego. El algoritmo expectiminimax esta enfocado para juegos que contienen un elemento de imprevisibilidad y como tal el árbol  de juego no es determinista. El árbol de juego que funciona en Minimax se basa entre dos conjuntos de nodos, nodos linfáticos Max y Min, sin embargo, el árbol de juego expectiminimax incluye otro conjunto de nodos linfáticos Probabilidad, que se muestran como círculos. Para cada jugador al girar hay un nodo de azar para cada posible permutación de los resultados elemento aleatorio (en el caso del material 2 dados hay 21 resultados distintos) y una probabilidad asociada de que el nodo que se produzcan.

El principal proceso de toma de decisiones del algoritmo Minimax está vinculada con su valor minimax. Sin embargo, debido a la elemento de imprevisibilidad, no es posible calcular un valor minimax definida para cada nivel, por lo que se utiliza el valor esperado del nivel. Cálculo del valor expectiminimax de un nodo está dada por la siguiente n:

• Seudocodigo tomado de:

https://en.wikipedia.org/wiki/Expectiminimax_tree

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 α 




COMPLEJIDAD:

La complejidad del algoritmo expectiminimax esta dado por: mayor O(b^m)-> O(b^m (n^m)) N: numero de resultados al azar.



EJEMPLOS:


Ejemplo tomado de la pagina: 

https://ia301ud.wordpress.com/2017/05/03/expectiminimax/

1. Nivel 4: Se genera el árbol, como en Minimax y por medio de una función de utilidad se da el valor a los nodos hojas (Árbol de la Fig 2).

2. Nivel 3: En cada nodo MIN, se escogerá el de menor valor de los valores de sus hijos, según el árbol de la fig 2 los menores son: 2,4,0 y -2. (De izq. a der.)


3. Nivel 2:Los nodos representados mediante círculos son de tipo Chance.Ahora calculamos el valor para cada nodo chance de la siguiente manera:

Primer nodo de izq. a der. :
𝑒𝑥𝑝𝑒𝑐𝑡𝑒𝑑_𝑣𝑎𝑙𝑢𝑒 = 0.5 ∗ 2 + 0.5 ∗ 4 = 1 + 2 = 3


Segundo nodo de izq a der:
𝑒𝑥𝑝𝑒𝑐𝑡𝑒𝑑_𝑣𝑎𝑙𝑢𝑒 = 0.5 ∗ 0 + 0.5 ∗ (−2) = −1
 

4. Nivel 1: El nodo max que en este caso es la raíz, aquí se selecciona el de mayor valor de los nodos hijos, para este caso se selecciona el 3.