PDF de programación - IA - Algoritmos de Juegos

Departamento de Lenguajes y Sistemas Informáticos



Inteligencia Artificial

UPC - FIB



IA – Algoritmos de Juegos



Pau A.F.
15 / 06 / 2008



CONTENIDO

1. INTRODUCCIÓN AL DOCUMENTO........................................................................................3
1.1 PROPÓ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 EN JUEGOS CON ADVERSARIO .................................................8
4.1 ALGORITMO MINIMAX.............................................................................................................8
4.2 TÉCNICAS PARA MEJORAR MINIMAX .....................................................................................10
4.2.1 Poda Alfa-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 de Movimientos 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 ................................................................... 16
4.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
el área de los algoritmos de juegos con adversario y conocer sus elementos
y características principales.


1.2 Visión General

El resto del documento contiene una definición de los algoritmos de juegos
con adversario, cómo suelen plantearse estos problemas, y acto seguido
toda una serie de algoritmos y técnicas utilizadas para mejorarlos
(centrando nuestro peso en MiniMax).

Finalmente el lector puede disponer de unos cuantos ejemplos de áreas
relacionadas donde estos algoritmos pueden (o son) utilizados, y sus
aplicaciones más immediatas.

El último punto del documento, como bien indica su nombre, es la lista de
enlaces web utilizados como bibliografía o que puedan resultar de interés.



3

2. Pongámonos en Situación


2.1 Qué es un Problema

La primera necesidad es definir el término problema. Sabemos lo que es un
problema matemático, un problema económico, o el término problema en
su mayor definición. Pero, ¿conocemos la definición de “problema” enfocada
al mundo de la inteligencia artificial?

Un problema, en nuestro contexto, será la abstracción de una serie de
elementos tales como: un objetivo, meta, o estado final a cumplir; un punto
de inicio donde empezaremos a enfocar el problema; y una serie de
movimientos que nos permitirán como mínimo aproximarnos del estado
inicial al final. Y en el mejor de los casos, nos permitirán salir airosos con la
mejor solución del problema.

Evidentemente, existen muchos tipos diferentes de problemas, pero todos
ellos
tienen elementos comunes que nos permiten clasificarlos,
estructuralos, y afrontarlos automáticamente de un u otro modo según su
tipo. Así pues, este documento se centrará en un único tipo de problema:
los juegos.

Los problemas de juegos son aquellos en que varios agentes –o
adversarios– compiten por lograr un mismo objetivo. Estos problemas se
resuelven mediante los denominados “algoritmos de juegos”, los cuales
trataremos en gran profundidad más adelante.

No es difícil ver que dentro del conjunto de problemas con adversario están
todos aquellos juegos de mesa para dos que seguramente todos hemos
jugado (tres en raya, dominó, ajedrez, etc.). Pero no sólo esos juegos
resolverán nuestros algoritmos, sinó que además podremos afrontas
problemas de cualquier ámbito donde varios individuos compitan, ya sean
juegos de cartas como el póker o el black jack, o incluso problemas del
mundo real.

2.2 Tipos de Juegos

Los juegos, que ya de por si son una subcategoría de problemas, también
pueden subclasificarse.

Incluso para los ordenadores no es lo mismo si intentas decidir la mejor
jugada en el tres en raya que si pretendes decidir si jugando a cartas
apuestas o te plantas. Por eso los juegos también deberán clasificarse
según ciertas propiedades presentes en todos ellos, facilitando así la
decisión de qué algoritmo utilizar para vencer.

La primera de las propiedades a tener en cuenta será el número de
jugadores o agentes involucrados, información de gran vitalidad a la hora



4

de diseñar el algoritmo. Un juego puede ser sin adversario (por ejemplo un
8-puzzle), con 1 adversario (por ejemplo el 3 en raya), o con N adversarios.

La siguiente propiedad a conocer es el orden de los movimientos. Saber
si por ejemplo los jugadores mueven alternativamente o por azar también
es muy importante.

Una vez situados los jugadores y sus turnos, hay que saber qué
conocimiento tienen éstos. En los juegos los jugadores pueden tener o bien
conocimiento perfecto, donde no afecta el azar y todos saben en todo
momento lo mismo, o bien conocimiento imperfecto, donde el azar sí
puede participar y además hay ocultación de información entre jugadores.

Al hecho de que el azar aparezca o no aparezca en alguna de las
propiedades anteriores se le conoce como determinismo.

También podemos encontrarnos juegos donde un movimiento que te
beneficia siempre perjudica al mismo nivel al adversario (equilibrio Nash),
o juegos donde ésto no ocurre.

Según sus características encontraremos juegos simétricos y asimétricos,
de suma cero y de suma no cero, cooperativos, simultáneos y secuenciales,
de información perfecta, de longitud infinita, o juegos bayesianos entre
otros.


2.3 Estrategias a Seguir

La idea básica cuando buscas vencer computacionalmente un adversario es
intentar predecir todos los posibles movimientos, todas las posibles
situaciones desde tu turno hasta el final de la partida, y elegir la que
prometa mejores resultados. Esta idea se la conoce como la de “generar
todo el árbol de búsqueda”. Pero esta estrategia tan bruta la gran mayoría
de veces será algo imposible e inaceptable, pues una partida no puede
durar siglos.

Lo que realmente haremos será buscar una aproximación de las mejores
jugadas, guiándonos mediante heurísticos, y prediciendo únicamente las
situaciones con mejor pinta (pues por ejemplo no sirve de nada saber las
situaciones que podrían darse después de hacer un paso en falso).

Para poder realizar los cálculos computacionalmente, hará falta una
abstracción codificable del juego. Entender e implementar realmente el
problema.

Necesitaremos una representación del estado (válida para cualquier
estadp), otra del estado inicial (desde dónde se empieza a jugar y quién
inicia el juego), otra del estado ganador (ya sea por estructura o por
propiedades), y finalmente definir los operadores de movimiento válidos