Expectiminimax

El algoritmo expectiminimax es una variación del algoritmo minimax , para su uso en sistemas de inteligencia artificial que juegan juegos de suma cero para dos jugadores , como el backgammon , en los que el resultado depende de una combinación de la habilidad del jugador y elementos de azar como las tiradas de dados. . Además de los nodos "mínimo" y "máximo" del árbol minimax tradicional, esta variante tiene nodos de "oportunidad" (" movimiento por naturaleza "), que toman el valor esperado de que ocurra un evento aleatorio. ^[1] En términos de teoría de juegos , un árbol expectiminimax es el árbol de juego de un juego de forma extensiva de información perfecta , pero incompleta .

En el método minimax tradicional , los niveles del árbol se alternan de máximo a mínimo hasta que se alcanza el límite de profundidad del árbol. En un árbol expectiminimax, los nodos de "posibilidad" se entrelazan con los nodos máximo y mínimo. En lugar de tomar el máximo o el mínimo de los valores de utilidad de sus hijos, los nodos de probabilidad toman un promedio ponderado, siendo el peso la probabilidad de que se alcance el hijo. ^[1]

El entrelazado depende del juego. Cada "turno" del juego se evalúa como un nodo "máximo" (que representa el turno del jugador de IA), un nodo "mínimo" (que representa el turno de un oponente potencialmente óptimo) o un nodo de "oportunidad" (que representa un efecto aleatorio o jugador). ^[1]

Por ejemplo, considere un juego en el que cada ronda consta de un solo lanzamiento de dado y luego decisiones tomadas primero por el jugador de la IA y luego por otro oponente inteligente. El orden de los nodos en este juego alternaría entre "oportunidad", "máximo" y luego "mínimo". ^[1]

Pseudocódigo

El algoritmo expectiminimax es una variante del algoritmo minimax y fue propuesto por primera vez por Donald Michie en 1966. ^[2] Su pseudocódigo se proporciona a continuación.

función expectiminimax(nodo, profundidad) si el nodo es un nodo terminal o profundidad = 0 devuelve el valor heurístico del nodo si el adversario va a jugar en el nodo // Valor de retorno del nodo secundario de valor mínimo sea ​​α := +∞ para cada hijo del nodo α := min(α, expectiminimax(niño, profundidad-1)) de lo contrario si vamos a jugar en el nodo // Valor de retorno del nodo secundario de valor máximo sea ​​α := -∞ para cada hijo del nodo α := max(α, expectiminimax(niño, profundidad-1)) de lo contrario, si es un evento aleatorio en el nodo // Devuelve el promedio ponderado de los valores de todos los nodos secundarios sea ​​α := 0 para cada hijo del nodo α := α + (Probabilidad[niño] × expectiminimax(niño, profundidad-1)) regresar α

Tenga en cuenta que para los nodos aleatorios, debe haber una probabilidad conocida de llegar a cada niño. (Para la mayoría de los juegos de azar, los nodos secundarios tendrán la misma ponderación, lo que significa que el valor de retorno puede ser simplemente el promedio de todos los valores secundarios).

búsqueda expectimax

La búsqueda Expectimax es una variante descrita en Universal Artificial Intelligence: Sequential Decisions Based on Algorithmic Probability (2005) de Tom Everitt y Marcus Hutter .

Poda alfa-beta

Bruce Ballard fue el primero en desarrollar una técnica, llamada *-minimax, que permite la poda alfa-beta en árboles expectiminimax. ^{[3] [4]} El problema con la integración de la poda alfa-beta en el algoritmo expectiminimax es que las puntuaciones de los hijos de un nodo de probabilidad pueden exceder el límite alfa o beta de su padre, incluso si el valor ponderado de cada hijo no lo hace. Sin embargo, es posible vincular las puntuaciones de los hijos de un nodo de oportunidad y, por lo tanto, vincular la puntuación del nodo OPORTUNIDAD.

Si una búsqueda iterativa estándar está a punto de puntuar el ésimo hijo de un nodo de probabilidad con hijos igualmente probables, esa búsqueda ha calculado puntuaciones para los nodos hijos del 1 al . Suponiendo una puntuación más baja posible y una puntuación más alta posible para cada niño no buscado, los límites de la puntuación del nodo de probabilidad son los siguientes: ${\displaystyle i}$ ${\displaystyle N}$ ${\displaystyle v_{1},v_{2},\ldots ,v_{i-1}}$ ${\displaystyle i-1}$ ${\displaystyle L}$ ${\displaystyle U}$

${\displaystyle {\text{score}}\leq {\frac {1}{n}}\left((v_{1}+\ldots +v_{i-1})+v_{i}+U\times (n-i)\right)}$

${\displaystyle {\text{score}}\geq {\frac {1}{n}}\left((v_{1}+\ldots +v_{i-1})+v_{i}+L\times (n-i)\right)}$

Si se da un límite alfa y/o beta al calificar el nodo de probabilidad, estos límites se pueden usar para interrumpir la búsqueda del decimoésimo niño. Las ecuaciones anteriores se pueden reorganizar para encontrar un nuevo valor alfa y beta que interrumpirá la búsqueda si provocara que el nodo de probabilidad exceda sus propios límites alfa y beta: ${\displaystyle i}$

${\displaystyle \alpha _{i}=N\times \alpha -\left(v_{1}+\ldots +v_{i-1}\right)+U\times (n-i)}$

${\displaystyle \beta _{i}=N\times \beta -\left(v_{1}+\ldots +v_{i-1}\right)+L\times (n-i)}$

El pseudocódigo para extender expectiminimax con poda alfa-beta resistente a fallas de esta manera es el siguiente:

función *-minimax(nodo, profundidad, α, β) si el nodo es un nodo terminal o profundidad = 0 devuelve el valor heurístico del nodo si el nodo es un nodo máximo o mínimo devuelve el valor minimax del nodo sea N = numSuccessors(nodo ) // Calcular α, β para niños sea ​​A = N * (α - U) + U sea B = N * (β - L) + L sea suma = 0 para cada hijo del nodo // Limita los hijos α, β a un rango válido sea ​​AX = max(A, L) sea BX = min(B, U) //Buscar al niño con nuevos valores de corte let puntuación = *-minimax(niño, profundidad - 1, AX, BX) // Comprobar las condiciones de corte α, β si puntuación <= A devuelve α si puntuación >= B devuelve β suma += puntuación //Ajusta α, β para el siguiente hijo A += U-v B += L-v // No se produjo ningún límite, devuelve la puntuación suma devuelta / N

Esta técnica pertenece a una familia de variantes de algoritmos que pueden limitar la búsqueda de un nodo CHANCE y sus hijos basándose en la recopilación de los límites superior e inferior de los hijos durante la búsqueda. Otras técnicas que pueden ofrecer beneficios de rendimiento incluyen sondear a cada niño con una heurística para establecer un mínimo o un máximo antes de realizar una búsqueda completa en cada niño, etc.

Ver también

• minimax
• Poda alfa-beta
• Negamax
• Valor esperado

Referencias

1. Russell, Stuart Jonathan; Norvig, Peter; Davis, Ernesto (2010). Inteligencia artificial: un enfoque moderno . Prentice Hall. págs. 177-178. ISBN 978-0-13-604259-4.
2. Michie, D. (1966). "Autómatas de juego y aprendizaje". Avances en Programación y Computación No Numérica . págs. 183-200. doi :10.1016/B978-0-08-011356-2.50011-2. ISBN 978-0-08-011356-2.
3. Ballard, Bruce W. (septiembre de 1983). "El procedimiento de búsqueda *-minimax para árboles que contienen nodos de azar". Inteligencia artificial . 21 (3): 327–350. doi :10.1016/S0004-3702(83)80015-0.
4. Hauk, Thomas; Buró, Michael; Schaeffer, Jonathan (2006). "Redescubriendo * -Minimax Search". Computadoras y Juegos . Apuntes de conferencias sobre informática. vol. 3846, págs. 35–50. doi :10.1007/11674399_3. ISBN 978-3-540-32488-1.