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 el que el resultado depende de una combinación de la habilidad del jugador y elementos de azar como tiradas de dados. Además de los nodos "min" y "max" del árbol minimax tradicional, esta variante tiene nodos de "azar" (" movimiento por naturaleza "), que toman el valor esperado de un evento aleatorio que ocurre. ^[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 "aleatorios" se intercalan con los nodos máximos y mínimos. En lugar de tomar el máximo o mínimo de los valores de utilidad de sus hijos, los nodos aleatorizados toman un promedio ponderado, donde el peso es la probabilidad de que se alcance 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 "casual" (que representa un efecto o jugador aleatorio). ^[1]

Por ejemplo, supongamos que se trata de un juego en el que cada ronda consiste en un único lanzamiento de dados y, a continuación, decisiones tomadas por el jugador de la IA y, a continuación, por otro oponente inteligente. El orden de los nodos en este juego se alternaría entre "azar", "máximo" y, a continuación, "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(hijo, 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(hijo, profundidad-1)) De lo contrario, si el evento es aleatorio en el nodo // Devuelve el promedio ponderado de los valores de todos los nodos secundarios sea α := 0 para cada hijo del nodo α := α + (Probabilidad[hijo] × expectiminimax(hijo, profundidad-1)) devuelve α

Tenga en cuenta que, en el caso de los nodos aleatorios, debe existir una probabilidad conocida de alcanzar a cada hijo. (En la mayoría de los juegos de azar, los nodos hijos tendrán la misma ponderación, lo que significa que el valor de retorno puede ser simplemente el promedio de todos los valores hijos).

Búsqueda de 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 aleatorio pueden superar el límite alfa o beta de su padre, incluso si el valor ponderado de cada hijo no lo hace. Sin embargo, es posible limitar las puntuaciones de los hijos de un nodo aleatorio y, por lo tanto, limitar la puntuación del nodo CHANCE.

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

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

${\text{puntaje}}\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 aleatorio, estos límites se pueden utilizar para interrumpir la búsqueda del hijo número 1. Las ecuaciones anteriores se pueden reorganizar para encontrar un nuevo valor alfa y beta que interrumpirá la búsqueda si esto hiciera que el nodo aleatorio exceda sus propios límites alfa y beta: ${\estilo de visualización i}$

$\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 falla estricta 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 // Limitar los hijos α, β a un rango válido sea AX = máx(A, L) sea BX = mín(B, U) // Busca al niño con nuevos valores de corte deje que la puntuación sea *-minimax(hijo, profundidad - 1, AX, BX) // Comprobar las condiciones de corte α, β Si la puntuación <= A devuelve α Si la puntuación >= B devuelve β suma += puntuación // Ajuste α, β para el próximo hijo A+= U-v B+= L-v // No se produjo ningún corte, devolver la puntuación devuelve suma / N

Esta técnica forma parte de 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 límites inferiores y superiores de los hijos durante la búsqueda. Otras técnicas que pueden ofrecer ventajas en el rendimiento incluyen sondear cada hijo con una heurística para establecer un mínimo o máximo antes de realizar una búsqueda completa en cada hijo, etc.

Véase también

Referencias

^ abcd 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 que juegan y aprenden 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 aleatorios". 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". Computadoras y juegos . Apuntes de clase en informática. Vol. 3846. págs. 35–50. doi :10.1007/11674399_3. ISBN 978-3-540-32488-1.