INGENIERÍA DE TELECOMUNICACIÓN Inteligencia en redes de comunicaciones

Juego de las Damas

Arias Fernández, Carlos García del Amo, Isidro

Inteligencia en Redes de Comunicaciones Juego de las Damas

Cómo se originó realmente el juego de las Damas Los historiadores afirmaron hasta 1986 que el juego de las damas era un invento francés. Otros decían incluso que era un invento de los egipcios. Y así hasta la fecha nadie sabía su origen. A pesar de que la mayoría de los importantes libros fueron escritos en España desde el año 1547 hasta 1901, España no fue tomada en cuenta. Después de una investigación de diez años por parte de Govert Westerveld (Monnickendam - Holanda, 1947) , la cosa ha cambiado en beneficio de los españoles, y es que ahora reconocen que efectivamente España fue la madre creadora del juego de las Damas, gracias a los árabes. Existen básicamente dos formas de jugar. Una es el juego español con 12 fichas, y otro es el juego con 20 fichas. Fue Alfonso X, gran impulsor de la cultura y aún de la amalgama de estas, quién primero realiza un compendio de los juegos conocidos y practicados en su época, que dio lugar al celebre "Juegos de ajedrez, dados y tablas" publicado en Sevilla en el año 1283. En tan reconocida obra, única en el mundo antiguo, no se da cuenta ni descripción del juego de Damas que conocemos, lo que nos indica claramente que ni siquiera muy avanzado el siglo XIII se tenía noticias de tal juego y por lo tanto es de invención posterior. Nada tienen que ver otros juegos descritos, el más próximo de los cuales es el alquerque, por lo que las suposiciones de si alguno de estos nombres (¿Tablas?) corresponde a las Damas carecen de fundamento. Esto termina también con la falacia de que el juego de Damas es de mayor antigüedad que el Ajedrez. El ajedrez, por ser muy conocido, no es preciso describirle y por supuesto también es conocido por Alfonso X, que lo sitúa en primer lugar. El tipo de tablero y piezas es de origen antiguo, probablemente oriental, llegando a España a través de los árabes, desde donde se difundió al resto del mundo. Lo primero que hago notar es que el juego traído por los árabes no es el ajedrez que conocemos, sino el antiguo ajedrez oriental, el cual fue modificado sustancialmente en España originando el ajedrez moderno que se juega en todo el mundo. También en el ajedrez las primeras obras escritas (aparte de Alfonso X) son españolas, como el célebre incunable de Lucena, punto de partida del ajedrez actual. El antiguo ajedrez es anterior a las Damas, pero seguramente también el ajedrez actual, aunque puede que no por mucho espacio de tiempo; el incunable de Lucena es más antiguo que el Torquemada, pero las fechas son próximas, aunque las aportaciones de uno a otro juego (del Ajedrez a las Damas, ya que en sentido contrario no existen) como es el mismo tablero de juego, indican claramente que el Ajedrez moderno se originó en tiempo algo (aunque relativamente poco) anterior a las Damas. En el estado que se encontraban los juegos después de Alfonso X el Sabio, se tenía por un lado el Ajedrez, cada vez más pujante, y por otro el Alquerque, bastante limitado en su espacio de juego y con tablero en desuso, ya que además era relativamente fácil de jugar para expertos. Esta es la situación que hizo, en el siglo XV, que el tablero bicolor se impusiera definitivamente y que alguien tuviese la idea de situar las doce piezas del alquerque (para cada bando) en filas opuestas del tablero de ajedrez, cubriendo por tanto un solo color y haciendo que de forma natural se conservase solamente el movimiento diagonal

2

Inteligencia en Redes de Comunicaciones Juego de las Damas

de las piezas, siguiendo con las capturas mediante salto. Es muy posible que en un principio las fichas fuesen los peones del ajedrez, sustituyendo por pieza superior si se coronaba; la primera descripción gráfica del tablero de juego (Timoneda) representa a las fichas como peones de ajedrez. En tal situación el armazón del juego ya estaba consolidado, aunque las características que le harían único vinieron después; en primer lugar se introdujo el concepto de coronación al llegar a primera fila contraria, sin duda proveniente del ajedrez moderno. Posteriormente se dotó a la pieza coronada de una fuerza inusual, haciendo que pudiese mover en cualquier sentido diagonal y con cualquier desplazamiento o captura si esta fuera posible. Estas dos últimas y geniales aportaciones configuraron definitivamente el juego de Damas. Por tanto el juego de Damas es el resultado de: •

Los peones y movimiento diagonal (no los otros) del alquerque español.

•

La forma de captura mediante salto del alquerque.

•

El tablero de ajedrez

•

La promoción de pieza en otra superior, idea proveniente del ajedrez.

•

Añadiendo los siguientes conceptos: •

Disposición inicial de los peones en el tablero.

•

Exclusión de todo movimiento no diagonal (utilizar casillas de un solo color).

•

Exclusión de movimiento retrogrado para el peón (en Alquerque es posible).

•

Movimiento largo y en cualquier sentido diagonal de la pieza coronada, con semejanza en el alfil del ajedrez

•

Capturas con pieza coronada mezcla de dos conceptos: •

El movimiento largo tipo alfil

•

El salto tipo Alquerque

•

Libertad de salto de captura a cualquier casilla posterior libre, no contemplado anteriormente en otro juego.

Por lo tanto el juego de Damas es la conjunción del Ajedrez con el Alquerque español, aumentado con nuevos y revolucionarios conceptos que harían de las Damas un juego único, nuevo y triunfante. Esta amalgama queda definitivamente establecida en el último tercio del siglo XV, algo posterior a la creación definitiva del ajedrez actual.

3

Inteligencia en Redes de Comunicaciones Juego de las Damas

Algoritmos de búsqueda Algunos juegos como las damas o el ajedrez, por tener información completa de inicio son idóneos para la búsqueda de caminos en un sistema complejo, pudiendo después aplicar lo descubierto a otros campos de la computación o de la ciencia en general. El primer juego que se intento computarizar y para el que se desarrolló un programa fue precisamente el juego de las damas. Posteriormente otros juegos fueron tratados en este aspecto, llegando al momento actual en que es el ajedrez el más estudiado y al que mayores esfuerzos se dedican en pos de la consecución del jugador perfecto, como sucedió con los programas Deep Blue y actualmente, 3DFritz. Las técnicas y algoritmos que se usan para todos estos juegos son básicamente los mismos, cambiando solo alguna particularidad del juego tratado, como la generación de jugadas, etc. Por todo ello, los algoritmos que se detallarán a continuación son válidos para las damas, el ajedrez... Ya en los años 50, Shannon describió los mecanismos que podían usarse en un programa jugara al ajedrez y Turing describió un programa para jugar al ajedrez pero no lo construyó. En los 60, Samuel construyó el primer programa de juegos importante y operativo, el cual jugaba a las damas y podía aprender de sus errores para mejorar su comportamiento. Los juegos proporcionan una tarea estructurada en la que es muy fácil medir el éxito o el fracaso. En comparación con otras aplicaciones de inteligencia artificial, por ejemplo comprensión del lenguaje, los juegos no necesitan grandes cantidades de conocimiento. En un primer momento se pensó que se podrían resolver por búsqueda exhaustiva en el árbol del juego, es decir, un árbol que contenga todos los movimientos posibles de ambos jugadores. Considerando por ejemplo el juego de las damas, en el comienzo de la partida un jugador puede realizar 7 movimientos, por lo que en el árbol de juego habría 49 nodos en el segundo nivel. Por el contrario, en el juego de ajedrez, en el comienzo de la partida un jugador puede realizar 20 movimientos, por lo que en el árbol de juego habría 400 nodos en el segundo nivel, así la complejidad aumentaría exponencialmente en cada nivel de profundidad del árbol Resulta evidente que una simple búsqueda directa no es posible de realizar en la práctica, y por lo tanto es necesario algún tipo de procedimiento de búsqueda heurística. Resulta evidente que la elección del camino a seguir será más acertada cuántas más capas se exploren antes de tomar la decisión. Se utiliza una función de evaluación estática (heurística) para elegir el movimiento más prometedor. Por ejemplo, Turing usó la sencilla función B/N (piezas blancas / piezas negras) para evaluar una posición dada de un tablero de ajedrez. Shannon utilizó una función lineal de funciones de evaluación simples para evaluar un tablero de damas: c1 * ventaja piezas + c2 * avance + c3 * amenazas dobles + ... En la función anterior, con un mecanismo de aprendizaje, los pesos o ponderaciones ci se incrementan o disminuyen siempre que sus componentes sugieran movimientos que conducen a la victoria o al fracaso respectivamente.

4

Inteligencia en Redes de Comunicaciones Juego de las Damas

En juegos y otros dominios la solución se encuentra mediante un proceso de búsqueda que debe combinarse de ser posible con una técnica directa. Por ejemplo en el ajedrez, las aperturas y los finales están ya estudiados y se almacenan en una base de datos. También sucede esto en las damas, en los que suele almacenarse en una base de datos los finales de las partidas, Cabe distinguir, ahora, para desarrollar los algoritmos o estrategias a utilizar, entre juegos sin adversario y juegos con adversario: Juegos sin adversario: estrategia A* Para juegos simples unipersonales (por ejemplo puzzle-8) puede usarse el algoritmo A* (Hart, 1968) que se describe en esta sección. Este algoritmo implementa una búsqueda primero el mejor. Se utiliza una función de evaluación estática f formada por: f=g+h La función g es una función de coste de llegar del estado inicial al estado evaluado. La función h es una estimación del coste de llegar desde el estado evaluado al estado final u objetivo del juego. En cada paso del algoritmo se selecciona el mejor nodo que no se ha expandido hasta el momento, es decir, aquel que tiene menor valor de función f. Este nodo se agrega a una lista de nodos explorados y sus nodos sucesores se agregan a la lista de nodos pendientes de ser explorados... Juegos con adversario: algoritmo Minimax En juegos bipersonales el algoritmo más usado es el denominado Minimax. El procedimiento de búsqueda Minimax es una búsqueda en profundidad (DFS) de profundidad limitada. La idea consiste en comenzar en la posición actual y usar el generador de movimientos posibles para generar las posibles posiciones sucesivas hasta un cierto límite de niveles. A continuación se aplica la función de evaluación estática a las posiciones obtenidas y se elige la mejor posición para el jugador correspondiente, llevando los valores un nivel hacia atrás para continuar la evaluación en todos los niveles anteriores. Se supone una función de evaluación estática que devuelve valores elevados para indicar buenas situaciones y valores negativos para indicar buenas situaciones para el oponente. Visto de esta manera, la meta es maximizar el valor de la función estática de la siguiente posición de tablero. El nombre del algoritmo deriva de considerar que, dada una función estática que devuelve valores en relación al jugador maximizante, éste procura maximizar su valor mientras que su oponente procura minimizarlo. En un árbol de juego donde los valores de la función estática están en relación al jugador maximizante, se maximiza y minimiza alternadamente de un nivel a otro.

5

Inteligencia en Redes de Comunicaciones Juego de las Damas

Poda alfa-beta de la búsqueda Minimax Los procedimientos de búsqueda en profundidad (DFS) pueden mejorar su eficiencia usando una técnica de ‘branch and bound’ (ramificación y acotación), con la cual una solución parcial se abandona cuando se comprueba que es peor que otra solución conocida o umbral. La estrategia de poda del algoritmo Minimax es llamada poda alfabeta, puesto que dado que existen dos jugadores (maximizador y minimizador), existen dos valores umbrales alfa y beta para acotar la búsqueda de cada uno respectivamente: el valor alfa representa la cota inferior del valor que puede asignarse en último término a un nodo maximizante y el valor beta representa la cota superior del valor que puede asignarse en último término a un nodo minimizante. Otros algoritmos El algoritmo Minimax, aún con los refinamientos descriptos, contiene algunos aspectos problemáticos, como por ejemplo, no considera el tiempo y confía fuertemente en la suposición de que el oponente elija el camino óptimo. Por ello, otros algoritmos que pueden utilizarse pueden ser: Minimax dependiente de adversario Según realiza la exploración del árbol de juego, el algoritmo Minimax supone que el oponente siempre elige el camino óptimo. Si se está frente a un adversario muy inteligente, éste podría llegar a explorar más capas que las exploradas por el algoritmo y por lo tanto tomar otra decisión que la supuesta. Aún suponiendo que el algoritmo siempre explora a una mayor profundidad que el adversario, éste último puede equivocarse y no elegir el camino óptimo. La consecuencia es que el algoritmo elige el movimiento basándose en una suposición errada. Ante una situación de derrota, según sugiere Berliner (1977), podría ser mejor asumir el riesgo de que el oponente puede cometer un error. Por tanto, cuando se debe elegir entre dos movimientos buenos, uno ligeramente mejor que el otro, podría resultar mejor elegir el menos mejor si al asumir el riesgo de que el oponente se equivoque nos conduce a una situación muchos más ventajosa. Pero para tomar esta clase de decisiones correctamente, el algoritmo debería modelar el estilo de juego de cada oponente en particular. Esto permitiría estimar la probabilidad de que cometa distintos errores. Sin lugar a dudas, esto es muy difícil de lograr y se necesita contar con técnicas de aprendizaje para que el algoritmo obtenga conocimiento sobre su oponente a lo largo del juego. Profundización iterativa La profundización iterativa es una idea que se utilizó por primera vez en un programa llamado CHESS 4.5 (Slate y Atkin, 1977). El nombre profundización iterativa hace referencia a que se realizan iteraciones de búsquedas cada vez más profundas. La principal razón para realizar iteraciones de búsquedas de diferentes profundidades incrementales, en lugar de realizar una búsqueda a la profundidad deseada, es que los programas de juegos pueden estar sujetos a restricciones de tiempo. Mediante esta técnica la primera iteración realiza una búsqueda de profundidad uno, la segunda iteración realiza una búsqueda de profundidad dos, etc. hasta que el tiempo destinado al movimiento se agote. El problema de la limitación de tiempo debe considerarse en juegos como el ajedrez, aunque no en el juego de las damas, por lo menos, en lo que a las reglas del juego se refiere.

6

Inteligencia en Redes de Comunicaciones Juego de las Damas

Algoritmos utilizados Para el desarrollo de este programa se ha utilizado un algoritmo Minimax, fijando un nivel máximo de profundidad en el árbol de seis niveles, que corresponde a tres movimientos de la máquina más los movimientos de respuesta del adversario. En cada nodo del árbol se almacena la información correspondiente al estado de la partida si se llevase a cabo dicho movimiento. Por ello, recorriendo el árbol se busca el movimiento que maximice la diferencia entre el número de piezas con las que juega la máquina y el número de piezas con las que juega el adversario (el usuario). Debemos tener en cuenta para determinar el número de piezas que pueden existir dos tipos de fichas para cada jugador: peones (piezas de salida) y damas. Debido a las mayores posibilidades de movimiento y acción de la dama, se le ha dado un peso a cada ficha: 1 punto por peón y 3 por dama. Así, se maximiza, para todos los movimientos posibles para la máquina y solamente para el mejor o los mejores para el adversario, la función 3*damasMaquina + peonesMaquina - 3*damasUsuario - peonesUsuaruio Es decir, se considerarán todos los movimientos que puede realizar la máquina, pero consideraremos que el usuario hará el mejor de sus movimientos, para ello, recorreremos el árbol de movimientos solamente para el mejor (o los mejores si el camino no es único) de los movimientos para cada caso del usuario. Si el resultado de la búsqueda del mejor movimiento no es único, entonces se ha recurrido a la aleatoriedad para determinar el movimiento a realizar. A cada uno de estos movimientos posibles se le asigna un peso dependiendo del número de nodos del último nivel de profundidad (que dependan de él) que permitan llegar a un máximo de la función explicada anteriormente. Por tanto, cuantos más caminos llevan a dicho resultado, mayor será la probabilidad de seguir ese camino. Esta aleatoriedad permite que la máquina no sea tan determinista ante situaciones idénticas desde el punto de vista del análisis del árbol de movimientos. El gestor de jugadas lleva una particularidad en este juego en relación con el ajedrez, ya que ciertos movimientos son obligatorios (en el juego de las Damas, es obligatorio el comer piezas si se puede), y dentro de varios movimientos obligatorios habrá que elegir uno de ellos, motivo por el que se aplicó el dar pesos a cada tipo de ficha, como se indicó anteriormente.

Implementación El programa fue desarrollado en Java, utilizando un entorno de desarrollo Java 2 SDK 1.3.1. El programa permite al usuario elegir con que fichas jugar, teniendo en cuenta que de cara al interfaz gráfico se han sustituido las piezas blancas por amarillas y las negras por azules, siendo por tanto las amarillas las que mueven primero al comenzar la partida. Para que el usuario realice un movimiento, debe pulsar la casilla inicial y después la casilla final haciendo un click simple con el ratón. Si el movimiento no es posible (porque no sea un movimiento posible del juego, o siendo posible, hay algún otro

7

Inteligencia en Redes de Comunicaciones Juego de las Damas

movimiento que es obligatorio y el actual no lo es), se muestra una ventana de dialogo al usuario indicándole esta situación e invitando a repetir el movimiento. Los movimientos se almacenan en los nodos de un árbol n-ario (pues el número de jugadas nunca es fijo) para lo que se han utilizado vectores. Para crear el árbol y recorrerlo para determinar el mejor movimiento posible se utilizan métodos recursivos para permitir variar la profundidad del árbol. El programa está formado por las siguientes clases: DamasApp.java

•

Clase que muestra la primera ventana de la aplicación para elegir piezas blancas o negras.

Tablero.java

•

Clase que se encarga de inicializar el interfaz gráfico y de recoger los eventos del ratón y pasar la información correspondiente al gestor del juego, la clase Damas.

Interfaz_tablero.java

•

Clase que muestra por pantalla el tablero del juego y las piezas en la posición correspondiente en cada momento.

Damas.java

•

Clase que gestiona la partida. Contiene información del estado actual de la partida, comprueba que el movimiento realizado por el usuario sea correcto, y contiene una referencia a Arbol_Mov, árbol con los movimientos del juego.

Arbol_Mov.java

•

Clase con estructura de árbol n-ario con información de todos los movimientos posibles. Permite elegir un movimiento (considerado óptimo) para la máquina mediante un algoritmo minimax. Cada nodo del árbol es de la clase Movimiento.

Movimiento.java

•

Clase que contiene la información necesaria para cada movimiento, como casilla inicial, casilla final, número de piezas que quedan en el tablero...

8

Inteligencia en Redes de Comunicaciones Juego de las Damas

Conclusiones Con el fin de probar la inteligencia del programa desarrollado, se han realizado pruebas con varios niveles de profundidad del árbol de movimientos, obteniéndose mejores resultados del juego de la máquina al aumentar este nivel. Se ha fijado en 6 niveles de profundidad, ya que con 8 niveles no siempre puede crearse el árbol de movimientos por falta de memoria. Por ello, se ha optado con utilizar 6 niveles en el programa. Inclusive con 6 niveles de profundidad, dependiendo de si el número de damas de ambos jugadores es alto, no siempre ha sido posible crear el árbol, saltando un java.lang.OutOfMemoryException, excepción que solamente se produce cuando ni el GarbageCollector puede liberar la cantidad de memoria requerida. En el caso de que sea imposible crear el árbol de movimientos, se ha optado por intentar crear el árbol con menor profundidad (4 niveles, 2 por cada jugador). De este modo, aunque se barajen menos posibilidades, podrá seguir siendo un buen movimiento por observar 4 movimientos hacia el futuro. Cabe destacar que el tiempo de respuesta es prácticamente nulo siempre que el número de damas en el tablero no sea significativo. No se han desarrollado técnicas para detectar empates, aunque la partida pueda seguir llevándose a cabo, como por ejemplo, dos damas contra una dama, situación que sólo tendría un ganador si se cometiese un gran e improbable error de algún jugador. En una pequeña comparativa del juego de las Damas con el Ajedrez, podemos señalar que mientras que en el Ajedrez es mayor la complejidad y el tamaño del árbol en anchura (más posibles movimientos en cada nivel del árbol), en las Damas es mayor la complejidad en el desarrollo y creación del árbol de movimientos, ya que una pieza debe seguir comiendo piezas rivales mientras pueda, y en el Ajedrez una pieza solamente comerá una pieza contraria, no siendo además este movimiento obligatorio. La construcción del árbol ha sido una de las tareas más complejas que se han desarrollado en esta práctica. Muchos programas encontrados que simulan un jugador de Damas (al igual que los programas de Ajedrez), utilizan bases de datos para mejorar los últimos movimientos de las partidas, cuando ya quedan pocas piezas sobre el tablero. De esta forma, pueden almacenarse finales de partidas ya jugadas y tomar un camino fijo hacia la victoria. Para este programa no se ha seguido esta técnica ya que se ha optado por un único algoritmo a utilizar durante toda la partida, que se ha intentado lo suficientemente genérico para cualquier situación que pueda darse en una partida.

9