Es un algoritmo propuesto por Donal Michie en 1996, basado en minimax, incluyendo sus nodos min y max, la diferencia es que utiliza un nodo adicional llamados chance, esté nodo toma el valor esperado de un evento aleatorio.
La toma de decisiones cambia debido al nodo chance, por este ya no se puede calcular el Minimax en cada nivel, así que solo se calcula un valor esperado de cierta posición, este se estima del promedio sobre todos los posibles resultados de los nodos chance.
En cada turno de los jugadores hay un nodo chance para cada posible cambio del resultado del elemento aleatorio y una probabilidad asociada de que ese nodo ocurra.
Este algoritmo es de Información completa, con azar, ya que los nodos chance toma valores que no se conocen y esto genera una cierta incertidumbre en el juego.
Fig. 1 Algoritmo expectiminimax [3]
Ejemplo del algoritmo
Fig. 2 Ejemplo del algoritmo expectiminimax [4]
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.
Complejidad:
Complejidad en el tiempo: O(b^m n^m)
n: número de resultados al azar
Pseudocódigo:
Fig 3. Pseudocódigo del algoritmo espectiminimax. [4]
Bibliografía
[1] Expectiminimax tree. (2016). En.wikipedia.org. Retrieved 5 May 2017, from https://en.wikipedia.org/wiki/Expectiminimax_tree
[2] Desai, X. Catalogue of Artificial Intelligence Techniques. Aicat.inf.ed.ac.uk. Retrieved 5 May 2017, from http://aicat.inf.ed.ac.uk/entry.php?id=690
[3] Russell, S., & Norving, P. (2010). Artificial intelligence (3rd ed., pp. 177-179). New Jersey: Pearson.
[4] Gomez Gomez, C. (2016). TUTOR DE ALGORITMOS DE JUEGOS (1st ed., pp. 19-21). Málaga. Retrieved from https://riuma.uma.es/xmlui/bitstream/handle/10630/12713/CristinaGomezGomezMemoriaTFG.pdf?sequence=1
[5]Alonso Jimenez, J., Graciani Dıaz, C., Martın Mateos, F. and Ruiz Reina, J. (2004). Técnicas heurısticas en juegos. [online] Available at: https://www.cs.us.es/cursos/iia-2004/temas/tema-04.pdf.
INTELIGENCIA ARTIFICIAL (IA) 