Please enable JavaScript.
Coggle requires JavaScript to display documents.
Búsqueda entre adversarios - Coggle Diagram
Búsqueda entre adversarios
Juegos
Entornos competitivos en los que los objetivos del agente están en conflicto, dan ocasión a problemas de
búsqueda entre adversarios
.
Juegos de suma cero
Un jugador gana (+1) y otro pierde (-1)
Requieren de la capacidad de tomar alguna decisión cuando es infactible calcular la decisión óptima.
Poda
Permite ignorar partes del árbol de búsqueda que no marcan una diferencia para obtener una opción final.
Decisiones óptimas en juegos
Estado inicial
Posición del tablero e identifica al jugador que mueve
Función sucesor
Lista de pares (movimiento, estado), indicando un movimiento legal y el estado que resulta.
Test terminal
Determina cuándo termina el juego
Función utilidad
(Función objetivo). Da un valor numérico a los estados terminales.
Algoritmo minimax
Calcula la decisión minimax del estado actual.
Realiza una exploración en profundidad completa del árbol de juegos.
Estrategias óptimas
Valor minimax: Utilidad para MAX de estar en el estado correspondiente, asumiendo que ambos jugadores juegan óptimamente.
Decisiones óptimas en juegos multijugador
En este tipo de juego hay más posibilidades: formar y romper alianzas.
Poda alfa-beta
Si m es mejor que n para el jugador, nunca se irá a n en el juego
Obtiene su nombre de:
ALFA
: Valor de la mejor opción (+ALTO) a lo largo del camino para MAX
BETA
: valor de la mejor opción (+BAJO) a lo largo del camino para MIN
Tabla de transposiciones
: tabla con permutaciones de secuencia que terminan en la misma posición.
Decisiones en tiempo real imperfectas
En un trabajo de 1950 se propuso:
Los programas deberían cortar la búsqueda antes y aplicar una función de evaluación heurística a los estados, convirtiendo los nodos no terminales en hojas terminales.
Alternar minimax o alfabeta: sustituyendo la función de utilidad por una heurística EVAL que da una estimación de la utilidad de la posición y sustituir el test-terminal por un test-límite que decide cuándo aplicar EVAL.
Debido a que la búsqueda debe cortarse en estados no terminales, el algoritmo es incierto sobre los resultados finales de los estados.
Función ponderada lineal
: función donde se suman los valores de las distintas características en cierta posición del juego.
Juegos que incluyen un elemento de posibilidad
Existen juegos en los que hay elementos aleatorios. En estos, su árbol de juego debe incluir
nodos de posibilidad
.
Juegos de cartas
Cuando la información falla, hay que tomar en cuenta la información con la que se contará en cada punto del juego
El algoritmo no busca el espacio de estados del mundo, sino el espacio de estados de creencia (creencia de quién tiene qué cartas y con qué probabilidad)
Programas de juegos
Damas
: El programa Chinook se convirtió en el campeón mundial
Otelo
: El programa Logistello derrotó al campeón mundial.
Ajedrez
: El programa FRITZ empató contra el campeón mundial, en una computadora ordinaria.
Backgammon
: El programa TD-Gammon se sitúa entre los primeros tres jugadores del mundo
Go
: Los programas más fuertes (Goemate y Go4++) se encuentran aún en nivel aficionado, debido a la gran ramificación del juego
Bridge
: El programa GIB ganó el campeonato
