Algoritmos De Juegos

Inteligencia Artificial
Departamento de Lenguajes y Sistemas Informáticos UPC - FIB

IA – Algoritmos de Juegos

Pau A.F. 15 / 06 / 2008

CONTENIDO
1. INTRODUCCIÓN AL DOCUMENTO ........................................................................................3 1.1PROPÓSITO............................................................................................................................3 1.2 VISIÓN GENERAL ....................................................................................................................3 2. PONGÁMONOS EN SITUACIÓN.............................................................................................4 2.1 QUÉ ES UN PROBLEMA...........................................................................................................4 2.2 TIPOS DE JUEGOS ..................................................................................................................4 2.3 ESTRATEGIAS A SEGUIR .........................................................................................................5 3. MÉTODOS UTILIZADOS EN JUEGOS SIN ADVERSARIO ...................................................7 4. MÉTODOS UTILIZADOS ENJUEGOS CON ADVERSARIO .................................................8 4.1 ALGORITMO MINIMAX .............................................................................................................8 4.2 TÉCNICAS PARA MEJORAR MINIMAX .....................................................................................10

4.2.1 PodaAlfa-Beta........................................................................................... 10 4.2.2 Poda de Inutilidades .................................................................................. 12 4.2.3 Espera del Reposo .................................................................................... 13 4.2.4 Búsqueda Secundaria................................................................................ 13 4.2.5 Uso deMovimientos de Libro..................................................................... 14 4.2.6 Búsqueda Sesgada.................................................................................... 14 4.2.7 MiniMax Dependiente del Adversario......................................................... 14 4.2.8 Técnica de Bajada Progresiva ................................................................... 164.2.9 Continuación Heurística ............................................................................. 16 4.2.10 Movimiento Nulo ...................................................................................... 17 4.2.11 Aspiration search ..................................................................................... 17 4.2.12 Algoritmo NegaMax................................................................................. 18 4.2.13 Algoritmo NegaScout ............................................................................... 18
4.3 ALGORITMO SSS* ................................................................................................................19 4.4 ALGORITMO SCOUT..............................................................................................................22 4.5 ALGORITMO MTD(F).............................................................................................................24 5. ÁREAS RELACIONADAS......................................................................................................26 6. APLICACIONES.....................................................................................................................27 7. BIBLIOGRAFÍA Y ENLACES.................................................................................................30

2

1. Introducción al Documento
1.1 Propósito
Este documento proporciona una visión divulgativa sobre el área de los algoritmos de juegos de la Inteligencia Artificial. Su propósito es servir como punto de partida a quien desee introducirse en...