PDF de programación - Algoritmo Poda Alpha-Beta - Inteligencia artificial

PODA ALPHA-BETA EQUIPO 2. INTELIGENCIA ARTIFICIAL.


Algoritmo Poda Alpha-Beta


Información imperfecta.


i JUEGO DE INSPECCION - Me imagino aquí a mi exalumno y ahora
colega, el Dr. Heinecken, actualmente Inspector de Instalaciones
Nucleares de la ONU.

i Los países con instalaciones que producen plutonio son inspeccionados
un número fijo de veces por año. Si el inspector adelanta sus visitas para
verificar que no han surgido novedades, el inspeccionado tiene tiempo,
luego de las visitas tempranas, para entrar en infracción (si eso quisiera
hacer). La fecha de las visitas es para el infractor un tema importante y
tiene que resultar para él un caso de información imperfecta. Por simetría,
también al inspector le gustaría saber en qué momento aparecen pistas
sospechosas, para frenar con su visita la tentación de su inspeccionado
de transformarse en infractor. Es determinístico.

i GUERRA MARINA – No vemos el tablero del adversario. No hay dados o

naipes. Es determinístico.



Decisiones imperfectas.


Hay juegos aleatorios y con información imperfecta, como el póquer, en
que se puede demostrar que hasta los mejores jugadores humanos se
equivocan. Para una máquina
la situación es
tremendamente inadaptada para la estructura de problemas que ella puede
encarar. Pero puede ir aprendiendo si se ponen dos máquinas a competir entre
ellas. Con ese propósito se empieza simplificando el póquer a otros juegos
similares pero más relajados en requisitos. Por ejemplo en lugar de usar un

jugadora de póquer



INSTITUTO TECNOLOGICO DE NUEVO LAREDO.

1

PODA ALPHA-BETA EQUIPO 2. INTELIGENCIA ARTIFICIAL.


mazo de 52 barajas, se usa uno de tres barajas, un J, una Q y un K – y cada
jugador recibe 1 baraja en lugar de las clásicas 3.


Ya en ese caso aparece la posibilidad de “bluff” (engaño) si una de las
dos máquinas apuesta a pesar de tener la peor de las barajas, un J. Pese a que
no hay regla explícita que lo autoriza, provista a la máquina, ella comete con alta
probabilidad el “bluff” de apostar si tiene un juego muy flojo. Para la otra
máquina el caso le da ventajas si tiene un K y la pone en duda si tiene un Q,
debiendo explorar el árbol para tomar la mejor decisión, cosa que hace. El árbol
resulta distinto que en el Juego de Inspección o en el de Guerra Marina.


Suponer que el espacio de problema es demasiado grande como para

llegar a los nodos terminales


Interrumpir la búsqueda en algún nivel y aplicar evaluaciones heurísticas

a las hojas


Polinomios

lineales ponderados -

forma habitual de adaptarse a

evaluaciones heurísticas


Pesos o ponderaciones ¿por aprendizaje?

Reglas sobre cuándo interrumpir la búsqueda

Profundidad fija



Profundización

iterativa hasta cuando el

tiempo permitido queda

satisfecho


Expandir con búsqueda secundaria nodos no quietos - teoría de la

extensión singular



INSTITUTO TECNOLOGICO DE NUEVO LAREDO.

2

PODA ALPHA-BETA EQUIPO 2. INTELIGENCIA ARTIFICIAL.



Irresoluble problema del horizonte (peón coronado)

Árbol de juego con turnos para los dos adversarios - aplicación de la

heurística alfa-beta.



Poda alfa-beta.



Omitir la expansión de nodos que por sus valores no pueden ser los



mejores (peores).
Valor del nodo max (alfa) menor que el más alto hasta este momento -
omitir nodo.
Valor del nodo min (beta) mayor que el nodo más bajo hasta el momento
- omitir nodo.

Alfa-beta permite búsqueda dos veces más profunda.
Ordenamiento de

los operadores,

resultante del conocimiento o

experiencia.

Únicamente importa el orden y no los valores exactos.
La poda no afecta al resultado final.



INSTITUTO TECNOLOGICO DE NUEVO LAREDO.

3

PODA ALPHA-BETA EQUIPO 2. INTELIGENCIA ARTIFICIAL.


Alfa-beta es una mejora del algoritmo minimax que evita revisar porciones
dominadas del árbol, que no pueden proveer información útil sobre la
jugada siguiente.

Alfa-beta es un algoritmo bpp, rama y cota, que avanza por el árbol en un
orden ya fijado (p.ej., de izquierda a derecha) y va usando la información
de la valuación de los nodos hoja para podar ramas dominadas que no
sirven para cambiar el valor minimax del nodo inicio (la jugada inminente).



Estructuras de datos.


Dos variables deben recordarse a lo largo de la búsqueda. alfa, que es el

límite inferior encontrado hasta ese momento, y Beta, que es el límite superior.


En los niveles maximizantes donde max debe optar, solo beta se usa para

podar la búsqueda y ;

En los niveles minimizantes donde min debe optar, solo alfa se usa para

podar.

Alfa-beta es el algoritmo más usado para buscar en árboles de juegos

determinísticos.



Origen del nombre alfa


su ruta de búsqueda en un nivel de min.
*si n es peor que alfa, max lo evitará ⇒ podar esa rama punteada
*m y n son nodos de min

Alfa es el nombre del mejor valor m, para max, encontrado hasta ahora en



INSTITUTO TECNOLOGICO DE NUEVO LAREDO.

4

PODA ALPHA-BETA EQUIPO 2. INTELIGENCIA ARTIFICIAL.



Algoritmo de búsqueda alfa-beta.


Corresponde a la combinación de tres aportes:

Ejecutar minimax +
Mantener recordados alfa y beta +
Podar



INSTITUTO TECNOLOGICO DE NUEVO LAREDO.



5

Función del
valor Mínimo.

v

Evaluar (Estado).

Si se va examinar un

corte (Estado).

Entradas:
-Estado, lugar en la estructura del juego.
-Juego, descripción del juego.
-alpha, el mejor puntaje para Máx. a lo largo
del juego.
-beta, el mejor puntaje para Máx. a lo largo
del juego.

PODA ALPHA-BETA EQUIPO 2. INTELIGENCIA ARTIFICIAL.



Máx. que se esta
estudiando (con las
reglas de Juego).

Beta es igual a Mín. de
beta, con el valor del

Para cada sucesor

del Estado.

Si beta es mayor

que alpha.

F

Retornar beta

v

Devolver alpha

F



INSTITUTO TECNOLOGICO DE NUEVO LAREDO.

6

Función del
valor Máximo.

Si se va examinar un

corte (Estado).

Entradas:
-Estado, lugar en la estructura del juego.
-Juego, descripción del juego.
-alpha, el mejor puntaje para Máx. a lo largo
del juego.
-beta, el mejor puntaje para Máx. a lo largo
del juego.

PODA ALPHA-BETA EQUIPO 2. INTELIGENCIA ARTIFICIAL.



Alpha es igual a Máx.
de alpha, con el valor
del Mín. que se esta
estudiando (con las
reglas de Juego).

Si alpha es

mayor que beta.

F

Para cada sucesor

del Estado.

v

Devolver beta

v

Evaluar (Estado).



INSTITUTO TECNOLOGICO DE NUEVO LAREDO.

F

Retornar alpha

7

PODA ALPHA-BETA EQUIPO 2. INTELIGENCIA ARTIFICIAL.

Comportamiento de los nuevos algoritmos de búsqueda en
juegos.


Aproximadamente, alfa-beta ha de buscar solamente b3/4 de los b
movimientos posibles desde una dada posición de juego. Alternativamente, esto
significa que la profundidad de búsqueda se puede incrementar por un factor =
log b / log b ~= 4/3 por encima de una búsqueda exhaustiva minimax . B es aquí
el factor de ramificación efectivo. Si los sucesores se ordenan a la perfección
(definido como que al usar alfa-beta la búsqueda es mínima), alfa-beta examina
2bd/2 - 1 posiciones de juego. Así tenemos


B = b ............en búsquedas exhaustivas,
B ~= b3/4 .....en alfa-beta ordenando al azar; y
B = b1/2 .......en alfa-beta ordenando perfectamente.



Tipos de juegos


Determinísticos, información perfecta:

Arriba, izq d ⇒ información imperfecta
Arriba, der


Aleatorios, información perfecta:

Abajo, izq a ⇒ información imperfecta:
Abajo, der



INSTITUTO TECNOLOGICO DE NUEVO LAREDO.

8

PODA ALPHA-BETA EQUIPO 2. INTELIGENCIA ARTIFICIAL.


Info Perf
Ta-te-ti

Otelo=Reversi
Ajedrez--Go
Truco mental
(sin naipes)

Back gamón
Chaquete
Monopolio

Info Imp
Juego de
Inspección
Guerra
marina

Scrabble sin pozo

Dominó
Truco
Bridge
Póquer

Scrabble con pozo



Juegos con una componente aleatoria (moneda, dados, etc.).



Nodos aleatorios (además de los nodos min/max) el árbol se incrementa
desmesuradamente porque debajo de la fila max aparece una nueva fila con las
posibilidades aportadas por los dados, debajo de la cual aparece una fila min y
de nuevo la fila de posibles combinaciones de dados. Es una tarea de búsqueda
muy compleja, p. Ej.:



INSTITUTO TECNOLOGICO DE NUEVO LAREDO.

9

PODA ALPHA-BETA EQUIPO 2. INTELIGENCIA ARTIFICIAL.


Un nodo para cada posibilidad (por ejemplo, puntos del dado) con

su probabilidad asociada.

Calcular el valor esperado (idem max e idem min) para cada
posibilidad (p.ej., de un dado) - con su probabilidad asociada - y
reemplazar el v