3.5 ExpectiMax [Inteligencia Artificial]

Vamos a utilizar un simple juego de mesa Aislamiento de seis movimientos para ilustrar las ideas.
Vamos a añadir círculos para mostrar los nodos de probabilidad.
Es el turno de O y tiene 4 movimientos posibles.


En el primer nodo vamos a explorar, es en el que O trata de ir más a la izquierda, en la primera posición, pero si se intenta se va a tener éxito solamente el 90% del tiempo.
Y el 10% del tiempo que va a terminar en la posición a su izquierda inmediata.

Sus movimientos son otros para tratar de ir un paso a la izquierda, lo que lo hará el 90% del tiempo y el 10% del tiempo que se rebase.

Pero si se intenta que las otras dos posiciones no tengan oportunidad de sobrepasar o quedarse corto, por lo que serán fácil. Pero vamos a concentrarnos en la mayor parte de la rama izquierda en primer lugar.

Cuando es el turno de X, que tendrán tres movimientos posibles. Se pued tratar de ir inmediatamente a la derecha con un 90% de probabilidad de tener éxito y 10 % de probabilidad de rebasarlo.

Del mismo modo, si se trata de ir todo el camino a la derecha, hara que sea 90% del tiempo y su oscilación 10% del tiempo. Y si va en diagonal hacia arriba y a la derecha que llegara al 100% del tiempo.

Asi que ahora tendremos que hacer unos cálculos, Utilizando nuestro número estándar de la función de evaluación se mueve, o tener un movimiento a disposición en este juego de mesa. Y dos nodos disponibles de aquí. Eso significa que el valor esperado de esta rama es:
0,9 x 1 + 0,1 x 2 = 1.1

Entonces, para el siguiente nodo más tenemos un valor de 2 para este nodo 0.9 veces mas el valor del nodo derecho, que es 1, los tiempos de 0,1.
Pero nótese que no tenemos para evaluar el nodo correcto.

Desde este nivel tenemos un nivel mínimo, tan pronto como vimos las 0,9 veces 2 que tenia 1,8 eso ya es más grande que el 1.1 que teníamos en el lado izquierdo, por lo que sabemos que nunca vamos a utilizar este nodo.

No tenemos que evaluar este nodo en absoluto. Eso está bien porque sabemos que la función de evaluación no puede ir por debajo de cero.
¿Pero puede nuestra función de evaluación ser negativa?
Nuestra función no puede ser negativa por que no podríamos podar.

En general en ExpectiMax, solo se pueden podar límites cuando ya conocen en los valores que serán devueltos por la función ExpectiMax.

Vamos a elegir la siguiente rama, ya que su valor es 1 y su probabilidad también es de 1. Por lo tanto el valor esperado para este nodo es de 1.
Vamos a probar el siguiente sub-árbol terminado.

Mirando a los nodos inferiores, todo lo que se evalúa como 2, todas las ramas se evalúan a 2 y el valor de este nodo es también 2.


Vamos a probar el siguiente sub-árbol.
Una vez más todos los nodos inferiores son 2s. Por lo que el valor de los nodos será de 2.


El siguiente es más interesante, el nodo más interior izquierdo tiene solo un movimiento restante para O. Y eso se multiplica por 0.9 añadido a eso las 2 veces el 0.1 en el nodo más cercano de X.
Eso nos lleva a una suma de 1,1

En cuanto a la siguiente rama si X trata de ir con todo el campo a la derecha, se obtienen dos veces 0,9 o 0,8. Ahora podemos podar esta otra rama.
Pero vamos a calcular hacia fuera para fines de ilustración.

El número de la función de evaluación de los movimientos, que es a su vez uno aquí, así que:
2 x 0,9 + 1 x 0,1 = 1,9
Sin embargo la última opción es la mejor. Devuelve un 1 con una probabilidad de 100%.

Por lo tanto el valor de este nodo seria de 1.


La siguiente opción sería fácil de calcular todo viene a 2s.


El que sigue también es fácil ya que todos los movimientos son 100% exactos.
Puesto que es un nodo de mediados vamos a elegir un 1.


Ahora que hemos calculado todos los valores, podemos elegir la rama con el valor mas alto en la parte superior del nodo Max.
A pesar de que no ayudara a O en este ejemplo de juego, O va a perder a menos que X haga una mala elección.
Si utilizamos este algoritmo y buscamos al final del juego, el algoritmo podría elegir una rama donde X puede perder.
Por desgracia nuestro simple número de movimientos de la función de evaluación no captura esta posibilidad.
Buscando un juego más profundo debería resolver el problema.

---

Vamos a repasar ahora.
Los valores de ramificación más a la izquierda se calculan multiplicando 0,1 x el valor mínimo que es 8 + 0,5 el valor mínimo de la siguiente rama que es 5 + 0,4 x 8 La suma es igual a 6,5
El nodo inferior izquierdo del sub-árbol medio devuelve un valor de 0
0,5 x 0 = 0

Ni siquiera necesitamos evaluar la rama derecha del árbol,
El máximo que podíamos conseguir es un 0,5 x 10 que es 5.0
Desde 5 es inferior a 6,5 podemos ignorarlo.

Tenga en cuenta que si nuestros nodos se ordenaran mejor, podrían haber tenido un 0 en la rama más a la izquierda. Entonces podríamos haber hecho caso omiso a todo lo demás.
Como sabemos que el valor de este sub-árbol va a ser 5 o inferior, en otras palabras, habríamos sabido que:
0,5 x 0 + 0,5 x 10 va a ser menor o igual a 5 para el sub-árbol derecho,

Tenemos 0,1 x 3 = 0,3
Conseguimos un 10 en la siguiente rama o en algunas de las ramas por lo que obtenemos un 0,9 veces sobre el resto del sub-árbol.
Así que solo toca continuar por que vamos a conseguir realmente un 8,3 en el final

Probablemente deberíamos evaluar estos sub-arboles con las más altas probabilidades primero y los más altos valores esperados en primer lugar.
Sin embargo en este caso seguimos con 0,5 x 8 = 4,5
Así que tenemos 0,3 + 4,5 por lo que ahora es 4,8

Todavía hay una posibilidad de que podamos conseguir un valor medio que el 6,5 por lo que continuamos.
En la siguiente rama se obtiene un 2 en este punto sabemos lo que este sub-árbol va a tener para un valor que es menor o igual a 0,1x3+0,5x9+0,4x2 que es =5.6
Por lo tanto hemos terminado la última rama no importa, ya que nuestro jugador va a elegir la rama más a la izquierda.

---

FIN