E

MONOGRAFIA : PROBLEMA JUEGO DE DAMAS

CURSO : PROGRAMACION LOGICA

CICLO :

VII

PROFESOR :

Ing. José Arturo Díaz Pulido

AUTORES :

- Castañeda Castillo, Carlos

- Santillán Huallán, Daniel

- Ulloa Paredes, Iván

TRUJILLO-PERU

2014

i

Contenido DEDICATORIA ....................................................................................................................... ii

INTRODUCCION .................................................................................................................... 5

MARCO TEORICO.................................................................................................................. 6

CAPITULO I: EL JUEGO DE DAMAS ................................................................................... 6

1.1. Resumen ...................................................................................................................... 6

1.2. Historia ........................................................................................................................ 6

1.3. Objetivo ....................................................................................................................... 7

1.4. Reglas Tradicionales..................................................................................................... 7

CAPITULO II: IMPLEMENTACION DEL JUEGO EN PROLOG........................................... 9

2.1. Representación del Juego .............................................................................................. 9

2.2. Predicados A Implementar .......................................................................................... 10

2.2.1. Manejo De Estado: .............................................................................................. 10

2.2.2. Interacción Con El Usuario ................................................................................. 10

2.2.3. Jugando Con La Maquina .................................................................................... 11

CAPITULO III: MINIMAX .................................................................................................... 12

3.1. MiniMax .................................................................................................................... 12

3.2. Teorema ..................................................................................................................... 12

3.3. Algoritmo ................................................................................................................... 12

3.4. Ejemplo ...................................................................................................................... 13

CAPITULO IV: ALGORITMO PODA ALFA – BETA .......................................................... 15

4.1. Poda Alfa – Beta......................................................................................................... 15

4.2. Algoritmo ................................................................................................................... 15

4.3. Ejemplo ...................................................................................................................... 16

CONCLUSIONES .................................................................................................................. 18

BIBLIOGRAFIA .................................................................................................................... 18

ii

DEDICATORIA

La presente proyecto monográfico se la dedico

a mi familia que a sus consejos y palabras de aliento

crecí como persona. Gracias por ayudarme a cumplir

mis objetivos como persona y estudiante.

CARLOS

iii

DEDICATORIA

A Dios Todopoderoso por darme

las fuerzas y el ímpetu para seguir

adelante a pesar de las adversidades.

A mis padres por su amor,

ayuda y apoyo en todo momento.

Gracias por esta hermosa herencia.

DANIEL

iv

DEDICATORIA

La presente proyecto monográfico

se la dedico a mi familia que a sus consejos

y palabras de aliento crecí como persona.

Gracias por ayudarme a cumplir mis

objetivos como persona y estudiante.

IVAN

5

INTRODUCCION

Históricamente, los ordenadores se han programado utilizando lenguajes muy cercanos a las

peculiaridades de la propia máquina: operaciones aritméticas simples, instrucciones de acceso a

memoria, etc. Un programa escrito de esta manera puede ocultar totalmente su propósito a la

comprensión de un ser humano, incluso uno entrenado. Hoy día, estos lenguajes pertenecientes

al paradigma de la Programación imperativa han evolucionado de manera que ya no son tan

crípticos.

En cambio, la lógica matemática es la manera más sencilla, para el intelecto humano, de

expresar formalmente problemas complejos y de resolverlos mediante la aplicación de reglas,

hipótesis y teoremas. De ahí que el concepto de "programación lógica" resulte atractivo en

diversos campos donde la programación tradicional es un fracaso.

En esta monografía trataremos sobre el Juego de Damas.

Las Damas, un juego para dos jugadores, que tiene como objetivo capturar las fichas del otro

jugador o imposibilitar el movimiento de sus fichas. Las piezas se desplazan en diagonal a

través de los cuadros negros de un tablero de ajedrez con la intención de capturar (comer) las

piezas del contrario saltando por encima de ellas.

El juego de las damas se inició en Egipto como una forma de pronóstico militar hacia el año

2000 a.C., y se conocía como alquerque. Había piezas “enemigas”, movimientos “hostiles” y

“capturas”. Se han encontrado ejemplares de este juego en tumbas egipcias y, junto con las

pinturas murales, revelan que el alquerque era un juego para dos, en el que cada jugador movía

hasta una docena de piezas a través de una matriz cuadriculada. Adoptado con ligeras

modificaciones por griegos y romanos, el juego de las damas se convirtió en el favorito de los

aristócratas.

6

MARCO TEORICO

CAPITULO I: EL JUEGO DE DAMAS

1.1. Resumen

Las damas es un juego de mesa para dos contrincantes. El juego consiste en mover las

piezas en diagonal a través de los cuadros negros o blancos de un tablero de 64 o 100

cuadros con la intención de capturar (comer) las piezas del contrario saltando por

encima de ellas.

Existen varias modalidades, con distintos tableros y número de piezas. La versión

internacional, también llamada «damas polacas», está reglada por la Fédération

Mondiale du Jeu de Dames (FMJD) y se juega en un tablero de 10×10 cuadros con dos

jugadores con 20 piezas cada uno.

1.2. Historia

Hoy en día todavía no existe un consenso claro sobre el lugar exacto de origen,

situándolo entre España y Francia. Durante los últimos años se han llevado a cabo

varios estudios para intentar aclarar de una vez cuál fue el lugar de nacimiento de las

Damas. La mayoría de ellos coinciden en afirmar que nació en España hacia el año 1100

d.C. Se han hallado restos arqueológicos de un juego similar a las Damas, y que lo

situarían en la antigua Persia, pero son meras especulaciones.

Sobre su aparición definitiva, la opinión generalizada es que surgió de la fusión de tres

juegos: las fichas de las tablas, el tablero del ajedrez y los movimientos del alquerque.

En sus inicios el juego era llamado "ferses", el nombre por el que se conocía a la reina

en el ajedrez. Conviene indicar que las piezas en las damas se mueven como lo hacía la

reina en el ajedrez de la época. El nuevo movimiento que introdujo este juego fue la

habilidad de saltar sobre las piezas del contrario y capturarlas. En ese momento el juego

pasó a ser conocido como "fierges". Fue en 1508 cuando se le empezó a llamar por su

nombre actual.

En sus orígenes, las reglas de juego eran muy diferentes; por ejemplo, capturar la pieza

del contrario era opcional. Más adelante, en 1535 se introdujo la obligatoriedad como

regla y, antes de convertirla en estándar, se jugaba como una variante llamada "jeu

forcé" (juego forzado).

Durante algunas épocas, el juego de las damas se vio desprestigiado por considerarlo de

mujeres, dado que el de hombres era el ajedrez. Sin embargo, jugarlo bien implica una

7

buena estrategia; los grandes jugadores llegan a planificar entre 15 y 20 movimientos

por adelantado.

1.3. Objetivo

Capturar o bloquear todas las piezas del oponente.

1.4. Reglas Tradicionales

Las damas es un juego para dos personas en un tablero de 64 casillas de 8 x 8 celdas. La

casilla de la izquierda tiene que tener el color negro.

Cada jugador dispone de 12 piezas de un mismo color (uno blanco y otro negro) que al

principio de la partida se encuentran en las casillas negras de las tres filas más próximas

a él. El objetivo del juego de damas es capturar las fichas del oponente o acorralarlas

para que los únicos movimientos que puedan realizar sean los que lleven a su

captura.(excepto las damas rusas la variante poddavki que gana quién se queda sin

fichas o tiene bloqueadas las que tiene).

Se juega por turnos alternos. Empieza a jugar quien tiene las fichas oscuras(negras). En

su turno cada jugador mueve una pieza propia.

Las piezas se mueven (cuando no comen) una posición adelante (nunca hacia atrás) en

diagonal a la derecha o a la izquierda, a una posición adyacente vacía.

1.4.1. Final De Partida

Una partida de damas finaliza cuando estamos en una de estas 3 situaciones:

Pierde quien se queda sin piezas sobre el tablero.

Si cuando llega el turno de un jugador no puede mover, puesto que todas las

piezas que le restan en juego están bloqueadas, ante esto se distinguen dos

reglas dependiendo el estilo practicado:

o 1. Pierde a quien le corresponde el próximo movimiento; ó

o 2. Gana quien más piezas tenga, a igual número de piezas gana quién

más reinas tenga, y si en esto también se empata la partida termina en

tablas. también se sabe que las reinas se mueven en grandes filas

El jugador que tenga muy pocas piezas puede retirarse del juego.

8

La partida también puede terminar en tablas si ambos jugadores quedan con un

número igual y muy reducido de piezas, tal que por muchos movimientos que se

hagan no se resolvería la partida. La reina siempre tiene prioridad para comer

antes que cualquiera otra ficha. También la dama solo se mueve un cuadro.

1.4.2. Resolución Matemática Del Juego

El 20 de julio de 2007, en un artículo publicado en la revista Science, se encontró la

resolución matemática para el juego de damas, siendo su resultado el de tablas. Es decir,

si ambos contrincantes juegan siempre la partida perfecta en base al análisis completo y

perfecto, las tablas están garantizadas.

Chinook es el nombre del software creado por Jonathan Schaeffer, el primer programa

que primero jugó a las damas a nivel de torneo, llegando a ganar al campeón del mundo

humano de la época: Don Lafferty, y que finalmente resolvió el desarrollo de la partida

hacia el empate ineludiblemente.

Se trataba en este caso del juego de damas de 12×12 fichas. Chinook nunca se usó para

el juego de damas internacional de 20×20 fichas que es un juego tan difícil como el

ajedrez.

1.5. VARIANTES

Checkers / Damas inglesas / Damas angloamericanas

Damas Españolas

Damas rusas / Shashki

Poddavki

Damas Turcas

Damas Chinas

9

CAPITULO II: IMPLEMENTACION DEL JUEGO EN

PROLOG

2.1. Representación del Juego

Las damas se juegan normalmente en un tablero de 8 × 8 (ocho casillas de alto y ocho

de ancho), pero para efectos de este proyecto, se va a usar un tablero general de n × n,

donde n es un número par y que n ≥ 4.

Un estado en las damas se representará mediante la estructura:

Estado (Tablero, Tamano, Turno)

Donde:

Tablero es una lista de n listas de n elementos, los cuales pueden ser:

- Vacio, representando una casilla vacía.

- Ficha (Color, Tipo) que indica que en esa casilla se encuentra una ficha del

color y tipo correspondiente.

- Color puede ser los átomos rojo y blanco, mientras que Tipo puede ser el

átomo normal (representando una ficha normal) o el átomo corona (indicando

una ficha coronada). Por ejemplo, una ficha blanca coronada sería ficha(blanco,

corona).

Tamano representa el tamaño del tablero (el n indicado anteriormente).

Turno indica el color que tiene el turno actualmente. Se usarán los mismos

átomos que representa el color de la ficha (rojo y blanco).

En el tablero, hay diferenciación entre las casillas negras y casillas blancas. Por

ejemplo, en el siguiente tablero:

Si consideramos que las filas y las casillas se enumeran de 0 a n−1, en las filas pares, las

casillas pares son negras mientras que en las filas impares ocurre al revés: las casillas

impares son negras. Esto es importante ya que en las damas, solo las casillas negras

pueden albergar fichas.

Se consideraran las reglas establecidas en el capítulo I.

10

2.2. Predicados A Implementar

2.2.1. Manejo De Estado:

tablero_inicial(+Tamaño, -Estado), el cual se satisface si Estado es un

estado que representa un tablero inicial de Tamano x Tamano. Un tablero

inicial de tamaño n x n cumple con que:

Las celdas negras en las primeras (n/2)-1 filas son ocupadas por

fichas blancas. En caso del tablero de 8 x 8, son las primeras tres

filas.

Las celas negras en las ultimas (n/2)-1 filas son ocupadas por fichas

rojas. En el caso del tablero de 8 x 8, son las últimas tres filas.

estado_valido (+Estado), que se cumple si Estado es un tablero valido. Un

estado es válido si el tablero contenido es del tamaño indicado, que el turno

es un valor valido y que el tablero respete las reglas del juego.

final (+Estado, +Color), predicado que se satisface si, para Color, la partida

ha terminado.

fichas_color (+Estado, +Color, -Fichas), que se satisface si Fichas es una

lista de pares que contienen las posiciones de las fichas que tiene Color en

el tablero contenido en Estado. La Posicion se representara mediante la

estructura pos(Fila, Columna), con Fila y Columna enteros tal que la fila

(columna) inicial es 0.

movimientos posibles (+Estado, -Movimientos), que se cumple si

Movimientos es la lista de todos los movimientos válidos para el color que

tiene el turno en el tablero especificado en Estado. Un movimiento va a ser

una lista de posiciones (indicada con la estructura dada en el predicado

anterior) que corresponde con la secuencia de movimientos (al menos uno,

pero puede haber más, por ejemplo si hay ataques encadenados) que realiza

la ficha partiendo en la posición dada.

jugada (+Estado, +Posicion, +Movimiento, -Resultado), que se satisface si

Resultado es el estado resultante de aplicar a Estado los movimientos en

Movimiento (la lista de movimientos tal cual como en la parte anterior.) a la

ficha ubicada en Posicion. Este nuevo estado debe tener como jugador

activo al jugador rival.

2.2.2. Interacción Con El Usuario

mostrar estado (+Estado), el cual triunfa si se muestra en pantalla el tablero

en Estado.

11

jugar_ 2, el cual realiza una partida de damas totalmente interactiva entre

dos jugadores humanos. Primero, se define el tamaño del tablero y luego,

para cada turno debería de mostrar: tablero actual, turno del jugador y

posibles movimientos a realizar. Se solicita un movimiento y luego se repite

el ciclo al menos que ya ocurra victoria.

2.2.3. Jugando Con La Maquina

Se implementara el algoritmo alpha-beta pruning que es una extensión

del algoritmo minmax.

Para implementar este algoritmo, primero se deben especificar los puntos

dependientes del problema.

sucesor (+Estado, -Sucesor), que se satisface si Sucesor es un sucesor de Estado cuando Jugador realiza una jugada. Para el caso de las damas,

tiene que ser el predicado jugada sobre todas las posibles jugadas del

jugador activo.

heurística (+Estado, -Valor) es una función que asigna para un estado

particular un valor adecuado.

Donde cada término se calcula como:

y n es el tamaño del tablero, NCor(c) son las fichas no coronadas del

color correspondiente, CNB(c) son las fichas coronadas del color que no se encuentran en un borde y CB(c) son las fichas coronadas del color

que se encuentran en un borde. Observe que un valor positivo es una

situación favorable para el color blanco mientras que un número negativo lo es para el color rojo.

Con estos puntos, se debe implementar el predicado:

alpha_beta(+Estado, +Profundidad, +Alfa, +Beta, -Valor, -Movimiento)

Que se satisface si, al haber aplicado el algoritmo alpha-beta pruning al estado Estado con Profundidad niveles máximos de profundidad, se

obtiene el valor del estado según el algoritmo, y que movimiento se

obtiene de este. (Nota: el espacio de búsqueda en damas es muy grande

– se estima que son 1020 posiciones validas en un tablero 8×8 – por lo

que, aunque es tolerable que su algoritmo no funcione adecuadamente

por ser muy grande, debería de funcionar para tableros 4 × 4 y 6 × 6 con

una profundidad razonable.)

Con el predicado alpha beta implementado, se deberá implementar

además los predicados:

12

obtener_jugada(+Estado, +Profundidad, -Movimiento)

Que se satisface si Movimiento es el movimiento obtenido por la aplicación del algoritmo anterior con los niveles de profundidad dados.

Y por último, implemente el predicado:

jugar_cpu (+Color)

El cuál hace lo mismo que jugar_2 pero con la diferencia que la partida

se realizará entre el usuario y el algoritmo realizado anteriormente. El color indicado corresponde con el color asociado al jugador humano.

CAPITULO III: MINIMAX

3.1. MiniMax

En teoría de juegos, Minimax es un método de decisión para minimizar la pérdida máxima esperada en juegos con adversario y con información perfecta. Minimax es un

algoritmo recursivo.

El funcionamiento de Minimax puede resumirse como elegir el mejor movimiento para

ti mismo suponiendo que tu contrincante escogerá el peor para ti.

3.2. Teorema

John von Neumann es el creador del teorema minimax, quien dio la siguiente noción de

lo que era un juego:

"Un juego es una situación conflictiva en la que uno debe tomar una decisión sabiendo que los demás también toman decisiones, y que el resultado del conflicto se determina,

de algún modo, a partir de todas las decisiones realizadas."

También afirmó que:

"Siempre existe una forma racional de actuar en juegos de dos participantes, si los intereses que los gobiernan son completamente opuestos."

3.3. Algoritmo

a. Generación del árbol de juego. Se generarán todos los nodos hasta llegar a un

estado terminal.

b. Cálculo de los valores de la función de utilidad para cada nodo terminal.

c. Calcular el valor de los nodos superiores a partir del valor de los inferiores.

Según nivel si es MAX o MIN se elegirán los valores mínimos y máximos

representando los movimientos del jugador y del oponente, de ahí el nombre de

Minimax.

d. Elegir la jugada valorando los valores que han llegado al nivel superior

El algoritmo explorará los nodos del árbol asignándoles un valor numérico

mediante una función de evaluación, empezando por los nodos terminales y

subiendo hacia la raíz. La función de utilidad definirá lo buena que es la posición

para un jugador cuando la alcanza.

13

3.3.1. Función De Evaluación: Una función de evaluación debe dar datos importantes

de la instancia del juego, por ejemplo en el juego de las damas es fundamental saber su

movilidad. Otras implementaciones de funciones de evaluación pueden ser más

complejas, por ejemplo dan información de la seguridad del rey.

3.4. Ejemplo

14

15

CAPITULO IV: ALGORITMO PODA ALFA – BETA

4.1. Poda Alfa – Beta

La poda alfa beta es una técnica de búsqueda que reduce el número de nodos evaluados

en un árbol de juego por el algoritmo Minimax. Se trata de una técnica muy utilizada en

programas de juegos entre adversarios como el ajedrez, el tres en raya o el Go.

El problema de la búsqueda Minimax es que el número de estados a explorar es

exponencial al número de movimientos. Partiendo de este hecho, la técnica de poda

alfa-beta trata de eliminar partes grandes del árbol, aplicándolo a un árbol Minimax

estándar, de forma que se devuelva el mismo movimiento que devolvería este, gracias a

que la poda de dichas ramas no influye en la decisión final.

4.2. Algoritmo

La búsqueda minimax es primero en profundidad, por ello en cualquier momento sólo se deben considerar los nodos a lo largo de un camino en el árbol.

La poda alfa-beta toma dicho nombre de la utilización de dos parámetros que describen

los límites sobre los valores hacia atrás que aparecen a lo largo de cada camino.

α es el valor de la mejor opción hasta el momento a lo largo del camino para

MAX, esto implicará por lo tanto la elección del valor más alto

β es el valor de la mejor opción hasta el momento a lo largo del camino para

MIN, esto implicará por lo tanto la elección del valor más bajo.

Esta búsqueda alfa-beta va actualizando el valor de los parámetros según se recorre el

árbol. El método realizará la poda de las ramas restantes cuando el valor actual que se

está examinando sea peor que el valor actual de α o β para MAX o MIN, respectivamente.

El desarrollo del algoritmo en pseudocódigo será el siguiente:

16

4.3. Ejemplo

Como la primera hoja debajo de B tiene valor 3 y siendo B un nodo MIN, tiene como

valor máximo a 3.

La segunda hoja de B tiene valor de 12, por lo tanto MIN evitara este movimiento,

debido a que el número es mayor que 3.

El siguiente nodo tiene valor de 8, quedando el valor de B en 3 y hasta el momento seria

3 para el nodo raíz.

17

La primera hoja de C es de valor 2, como C es un nodo MIN con el máximo valor de 2

y B vale 3, el nodo raíz MAX nunca elegiría a C, y no es necesario revisar sus nodos

sucesores.

La primera hoja de D es 14 y como es más alto que el 3 de B, existe la necesidad de

seguir los demás nodos hojas.

El siguiente valor de D es 5, seguimos explorando; el tercer valor es 2 así que D vale 2.

La decisión de MAX en la raíz es moverse a B, quedando como valor final 3.

18

CONCLUSIONES

En este trabajo se implementó un programa de reproducción de fichas basadas en el

algoritmo Minimax con corte alfa-beta. El programa permite al usuario elegir el nivel de

profundidad de la búsqueda llevada a cabo por el algoritmo, simulando así diferentes

niveles de dificultad para el juego.

El diseño y construcción de juegos clásicos de tablero no resulta ser sencillo debido a la

gran variedad de posibilidades que se tienen con respecto a los movimientos.

Finalmente podemos decir que el juego, en una versión interesante, puede

implementarse de forma distribuida o paralela y en tiempos relativamente cortos.

BIBLIOGRAFIA

1. Wikepedia – Poda alfa-beta – Ultima lectura 25 Junio 2014

http://es.wikipedia.org/wiki/Poda_alfa-beta

2. Wikepedia – Damas – Ultima lectura 27 Junio 2014

http://es.wikipedia.org/wiki/Damas

3. http://www.dma.fi.upm.es/docencia/primerciclo/matrecreativa/juegos/damas/data/

reglas.html

4. Wikepedia – Minimax – Ultima lectura 27 Junio 2014

http://es.wikipedia.org/wiki/Minimax