Expecti minimax

puntos a trabajar:

1) que es?

2) como funciona, de ejemplos.

3) complejidad.

4)seudocodigo.

Solucion:

1) que es?

R/ el algoritmo expectiminimax es una especial variacion del algoritmo minimax utilizado en los sistemas de inteligencia artificial en busqueda con adversario y juegos de dos jugadores como el backgammon, en donde se tiene un elemento al azar y los valores conocidos de los nodos en los cuales se este desarrollando el algoritmo de tal forma que en el momento de estar realizando la busqueda se tiene en cuenta al momento de desarrollar el algoritmo minimax un elemento aleatorio el cual ifluye y ayuda en la desicion de los nodos a recorrer en el arbol.

2) como funciona, de ejemplos.

R/

3) complejidad.

R/la complejidad del algoritmo es:
Complejidad en el tiempo: O(b^m n^m)

n: número de resultados al azar

4)seudocodigo.

R/
 function expectiminimax(nodo, profundidad)

    si en nodo es un nodo terminal o la profundidad = 0
        retorne el valor de la heuristica del nodo
        si el adversario debe jugar en el nodo
        //retorne el valor del minimo valor del nodo hijo
        // Return value of minimum-valued child node
        haga α := +∞
        por cada nodo hijo
            α := min(α, expectiminimax(hijo, profundidad-1))
    else if nosotros debemos jugar con el nodo hijo
        // retorne el valor del maximo-valor del nodohijo
        haga α := -∞
        por cada nodo hijo
            α := max(α, expectiminimax(hijo, profundidad-1))
    else if hay un evento aleatorio en el nodo
        // retorne Promedio ponderado de los valores de todos los nodos hijos
        haga α := 0
        por cada nodo hijo
            α := α + (Probability[hijo] * expectiminimax(hijo, profundidad-1))
    retorne α

Bibliografia:

• https://courses.cs.washington.edu/courses/cse473/12au/slides/lect8.pdf
• https://courses.cs.washington.edu/courses/cse473/11au/slides/cse473au11-adversarial-search.pdf
• https://en.wikipedia.org/wiki/Expectiminimax_tree
• http://agents.csie.ntu.edu.tw/~yjhsu/courses/u0220/1997/10-29/webnotes.html