Búsqueda

EXPECTIMINIMAX

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.

 

expectiminimaz

Fig. 1 Algoritmo expectiminimax [3]

Ejemplo del algoritmo

ejemplo expectiminimaxFig. 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:

pseudo expectim
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.

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 )

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 )

Google+ photo

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

Conectando a %s