EXPECTIMINIMAX

Es una variación del algoritmo minimax, el cual tiene un gran uso en la teoría de juegos en inteligencia artificial, especialmente a aquellos que son de suma cero y son búsqueda con adversario, pero en estos especialmente son aquellos que el resultado depende de la combinación de la habilidad del jugador y del azar, como por ejemplo los dados.

En expectiminimax además de los nodos Min y Max de minimax, también se le agrega una variante, que son los nodos casuales o aquellos que deben moverse por naturaleza, sin ningún tipo de intervención del jugador. Estos nodos se alternan con los nodos Max y Min, y estos en vez de tomar el valor máximo o mínimo lo que hacer es tomar un promedio, haciendo uso de la probabilidad de que ese nodo sea alcanzado.

Esta alternación se entrelaza, pero esto depende netamente del juego, en el cual primero se evalúa el nodo con el Max, seguido de un nodo change, después se evaluar el nodo con el Min del oponente, y vuelve a jugar el nodo change.

EJEMPLO

El backgammon es un juego que utiliza el expectiminimax para su realización; este juego tiene 2 jugadores, al tirar los dados se decide qué número de casillas puede mover cada uno de los jugadores, por lo tanto el número obtenido en el lanzamiento es representado en el árbol como el nodo change, al realizar el lanzamiento de los dados, pueden ser muchas las opciones que se pueden desprender, y ahí es donde se hace uso del máximo y mínimo, dependiendo del turno de cada jugador.

En la siguiente imagen se puede ver que el jugador blanco lanzo los dados y obtuvo 6 y 5 u 11, estos valores estarían comprendidos en el nodo change y dependiendo de si es máximo o mínimo se decidirá cuál de las opciones se tomara.

Aquí se muestra la forma en la que se representa la búsqueda en el árbol, generándolo cada vez que se realiza una jugada y cuando el movimiento sea realzado, este se borra y con el siguiente turno se vuelve a generar otro árbol, teniendo en cuenta los nodos change, que como en el ejemplo anterior, se generan con el lanzamiento de los dados, pero esto puede variar en cada juego.

COMPLEJIDAD

El costo de la búsqueda incrementa del de minimax, ya que en este se deben agregar los movimientos al azar, por esto la complejidad varia en el orden de:

Donde n es el número de resultados al azar. 

SEUDOCODIGO