Algoritmos De Juegos
Enviado por miltonreinaldo • 5 de Octubre de 2012 • 4.561 Palabras (19 Páginas) • 552 Visitas
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
...