Expectiminimax

El algoritmo expectiminimax es una variación del algoritmo minimax , para 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 "min" y "max" del árbol minimax tradicional, esta variante tiene nodos "chance" (" 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 en forma extensiva de información perfecta , pero incompleta .

En el método minimax tradicional , los niveles del árbol alternan entre máximo y mínimo hasta alcanzar el límite de profundidad. En un árbol expectiminimax, los nodos de "probabilidad" se intercalan 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, donde el peso es la probabilidad de alcanzar a ese hijo. ^{[ 1 ]}

La intercalación 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 "azar" (que representa un efecto o jugador aleatorio). ^{[ 1 ]}

Por ejemplo, consideremos un juego en el que cada ronda consiste en un solo lanzamiento de dado, seguido de decisiones tomadas primero por el jugador de IA y luego por otro oponente inteligente. El orden de los nodos en este juego alternaría entre "azar", "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 muestra a continuación.

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

Cabe destacar que, para los nodos aleatorios, debe existir una probabilidad conocida de alcanzar cada nodo hijo. (En la mayoría de los juegos de azar, los nodos hijos tendrán el mismo peso, lo que significa que el valor de retorno puede ser simplemente el promedio de todos los valores de los nodos hijos).

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 de integrar la poda alfa-beta en el algoritmo expectiminimax es que las puntuaciones de los hijos de un nodo de azar 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 acotar las puntuaciones de los hijos de un nodo de azar y, por lo tanto, acotar la puntuación del nodo de Azar.

Si una búsqueda iterativa estándar está a punto de puntuar la $i$ hijo de un nodo de probabilidad con $N$ Los niños tienen la misma probabilidad de que esa búsqueda haya calculado las puntuaciones. $v_{1},v_{2},\ldots,v_{i-1}$ para los nodos hijos del 1 al $i-1$ Suponiendo la puntuación más baja posible $L$ y la puntuación más alta posible $U$ Para cada hijo no examinado, los límites de la puntuación del nodo de probabilidad son los siguientes:

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

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

Si se proporciona un límite alfa y/o beta al puntuar el nodo de probabilidad, estos límites se pueden utilizar para recortar la búsqueda del $i$ El niño. Las ecuaciones anteriores se pueden reorganizar para encontrar un nuevo valor alfa y beta que interrumpa la búsqueda si provoca que el nodo de probabilidad exceda sus propios límites alfa y beta:

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

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

El pseudocódigo para extender expectiminimax con poda alfa-beta de fallo estricto de esta manera es el siguiente:

función *-minimax(nodo, profundidad, α, β) si nodo es un nodo terminal o profundidad = 0 devuelve el valor heurístico de nodo si nodo es un nodo máximo o mínimo devuelve el valor minimax del nodo sea N = numSucesores(nodo) // Calcular α, β para niños sea A = N * (α - U) + U sea B = N * (β - L) + L sea suma = 0 para cada hijo del nodo // Limitar los elementos secundarios α y β a un rango válido sea AX = max(A, L) sea BX = min(B, U) // Buscar al niño con nuevos valores de corte sea puntuación = *-minimax(hijo, profundidad - 1, AX, BX) // Comprobar las condiciones de corte α, β Si la puntuación es menor o igual a A, devuelve α; si la puntuación es mayor o igual a B, devuelve β. suma += puntuación // Ajustar α, β para el siguiente hijo A += U - v B += L - v // No se produjo ningún corte, devolver puntuación suma de retorno / N

Esta técnica pertenece a una familia de variantes de algoritmos que permiten delimitar la búsqueda de un nodo CHANCE y sus hijos, basándose en la recopilación de límites inferiores y superiores de los hijos durante la búsqueda. Otras técnicas que ofrecen ventajas en cuanto al rendimiento incluyen sondear cada hijo con una heurística para establecer un mínimo o un máximo antes de realizar una búsqueda completa en cada uno de ellos, etc.

Véase también

Referencias

1 2 3 4 Russell, Stuart Jonathan; Norvig, Peter; Davis, Ernest (2010). Inteligencia artificial: un enfoque moderno . Prentice Hall. págs. 177–178 . ISBN 978-0-13-604259-4.
↑ Michie, D. (1966). «Autómatas de juego y aprendizaje de juegos». 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.
↑ Ballard, Bruce W. (septiembre de 1983). "El procedimiento de búsqueda *-minimax para árboles que contienen nodos de probabilidad". Inteligencia Artificial . 21 (3): 327– 350. doi : 10.1016/S0004-3702(83)80015-0 .
↑ Hauk, Thomas; Buro, Michael; Schaeffer, Jonathan (2006). "Redescubriendo la búsqueda *-minimax". Computers and Games . Lecture Notes in Computer Science. Vol. 3846. pp. 35–50 . doi : 10.1007/11674399_3 . ISBN 978-3-540-32488-1.

[RussellNorvig2009-1] 1 2 3 4 Russell, Stuart Jonathan; Norvig, Peter; Davis, Ernest (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 de juegos». 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 probabilidad". Inteligencia Artificial . 21 (3): 327– 350. doi : 10.1016/S0004-3702(83)80015-0 .

[4] Hauk, Thomas; Buro, Michael; Schaeffer, Jonathan (2006). "Redescubriendo la búsqueda *-minimax". Computers and Games . Lecture Notes in Computer Science. Vol. 3846. pp. 35–50 . doi : 10.1007/11674399_3 . ISBN 978-3-540-32488-1.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]