Árbol Expectiminimax

Un árbol expectiminimax es una variación especializada de un árbol de juego minimax. Es utilizado en sistemas de inteligencia artificial en juegos de suma cero para dos jugadores o más como por ejemplo: backgammon, en que el resultado depende de una combinación de habilidad y elementos de posibilidad del jugador como lanzamiento de dados. Además de min y max, nodos tradicionales del árbol minimax , esta variante tiene nodos de posibilidad ("movimiento por naturaleza"), los cuales toman el valor esperado de un acontecimiento aleatorio que ocurre.​ En términos de teoría de juegos, un árbol expectiminimax es el árbol de juego de un juego de forma extensa de información perfecta, pero incompleta.

En el método tradicional minimax, los niveles del árbol alternan de max a min hasta que el límite de profundidad del árbol ha sido alcanzado. En un árbol expectiminimax, los nodos de posibilidad son intercalados con los nodos max y min. En vez de tomar el max o min de los valores de utilidad de sus hijos, los nodos de posibilidad toman un peso promedio, siendo el peso la probabilidad de  que el hijo sea alcanzado.

El valor a utilizar (min, max o la probabilidad) depende del juego. Cada turno del juego es evaluado como un nodo max (representando el turno del jugador AI), un nodo min (representando un turno del adversario potencialmente-optimal), o un nodo de posibilidad o chance(representando un efecto aleatorio o un jugador).

Por ejemplo, considerare un juego en que cada ronda consta del lanzamiento de un solo dado, las decisiones hechas por el primer jugador AI, y  otro adversario inteligente. El orden de los nodos en este juego alternarían entre posibilidad, max y entonces min.

Pseudocódigo

El algoritmo expectiminimax es una variante del minimax, propuesto anteriormente por Donald Michie en 1966. Su pseudocódigo se muestra a continuación.

función expectiminimax(nodo, profundidad)
    si el nodo es un nodo terminal o profundidad == 0
        retornar el valor heurístico del nodo
    si el adversario juega en el nodo
        //retornar el valor del nodo hijo con menor valor
        α := +∞
        por cada hijo del nodo
            α := min(α, expectiminimax(hijo, profundidad-1))
    sino si nos toca jugar en el nodo
        //retornar el valor del nodo hijo con mayor valor        
        α := -∞
        por cada hijo del nodo
            α := max(α, expectiminimax(hijo, profundidad-1))
    sino si el nodo es de acontecimiento aleatorio
        //retornar el valor promedio de todos los nodos hijos
        α := 0
        por cada hijo del nodo
            α := α + (Probabilidad[hijo] * expectiminimax(hijo, profundidad-1))
    retornar α

Notar que para nodos aleatorios, debe existir una probabilidad conocida para  llegar a cada uno de sus descendientes. Para la mayoría de los juegos de probabilidad, el peso de los nodos hijos estará igualmente distribuido, lo cual significa que el valor de regreso sencillamente puede ser el promedio de los valores de los hijos.

Complejidad

Si el programa conoce de antemano todas las posibles jugadas que ocurrirían durante el resto del juego, resolver un juego con dados sería como resolver un juego sin dados. Minimax simula este proceso con una complejidad temporal de $O(b^{m})$ , donde b es el factor de ramificación y m es la profundidad máxima del árbol de juego. Debido a que Expectiminimax también está considerando todas las secuencias de jugadas posibles, tomará $O(b^{m}*n^{m})$, donde n es el número de tiradas distintas.​

Ejemplo

Dado el siguiente árbol, los pasos a seguir serían​:

MAX                  ( 3 )
                    /     \
CHANCE       ( 3 )          ( -1 )
               /\             /\
          0.5 /  \ 0.5   0.5 /  \ 0.5
             /    \         /    \
MIN      ( 2 )   ( 4 )  ( 0 )   ( -2 )
          /\      /\      /\      /\
         2  4    7  4    6  0    5 -2

Fig1. Ejemplo de Árbol 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.
2. Nivel 3: En cada nodo MIN, se escogerá el valor del menor de sus hijos, según el árbol de la Fig1 los menores son: 2, 4, 0 y -2. (De izquierda a derecha)
3. Nivel 2: Los nodos intermedios son los nodos tipo chance o posibilidad.
   1. Se calcula el valor para cada nodo chance de la siguiente manera:
      1. Primer nodo de izquierda a derecha : 𝑒𝑥𝑝𝑒𝑐𝑡𝑒𝑑_𝑣𝑎𝑙𝑢𝑒 = 0.5 ∗ 2 + 0.5 ∗ 4 = 1 + 2 = 3
      2. Segundo nodo de izquierda a derecha: 𝑒𝑥𝑝𝑒𝑐𝑡𝑒𝑑_𝑣𝑎𝑙𝑢𝑒 = 0.5 ∗ 0 + 0.5 ∗ (−2) = −1
4. Nivel 1: En el nodo MAX, que en este caso es la raíz, se selecciona el valor del mayor de sus nodos hijos, para este caso se selecciona el 3.

Véase también

• Minimax
• Valor Esperado
• Árbol de juego

Referencias

• Datos: Q1384259