Arbre Expectiminimax

Un arbre expectiminimax és una variació especialisada d'un arbre de joc minimax. És utilisat en sistemes d'inteligència artificial en jocs de suma zero per a dos jugadors o més com per eixemple: backgammon, que el resultat depén d'una combinació d'habilitat i elements de possibilitat del jugador com a llançament de daus. Ademés de min i max, nodos tradicionals del arbre minimax , esta variant té nodos de possibilitat ("moviment per naturalea"), els quals prenen el valor esperat d'un acontenyiment aleatori que ocorre. En térmens de teoria de jocs, un arbre expectiminimax és l'arbre de joc d'un jugue de forma extensa d'informació perfecta, pero incompleta.

En el método tradicional minimax, els nivells de l'arbre alternen de max a min fins que el llímit de profunditat de l'arbre ha segut alcançat. En un arbre expectiminimax, els nodos de possibilitat són intercalados en els nodos max i min. En lloc de prendre el max o min dels valors d'utilitat dels seus fills, els nodos de possibilitat prenen un pes promig, sent el pes la provabilitat de  que el fill siga alcançat.

El valor a utilisar (min, max o la provabilitat) depén del joc. Cada tanda del joc és evaluat com un nodo max (representant la tanda del jugador AI), un nodo min (representant una tanda de l'adversari potencialment-optimal), o un nodo de possibilitat o chance(representant un efecte aleatori o un jugador).

Per eixemple, considerara un joc en que cada ronda consta del llançament d'un sol dau, les decisions fetes pel primer jugador AI, i  un atre adversari inteligent. L'orde dels nodos en este joc alternarien entre possibilitat, max i llavors min.

Pseudocódigo

L'algoritme expectiminimax és una variant del minimax, propost anteriorment per Donald Michie en 1966. El seu pseudocódigo es mostra a continuació.

funció expectiminimax(nodo, profunditat)
    si el nodo és un nodo terminal o profunditat == 0
        retornar el valor heurístic del nodo
    si l'adversari juga en el nodo
        //retornar el valor del nodo fill en menor valor
        α := +∞
        per cada fill del nodo
            α := min(α, expectiminimax(fill, profunditat-1))
    sino si nos toca jugar en el nodo
        //retornar el valor del nodo fill en major valor        
        α := -∞
        per cada fill del nodo
            α := max(α, expectiminimax(fill, profunditat-1))
    sino si el nodo és d'acontenyiment aleatori
        //retornar el valor promig de tots els nodos fills
        α := 0
        per cada fill del nodo
            α := α + (Provabilitat[fill] * expectiminimax(fill, profunditat-1))
    retornar α

Notar que per a nodos aleatoris, deu existir una provabilitat coneguda per a  aplegar a cada u dels seus descendents. Per a la majoria dels jocs de provabilitat, el pes dels nodos fills estarà igualment distribuït, lo que significa que el valor de tornada senzillament pot ser el promig dels valors dels fills.

Complexitat

Si el programa coneix de bestreta totes les possibles jugades que ocorrerien durant el restant del joc, resoldre un joc en daus seria com resoldre un joc sense daus. Minimax simula este procés en una complexitat temporal de $O(b^m)$ , a on b és el factor de ramificació i m és la profunditat màxima de l'arbre de joc. Degut a que Expectiminimax també està considerant totes les seqüències de jugades possibles, prendrà $O(b^m*n^m)$, a on n és el número de tirades distintes.

Vore també

• Minimax
• Valor Esperat
• Arbre de joc