Problemática de los juegos en la inteligencia artificial

2. Formalización
   del problema
3. 
   Procedimiento Minimal
4. 
   Procedimiento Alfa – Beta
5. 
   El juego de ajedrez
6. 
   Bibliografía

Problemática de los
juegos

La clase de
juegos
considerada es la que incluye los juegos donde intervienen dos
jugadores con información completa. Hay dos jugadores
adversarios quienes alternan sus movimientos, cada uno ve las
fallas de su oponente y sus propios éxitos. En cada turno
las reglas del juego definen
los movimientos legales y que efecto tendrá cada movimiento
posible. Los juegos comienzan a partir de un estado inicial
especificado y termina en una posición que puede ser
declarada ganadora, perdedora o tabla.

La problemática de los juegos siempre ha atraído
el interés
de los investigadores en IA. Entre los resultados más
importantes están los siguientes. En 1951 Alan Turing
escribió el primer programa de
computadora
capaz de jugar un juego completo de ajedrez; este
programa nunca corrió realmente sobre una computadora. Al
principio de los sesenta Arthur Samuel tuvo éxito
al construir el primer programa importante y operacional para
jugar; este programa jugaba a las damas y podía aprender
de sus errores. Se han desarrollado diversas máquinas
jugadoras de ajedrez, entre ellas la Deep Thought 2 que a
mediados de esta década alcanzó un ELO de 2600
(Kasparov alcanzó 2805). El 10/02/96 el programa Deep Blue
derrotó a G. Kasparov, este programa valora 50 000
millones de posiciones en tres minutos.

Entre las razones que explican este interés
están:

• ? Proporcionan una tarea estructurada en la que es
  muy fácil medir éxito o fracaso.

• ? Las estrategias aplicables son útiles para
  resolver problemas complejos en diversos dominios de la vida
  real.

• ? Resulta conveniente hacer buenos programas de
  juegos que sirvan para medir la fortaleza de humanos.

Desde la perspectiva de un problema de búsqueda se
tiene un árbol de juego que es una representación
explícita de todos los posibles caminos de una partida. El
nodo raíz es la posición inicial del juego, sus
sucesores son las posiciones que el primer jugador puede
alcanzar, los sucesores de estos nodos son las posiciones
resultantes de la réplica del segundo jugador, y
así sucesivamente. Los nodos terminales u hojas
representan posiciones ganadoras, perdedoras o tablas. Cada
camino de la raíz a un nodo terminal representa una
partida completa del juego. El problema está en las
dimensiones de este árbol de juego; por ejemplo, en el
juego de ajedrez se ha determinado que el factor de
ramificación promedio es de alrededor de 35 y que en un
juego promedio cada jugador realiza 50 movimientos, por tanto
para examinar el árbol del juego completo es necesario
examinar 35100 posiciones.

Por lo tanto, es evidente que un programa que realice una
búsqueda a ciegas no podrá seleccionar ni siquiera
su primer movimiento. Es necesario algún procedimiento de
búsqueda heurística. La técnica utilizada es
la siguiente: desarrollar una parte del árbol de juego
hasta una profundidad determinada en función de
la potencia de
cálculo
disponible y de la estabilidad de la posición, evaluar
estáticamente las posiciones alcanzadas y luego propagar
hacia la raíz del árbol estos valores. Se
utilizan diferentes ardides algorítmicos que permiten
evaluar seriamente las jugadas posibles explorando solamente un
pequeño porcentaje del árbol de búsqueda. El
procedimiento de propagación hacia la raíz de
los valores
estimados para las hojas del árbol más conocido es
el MINMAX, y el ardid más viejo para simplificar el
árbol es el Alfa – Beta.

Formalización del
problema

Las seis reglas que definen un juego desde la perspectiva de
la Teoría de
juegos son:

• 1. Hay al menos dos jugadores.

• 2. El juego comienza por uno o más jugadores
  tomando una decisión entre las alternativas
  especificadas.

• 3. Después que el primer movimiento se realiza
  una cierta situación resulta del mismo. Esta
  situación determina quien hará el
  próximo movimiento y cuales son sus alternativas.

• 4. Las selecciones hechas por los jugadores pueden o
  no ser conocidas.

• 5. Si un juego se describe en términos de
  movimientos sucesivos, entonces hay una regla de
  terminación.

• 6. Cada juego termina en una cierta situación.
  Cada jugador recibe un pago.

Con respecto a la regla cuatro, si todos los jugadores conocen
todas las alternativas posibles para un jugador en particular en
cualquier momento, el juego se denomina juego de
información perfecta.