Juegos y búsqueda entre adversarios

Una búsqueda en juegos comienza con un estado: información suficiente para determinar qué puede suceder después. En el tres en raya, esto significa el tablero y el jugador al que le toca jugar. El tablero por sí solo está incompleto porque la siguiente marca cambia según el turno.

Define los seis componentes

Un modelo de juego proporciona:

• Un estado inicial, $S_0$.
• Una función, $\text{Turno}(s)$, que indica el jugador que actúa en el estado $s$.
• Las jugadas legales, $\text{Acciones}(s)$.
• Un modelo de transición, $\text{Resultado}(s,a)$, que da el estado después de la acción $a$.
• Una prueba de terminación, $\text{Es-Terminal}(s)$, que detecta el final del juego.
• Una función de utilidad, $\text{Utilidad}(s,p)$, que da al jugador $p$ una recompensa numérica en un estado terminal.

Para el tres en raya, comienza con un tablero vacío de 3 por 3 y el turno de X. Una acción elige una casilla vacía. La transición coloca la marca del jugador actual y cambia el turno. La partida termina en cuanto alguien forma una fila, columna o diagonal de tres, o cuando el tablero se llena y hay empate. Desde el punto de vista de X, puntúa una victoria como +1, un empate como 0 y una derrota como −1. La prueba de terminación debe ejecutarse antes de colocar otra marca: la partida no continúa después de una victoria.

Clasifica el juego según ejes independientes

Estos ejes son independientes. Los dados hacen que el backgammon sea estocástico aunque su tablero esté a la vista. Las cartas ocultas afectan a la información, no a si una acción es aleatoria. En un juego de información oculta, un jugador razona sobre los estados posibles compatibles con sus observaciones, llamados en conjunto estado de creencia.

Mantén fijo el punto de vista de la recompensa

En un juego de dos jugadores y suma cero, la ganancia de un jugador es la pérdida del otro. Las puntuaciones de suma constante se comportan igual: 1 por victoria, 0 por derrota y ½ para cada uno por empate siempre suman 1. Basta un número para expresar la oposición. Llama MAX al jugador que quiere aumentarlo y MIN al que quiere reducirlo. Son roles; MAX no tiene por qué ser siempre las blancas o X.

En una búsqueda habitual se puede elegir cada acción de un camino. Un agente que juega debe responder a jugadas que no controla. Su solución es una estrategia, que especifica qué hacer en cada situación a la que pueda enfrentarse. Un plan que solo funciona si el oponente responde de forma favorable no basta.

Un árbol de juego comienza en el estado actual. Cada arista saliente representa una jugada legal y su hijo es el estado resultante. Etiqueta cada nodo no terminal con el jugador que actúa en él. En un juego alternado de dos jugadores, los niveles de MAX y MIN se alternan.

Cuenta los turnos individuales

Una media jugada es una jugada de un jugador. En ajedrez, una jugada completa suele incluir un turno de las blancas y uno de las negras, por lo que abarca dos medias jugadas. Una búsqueda de profundidad 4 desde el turno de las blancas llega a posiciones después de que hayan actuado las blancas, las negras, las blancas y las negras. Cuenta las aristas desde la raíz, cuya profundidad es cero.

Sean $b$ el factor de ramificación y $m$ la profundidad máxima. Un árbol uniforme tiene $b^d$ nodos a profundidad $d$ y $b^m$ hojas. Su número total de nodos es:

Para $b>1$, predominan los niveles más profundos, lo que da lugar a un crecimiento exponencial. Con cuatro jugadas por posición, la profundidad 3 tiene 64 hojas y la profundidad 4 tiene 256. Una media jugada adicional multiplica por cuatro el número de hojas, no por uno.

Distingue las partidas de las posiciones

El tres en raya tiene como máximo $9!=362880$ órdenes para llenar el tablero. Muchos de esos órdenes continuarían después de una victoria anterior y no son partidas legales completas. Detenerse inmediatamente al producirse una victoria da 255 168 partidas completas: 131 184 victorias de X, 77 904 victorias de O y 46 080 empates. En el juego legal hay solo 5478 posiciones distintas del tablero, incluido el tablero vacío.

La diferencia se debe en parte a las transposiciones: distintos órdenes de jugadas que llegan al mismo estado. X puede jugar en una esquina, O en el centro y X en la esquina opuesta, o X puede jugar en esas dos esquinas en el orden inverso. Ambos caminos terminan en el mismo tablero y turno. Un árbol conserva ambos caminos; un grafo de juego puede almacenar su estado compartido una sola vez. Reutilizar el trabajo exige identificar estados completos, no solo tableros visualmente parecidos.

Comprende por qué la búsqueda completa deja de ser viable

El ajedrez suele modelarse con unas 35 jugadas legales por posición y una partida de 100 medias jugadas, o 50 jugadas de cada jugador. Esto da la escala aproximada:

Las ramas reales terminan a distintas profundidades y tienen diferentes números de jugadas, pero esta estimación ya explica por qué enumerar un árbol de juego completo de ajedrez es inviable. En un tablero vacío de go de 19 por 19, solo la primera piedra tiene 361 puntos posibles.

El árbol de búsqueda es lo que un algoritmo genera realmente. Minimax sin modificaciones genera el árbol de juego completo por debajo del estado cuando busca hasta el final de un juego finito. La poda, los límites de profundidad y la simulación selectiva generan menos. Por tanto, una hoja de corte puede ser una posición no terminada, aunque una hoja del árbol de juego completo sea terminal.

Imagina una estrategia dentro del árbol

Un subárbol de estrategia para MAX conserva una arista seleccionada en cada nodo MAX y todas las aristas legales en cada nodo MIN. MAX elige su propia acción, pero debe conservar una respuesta para cualquier jugada del oponente. Un solo camino de la raíz a una hoja describe solo una partida posible. No puede mostrar que el plan elegido resiste las demás respuestas.

Minimax elige el mejor resultado que MAX puede garantizar frente a un oponente óptimo. Toda utilidad de hoja se mide para MAX. Un número grande favorece a MAX incluso cuando el nodo evaluado pertenece a MIN.

Trabaja desde las hojas hacia la raíz

En un nodo terminal, devuelve su utilidad. En un nodo MAX, devuelve el mayor valor de sus hijos. En un nodo MIN, devuelve el menor. Continúa hasta que la raíz reciba un valor:

El valor de un hijo ya resume la continuación óptima desde ese hijo. Por eso un nodo padre compara los valores devueltos en lugar de volver a examinar cada hoja que hay debajo. La recursión funciona con cualquier número de niveles alternos.

Sigue una decisión de dos medias jugadas

MAX tiene tres jugadas, cada una de las cuales conduce a un nodo MIN:

Primero toma el mínimo dentro de cada fila. MIN puede hacer que A valga 4, B valga 2 y C valga 5. Después MAX toma el máximo de esos tres resultados:

El valor minimax es 5. La decisión minimax es la jugada hacia C. Uno es un número que describe la posición; la otra es una acción que el programa puede realizar.

La hoja de mayor valor, 15, está bajo B, pero MAX no controla la respuesta que llega a ella. MIN elegiría 2. El promedio de las hojas de B da 10, que también parece atractivo, pero promediar modela una elección aleatoria con probabilidades adecuadas. Un oponente óptimo exige tomar un mínimo.

Interpreta la variante principal

La variante principal es la línea que se sigue cuando los jugadores eligen jugadas óptimas. Aquí MAX juega hacia C y MIN elige su hoja de valor 5. En un árbol más profundo, sigue el máximo o mínimo elegido en cada nivel. La utilidad terminal de esa línea coincide con el valor de la raíz. Si varias jugadas empatan, puede haber más de una línea óptima.

Comprende la garantía

En un juego finito determinista de dos jugadores, de suma cero y con información perfecta, seguir la estrategia minimax garantiza al menos el valor de la raíz. Un oponente óptimo limita a MAX a ese valor. Un error del oponente puede permitir un resultado mejor, por lo que 5 es un mínimo garantizado, no una predicción de que cada partida deba terminar exactamente en 5.

Un programa puede aprovechar la debilidad del oponente conservando ese mínimo. Si dos jugadas tienen valor minimax 5, puede preferir la que dé más oportunidades al oponente de equivocarse. Elegir una jugada de valor minimax 2 porque contiene un atractivo 15 supone abandonar la garantía de 5. La diferencia está en si la jugada conserva el mejor valor del peor caso.

La definición de minimax ya es un programa recursivo. Una función de valor recibe un estado y devuelve un número. Una función de búsqueda compara las posibles primeras jugadas y devuelve la acción que se debe realizar.

Separa la elección de la jugada del cálculo del valor

El siguiente pseudocódigo supone que MAX actúa en la raíz y que los turnos se alternan:

MINIMAX-SEARCH(s):
    if Is-Terminal(s): return no action
    bestMove = no action
    bestValue = -infinity
    for a in Actions(s):
        value = MIN-VALUE(Result(s, a))
        if value > bestValue:
            bestValue = value
            bestMove = a
    return bestMove

MAX-VALUE(s):
    if Is-Terminal(s): return Utility(s, MAX)
    v = -infinity
    for a in Actions(s):
        v = max(v, MIN-VALUE(Result(s, a)))
    return v

MIN-VALUE(s):
    if Is-Terminal(s): return Utility(s, MAX)
    v = +infinity
    for a in Actions(s):
        v = min(v, MAX-VALUE(Result(s, a)))
    return v

Inicializa MAX con infinito negativo para que cualquier hijo lo mejore; inicializa MIN con infinito positivo. Comprueba la terminación antes de generar sucesores. Un tablero lleno de tres en raya sin una línea ganadora es un empate, no una posición no terminal cuya mejor jugada deba elegirse de una lista vacía.

Sigue lo que descubre la recursión

Considera este tablero de tres en raya, con el turno de X y un punto para cada casilla vacía:

X O X
. O .
. . .

O amenaza la columna central. Si X juega en cualquier lugar salvo la casilla central inferior, O puede ganar en el siguiente turno. Esas jugadas tienen valor −1 para X. Jugar en la casilla central inferior bloquea la victoria inmediata y permite un empate con juego óptimo, lo que da valor 0. La raíz devuelve la casilla central inferior. El algoritmo no necesita una instrucción separada que nombre esta amenaza: los resultados terminales determinan los valores.

Calcula el costo de tiempo y memoria

Minimax en profundidad examina $O(b^m)$ nodos para un factor de ramificación $b$ y una profundidad máxima $m$. Almacenar todos los hermanos generados en cada nivel activo necesita $O(bm)$ de memoria. Generar sucesores de uno en uno reduce el almacenamiento de la búsqueda activa a $O(m)$, aparte de la representación del estado. El tiempo exponencial, no la pila de recursión, suele ser el principal obstáculo.

Conserva la convención de puntuación

En el código MAX/MIN, cada llamada devuelve la utilidad de MAX. No cambies su signo solo porque MIN actúe después. Negamax usa otra convención: cada valor se expresa desde el punto de vista del jugador actual, por lo que el valor de un hijo se niega antes de que el padre lo maximice:

Para un juego que termina en menos de 100 medias jugadas, se puede incluir el momento del resultado puntuando una victoria de MAX a profundidad $d$ como $100-d$, una derrota como $-100+d$ y un empate como 0. Las victorias más rápidas reciben mayor puntuación y las derrotas retrasadas son menos negativas. El límite estricto de profundidad mantiene positiva toda victoria y negativa toda derrota.

Por ejemplo, las victorias en las medias jugadas 3 y 7 reciben 97 y 93 puntos, por lo que se prefiere la victoria más rápida. Las derrotas a esas profundidades reciben −97 y −93 puntos, lo que hace preferible la derrota posterior, aunque ambas siguen siendo peores que un empate.

Una sola utilidad de MAX funciona cuando los intereses de dos jugadores están estrictamente contrapuestos. Con varios jugadores o intereses coincidentes, mantén un vector de utilidades. Para los jugadores A, B y C, el vector (1, 2, 6) da sus recompensas en ese orden.

Elige según la entrada del jugador activo

En un nodo donde actúa C, compara las terceras entradas de los vectores de los hijos. Devuelve el vector completo del hijo que prefiere C. En un nodo B, compara las segundas entradas de esos vectores devueltos; en un nodo A, compara las primeras.

No maximices cada entrada por separado. Si los resultados disponibles son (1, 2, 6) y (4, 2, 3), C elige (1, 2, 6). La combinación (4, 2, 6) no es un resultado disponible y no se puede propagar.

Trabaja hacia atrás con tres jugadores

A juega primero, luego B y después C. Tras la jugada izquierda de A, B elige entre dos nodos C:

• El primero tiene las hojas (1, 2, 6) y (4, 2, 3). C elige (1, 2, 6).
• El segundo tiene las hojas (6, 1, 2) y (7, 4, 1). C elige (6, 1, 2).

B compara las segundas entradas 2 y 1, por lo que la rama izquierda devuelve (1, 2, 6).

Tras la jugada derecha de A:

• C elige (5, 4, 5) en lugar de (2, 5, 4), porque 5 supera a 4 en la tercera entrada.
• C elige (5, 2, 4) en lugar de (7, 7, 1), porque 4 supera a 1 en la tercera entrada.

B compara las segundas entradas 4 y 2, por lo que la rama derecha devuelve (5, 4, 5). Por último, A compara las primeras entradas 1 y 5 y elige la derecha. La raíz recibe el vector completo (5, 4, 5).

Indica cómo se resuelven los empates

Si C puede elegir (2, 3, 4) o (6, 1, 4), ambos le dan 4. La recompensa final de A podría ser 2 o 6. Una predicción necesita una regla de desempate o un modelo de la elección de C. La indiferencia de otro jugador no tiene por qué ser indiferente para el jugador de la raíz.

Si dos perseguidores quieren atrapar a MAX, una ronda tiene una capa MAX y una capa MIN por cada perseguidor. Con dos perseguidores, una ronda tiene tres medias jugadas. Este modelo es distinto del de tres jugadores independientes que persiguen sus propias recompensas.

Permite que los intereses coincidan

En un juego de suma general, ambos jugadores pueden preferir (100, 100) a recompensas conjuntas menores. Los jugadores también pueden beneficiarse temporalmente de atacar a un líder común. Ese comportamiento parecido a una alianza puede surgir de sus propias preferencias y cambiar cuando cambia la posición.

Los cortes habituales de alfa-beta dependen de intereses contrapuestos y no se trasladan directamente a los vectores de utilidades. El modelo paranoico restablece una oposición de dos jugadores y permite la búsqueda alfa-beta, pero puede predecir una hostilidad coordinada que los demás jugadores no elegirían en realidad.

La poda alfa-beta da el mismo valor de la raíz que minimax sobre el mismo árbol con los mismos valores de hoja. Ahorra trabajo al demostrar que algunas ramas no pueden mejorar la elección. Las jugadas óptimas empatadas pueden devolverse en un orden diferente.

Pasa una ventana de búsqueda por el camino

Dos cotas describen las opciones disponibles por encima del nodo actual:

• $\alpha$ es el mejor valor disponible para MAX a lo largo del camino: MAX ya puede obtener al menos esa cantidad.
• $\beta$ es el mejor valor disponible para MIN a lo largo del camino: MIN ya puede limitar a MAX como máximo a esa cantidad.

Comienza la raíz con infinito negativo y positivo. Cada hijo recursivo recibe las cotas actuales. Son argumentos locales, no números globales compartidos entre búsquedas de hermanos no relacionadas.

En un nodo MAX, conserva el mayor valor de hijo observado. Detente cuando alcance o supere beta: MIN, más arriba, ya tiene una alternativa no mayor que beta. De lo contrario, eleva alfa cuando MAX encuentre una mejora. En un nodo MIN, conserva el menor valor de hijo observado. Detente cuando alcance alfa o quede por debajo: MAX, más arriba, ya tiene una alternativa al menos igual de buena. De lo contrario, reduce beta.

MAX-VALUE(s, alpha, beta):
    if Is-Terminal(s): return Utility(s, MAX)
    v = -infinity
    for a in Actions(s):
        v = max(v, MIN-VALUE(Result(s, a), alpha, beta))
        if v >= beta: return v
        alpha = max(alpha, v)
    return v

MIN-VALUE(s, alpha, beta):
    if Is-Terminal(s): return Utility(s, MAX)
    v = +infinity
    for a in Actions(s):
        v = min(v, MAX-VALUE(Result(s, a), alpha, beta))
        if v <= alpha: return v
        beta = min(beta, v)
    return v

La raíz compara las acciones y conserva alfa entre ellas:

ALPHA-BETA-SEARCH(s):
    if Is-Terminal(s): return no action
    alpha = -infinity
    beta = +infinity
    bestMove = no action
    for a in Actions(s):
        v = MIN-VALUE(Result(s, a), alpha, beta)
        if v > alpha:
            alpha = v
            bestMove = a
    return bestMove

Sigue un corte MIN

Explora las ramas MIN A = (4, 9, 6), B = (2, 15, 13) y C = (5, 8, 10), de izquierda a derecha. A debe examinar las tres hojas y devuelve 4. La raíz tiene ahora alfa 4. La primera hoja de B es 2. Su mínimo final solo puede mantenerse en 2 o bajar, por lo que B no puede superar a A. Omite las dos hojas restantes de B. C examina las tres hojas y devuelve 5. La raíz elige C después de examinar siete de las nueve hojas.

Sigue un corte MAX

Supón que un padre MIN ya tiene un hijo de valor 3, lo que fija beta en 3. Su siguiente hijo MAX encuentra una hoja de valor 6. El valor de ese hijo es al menos 6, por lo que MIN preferirá su 3 actual. Omite los hijos restantes de ese nodo MAX. El razonamiento del corte usa la alternativa de MIN, aunque el nodo actual sea MAX.

Un nodo MIN podado puede devolver una cota superior; un nodo MAX podado puede devolver una cota inferior. Sus valores exactos siguen siendo desconocidos. El valor final de la raíz es exacto para el árbol explorado. La igualdad también permite un corte porque una rama que solo puede empatar no puede mejorar el mejor valor actual.

Alfa-beta ahorra más trabajo cuando las jugadas fuertes se exploran pronto. Los valores no cambian con el orden de las jugadas; sí cambia el momento en que la búsqueda puede demostrar un corte.

Compara dos órdenes

Para las tres ramas MIN A = (4, 9, 6), B = (2, 15, 13) y C = (5, 8, 10), comenzar por A supone examinar siete hojas. Comienza por C. Sus tres hojas establecen alfa 5. Entonces A encuentra 4 inmediatamente y corta; B encuentra 2 inmediatamente y corta. Solo se evalúan cinco hojas y la respuesta sigue siendo C con valor 5.

Para un árbol uniforme con ordenación perfecta, el número de hojas es:

Esto es aproximadamente $O(b^{m\mathrm{/}2})$ en lugar del $O(b^m)$ de minimax. El factor de ramificación efectivo baja a aproximadamente $\sqrt{b}$, lo que permite aproximadamente el doble de profundidad con un presupuesto comparable. Con $b=35$, la profundidad 8 con ordenación perfecta evalúa 3 001 249 hojas; minimax ordinario de profundidad 4 tiene 1 500 625 hojas. La comparación se refiere a la escala, no a tiempos de ejecución idénticos.

Con el peor orden, alfa-beta puede examinar todas las hojas de minimax. Sus comprobaciones adicionales de cotas añaden trabajo incluso cuando no ahorran hojas.

Usa indicios de ordenación de bajo costo

La mejor jugada exacta se desconoce antes de la búsqueda. Los programas usan estimaciones rápidas. En ajedrez pueden probar capturas, luego amenazas y después jugadas tranquilas. Una jugada asesina causó un corte en otro lugar a la misma profundidad de búsqueda y se prueba pronto en otra posición. Estos indicios afectan a la eficiencia; no justifican descartar las demás jugadas legales.

La profundización iterativa busca hasta la profundidad 1, luego 2, luego 3 y así sucesivamente. Una jugada fuerte de la iteración anterior se convierte en una candidata temprana en la siguiente. El resultado completo más profundo también queda listo si se acaba el tiempo.

El trabajo repetido tiene distintos costos según la poda. Para una búsqueda uniforme sin poda con factor de ramificación 35, todas las iteraciones menos profundas añaden aproximadamente $1\mathrm{/}(35-1)\approx \mathrm{2,9}\mathrm{\%}$ a la búsqueda final. Para alfa-beta con ordenación perfecta, las profundidades 1 a 7 juntas evalúan 1 677 159 hojas, aproximadamente el 56 % del recuento de profundidad 8. Una mejor ordenación aún puede hacer que el proceso completo merezca la pena.

Guarda posiciones con su significado

Una tabla de transposiciones almacena resultados indexados por el estado completo del juego. Si otro orden de jugadas llega a ese estado, el programa puede reutilizar una entrada adecuada. Almacena la profundidad explorada y si el resultado es exacto, una cota inferior o una cota superior. Una entrada superficial no sustituye a la información requerida por una búsqueda más profunda. Una cota puede estrechar una ventana o justificar un corte, pero no debe tratarse como un valor exacto.

Una función de evaluación estima lo favorable que es una posición no terminada para MAX. Hace posible la búsqueda de profundidad limitada: la frontera recibe valores estimados que pueden propagarse mediante minimax o alfa-beta.

Haz que las puntuaciones sean útiles para la búsqueda

Un buen evaluador es rápido, coincide con el orden de los resultados terminales reales y se correlaciona con el éxito desde posiciones no terminales. Los propios estados terminales deben recibir su utilidad exacta. Una victoria de MAX debe puntuar por encima de toda estimación no terminal, para que acumular piezas no resulte más atractivo que ganar.

Una forma de entender la evaluación es agrupar posiciones por características compartidas. Si ese grupo produce un 72 % de victorias, un 8 % de empates y un 20 % de derrotas, con utilidades 1, ½ y 0, su utilidad media es:

Esta interpretación depende de cómo se hayan muestreado las posiciones y las continuaciones. Es una estimación de la calidad del resultado, no una demostración de victoria forzada.

Añade características ponderadas

Un diseño habitual es una suma ponderada:

Cada característica $f_i(s)$ mide una propiedad de la posición; cada peso $w_i$ indica cuánto contribuye. Las diferencias entre los bandos mantienen claro el punto de vista. Una diferencia material positiva significa que MAX tiene más material.

Los valores tradicionales de ajedrez son: peón 1, caballo 3, alfil 3, torre 5 y dama 9. Al rey no se le asigna un valor material de pieza capturable. Supón que MAX juega con blancas. Las blancas tienen una dama, dos torres, un alfil y seis peones:

Las negras tienen dos torres, dos caballos, un alfil y siete peones:

Por tanto, la característica de material es $28-26=2$. Si las blancas tienen 30 jugadas legales y las negras 24, la diferencia de movilidad es 6. Con peso 1 para el material y peso 0,1 para la movilidad:

Ese 2,6 es una puntuación de características, no una probabilidad de victoria del 260 %. Los pesos definen su escala.

Ten en cuenta las características que interactúan

Una suma lineal simple da a cada característica una contribución fija independiente de las demás. El valor real en el juego puede depender de combinaciones: una pareja de alfiles puede valer más que la suma de sus efectos por separado, y la importancia de un peón puede cambiar en un final de partida. Las características combinadas, los pesos dependientes de la fase o los evaluadores no lineales pueden captar estos efectos. Los pesos pueden elegirse según el criterio de quien diseña el sistema o ajustarse a los resultados de partidas registradas.

Más características también cuestan tiempo. Un evaluador elaborado que impida buscar una media jugada útil adicional puede perjudicar la decisión, aunque mejoren sus estimaciones individuales.

Ajusta la escala a la regla de propagación

En minimax determinista, aplicar de manera uniforme transformaciones estrictamente crecientes conserva el orden a través de máximos y mínimos. Elevar al cuadrado solo puntuaciones positivas, por ejemplo, conserva su orden. Elevar al cuadrado puntuaciones con signos arbitrarios no lo conserva. En los nodos de azar, las distancias reales entre utilidades importan porque los valores se promedian. Una puntuación diseñada solo para ordenar posiciones necesita calibración antes de poder representar la utilidad esperada.

El minimax heurístico se detiene antes de que termine la partida. Su respuesta es óptima para el árbol explorado con las puntuaciones asignadas a su frontera. Aun así, puede elegir una jugada perdedora en el juego real cuando esas estimaciones no captan lo que ocurre después.

Distingue los estados terminales de los cortes

Un estado terminal tiene un resultado conocido. Un corte por profundidad deja la partida sin terminar y necesita una estimación. Compruébalos en ese orden:

H-MINIMAX(s, d):
    if Is-Terminal(s): return Utility(s, MAX)
    if Is-Cutoff(s, d): return Eval(s)
    if To-Move(s) == MAX:
        return max over a of H-MINIMAX(Result(s, a), d + 1)
    return min over a of H-MINIMAX(Result(s, a), d + 1)

El corte suele comprobar si la profundidad ha alcanzado un límite. Alfa-beta puede podar este mismo árbol heurístico. Su poda sigue siendo exacta respecto de esos valores de frontera; no convierte las estimaciones en resultados reales del juego.

Con un límite de tiempo, la profundización iterativa conserva la acción de la iteración completa más profunda. Una raíz explorada solo en parte a mayor profundidad puede favorecer la primera rama simplemente porque sus competidoras aún no se han evaluado.

Termina un intercambio táctico

Una posición tranquila es lo bastante estable como para que sea poco probable que una continuación forzada breve cambie bruscamente su evaluación. La búsqueda de quietud continúa más allá de la profundidad normal en posiciones inestables, normalmente siguiendo capturas hasta que el intercambio se estabiliza.

Supón que la dama blanca captura un peón justo en el límite de profundidad. La puntuación material mejora en 1. Pero las negras pueden recapturar esa dama en la siguiente media jugada. El cambio neto de material es:

Detenerse después de la primera captura indica +1; una breve extensión de capturas revela −8. El problema es evaluar a mitad de un intercambio, no un fallo de la regla de propagación de minimax.

Reconoce las pérdidas retrasadas

El efecto horizonte ocurre cuando un programa retrasa una pérdida inevitable hasta situarla más allá de la profundidad de búsqueda. Un alfil atrapado puede perderse igualmente después de varios jaques con peones. Si la búsqueda ve los jaques pero se detiene antes de la captura del alfil, puede sacrificar peones para ocultar esa pérdida futura.

Una extensión singular busca más a fondo una jugada que destaca claramente sobre sus alternativas. Los programas también extienden jaques forzados o recapturas. Las extensiones dedican profundidad adicional a líneas seleccionadas; requieren un presupuesto para que la búsqueda pueda terminar.

La poda hacia delante, como conservar solo unas pocas de las mejores jugadas, puede descartar la jugada ganadora. Su ahorro no cuenta con la garantía de alfa-beta.

Sustituye la búsqueda por conocimiento exacto almacenado

Un libro de aperturas proporciona jugadas iniciales estudiadas. Las bases de tablas de finales trabajan hacia atrás desde resultados conocidos mediante análisis retrógrado. Las bases de tablas de finales de ajedrez de siete piezas incluyen los dos reyes y proporcionan resultados exactos para los finales que cubren. Las reglas y la información de estado de una consulta deben coincidir con el juego que se está jugando.

Un nodo de azar representa un suceso aleatorio. Sus ramas enumeran los resultados posibles y sus probabilidades, que suman 1. Ningún jugador elige la rama que más le favorece.

Usa la regla correspondiente a cada nodo

Para los resultados $r$, un nodo de azar tiene el valor:

Expectiminimax combina las cuatro reglas. Expectimax usa MAX y azar cuando no hay un jugador que minimice. Un modelo probabilístico de un oponente aleatorio puede proporcionar ramas de azar incluso en un juego cuyas reglas de movimiento sean deterministas.

Trabaja hacia atrás con azar y oposición

MAX elige L o R. Cada jugada conduce a un suceso aleatorio, seguido de una elección de MIN.

Tras L, una moneda equilibrada da dos nodos MIN. Sus hojas son (3, 7) y (8, 4). MIN devuelve 3 y 4. El nodo de azar da entonces:

Tras R, las probabilidades 0,25 y 0,75 conducen a nodos MIN con hojas (10, 1) y (6, 5). Sus valores son 1 y 5, por lo que:

MAX elige R porque 4 supera a 3,5. Promediar primero las hojas terminales sin procesar permitiría que el azar sustituyera la decisión de MIN. Procesa cada nodo después de haber resuelto sus hijos.

Asigna las probabilidades correctas

Dos dados equilibrados tienen 36 resultados ordenados igualmente probables. El backgammon agrupa los órdenes inversos, como 3–5 y 5–3, en una misma tirada. Esto da 21 tiradas distintas: seis dobles con probabilidad 1/36 cada uno y 15 tiradas no dobles con probabilidad 1/18 cada una. La comprobación es:

Dar a las 21 tiradas una probabilidad de 1/21 contaría los dobles de más y las tiradas no dobles de menos. Las ramas que parecen iguales no tienen por qué tener probabilidades iguales.

Si cada etapa de decisión tiene $b$ jugadas legales y un suceso aleatorio con $n$ resultados, buscar $m$ etapas de ese tipo cuesta aproximadamente $O(b^m{n}^m)$. La convención de profundidad debe tener en cuenta con qué frecuencia interviene el azar. Con unas 20 jugadas legales y 21 tiradas, las ramas de azar añadidas del backgammon limitan rápidamente la anticipación exhaustiva.

Por ejemplo, dos etapas que contienen cada una 21 resultados del azar y 20 acciones producen $(21\times 20{)}^2=176400$ caminos. Cuenta los sucesos aleatorios por separado de las medias jugadas de los jugadores al estimar ese costo.

Poda solo cuando los resultados no vistos estén acotados

Un promedio parcial no es una cota minimax. Si las utilidades están entre 0 y 10 y el primero de dos resultados igualmente probables vale 2, el nodo completo está entre 1 y 6. En particular:

Si MAX ya tiene otra jugada de valor 7, este nodo de azar no puede superarla y se puede omitir el resultado restante. Sin una cota adecuada para los valores no vistos, un resultado extremo aún podría cambiar el promedio lo suficiente como para invertir la elección.

Minimax pregunta qué resultado puede garantizar un oponente. Expectimax pregunta qué utilidad media se deriva de un modelo probabilístico. Sus decisiones pueden diferir incluso en el mismo árbol porque representan comportamientos diferentes.

Compara la oposición óptima y la aleatoria

Para las ramas MIN A = (4, 9, 6), B = (2, 15, 13) y C = (5, 8, 10), minimax elige C con una garantía de 5. Si, en cambio, el oponente elige cada respuesta de manera uniforme, los valores esperados son aproximadamente 6,33, 10 y 7,67. Expectimax elige B.

Esto es razonable con el modelo uniforme, pero un adversario hábil puede responder a B con 2. Expectimax no supone que el oponente minimice un promedio. Usa las probabilidades especificadas. Con un modelo correcto maximiza la utilidad esperada; la protección en el peor caso es más débil que la de minimax. Puede igualar el rendimiento medio de minimax cuando ambos recomiendan la misma jugada.

Un árbol puede mezclar modelos. El nodo de un agente adversario toma un mínimo, mientras que el de un agente aleatorio toma un promedio ponderado. Usa la regla del agente que actúa en ese nodo, no una sola regla para cada capa que no sea MAX.

Comprende por qué el orden no basta

Supón que la jugada A da 2 con probabilidad 0,6 y 3 con probabilidad 0,4. La jugada B da 1 con probabilidad 0,6 y 4 con probabilidad 0,4:

A tiene la mayor esperanza. Ahora eleva al cubo cada valor terminal. Su orden se mantiene, pero las esperanzas pasan a ser:

Ahora B gana la comparación. Promediar resultados transformados es diferente de transformar su promedio. Elevar al cubo amplifica lo suficiente el beneficio del resultado alto de B como para cambiar la decisión.

Conserva las decisiones con las transformaciones adecuadas

Una transformación afín de pendiente positiva multiplica cada esperanza por el mismo número positivo y añade la misma constante. Aplicar $10x+5$ da a A un valor de 29 y a B un valor de 27, por lo que A sigue siendo la opción preferida.

Si A y B fueran nodos MIN, sus valores serían 2 y 1 antes de elevar al cubo y 8 y 1 después. Su orden no cambiaría. Los máximos y mínimos seleccionan el valor de un hijo; los promedios combinan las magnitudes de varios valores.

Por tanto, un evaluador usado con azar debe estimar la utilidad esperada prevista en una escala uniforme, como la probabilidad de ganar o una transformación afín de pendiente positiva de ella. Una puntuación no lineal de ordenación puede ser adecuada para minimax determinista y, a la vez, llevar a compromisos incorrectos entre riesgos cuando interviene el azar.

La búsqueda en árbol de Monte Carlo, o MCTS, estima jugadas a partir de partidas simuladas mientras construye un árbol que guía las simulaciones futuras. Una continuación simulada hasta el final es una simulación de partida o partida simulada. Su política puede seleccionar jugadas legales aleatorias o usar conocimientos de bajo costo para producir un juego más razonable.

Almacena evidencia en cada nodo

Mantén un número de visitas $N(n)$ y una recompensa acumulada $U(n)$. En un juego de dos jugadores con victorias y derrotas, usa las victorias del jugador que realizó la jugada que llevó al nodo $n$. Un empate suele añadir media victoria. Así, $U(n)\mathrm{/}N(n)$ estima la tasa de éxito de ese jugador.

La raíz no tiene una jugada entrante. Sus visitas siguen contando cada iteración; si es necesario, sus victorias pueden registrarse desde el punto de vista del jugador de la raíz. Las puntuaciones de los hijos, que guían la selección, deben usar de forma uniforme el punto de vista del jugador que realizó la jugada entrante.

Repite las cuatro fases

1. Selección: Desde la raíz, sigue una política de selección por los hijos existentes hasta llegar a un nodo terminal o a un nodo con una jugada sin probar.
2. Expansión: Si no es terminal, añade un hijo para una jugada legal sin probar.
3. Simulación: Ejecuta una simulación de partida desde ese hijo hasta un resultado terminal.
4. Retropropagación de resultados: Actualiza las visitas y recompensas de los nodos del camino seleccionado.

Si la selección llega a un nodo terminal, omite la expansión y la simulación. Su resultado conocido puede propagarse inmediatamente. No es necesario almacenar la continuación temporal de una simulación como nuevos nodos del árbol: la expansión habitual añade un hijo por iteración.

Sigue una actualización de recompensas

Las blancas actúan en la raíz. La selección y la expansión siguen este camino:

• n1, alcanzado mediante una jugada de las blancas;
• n2, alcanzado mediante una jugada de las negras;
• n3, alcanzado mediante una jugada de las blancas.

La simulación termina con una victoria de las negras. Aumenta las visitas en uno en la raíz y en n1, n2 y n3. Entre estos tres nodos hijos, aumenta las victorias solo en n2, porque el jugador de la jugada entrante de n2 fue el de las negras. Los nodos hijos de las blancas no reciben ningún incremento de victorias. Con una convención basada en el jugador de la raíz, el total de victorias de la raíz también permanece sin cambios.

Un empate añadiría 0,5 a la recompensa de cada hijo. Contar la victoria de las negras como un éxito en todos los nodos haría que las blancas seleccionaran jugadas que ayudan a las negras.

Deja que el árbol crezca de forma desigual

Las iteraciones repetidas concentran las simulaciones en ramas prometedoras o inciertas. Las jugadas que parecen fuertes tienden a adquirir subárboles mayores, mientras que se dedica menos trabajo a las malas. La búsqueda no impone una profundidad fija a todas las líneas. Una vez disponible una jugada legal, puede detenerse al alcanzar un límite de tiempo y usar las estadísticas acumuladas.

La acción final suele ser el hijo de la raíz con más visitas. Una jugada con dos victorias en dos simulaciones tiene una tasa observada perfecta, pero poca evidencia. Una jugada muy visitada refleja mucho más examen por parte de la búsqueda.

La búsqueda pura de Monte Carlo asigna simulaciones independientes a las jugadas de la raíz sin construir un árbol de decisión. Puede pasar por alto repetidamente una respuesta fuerte del oponente porque el juego posterior sigue regido por la política de simulación. MCTS aprende dónde ramificarse a mayor profundidad al acumular evidencia, aunque una refutación táctica poco frecuente aún puede tardar en descubrirse.

MCTS debe decidir dónde es más útil otra simulación. La explotación vuelve a visitar jugadas que ya parecen fuertes. La exploración investiga jugadas con menos evidencia que podrían resultar mejores. Perseguir siempre la mayor tasa de victorias observada puede hacer que la búsqueda se quede fijada en un resultado inicial afortunado.

Calcula una puntuación UCB1

La puntuación de cota superior de confianza para el hijo $n$ es:

El primer término es la tasa de victorias observada. El segundo es una bonificación de exploración. Crece a medida que el padre acumula visitas y disminuye a medida que el hijo recibe más visitas. El logaritmo es natural. Durante la selección, elige el hijo con la mayor puntuación combinada.

Trata un hijo no visitado como si tuviera prioridad infinita en lugar de dividir por cero. Cada jugada legal de un nodo se prueba antes de que la selección favorezca repetidamente alternativas ya visitadas. MCTS que usa esta regla de selección se llama UCT, búsqueda en árbol con cotas superiores de confianza.

Compara tres hijos

Un padre tiene 50 visitas. Sus hijos tienen recuentos de victorias y visitas 21/30, 7/12 y 3/8. Con $C=\sqrt{2}$ y $\ln 50\approx \mathrm{3,912}$:

Se selecciona el segundo hijo. Su tasa de victorias actual es inferior a la del primero, pero su bonificación por incertidumbre es mayor. El tercero está aún menos visitado, pero su menor tasa de victorias deja su total ligeramente por debajo del segundo.

Con $C=\mathrm{0,5}$, los mismos totales pasan a ser aproximadamente 0,881, 0,869 y 0,725. Ahora la selección favorece al primer hijo. Ningún resultado ha cambiado; el programa ha cambiado la intensidad con que premia la incertidumbre.

Interpreta la constante de exploración

Un $C$ positivo mayor da más peso a la exploración. Fijarlo en cero elimina la bonificación y elige solo según la media observada. La formulación del bandido con recompensas entre 0 y 1 justifica $C=\sqrt{2}$ en esta forma de la ecuación; los programas de juegos prácticos ajustan la constante. Cambiar la escala de recompensa también cambia el equilibrio con el término de exploración.

En cada padre, sus hijos registran las victorias del jugador que elige allí. Esto hace razonable maximizar UCB1 en los turnos de ambos jugadores. Almacenar solo las victorias de las blancas en todo el árbol y maximizar cada puntuación haría que las negras favorecieran el éxito de las blancas.

Separa la prioridad de búsqueda de la calidad de la jugada

UCB1 elige dónde dedicar la siguiente simulación. Una gran bonificación por incertidumbre puede hacer que merezca la pena investigar una jugada poco muestreada. Al final de la búsqueda, elige el hijo de la raíz más visitado, no el que tenga la puntuación UCB1 más alta en ese momento. Bajo las condiciones de juego finito de UCT y con exploración continua, una búsqueda ilimitada converge hacia el comportamiento minimax; un presupuesto finito sigue dejando incertidumbre de muestreo.

Un método de búsqueda se adapta al tamaño del espacio de jugadas, la calidad de la evaluación disponible y el tipo de incertidumbre del juego. Un mismo presupuesto de tiempo puede producir decisiones muy distintas según lo que investigue el método.

Compara la cobertura táctica y la simulación

Alfa-beta puede encontrar una única refutación táctica dentro de su profundidad de búsqueda. MCTS puede preferir inicialmente una jugada que gana la mayoría de las simulaciones aleatorias pero pierde ante una respuesta precisa. A medida que crece su árbol, puede descubrir esa respuesta, pero un presupuesto breve de simulaciones puede pasarla por alto. Por tanto, una alta tasa de victorias en las simulaciones no es una garantía para el peor caso.

Relaciona los métodos con programas emblemáticos

En 1997, Deep Blue de IBM usó búsqueda alfa-beta, hardware especializado y evaluación de ajedrez para derrotar al campeón mundial Garry Kasparov por 3½–2½ en seis partidas. Su éxito mostró cuánto podían lograr juntos una búsqueda sólida y una evaluación específica del juego.

El go hizo más difícil esa combinación. Un tablero vacío de 19 por 19 ofrece 361 lugares para colocar una piedra, y juzgar una posición mediante características simples es difícil. MCTS se convirtió en un enfoque sólido porque podía estimar resultados mediante partidas y expandir un árbol selectivo sin requerir un evaluador estático escrito a mano.

AlphaGo combinó MCTS con redes neuronales que sugerían jugadas y evaluaban posiciones. Su descripción en Nature en 2016 precedió a su victoria por 4–1 sobre Lee Sedol en marzo de 2016. Más tarde, AlphaZero usó la evaluación de una red neuronal en lugar de simulaciones aleatorias y alcanzó un nivel de juego sobrehumano en ajedrez, shōgi y go. Estos programas muestran que un marco de búsqueda puede usar distintas fuentes de valores de posición.

Distingue jugar bien de resolver un juego

Un programa puede vencer a un campeón sin demostrar el valor de la posición inicial. En 2007, el equipo de Jonathan Schaeffer usó búsqueda y grandes bases de datos de finales para establecer que las damas terminan en empate con juego perfecto. Resolver el juego establece un resultado frente a todas las estrategias posibles del oponente, no solo frente a los oponentes probados en encuentros.

Adapta el método al modelo

En un juego estocástico, muestrea los resultados aleatorios según sus probabilidades reales durante el recorrido del árbol y las simulaciones. Un suceso con probabilidad 0,8 debería ocurrir aproximadamente cuatro veces más que uno con probabilidad 0,2 a lo largo de muchas muestras. Esto estima la misma esperanza ponderada que calcula la propagación explícita del azar.

Todos los enfoques siguen dependiendo de reglas y transiciones de estado correctas. Alfa-beta con profundidad limitada depende de su evaluador; MCTS depende de su política de simulación o evaluación y de su presupuesto finito de muestras. Modelar como aleatorio a un oponente adversario puede resultar costoso, sea cual sea el mecanismo de búsqueda usado para calcular la respuesta de ese modelo.