5.

Búsqueda con adversario

Daniel Fernández González

Algoritmos Básicos de Aprendizaje Automático

Introducción
● También Búsqueda en juegos.
● Características:
Introducción
● Nos centraremos primero en: Juegos de 2 jugadores con información completa

, ya que interviene el azar.

Juegos de 2 jugadores con información completa

sobre posiciones finales

(heurística)
(se aplica sobre nodos hoja, que no son estados finales)
Por lo general, no es factible considerar el árbol entero de juegos, entonces tenemos que cortar la
búsqueda en algún punto y aplicar una función de evaluación que dé una estimación de la utilidad
de un estado.
Juegos de 2 jugadores con información completa

(o árboles de juegos)
Juegos de 2 jugadores con información completa

35
Juegos de 2 jugadores con información completa

● Tenemos 2 jugadores que denominamos MAX (el jugador principal) y

MIN (el oponente).
● Los valores altos (o positivos) son buenos para MAX y malos para MIN y
viceversa (de ahí los nombres de los jugadores).
● El árbol se interpreta desde el punto de vista de MAX.
○ Queremos encontrar su mejor movimiento actual.
 Juegos de 2 jugadores con información completa
En la función de utilidad:
-1 marca la derrota.
0 marca el empate.
+1 marca la victoria.

Si no se pudiese
construir todo el árbol, se
utilizaría una función de
evaluación que trataría
de medir cómo de bueno
es cada estado hoja del
árbol incompleto.
Algoritmo MINIMAX
● Publicado por primera vez en 1912 por Ernst Zermelo (aunque con algunos errores).
● Este algoritmo genera un árbol de juegos y decide cuál es el mejor movimiento para
MAX.
● En un problema de búsqueda normal, la solución óptima sería una secuencia de
movimientos que conducen a un estado objetivo (un estado terminal que es ganador).
● En un juego, por otra parte, MIN tiene algo que decir sobre ello.
● MAX por lo tanto debe encontrar una estrategia óptima, que determina el movimiento
de MAX en el estado inicial, después los movimientos de MAX en los estados que
resultan de cada respuesta posible de MIN, después los movimientos de MAX en los
estados que resultan de cada respuesta posible de MIN de los anteriores movimientos,
etc.
● Incluso un juego simple como tic-tac-toe es demasiado complejo para dibujar el árbol
de juegos entero. Entonces vamos a verlo en un ejemplo más simple.
 Algoritmo MINIMAX

● Ejemplo más simple:

○ MAX posee el turno (es el que
empieza siempre a jugar).
○ Los movimientos posibles para
MAX, en el nodo raíz, se
etiquetan por a1, a2, y a3. Las
respuestas posibles a a1, para
MIN, son b1, b2, b3, etc.
○ El juego finaliza después de un
movimiento para MAX y MIN.
○ Las utilidades de los estados
terminales en este juego varía
desde 2 a 14.
 Algoritmo MINIMAX
● En el lenguaje de juegos, decimos que
este árbol es un movimiento en
profundidad, que consiste en dos
medios movimientos, cada uno de los
cuales se llama capa.
○ capa = jugada (1 nivel del árbol)
○ profundidad = 2 jugadas/capas
[MAX + MIN]
○ nodo raíz (MAX) en capa 0 y
profundidad 0
○ nodos en profundidad k = nodos
MAX en capa 2k + nodos MIN
en capa 2k + 1. Por ejemplo,
profundidad 0 incluye nodos
MAX en capa 0 y nodos MIN en
capa 1, profundidad 1 incluye
nodos MAX en capa 2 y nodos
MIN en capa 3, etc.
○ Turno MAX en capas pares y
turno MIN en capas impares.
 Algoritmo MINIMAX
capa 0
profundidad 0
capa 1

capa 2
profundidad 1
capa 3
 Algoritmo MINIMAX

● Según el algoritmo MINIMAX, la estrategia

óptima puede determinarse examinando el
valor minimax de cada nodo sucesor del
nodo raíz y seleccionando el valor más
alto.
● Valor minimax = utilidad de un nodo (para
MAX), asumiendo que ambos jugadores
juegan óptimamente de ahí al final del
juego.
● El nodo raíz se va a corresponder con la
situación actual del juego.
○ Se elige el mejor movimiento para
MAX en ese momento concreto del
juego.
 Algoritmo MINIMAX

● Para ello, el algoritmo MINIMAX:

○ Primero se asignan los valores
minimax en las hojas aplicando la
función de utilidad (eval.
estática).
○ Después, se propagan los valores
hacia arriba en el árbol (eval.
dinámica):
■ En la capa MIN, se
asignan los valores
mínimos de sus sucesores
(nodo B con 3, dados 3, 12
y 8) y en la MAX, los
valores más grandes (nodo
A con 3, dados 3, 2 y 2).
 Algoritmo MINIMAX

● MAX preferirá moverse a un estado de

valor máximo (máximiza la utilidad de
sus sucesores), mientras que MIN
prefiere un estado de valor mínimo
(mínimiza la utilidad de sus sucesores).
● Objetivo: encontrar el mejor
movimiento en la situación actual del
juego que haga que MAX sea el
ganador.
● El mejor movimiento de MAX en la raíz
es a1, porque conduce al sucesor con
el valor minimax más alto, y la mejor
respuesta de MIN es b1, porque
conduce al sucesor con el valor
minimax más bajo.
 Algoritmo MINIMAX

● Suposición de partida: MIN también

juega óptimamente.
○ MIN elegirá siempre la mejor
jugada para él (y peor para
MAX).
○ MIN es, al menos, tan inteligente
como MAX (sabe evaluar
también como MAX, ya que usa
la misma función de utilidad.
● ¿Y si MIN no juega óptimamente? En-
tonces es fácil demostrar que MAX lo
hará aún mejor.
○ Si MIN escoge sucesor con valor
12 en lugar de con valor 3, el
resultado para MAX será aún
mejor.
Algoritmo MINIMAX

○ Determina el mejor movimiento que haga que MAX sea ganador.

○ Consiste en:

(ya que 1 profundidad = 2 capas/niveles)

Algoritmo MINIMAX

● Pasos:
Algoritmo MINIMAX
Algoritmo MINIMAX

○ Función de evaluación:
■ Se aplica cuando los nodos hoja del árbol generado no son posiciones
terminales (ganadora, perdedora o empate).
■ Devuelve una estimación de la utilidad esperada de una posición dada, tal
como hacen las funciones heurísticas.
■ El buen funcionamiento de MINIMAX va a dependender de la calidad de la
función de evaluación.
■ Una función de evaluación debería:
● Ordenar los nodos hoja igual que lo hace la función de utilidad.
● Ser eficiente y no consumir demasiado tiempo.
● Para estados no terminales, estar fuertemente correlacionada con las
posibilidades reales de ganar.
Algoritmo MINIMAX
○ Función de evaluación:
■ La mayoría de las funciones de evaluación trabajan calculando varias
características del estado (por ejemplo, en el juego de ajedrez, el número de
peones capturados por cada lado).
■ La mayoría de las funciones de evaluación calculan las contribuciones numéricas
de cada característica y luego las combinan para encontrar el valor total.
● Por ejemplo, los libros de ajedrez dan el valor material para cada pieza: cada
peón vale 1, un caballo o el alfil valen 3, una torre 5, y la reina vale 9.
■ Estos valores de características, entonces, simplemente se suman de forma
ponderada para obtener la evaluación de la posición.
Algoritmo MINIMAX
● Ejemplo TIC-TAC-TOE
○ Evaluación estática:

Las hojas del árbol resultante pueden ser posiciones finales (ganadora, perdedora o de empate), pero
también pueden ser estados intermedios del árbol global que se convierten en hojas en el árbol parcial
resultante de la limitación de profundidad.
Algoritmo MINIMAX
Algoritmo MINIMAX

Si no es posición final,
entonces evaluamos el
nodo hoja mediante una
función de evaluación.

Dados una posición (estado actual) y un

nivel (capa) en cada llamada recursiva,
la recursión avanza hacia las hojas del
árbol, y entonces los valores minimax
retroceden por el árbol cuando la
recursión se va deshaciendo.

El pseudocódigo del algoritmo MINIMAX

retorna el valor del mejor movimiento
para MAX. Dicha información será
utilizada para seleccionar el próximo
mejor movimiento para MAX.
Algoritmo MINIMAX
● Ejemplo TIC-TAC-TOE

NOTA: 8 = 3 filas + 3 columnas + 2 diagonales. MAX juega con las X y MIN con los O.

Empate:
abiertos(MAX) = 8 - 3 filas ocupadas - 3 columnas ocupadas - 2 diagonales ocupadas = 0
abiertos(MIN) = 8 - 3 filas ocupadas - 3 columnas ocupadas - 2 diagonales ocupadas = 0
evaluación(E) = abiertos(MAX) - abiertos(MIN) = 0
Algoritmo MINIMAX
● Ejemplo TIC-TAC-TOE

NOTA: 8 = 3 filas + 3 columnas + 2 diagonales. MAX juega con las X y MIN con los O.

Hemos alcanzado el límite de profundidad y el ejemplo es un estado hoja a evaluar con la

función de evaluación:
abiertos(MAX) = 8 - 1 filas ocupada - 1 columnas ocupadas - 0 diagonales ocupadas = 6
abiertos(MIN) = 8 - 1 filas ocupadas - 2 columnas ocupadas - 2 diagonales ocupadas = 3
utilidad(E) = abiertos(MAX) - abiertos(MIN) = 3
Algoritmo MINIMAX
● Características:
■ El algoritmo realiza una exploración en profundidad completa del árbol de
juegos.
■ Si la profundidad máxima del árbol es m, y hay b movimientos legales en
cada posición, entonces la complejidad temporal del algoritmo MINIMAX es
O(bm).
■ La complejidad espacial es O(bm) para un algoritmo que genere todos los
sucesores a la vez, o O(m) para un algoritmo que genere los sucesores uno
por uno.
■ Para juegos reales, los costes de tiempo son poco prácticos, pero este
algoritmo sirve como base para el análisis matemático de juegos y para
algoritmos más prácticos.
Poda ALFA-BETA

(hacia arriba)

(el número de estados que tiene que generar es exponencial

en el número de movimientos)
Poda ALFA-BETA

● John McCarthy concibió la idea de la búsqueda con poda alfa-beta en 1956,

aunque no lo publicó.
● Según Nilsson (1971), el programa de damas de Arthur Samuel también
utilizaba la búsqueda alfa-beta, aunque Samuel no lo mencionara en los
informes publicados sobre el sistema.
● Los trabajos que describen alfa-beta fueron publicados a principios de 1960
(Hart y Edwards, 1961; Brudno, 1963; Slagle, 1963).
Poda ALFA-BETA
Poda ALFA-BETA
Poda ALFA-BETA
● Ejemplo:

Partimos del nodo raíz con la ventana [-∞, +∞] (propagada hacia los nodos hoja) e iremos generando el árbol en profundidad.
El primer nodo hoja debajo de B tiene el valor 3. De ahí B (que es un nodo MIN y escoge el mínimo valor minimax) va a
propagar un valor de como máximo 3 (β = 3).
Poda ALFA-BETA
● Ejemplo:

El segundo nodo hoja debajo de B tiene un valor de 12; MIN evitaría este movimiento (porque minimiza el valor
minimax), entonces el valor de β en B es todavía como máximo 3.
Poda ALFA-BETA
● Ejemplo:

La tercera hoja debajo de B tiene un valor de 8; hemos visto a todos los sucesores de B, entonces el valor de B es
exactamente 3. Por lo tanto el intervalo [α, β] queda en [3, 3]. Ahora, podemos deducir que el valor de la raíz es al menos
3, porque MAX tiene una opción como mínimo de 3 en la raíz. Entonces en el nodo raíz α es igual a 3.
Poda ALFA-BETA
● Ejemplo:

Seguimos explorando la siguiente rama, donde el primer nodo hoja debajo de C tiene el valor 2. De ahí, C, que es un nodo
MIN, tiene un valor de como máximo 2 (β = 2). Pero sabemos que B vale 3, entonces MAX nunca elegiría C. C podría tener
otros nodos hoja con menor valor minimax, pero MAX siempre elegiría a B (ya que maximiza los valores minimax). Por lo
tanto, no hay ninguna razón en seguir comprobando los otros sucesores de C. Este es un ejemplo de poda alfa-beta.
Poda ALFA-BETA
● Ejemplo:

Nos vamos a la tercera rama, donde el primer nodo hoja debajo de D tiene el valor 14, entonces D vale como máximo 14 (β = 14).
Este es todavía más alto que la mejor alternativa de MAX (es decir, 3), entonces tenemos que seguir explorando a los sucesores
de D. Además, ahora completamos el intervalo sobre todos los sucesores de la raíz A con un β = 14, resultando en [3, 14]. D
podría tener un sucesor con valor superior a 14, pero D (como nodo MIN) siempre va a escoger el valor minimax más bajo.
Poda ALFA-BETA
● Ejemplo:

El segundo sucesor de D vale 5, así que otra vez tenemos que seguir explorando. El tercer sucesor vale 2, así que ahora D
vale exactamente 2 (resultando en el intervalo [2, 2] en D y [3, 3] en A).
La decisión de MAX en la raíz es moverse a B, dando un valor de 3, y nos hemos ahorrado generar y evaluar 2 nodos hoja.
Poda ALFA-BETA
● Ejemplo:

Puede verse como que el valor minimax de la raíz A (de la que depende la decisión tomada por el algoritmo), es
independiente de los dos nodos podados.
Poda ALFA-BETA
Poda ALFA-BETA
■ Podas (cortes):
 Poda ALFA-BETA
● Ejemplo 2: MAX

B
MIN
El valor minimax que
sube del nodo MAX
actualiza la cota β en C
el nodo MIN. De MAX
momento, como
máximo MIN va a
concederle a MAX
en el siguiente nivel
un 3.
Poda ALFA-BETA
● Ejemplo 2: MAX

MIN

MAX

¡Corte β!
α > βpadre
Poda ALFA-BETA
● Ejemplo 2: MAX

MIN

MAX
Poda ALFA-BETA
● Ejemplo 2: MAX

MIN

MAX
Poda ALFA-BETA
● Ejemplo 2: MAX

MIN
¡Corte α!
β < αpadre
MAX
Poda ALFA-BETA
● Ejemplo 2: MAX

MIN

MAX
Poda ALFA-BETA
■ Algoritmo:

)
Poda ALFA-BETA
■ Algoritmo:
 Poda ALFA-BETA
■ Algoritmo:

En los nodos MAX actualizamos la cota

α (la cota β no se modifica). Además, α
se va actualizando a medida que
exploramos los sucesores, de tal forma
que podamos llevar a cabo una poda β.

)
 Poda ALFA-BETA
■ Algoritmo:

En los nodos MIN actualizamos la cota

β (la cota α no se modifica). Además, β
se va actualizando a medida que
exploramos los sucesores, de tal forma
que podamos llevar a cabo una poda α.
)

Finalmente, retornamos el valor

minimax obtenido por el método
ALFA_BETA().
Poda ALFA-BETA
■ Algoritmo:
Poda ALFA-BETA

MINIMAX
Poda ALFA-BETA
● Con ordenación perfecta de sucesores, tendría que examinar sólo O(bm/2) nodos para
escoger el mejor movimiento, en vez de O(bm) para MINIMAX, siendo b el factor de
ramificación y m la profundidad máxima.
○ Entonces complejidad temporal O(bm/2) si la ordenación es perfecta.
○ Esto implica que ALFA-BETA podrá alcanzar un nivel aproximadamente dos veces
mayor que MINIMAX en la misma cantidad de tiempo.
○ Y significa que el factor de ramificación eficiente sería √b* en vez de b* (e.j., para
el ajedrez, 6 en vez de 35).
○ En la práctica la ordenación perfecta no es posible (tendríamos que explorar todos
los sucesores y eso mismo es lo que tratamos de evitar), pero podemos aplicar
primero una función de evaluación simple para preordenar los sucesores.
● Si los sucesores se examinan en orden aleatorio, el número total de nodos examinados
será aproximadamente O(b3m/4), tal y como ha sido demostrado empíricamente.
● La complejidad espacial sigue siendo O(bm).
Mejoras MINIMAX
Mejoras MINIMAX

Ejemplo: en el turno del jugador negro, la búsqueda a profundidad d

ha terminado y establece que la posición mostrada en la Figura tiene
un valor positivo, debido a la superioridad en material de las negras, lo
que indicará al algoritmo de búsqueda que ésta es una posición
favorable. Sin embargo, la posición es muy mala, debido a que se está
perdiendo a la reina que se encuentra en la línea de ataque del alfil
enemigo y no puede moverse debido a que su rey se encuentra
detrás. Para poder haber evitado esta posición y que la función de
evaluación encontrara que el valor real de la posición, era necesario
explorar 10 jugadas más a futuro. La búsqueda se extiende debido a
que se pueden interponer peones en la línea de ataque del alfil, pero
lo único que se logra es posponer la pérdida de la reina. La posición
para el jugador negro debería estimarse cercana a Mate, aunque el
jugador negro tenga una torre en vez de un alfil y más peones en esa
posición.
Mejoras MINIMAX

o Búsqueda Quiescence

o estables (quiescent)
extremo
● Dado un valor extremo estimado por la función de evaluación sobre nodos
hojas (no posiciones finales), se sigue profundizando por esa rama hasta que
la función de evaluación retorna un valor menos extremo.

Los jugadores humanos usualmente tienen suficiente intuición para decidir si deben abandonar líneas de movimientos que parezcan malas, o
buscar movimientos prometedores a gran profundidad. La búsqueda Quiescence intenta emular este comportamiento al seleccionar
posiciones relevantes o inestables para buscar a mayor profundidad. La heurística pretende evitar trampas escondidas y obtener una mejor
estimación del valor real de las posiciones. De esta manera, se mitiga el efecto horizonte al continuar la búsqueda, aun cuando la profundidad
límite se haya alcanzado, continuando hasta que no existan más posiciones inestables (hasta alcanzar la tranquilidad = quiescence).
Mejoras MINIMAX
Mejoras MINIMAX
Mejoras MINIMAX

(killer moves)

(mediante una heurística para ordenar sucesores)

Mejoras MINIMAX

5. Uso de tablas de transposiciones:

○ En los juegos, los estados repetidos ocurren con frecuencia debido a
transposiciones (permutaciones diferentes de la secuencia de
movimientos que terminan en la misma posición).
○ Entonces se puede almacenar la evaluación de cada posición en una
tabla la primera vez que se encuentre, de modo que no tuviéramos que
volver a calcularlo las siguientes veces.
○ Su uso puede tener un efecto notable, tanto como doblar la
profundidad accesible de búsqueda en el ajedrez.
○ Por otra parte, si evaluamos un millón de nodos por segundo, no es
práctico guardar todos ellos en la tabla de transposiciones.
■ Se utilizan estrategias para elegir los más valiosos.
Mejoras MINIMAX

6. Poda hacia delante (Forward Pruning):

○ Búsqueda en Haz Local (Beam Search):
■ Sólo se prueban las n acciones más prometedoras según una
heurística (muy rápida).
○ Corte Probabilístico (ProbCut):
■ Utiliza la probabilidad obtenida mediante técnicas de aprendizaje
para eliminar aquellas acciones que podrían estar fuera del rango
ALFA-BETA.
● Se adelanta a la poda ALFA-BETA.
Juegos con elementos de azar (y dos jugadores)
Juegos con elementos de azar
Juegos con elementos de azar
● Ejemplo backgammon: juego que
utiliza dos dados.
○ Hay 36 resultados DADO
posibles de lanzar 2 dados
○ La probabilidad de sacar
lo mismo en ambos dados
(de 1-1 a 6-6) es 1/36.
○ El resto de combinaciones
es 1/18, porque, cuando
se utilizan dos dados, da DADO
lo mismo sacar un 5-6 que
un 6-5.
● El nodo DADO se suele
denominar nodo de posibilidad.
Juegos con elementos de azar
● Se amplía MINIMAX a MINIMAXESPERADO (EXPECTED-MINIMAX), donde:
Juegos con elementos de azar
● Por lo general, se propaga la media ponderada de acuerdo a probabilidades:
○ Se generaliza el valor minimax para juegos deterministas a un valor
minimaxesperado para juegos con elementos de azar.
○ Los nodos terminales y los MAX y MIN (para los que se conocen sus resultados)
trabajan exactamente del mismo modo que antes; los nodos de posibilidad se
evalúan tomando el promedio ponderado de los valores que se obtienen de todos
los resultados posibles, es decir:

donde la función sucesor para un nodo de posibilidad n simplemente aumenta el estado n con cada resultado
posible para producir cada sucesor s, y P(s) es la probabilidad de que ocurra ese resultado.
Juegos con elementos de azar

2*0,9 + 3*0,1 = 2,1

1*0,9 + 4*0,1 = 1,3

2 3 5 3 1 6 7 4
Juegos con elementos de azar
● Complejidad del MINIMAXESPERADO
○ Introducir movimientos de azar incrementa el espacio de búsqueda
■ Estamos añadiendo una capa adicional en cada jugada con un alto factor de ramificación.
○ Si el programa supiera de antemano todos los resultados de las tiradas que ocurrirían para el
resto del juego, resolver un juego con dados sería como resolver un juego sin dados, en el que
MINIMAX explora O(bm) nodos (siendo b el factor de ramificación y m la profundidad o límite de
profundidad).
○ Sin embargo, MINIMAXESPERADO considera también todas las secuencias de las tiradas
posibles y, por lo tanto, el árbol resultante tendrá en el peor de los casos O(bmnm) nodos, donde
n es el número de resultados distintos del nodo posibilidad.
○ El coste adicional, comparado con el de MINIMAX, lo hace poco realista para considerar
anticiparse muy lejos en la mayoría de los juegos de azar. En backgammon n es 21 y b está por
lo general alrededor de 20. Tres capas serían, probablemente, todo lo que podríamos manejar.
○ No deberíamos aplicar poda ALFA-BETA sobre MINIMAXESPERADO porque no funcionaría de
forma correcta (no tenemos valores exactos en los nodos de posibilidad, sino probabilidades).
Algoritmo de Monte Carlo
○ Conocido como el algoritmo Monte-Carlo Tree Search (MCTS)
○ Es un algoritmo de búsqueda informada aplicado, entre otras tareas, a juegos.
○ Está basado en una exploración aleatoria del espacio de búsqueda, pero usa los
resultados de previas exploraciones.
○ Para ello construye gradualmente un árbol MCTS en memoria, que mejora
sucesivamente estimando los valores de los movimientos más prometedores.
○ Puede manejar información incompleta o incertidumbre:
■ Es útil cuando la información sobre el juego o el entorno es incompleta o
incierta.
Algoritmo de Monte Carlo
○ Una partida se representa como un árbol MCTS, en la que cada nodo
corresponde a un estado particular.
○ El nodo raíz representa la posición de inicio de partida y tenemos un jugador por
capa.
○ Los hijos de cada nodo son estados alcanzables en un movimiento.
○ Cada nodo i representa una posición alcanzada de una partida y contiene:
■ wi es el valor actual de la posición, dependiendo el problema representará
una cosa u otra. Suele representar el número de partidas ganadas que
pasaron por ese nodo. Inicializado a 0.
■ ni es el contador de visitas que ha sufrido ese nodo. Inicializado a 0.
■ Ci es el contenido asociado al problema concreto en el que estemos
trabajando. En juegos representa un movimiento realizado desde el estado
del nodo padre.
Algoritmo de Monte Carlo

● Fases:
○ Selección: El árbol se recorre desde el nodo raíz hasta alcanzar un nodo hoja. La selección de sucesores se hace en base a una estrategia que utiliza la
información almacenada en cada nodo en ese momento y es independiente del juego. La estrategia original es aplicar aleatoriedad; sin embargo, una de las
más utilizadas (por simplicidad, eficiencia y equilibrio en la exploración) es UCT (Upper Confidence bounds applied to Trees):
● Para cada uno de los sucesores i, calcula el valor UCTi y selecciona el más alto:
UCTi=

● Ni es el número de veces que se ha visitado el padre del nodo y wi / ni es la tasa de éxito de ese nodo. El primer término de la suma (tasa de éxito)
está relacionado con la explotación (ratio alto sobre nodos exitosos), y el segundo término está relacionado con la exploración (más alto sobre nodos
poco visitados). Dependiendo del coeficiente c (superior a 0) empleado en la combinación de ambos valores, se puede dar mayor prioridad a la
explotación o a la exploración (suele utilizarse raíz cuadrada de 2, aunque es recomendable determinarlo empíricamente).
Algoritmo de Monte Carlo

● Fases:
○ Expansión: Salvo que el nodo hoja seleccionado sea una posición final del juego, se añaden nodos al árbol a partir de ese nodo hoja siguiendo una
estrategia de expansión. Entre ellas destacamos las siguientes variantes:
■ Se expande un nodo siempre independientemente de su número de visitas.
■ Se expande sólo si ese nodo ha superado un número mínimo de visitas. La no expansión hasta que no se alcance un número mínimo de
visitas, permite ahorrar espacio en memoria, pudiendo evitar en muchos casos crear ramas innecesarias.
○ También se puede:
■ Añadir un solo sucesor en la expansión (ahorra memoria, pero en cada iteración hay que comprobar qué sucesores ya hemos generados
previamente).
■ Añadir todos los sucesores en la expansión y seleccionar uno cualquiera (ocupa más memoria, pero ahorra comprobaciones posteriores).
○ El nodo raíz se trata como un caso especial y siempre se expande.
Algoritmo de Monte Carlo

● Fases:
○ Simulación: Se realiza una partida simulada (aleatoriamente o basado en una heurística) partiendo del
nodo alcanzado en las fases anteriores (simulación de Monte Carlo). Durante esta partida simulada, el
programa juega solo, realizando los movimientos de todos los jugadores que intervienen hasta que la
partida finalice y se obtenga un resultado R (un valor de utilidad o recompensa).
Algoritmo de Monte Carlo

● Fases:
○ Retropropagación: El resultado de la simulación se propaga hacia los nodos atravesados previamente
(desde la raíz). Por un lado, se actualizan (incrementan en una unidad) el número de visitas ni de los nodos
implicados en la jugada. Por otro lado, se actualiza el valor wi usando el resultado R de la simulación en
función de si ha ganado o perdido. En concreto, dados 2 jugadores, se incrementa R sobre wi en únicamente
aquellos nodos que representan el jugador opuesto al que ha ganado. Esto se debe a que para elegir el mejor
movimiento en cada nodo padre, se basa en la información almacenada en el nodo hijo (que será el jugador
contrincante).
Algoritmo de Monte Carlo

● Cuando el tiempo o número de simulaciones haya finalizado, el movimiento elegido será el sucesor del nodo raíz más prometedor. Este
puede seleccionarse en base a una de las siguientes estrategias:
○ El sucesor con el valor máximo wi (número de jugadas ganadas)
○ El sucesor con un mayor número de visitas ni (más robusto).
○ El sucesor con un valor máximo wi dentro de los que han sido más visitados.
● Kocsis y Szepesvári demostraron que la probabilidad de seleccionar una acción subóptima (es decir, no la mejor) para la raíz del árbol
tiende a 0 si el número de iteraciones tiende a infinito, lo que significa que, con suficiente tiempo y memoria, el algoritmo de Monte Carlo
con UCT tiende (converge) al MINIMAX (construiría un árbol MINIMAX).
Algoritmo de Monte Carlo
● Una versión simplificada de este algoritmo se consigue haciendo que la recompensa R esté limitada a 3
posibles valores: 1, cuando el jugador gana; 0, cuando el jugador pierde; y 0.5, cuando se produce un
empate entre ambos jugadores.
○ Fase: Selección (aplicando UCT)
Algoritmo de Monte Carlo
● Una versión simplificada de este algoritmo se consigue haciendo que la recompensa R esté limitada a 3
posibles valores: 1, cuando el jugador gana; 0, cuando el jugador pierde; y 0.5, cuando se produce un
empate entre ambos jugadores.
○ Fase: Expansión (un único sucesor)
Algoritmo de Monte Carlo
● Una versión simplificada de este algoritmo se consigue haciendo que la recompensa R esté limitada a 3
posibles valores: 1, cuando el jugador gana; 0, cuando el jugador pierde; y 0.5, cuando se produce un
empate entre ambos jugadores.
○ Fase: Simulación
Algoritmo de Monte Carlo
● Una versión simplificada de este algoritmo se consigue haciendo que la recompensa R esté limitada a 3
posibles valores: 1, cuando el jugador gana; 0, cuando el jugador pierde; y 0.5, cuando se produce un
empate entre ambos jugadores.
○ Fase: Retropropagación

Antes:
Algoritmo de Monte Carlo
● Monte Carlo VS MINIMAX
○ MINIMAX es adecuado para juegos deterministas de dos jugadores con información completa, mientras que el
método de Monte Carlo se puede aplicar también en juegos con información incompleta e incertidumbre.
○ Aunque se ha demostrado empíricamente que el algoritmo de Monte Carlo converge en el MINIMAX cuando
utilizamos la estrategia UTC, la versión original de Monte Carlo sólo converge en cierto tipo de juegos denominados
Monte Carlo Perfect Games (clase de juegos donde el método de Monte Carlo alcanza resultados óptimos o muy
cercanos a óptimos).
○ En contraste con el algoritmo MINIMAX, el algoritmo Monte Carlo original no requiere de función de evaluación (sí de
utilidad). Sólo requiere de una implementación simple de la mecánica del juego (movimientos permitidos y posiciones
finales). Por lo tanto, el algoritmo de Monte Carlo puede ser aplicado sobre cualquier juego, incluso sobre aquellos
que no tienen unos estudios teóricos extensos.
○ Mientras que MINIMAX explora todo el espacio de búsqueda hasta una profundidad determinada, considerando
todas las posibles jugadas (búsqueda exhaustiva); el algoritmo de Monte Carlo no necesita explorar todas las
posibles acciones, sino que utiliza simulaciones aleatorias para estimar la utilidad esperada de aquellas acciones más
prometedoras.
○ En el método de Monte Carlo el árbol crece de forma asimétrica a medida que el algoritmo se concentra en las ramas
más prometedoras. El MINIMAX explora el árbol completo, salvo que apliquemos algún tipo de poda como la
ALFA-BETA. Por lo tanto, el algoritmo de Monte Carlo es más adecuado para juegos más complejos con un alto
factor de ramificación.
○ Si el tiempo requerido para la simulación es muy costoso, el algoritmo de Monte Carlo puede no ser aplicable.
Ejemplos de prácticos: Ajedrez
○ En 1951, Alan Turing escribió el primer programa de computador capaz de jugar
un juego completo de ajedrez (pero nunca se llegó a ejecutar).
○ En 1957, Herbert Simon predijo que dentro de 10 años los computadores
ganarían al campeón mundial humano.
○ Se equivocó: fue en 1997 (40 años más tarde) cuando el programa Deep Blue
derrotó a Garry Kasparov en un partido de exhibición a seis juegos.
○ Deep Blue fue desarrollado por Campbell, Hsu, y Hoane en IBM, construido
sobre el diseño de Deep Thought (desarrollado anteriomente por Campbell y Hsu
en Carnegie Mellon).
○ Deep Blue buscó 126 millones de nodos por segundo, como regla general, con
una velocidad máxima de 330 millones de nodos por segundo. Generó hasta 30
billones de posiciones (estados) por movimiento, y alcanzó la profundidad 14
por defecto.
Ejemplos de prácticos: Ajedrez
○ Deep Blue se basaba en una búsqueda ALFA-BETA estándar de profundidad
iterativa con una tabla de transposiciones, pero la clave de su éxito parece
haber estado en su capacidad de generar extensiones más allá del límite de
profundidad para líneas suficientemente interesantes. En algunos casos la
búsqueda alcanzó una profundidad de 40 capas.
○ La función de evaluación tenía más de 8.000 características, muchas de ellas
describiendo modelos muy específicos de las piezas.
○ Se usaron «movimientos de libro» con 700.000 jugadas de gran maestro y de
finales del juego de posiciones resueltas, conteniendo todas las posiciones con
cinco piezas y muchas con seis piezas. Esta base de datos servía para ampliar la
profundidad efectiva de búsqueda, permitiendo a Deep Blue jugar perfectamente
en algunos casos aún cuando se alejaba del jaque mate (esto es, el árbol
generado no llegaba a estados terminales).
Ejemplos de prácticos: Ajedrez
○ En 2006, el programa Deep Fritz, funcionando simplemente en un ordenador
personal con procesador Intel Core 2 Duo, consiguió derrotar también al entonces
campeón mundial Vladímir Krámnik.
○ En 2008, se desarrolla Stockfish, un sistema que puede usar hasta 512 hilos de
CPU en sistemas multiprocesador, que le permiten examinar 70 millones de
posiciones por segundo, e implementa una poda ALFA-BETA avanzada que se
caracteriza por su gran profundidad de búsqueda, entre otras mejoras.
■ Varias veces número 1 en los rankings no oficiales.
○ En 2017, Stockfish 8 (versión del 2016) se enfrentó a AlphaZero desarrollado
por DeepMind (Google). Se enfrentaron en una serie de cien partidas, la mitad
jugando con blancas y la mitad con negras. AlphaZero ganó 28 e hicieron tablas
en 72.
Ejemplos de prácticos: Ajedrez
○ Para lograrlo, AlphaZero tan solo necesitó conocer las reglas del juego y 4 horas de
entrenamiento jugando contra sí mismo (sin acceso a libros de apertura o base de datos de
jugadas finales).
○ Hasta ese momento se utilizaba MINIMAX con poda ALFA-BETA y una función de evaluación
compleja, pero DeepMind desarrolló un sistema que combinaba técnicas aprendizaje por
refuerzo, redes neuronales profundas (convolucionales sobre imágenes del tablero) y el
algoritmo de Monte Carlo.
■ En particular, mejoran el algoritmo de Monte Carlo original al utilizar redes neuronales
profundas para:
● Evaluar las posiciones del juego durante la exploración en la fase de selección.
● Generación de los nodos más prometedores en la fase de expansión.
■ Utilizan el algoritmo de Monte Carlo que evalúa una posición generando una serie de
secuencias de movimientos aleatorios y, haciendo una media de los resultados finales que
genera (victoria/tablas/derrota) y actualizando los pesos de la red neuronal cuando los
movimientos aleatorios le llevan a posiciones “buenas” (aprendizaje por refuerzo).
○ No entrenaron AlphaZero con jugadas humanas sino que dejaron que él se fuese
auto-entrenando desde cero, aprendiendo una forma de jugar diferente a la humana (y que
muchas veces sacrifica piezas valiosas que un humano no haría).
Ejemplos de prácticos: Damas
○ En 1952, Arthur Samuel de IBM, trabajando en sus ratos libres, desarrolló un
programa de damas que aprendió su propia función de evaluación jugando con él
mismo miles de veces.
○ El programa de Samuel comenzó como un principiante, pero después de unos
días jugando contra si mismo, se había mejorado más allá del propio nivel de
Samuel (aunque él no era demasiado bueno).
○ En 1962, derrotó a Robert Nealy, un campeón de las damas.
○ Muchas personas señalaron que, a las damas, los computadores eran superiores
al ser humano.
○ Aún así, si consideramos que el equipo de Samuel (un IBM 704) tenía 10.000
palabras de memoria principal, cinta magnetofónica para el almacenaje a largo
plazo y un procesador de 0,000001 GHz, el triunfo sigue siendo un gran logro.
Ejemplos de prácticos: Damas
○ Después, Jonathan Schaeffer y sus colegas desarrollaron Chinook, que se
ejecuta sobre computadores personales y usa la búsqueda alfa-beta.
○ Chinook usa una base de datos precalculada de 444 billones de posiciones con
ocho o menos piezas sobre el tablero para así hacer la fase final del juego de
forma impecable.
○ El partido del campeonato mundial en agosto de 1994 entre Tinsley (campeón
mundial durante 40 años con sólo 3 derrotas) y Chinook se saldó con victoria de
éste último (Tinsley se retiró por motivos de salud).
○ Chinook se convirtió en el campeón mundial oficial.
Ejemplos de prácticos: Go
○ Como el tablero es de 19x19, el factor de ramificación es de 361, que desalienta también
a los métodos regulares de búsqueda.
○ Hasta 2015 no había ningún programa capaz de vencer a jugadores profesionales sin
emplear piedras de handicap (con ventaja para la máquina).
○ En 2015, AlphaGo, desarrollado por DeepMind (Google), se convirtió en la primera
máquina de Go en ganar a un jugador profesional sin handicap en un tablero de 19x19.
○ Se enfrentó contra el jugador chino Fan Hui en una serie de 5 partidas oficiales, las
cuales AlphaGo ganó, seguidas por unas partidas informales que acabaron 3-2 a favor
de la inteligencia artificial.
○ Hasta marzo del 2016, AlphaGo estaba clasificado como número dos del mundo en el
ranking no oficial de Rémi Coulom.
○ En 2017, AlphaZero, del propio DeepMind, superó a la versión AlphaGo después de
solo 24 horas de juego. Después de 4 horas de juegos adquirió un nivel superhumano.
○ AlphaGo y sus sucesores se basan en el algoritmo de Monte Carlo.