Búsqueda Adversaria y Juego

La búsqueda adversaria es el estudio de la toma de decisiones en entornos competitivos, donde un agente debe elegir movimientos en un árbol de juego contra un oponente que intenta lograr el resultado opuesto.

Definition

La búsqueda adversaria calcula un movimiento para un jugador explorando un árbol de juego en el que los jugadores alternan turnos, utilizando el principio minimax (cada jugador optimiza asumiendo que el oponente juega de manera óptima) junto con la poda y la evaluación heurística para hacer frente a árboles grandes.

Scope

Este tema cubre la búsqueda en juegos de dos jugadores, de suma cero y de información perfecta: la regla de decisión minimax, la poda alfa-beta que permite a minimax omitir ramas demostrablemente irrelevantes, las funciones de evaluación y la búsqueda con profundidad limitada para juegos demasiado grandes para resolverlos exactamente, y la búsqueda en árbol Monte Carlo para juegos con factores de ramificación muy grandes. Aborda cómo se modelan los árboles de juego y cómo los límites computacionales fuerzan los cortes heurísticos. No cubre el análisis general del equilibrio de la teoría de juegos de los incentivos multiagente, que se trata en sistemas multiagente.

Core questions

• ¿Cómo determina la regla minimax un movimiento óptimo contra un oponente óptimo?
• ¿Cómo elimina la poda alfa-beta las ramas sin afectar el valor minimax?
• ¿Cómo se utilizan las funciones de evaluación para cortar la búsqueda a una profundidad fija en juegos grandes?
• ¿Cuándo es preferible la búsqueda en árbol Monte Carlo a minimax con profundidad limitada?

Key concepts

• árbol de juego
• valor minimax
• poda alfa-beta
• función de evaluación (heurística)
• búsqueda con profundidad limitada y el efecto horizonte
• juegos de suma cero con información perfecta
• búsqueda en árbol Monte Carlo
• ordenación de movimientos

Key theories

Regla de decisión Minimax

En un juego de suma cero de dos jugadores, cada jugador elige el movimiento que maximiza su propio resultado mínimo garantizado; la propagación de estos valores máximos/mínimos hacia arriba en el árbol de juego produce el movimiento óptimo en la raíz.

Poda alfa-beta

Al rastrear los mejores valores ya garantizados a los jugadores maximizadores y minimizadores, la búsqueda alfa-beta demuestra que ciertos subárboles no pueden afectar la decisión final y los omite, devolviendo el valor minimax exacto mientras que, en el mejor de los casos, cuadra aproximadamente la profundidad alcanzable en un tiempo dado.

Búsqueda en árbol Monte Carlo

Cuando los factores de ramificación son demasiado grandes para una búsqueda exhaustiva, la búsqueda en árbol Monte Carlo construye un árbol asimétrico guiado por tiradas aleatorias y una regla de selección que equilibra la exploración y la explotación, un método que transformó el juego por computadora en juegos como Go.

Clinical relevance

La búsqueda adversaria produjo sistemas de IA históricos, desde motores de ajedrez que utilizan la búsqueda alfa-beta hasta programas de Go basados en la búsqueda en árbol Monte Carlo, y las mismas técnicas informan la negociación automatizada, los juegos de seguridad y cualquier entorno modelado como una contienda entre partes optimizadoras.

History

El artículo de Shannon de 1950 enmarcó el ajedrez por computadora como una búsqueda minimax con una función de evaluación, y el teorema minimax de von Neumann proporcionó la base teórica de juegos. La poda alfa-beta se desarrolló durante las décadas de 1950 y 1960 y fue analizada rigurosamente por Knuth y Moore (1975). La búsqueda en árbol Monte Carlo, formalizada en la década de 2000, impulsó el siguiente salto en la fuerza de juego, especialmente en Go.

Key figures

• Claude E. Shannon
• John von Neumann
• Arthur Samuel
• Donald E. Knuth
• Ronald W. Moore

Seminal works

• shannon1950
• knuth1975
• browne2012

Frequently asked questions

¿La poda alfa-beta cambia el movimiento que elegiría minimax?

No. La poda alfa-beta devuelve exactamente el mismo valor y movimiento que el minimax completo; solo evita explorar ramas que demostrablemente no pueden influir en el resultado. Su beneficio es la velocidad, y con una buena ordenación de movimientos puede buscar aproximadamente el doble de profundidad en el mismo tiempo.

¿Por qué usar la búsqueda en árbol Monte Carlo en lugar de minimax en juegos como Go?

Go tiene un factor de ramificación enorme y carece de una función de evaluación simple y precisa, por lo que el minimax de profundidad fija es ineficaz. La búsqueda en árbol Monte Carlo, en cambio, estima la calidad del movimiento a través de muchas jugadas aleatorias y hace crecer el árbol selectivamente hacia líneas prometedoras, lo que escala mucho mejor en este tipo de juegos.