Download tamaño: 60737B

Tema 4
INTRODUCCIÓN A JUEGOS
(BÚSQUEDA CON ADVERSARIOS)
BÚSQUEDA CON ADVERSARIOS
•
•
•
•
•
BIBLIOGRAFÍA:
-Nilsson, cap. 12
-Russell-Norvig, cap.6
-Poole-Mackworth, sec. 10.3
-Fdez. Galán-Glez.Boticario-Mira Mira,
Problemas resueltos de I.A. , sec. 2.2.4
INTRODUCCIÓN
Se trata de modelizar juegos, situaciones en las
que hay varios contrincantes:
- oponentes entre sí
- interactúan, reaccionando frente a las
acciones de los demás
- usando diversos grados de información,
- persiguen premios o fines
INTRODUCCIÓN
EJEMPLOS:
- Nim
- Ajedrez, damas
- Juegos de cartas, Poker
- Inversión en bolsa
- Tenis
Juego de Nim
Versión 1ª:
Dados dos jugadores, y una cantidad de objetos
idénticos, separar en cantidades diferentes una
dada, en jugadas alternativas, perdiendo el que
no puede seguir.
Versión 2ª:
Dados dos jugadores, y una cantidad de objetos
idénticos, quitar de ella 1, 2 ó 3 objetos, en
jugadas alternativas, perdiendo el que retire el
último.
CARACTERÍSTICAS DE LOS JUEGOS
•
•
•
•
•
•
Número de jugadores
Información completa o incompleta
Intervención o no del azar
Existencia o no de coaliciones
Turnos de juego
Cantidad de jugadas (decisiones) posibles en
cada momento para cada jugador
Tipo de juegos aquí considerados
• De dos jugadores
• Juegan alternativamente
• Con información completa, sin azar
• Número finito de opciones
• Competencia completa (suma nula)
Ejemplos: Nim, damas, ajedrez, go, tres en raya
Ejemplos que no cumplen: tenis, poker, bolsa
JUEGOS COMO BÚSQUEDA
•
•
•
•
•
Jugadores: 1º (Max), 2º (Min)
Estados: situaciones del juego
Inicial: comienzo
Final: Gana uno de los jugadores, o empatan
Jugadas o movimientos: cambios hechos por cada
jugador en su turno
• Premio: función numérica que establece la
puntuación del jugador 1º en las jugadas finales
ÁRBOLES DEL JUEGO
• Se representan en un árbol todas las opciones
disponibles en su turno al jugador
correspondiente. Nodo=turno, arcos=jugadas
posibles en el turno
• Cada turno de jugador corresponde a un nivel
de profundidad del árbol, los niveles pares al
1º y los impares al 2º
ALGORITMO MINIMAX
Teniendo en cada momento información completa,
en cada turno:
- Contemplar para cada sucesión de jugadas
posible la rama correspondiente hasta el final
- Propagar de abajo a arriba la puntuación del valor
desde las jugadas finales (hojas)hacia las
anteriores
- Etiquetar cada nodo con el valor del movimiento
que dé mejor puntuación al jugador (la máxima
para MAX, lo contrario para MIN) en él
ALGORITMO MINIMAX
Propagación de valores:
- Si el nodo es hoja (final), devolver su puntuación
- Si el nodo es impar (jugador MAX), asignarle el
máximo de las puntuaciones de los sucesores
- -Si el nodo es par (jugador MIN), asignarle el
mínimo de las puntuaciones de los sucesores
La estrategia conveniente para cada jugador en
cada momento queda determinada: seguir la
opción con la puntuación seleccionada para el
nodo
ALGORITMO MINIMAX
Observaciones:
- El Minimax requiere desarrollar por completo el árbol del juego.
- En la mayoría de juegos reales este árbol es enorme, las complejidades espacial y
temporal impiden aplicarlo: en el ajedrez, estadísticamente hay por termino medio
100 jugadas con más de 30 opciones(árbol con más de 30100 nodos)
Opciones:
- Desarrollar el árbol sólo hasta un determinado nivel de profundidad “horizonte” y
evaluar los nodos de dicho horizonte mediante funciones heurísticas que evalúen
las jugadas
-
Realizar la poda de subramas innecesarias para evaluar los nodos (Minimax con
poda α-β)
PODA α-β
ALGORITMO α-β
Entrada: Nodo N, valores α, β
Salida: V(N, α , β) (valor α-β de N)
- Si N es hoja, devolver V(N, α , β)= valor de N
- Si N es nodo MAX no hoja para cada hijo n, hacer α = max (m, V(n, α , β))
Si α >= β, devolver β como V(N, α , β)
Si usados todos hijos, devolver α como V(N, α, β)
-Si N es nodo MIN, no hoja para cada hijo n, hacer β = min (m, V(n, α , β))
Si α >= β, devolver α como V(N, α , β)
Si usados todos hijos, devolver β como V(N, α, β)
JUEGOS NO BINARIOS
-Las valoraciones finales vendrían dadas por
vectores con las puntuaciones de cada jugador
-El árbol se desarrollaría con las posibles
alternativas de cada jugador, en los turnos
correspondientes
-La propagación de abajo a arriba se
desarrollaría transmitiendo el vector que
maximiza la puntuación del jugador en turno
JUEGOS BINARIOS CON AZAR
-El árbol contendría tres clases de niveles,
correspondientes a los dos jugadores y a el
mecanismo de azar
-La propagación de valores desde las hojas hacia
arriba se haría asignando como valor, en los
niveles de azar, la esperanza de ganancia (suma
de productos de probabilidades por utilidades de
sus hojas) y , en los niveles de jugador Max o Min,
lo mismo que en el Minimax ordinario