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
turnos.
Tipos de Juegos



Info Perf
Info Imp
Determinísticos,
Juego de
Ta-te-ti
información perfecta:
Inspección
Otelo=Reversi
 Arriba, Izq
D 
Guerra
Ajedrez--Go
Determinísticos, información imperfecta
marina
Truco mental
 Arriba, Der
(sin naipes) Scrabble sin pozo
Aleatorios, información perfecta:
 Abajo, Izq
 Aleatorios,
imperfecta:
 Abajo, Der
A  información
Dominó
Back gamón
Truco
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
Descargar

Cap 6 (ex 5) - r&n - Inteligencia Artificial