PDF de programación - búsqueda con adversario - Juegos

Búsqueda con adversario

Juegos

Introducción

Uso: Decidir mejor jugada en cada momento para cierto tipo de
juegos
Hay diferentes tipos de juegos según sus características:

Numero de jugadores, toda la información conocida por todos los
jugadores, azar, indeterminismo, cooperación/competición, recursos
limitados, ...

Nos focalizaremos en juegos con:

2 jugadores.
Movimientos alternos (jugador MAX, jugador MIN)
Información perfecta
Por ejemplo: ajedrez, damas, otello, go, ...

c b e a (LSI-FIB-UPC)

Introducción a la Inteligencia Artificial

Curso 2011/2012

1 / 16

Representación del juego

Juegos

Introducción

Puede ser definido como un problema de espacio de estados

Estado = Elementos del juego
Estados finales= Estados ganadores (Definidos por sus propiedades)
Acciones/operadores = Reglas del juego

Son problemas con características especiales

La accesibilidad de los estados depende de las acciones elegidas por el
contrario
Dos tipos de soluciones diferentes (una para cada jugador)
No hay nocion de optimalidad (todas las soluciones son iguales, no
importa la longitud del camino)

c b e a (LSI-FIB-UPC)

Introducción a la Inteligencia Artificial

Curso 2011/2012

2 / 16

Búsqueda con adversario

Juegos

Introducción

La aproximación trivial es generar todo el árbol de jugadas
Etiquetamos las jugadas terminales dependiendo de si gana MAX o
MIN (+1 o -1)
El objetivo es encontrar un conjunto de movimientos accesible que de
como ganador a MAX
Se propagan los valores de las jugadas terminales de las hojas hasta la
raíz, elegimos una rama de una hoja ganadora accesible
Una búsqueda en profundidad minimiza el espacio
En juegos mínimamente complejos esta búsqueda es impracticable
(p.e.: ajedrez O(235), go O(2300))

c b e a (LSI-FIB-UPC)

Introducción a la Inteligencia Artificial

Curso 2011/2012

3 / 16

Búsqueda con adversario

Juegos

Introducción

+1

+1

+1

+1

-1

-1

-1

c b e a (LSI-FIB-UPC)

Introducción a la Inteligencia Artificial

Curso 2011/2012

4 / 16

Búsqueda con adversario

Juegos

Introducción

+1

+1

+1

+1

+1

+1

-1

-1

-1

c b e a (LSI-FIB-UPC)

Introducción a la Inteligencia Artificial

Curso 2011/2012

5 / 16

Búsqueda con adversario

Juegos

Introducción

+1

+1

+1

-1

-1

-1

-1

+1

+1

+1

-1

-1

c b e a (LSI-FIB-UPC)

Introducción a la Inteligencia Artificial

Curso 2011/2012

5 / 16

Búsqueda con adversario

Juegos

Introducción

+1

+1

+1

-1

-1

-1

-1

-1

+1

+1

+1

-1

-1

c b e a (LSI-FIB-UPC)

Introducción a la Inteligencia Artificial

Curso 2011/2012

5 / 16

Búsqueda con adversario

Juegos

Introducción

+1

+1

+1

-1

-1

-1

-1

-1

+1

+1

-1

-1

-1

+1

-1

c b e a (LSI-FIB-UPC)

Introducción a la Inteligencia Artificial

Curso 2011/2012

5 / 16

Búsqueda con adversario

Juegos

Introducción

+1

+1

+1

-1

-1

-1

-1

-1

+1

+1

-1

-1

-1

+1

+1

-1

c b e a (LSI-FIB-UPC)

Introducción a la Inteligencia Artificial

Curso 2011/2012

5 / 16

Búsqueda con adversario

Juegos

Introducción

+1

+1

+1

-1

-1

-1

-1

-1

+1

+1

+1

+1

-1

-1

-1

+1

+1

-1

c b e a (LSI-FIB-UPC)

Introducción a la Inteligencia Artificial

Curso 2011/2012

5 / 16

Búsqueda con adversario

Juegos

Introducción

+1

+1

+1

-1

-1

-1

-1

-1

+1

+1

+1

-1

-1

-1

+1

+1

+1

-1

-1

-1

-1

c b e a (LSI-FIB-UPC)

Introducción a la Inteligencia Artificial

Curso 2011/2012

5 / 16

Búsqueda con adversario

Juegos

Introducción

+1

+1

+1

-1

+1

-1

-1

-1

-1

-1

+1

+1

+1

-1

-1

-1

+1

+1

-1

-1

-1

-1

c b e a (LSI-FIB-UPC)

Introducción a la Inteligencia Artificial

Curso 2011/2012

5 / 16

Búsqueda con adversario

Juegos

Introducción

+1

+1

+1

-1

+1

+1

+1

-1

-1

-1

-1

+1

+1

+1

-1

-1

-1

-1

-1

+1

-1

-1

-1

c b e a (LSI-FIB-UPC)

Introducción a la Inteligencia Artificial

Curso 2011/2012

5 / 16

Búsqueda con adversario

Juegos

Introducción

+1

+1

+1

-1

+1

+1

+1

-1

-1

-1

-1

+1

+1

+1

-1

-1

-1

-1

-1

+1

-1

-1

-1

c b e a (LSI-FIB-UPC)

Introducción a la Inteligencia Artificial

Curso 2011/2012

5 / 16

Búsqueda con adversario

Juegos

Introducción

Aproximación heurística: Definir una función que nos indique lo cerca
que estamos de una jugada ganadora (o perdedora)
En esta función intervendrá información del dominio
Esta función no representa ningún coste ni es una distancia en pasos
Por convención las jugadas ganadoras se evalúan a +∞ y las
perdedoras a −∞
El algoritmo busca con profundidad limitada y sólo decide la siguiente
jugada a partir del nodo raíz
Cada nueva decisión implicará repetir la búsqueda
A mayor profundidad en la búsqueda mejor jugaremos

c b e a (LSI-FIB-UPC)

Introducción a la Inteligencia Artificial

Curso 2011/2012

6 / 16

Algoritmo Minimax

Juegos

Introducción

Función: MiniMax (g)
movr:movimiento; max,maxc:entero
max ← −∞
para cada mov ∈ movs_posibles(g)
hacer

cmax ← valor_min(aplicar(mov,g))
si cmax > max entonces

max ← cmax
movr ← mov

fin

fin
retorna movr

g: Representación del estado (posición de
las piezas, profundidad máxima a explorar,
turno actual, ...)
movs_posibles(g): genera la lista de
todos los movimientos posibles en el estado
actual
aplicar(mov,g): Genera el estado que se
obtiene al aplicar el movimiento al estado
actual

Se inicia un recorrido en profundidad del árbol del juego hasta una profundidad
máxima
Dependiendo del nivel se llama a una función que obtiene el valor máximo o
mínimo de la evaluación de los descendientes (valorMax, valorMin)
El recorrido se inicia con la jugada del jugador MAX
Asumimos que la función de evaluación es la misma para los dos jugadores

c b e a (LSI-FIB-UPC)

Introducción a la Inteligencia Artificial

Curso 2011/2012

7 / 16

Algoritmo Minimax

Juegos Minimax

Función: valorMax (g)
vmax:entero
si estado_terminal(g) entonces

sino

retorna valor(g)
vmax ← −∞
para cada mov ∈ movs_posibles(g)
hacer

vmax ← max(vmax,
valorMin(aplicar(mov,g))

fin
retorna vmax

fin

Función: valorMin (g)
vmin:entero
si estado_terminal(g) entonces

sino

retorna value(g)
vmin ← +∞
para cada mov ∈ movs_posibles
hacer

vmin ← min(vmin,
valorMax(aplicar(mov,g))

fin
retorna vmin

fin

estado_terminal(g): Determina si el estado actual es terminal (profundidad máxima,
jugada ganadora)
evaluacion(g): Retorna el valor de la función de evaluación para el estado actual

c b e a (LSI-FIB-UPC)

Introducción a la Inteligencia Artificial

Curso 2011/2012

8 / 16

Ejemplo: 3 en raya (1)

Juegos Minimax

e = número de filas, columnas y diagonales completas disponibles para MAX - número de filas, columnas y
diagonales completas disponibles para MIN
MAX juega con X y desea maximizar e, MIN juega con O y desea minimizar e
Los valores altos significan una buena posición para el que tiene que mover, Podemos controlar las
simetrías, establecemos una profundidad de parada (en el ejemplo 2)

La mejor jugada es en la que MAX coloca su ficha en el centro

c b e a (LSI-FIB-UPC)

Introducción a la Inteligencia Artificial

Curso 2011/2012

9 / 16

XXXXXXXXXXXXXOOOOOXXOOOOOOMax=1Min=1Min=−1Min=−26−4=26−5=14−5=−15−5=06−5=15−5=05−6=−16−6=06−6=05−6=−14−6=−25−4=1OEjemplo: 3 en raya (2)

Juegos Minimax

Suponiendo que MIN coloca su ficha en la posición superior de la columna central

La mejor jugada de MAX es colocar su ficha en la esquina inferior izquierda

c b e a (LSI-FIB-UPC)

Introducción a la Inteligencia Artificial

Curso 2011/2012

10 / 16

Max=14−2=24−2=24−2=2Min=0Min=0Min=1Min=0XOXXXXXXXXXX4−2=25−2=33−2=1XXXXXXOOOOOOOOOOOOOOOOXXXXXXXXXXOOOOOOOOOO4−2=23−2=14−2=22−2=04−2=23−2=1XXOXXXXOEjemplo: 3 en raya (3)

Juegos Minimax

Suponiendo que MIN coloca su ficha en la esquina superior derecha

La mejor jugada de MAX es colocar su ficha en la esquina superior izquierda

c b e a (LSI-FIB-UPC)

Introducción a la Inteligencia Artificial

Curso 2011/2012

11 / 16

XOXOMax=1Min=1Min=−infMin=−infMin=−infMin=−inf2−1=13−1=23−1=22−1=1XOXOXOXOXOXOXOXOXOXXOXOXXOXOXXOXOXXOXOXXOOOOOXXXXMinimax con poda αβ

Juegos Minimax con poda

No tiene sentido seguir explorando
sucesores de c ya que tenemos el mejor
valor posible

En c tendremos e = min(-.05, vg ), por lo
tanto en a tendremos
e = max (.03, min(-.05, vg )) = .03
Podemos pues podar todos los nodos de g ya
que no aportan nada

c b e a (LSI-FIB-UPC)

Introducción a la Inteligencia Artificial

Curso 2011/2012

12 / 16

−infbcamin(−inf, ?,?,?, ...)=−infbcdegf???−.05−.1.03ae=max(−.1,−.05)=−.05Minimax con poda αβ

Juegos Minimax con poda

e(e) = min(-.1,g)
Como la rama b ya me da un .03 cualquier cosa
peor no nos sirve ⇒ No hay que explorar g
e(d) = max(e(e), h) ⇒ Sí hay que explorar h

Al valor mínimo alcanzado hasta el momento para
los nodos max le llamaremos cota α y nos da un
límite inferior de e(n).
Al valor máximo alcanzado por los nodos min le
llamaremos cota β y nos dará un límite superior de
e(n)
En el ejemplo el nodo a (max) tiene de momento
un valor mínimo de .03 proporcionado por su hijo
b
Fijémonos en que el valor que se puede asignar a
un nodo max viene aportado por nodos min y
viceversa

c b e a (LSI-FIB-UPC)

Introducción a la Inteligencia Artificial

Curso 2011/2012

13 / 16

bcde.03afghi−.1Minimax con poda αβ

Juegos Minimax con poda

Si vi > α entonces modificar α
Si vi ≥ β entonces poda β
Retornar α

Si vi < β entonces modificar β
Si vi ≤ α entonces poda α
Retornar β

Las cotas α y β se transmiten de padres a hijos de 1 en 1 y en el orden de
visita de los nodos.
α es la cota inferior de un nodo max - β es la cota superior de un nodo min
=⇒ La efectividad de la poda depende del orden de exploración de los
descendientes

c b e a (LSI-FIB-UPC)

Introducción a la Inteligencia Artificial

Curso 2011/2012

14 / 16

vi[α,β]MAXiv[α,β]MINAlgoritmo Minimax con poda

Juegos Minimax con poda

Función: valorMax (g,α,β)
si estado_terminal(g) entonces

sino

retorna valor(g)
para cada mov ∈ movs_posibles(g) hacer

α ← max(α,valoeMin(aplicar(mov,g) ,α,β))
si α ≥ β entonces

retorna β

fin

fin
retorna α

fin

Función: valorMin (g,α,β)
si estado_terminal(g) entonces

sino

retorna