Inteligencia Artificial
Algoritmo Poda
Alpha-Beta
Información Imperfecta.
JUEGO DE INSPECCION - Es determinístico.
GUERRA MARINA – No vemos el tablero del
adversario. No hay dados o naipes. Es
determinístico.
Decisiones Imperfectas.
- 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
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
- en mejor caso, alfa-beta permite búsqueda dos
veces más profunda
- ordenamiento de los operadores, resultante del
conocimiento o experiencia
Poda alfa-beta.
UNICAMENTE IMPORTA EL ORDEN Y NO LOS
VALORES EXACTOS.
LA PODA NO AFECTA AL RESULTADO FINAL.
Poda alfa-beta
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).
.
Poda alfa-beta.
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
Alfa es el nombre del mejor
valor m, para MAX,
encontrado hasta ahora en
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
Algoritmo de Búsqueda Alfa-Beta.
Corresponde a la combinación de tres
aportes:
ejecutar MINIMAX +
mantener recordados alfa y beta +
podar
Algoritmo de Búsqueda Alfa-Beta.
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.
Clasificación de Juegos con adversario y
Tipos de Juegos
turnos.
Info Perf Info Imp
Determinísticos,
Ta-te-ti Juego de
información perfecta:
Otelo=Reversi Inspección
Arriba, Izq D
Ajedrez--Go
Determinísticos, información imperfecta
Guerra
Arriba, Der Truco mental marina
Aleatorios, información perfecta: (sin naipes) Scrabble sin pozo
Abajo, Izq
Aleatorios, A información Dominó
imperfecta: Back gamón Truco
Abajo, Der Chaquete Bridge
Monopolio 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.:
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 valor Minimax del algoritmo.
Diferencias absolutas en la función de evaluación pueden
afectar cual movimiento elegir.
Posibles podas si los valores están acotados.
Conclusiones
Mejoras pretendidas en la forma de encarar los juegos:
usar distribuciones de probabilidad sobre valores posibles en lugar
de valores crudos para incrementar la discriminación del significado
de diferencias en valores
no fijarse tanto si es legal una expansión de nodos, sino si muestra
utilidad.
combinar dos proyectos: el de la búsqueda de victoria y el de
satisfacer una meta “secundaria”, p.ej., capturar la reina en ajedrez.
Equivale a tener una estrategia.
¿Extensión del sistema Gala por parte de los bots jugadores? – 1)
mejores los juegos heurísticamente adaptados a un ambiente
concreto. 2) competencia de la máquina consigo misma a la manera
del TD-gammon.
Conclusiones.
El diseño de programas de la IA se concreta en los juegos
Durante el diseño de un juego surgen temas muy
importantes-Samuel (1959) mide en el juego de damas la
DIFERENCIA entre el resultado del cálculo de EVAL
directamente de una posición y el resultado PREDICHO de
una exploración hacia niveles más profundos.
Esa DIFERENCIA implica la posibilidad de un aprendizaje
por refuerzo de EVAL, mejorandolo y abriendo campos a
la curiosidad con cada nuevo aprendizaje.
Conclusiones.
Cada nueva táctica creada proporciona información sobre
buen o mal éxito de las reglas tácticas de búsqueda, cada
acción del oponente provee información sobre buen o mal
éxito de las inferencias probabilísticas.
BIBLIOGRAFIA
http://www.angelfire/oh4/ohcop/ClaseCap7nu.ppt
http://www.angelfire/oh4/ohcop/ClaseCap7nu.ppt
http://www.angelfire/oh4/ohcop/ClaseCap7nu.ppt
http://www.angelfire/oh4/ohcop/ayuda55.html
http://www.angelfire/oh4/ohcop/ayuda55.html
http://www.angelfire/oh4/ohcop/ayuda55.html
