Algoritmos De Juegos

3

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. 4

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 5

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

de los jugadores, que determinarán las jugadas que puede hacer un agente

desde el estado actual.

6

Además deberemos definir la aproximación heurística, es decir, la

función que nos indique lo cerca que estamos de una juagada ganadora. En

esta función intervendrá información del dominio del juego, y deberá tener

un coste computacional lo más bajo posible.

Una vez definido el universo del juego, nos tocará aplicar el algoritmo más

adecuado.

7

3. Métodos Utilizados en Juegos Sin Adversario

Para algoritmos de juegos unipersonales (por ejemplo los puzzles o el

solitario) suelen utilizarse los algoritmos más comunes de búsqueda

heurística, aunque realmente las soluciones a un juego unipersonal

pueden encontrarse con cualquier algoritmo de fuerza bruta sin heurística

alguna, siempre y cuando se disponga del tiempo y memoria necesarios.

De entre los algoritmos de búsqueda heurística, suele utilizarse o bien el

algoritmo A*, que se describe en esta sección, o bien el algoritmo IDA*

(según los recursos del computador).

El algoritmo A* (Hart, 1968) implementa una búsqueda primero el

mejor (best-first). En otras palabras, se basa en intentar encontrar todos

los movimientos necesarios para llegar del estado inicial al estado final,

usando preferiblemente aquellos movimientos que sean más favorables.

Así, entre otras cosas, se puede lograr minimizar los pasos de la solución, o

el tiempo de cálculo.

Para conocer qué movimiento es mejor se utiliza una función de evaluación

estática formada descompuesta como:

f = g + h

Donde “f” será el valor numérico del movimiento estudiado, la función “g”

es una función del coste de llegar del estado inicial al estado actual, y la

función “h” es una estimación del coste de llegar desde el estado actual al

estado final o objetivo. Lógicamente, “h” es una estimación porque no

conocemos a priori el camino exacto hacia la solución.

El algoritmo A*, simplificado y con sintaxis imprecisa, viene a ser el

siguiente:

Algoritmo A*

Estados_pendientes.insertar(Estado_inicial);

Actual = Estados_pendientes.primero();

...