Resumen
El salto del
caballo de ajedrez consiste en un recorrido por todas las casillas del tablero
sin pasar dos veces por la misma casilla, utilizando un solo movimiento válido:
dos casillas horizontales y una vertical o de forma inversa. El objetivo de
este trabajo es utilizar técnicas de resolución de problemas de satisfacción de
restricciones que nos puedan ayudar a encontrar la mejor solución o una
aproximación a la misma, de modo tal, que nos permita recorrer todas las
casillas de un tablero con los movimientos permitidos del caballo de ajedrez,
sin visitar aquellas casillas que ya fueron exploradas o aquellas que posean
obstáculos. Se realizarán experimentos para poder probar y demostrar cómo se
comportan las distintas búsquedas combinadas con distintas heurísticas y comparando las medidas de rendimientos de las
mismas.
1 Presentación del problema
Disponemos de un
tablero de dimensión n x m, (tanto la variable n y m, serán definidas
por el usuario) el formato de dicho tablero es similar al tablero de ajedrez.
Este
procedimiento consiste en completar el recorrido del caballo de forma tal que
no se tropiece con los obstáculos colocados en el tablero. Los obstáculos
podrán ser generados tanto de forma aleatoria como manual.
El procedimiento
consiste en partir de la casilla inicial hasta la última casilla del tablero, visitando
todas las casillas que se encuentren sobre el tablero, obedeciendo las
siguientes normas:
·
Recorrer
todas las casillas, excepto aquellas que presentan obstáculos o ya fueron
visitadas.
·
Cada
casilla sólo puede visitarse una sola vez.
El movimiento del
caballo será igual al juego de ajedrez por lo que el caballo sólo se podrá
mover en L, esto quiere decir que el movimiento del caballo se compone de
aquellas casillas que estén a una distancia de dos casillas horizontales y una
vertical o viceversa.
Se muestra un
ejemplo en la figura que se muestra a continuación, en donde
se describe un tablero de tamaño n, m =
5, en total se tienen 8 posibles movimientos para la casilla central en donde
se encuentra el caballo, los movimientos posibles se marcan con una X y la
casilla inicial se marca con la figura del caballo de ajedrez, la posición
inicial puede ser cualquier posición en el tablero (exceptuando aquellos
lugares que contengan un obstáculo).
El juego se da
por finalizado cuando se recorrieron todas las casillas del tablero sin repetir
ninguna casilla entre las casillas válidas a visitar.
Nuestra propuesta
consiste en resolver el problema con algoritmos de satisfacción de
restricciones con vuelta atrás.
Este
tipo de algoritmos se encarga de explorar todo el espacio de estados abarcando
todas las posibilidades, teniendo en cuenta cada una de ellas. Estos algoritmos
son de naturaleza recursiva, por lo tanto iteran estados hasta alcanzar el
éxito, excepto en aquellos casos en que es imposible seguir iterando y es
necesario volver a estados anteriores para probar otra alternativa y así llegar
a la solución o poder confirmar que el problema no tiene solución.
Por
lo tanto y viendo los beneficios que estas técnicas nos van a proporcionar para
resolver la problemática, decidimos realizarlo con Backtracking cronológico y
el algoritmo Arco-Consistencia (AC-3); de esta manera vamos a poder comparar el
desempeño de dichos algoritmos para determinar cuál de ellos nos resulta más
adecuado para este proyecto, evaluándolos a través de sus medidas de
rendimiento.
Haremos uso de
heurísticas para mejorar aún más las búsquedas, considerando que las
heurísticas presentan grandes ventajas, tales como:
Ø
Nos
proporcionan una buena aproximación a la solución, no necesariamente la óptima.
Ø
Se
aplica una heurística para guiar a un método de resolución de problema.
Ø
Se
pueden obtener mejores resultados para el problema, debido a que se pueden
explorar primero aquellas alternativas que nos lleven rápido al fracaso, y de
esta manera poder podar el árbol de opciones y llegar a la solución de forma
más rápida.
Algunas heurísticas a utilizar pueden
ser:
1.
Variable más
restringida:
vamos a elegir aquella casilla que se encuentre más restringida, es decir, para una casilla dada, se elegirá aquella que
tenga la menor cantidad de movimientos posibles.
2.
Heurística de
grado:
selecciona de las casillas posibles, aquella que se encuentre implicada en la mayor
cantidad de restricciones, es decir, para una casilla dada, se elegirá aquella
que tenga la mayor cantidad de movimientos posibles.
2 Problema
2.1 Estado de
la cuestión
Se investigó
sobre el Salto del Caballo en internet, pero no se encontró mucha información, en
muchas páginas se informa lo mismo, se encontraron algunos proyectos realizados
por otros alumnos, pero ninguno estaba completamente implementado y solo
mostraba algunas variantes.
Una información
importante que encontramos en la web, es sobre los estudios anteriores
realizados por una gran personalidad matemática, Euler. En donde dicha información
es citada a continuación:
"El primer
estudio matemático importante sobre este problema se cree que es el que efectúo
el genial matemático Leonhard Euler (1707–1783), quien presentó su
trabajo a la Academia de las Ciencias de Berlín en 1759.
En realidad Euler (una figura
reconocida que publicó más de mil trabajos y libros
brillantes durante toda su vida) sabía que la Academia ofrecía un premio de
4000 francos a aquel que pudiese arrojar algo de luz al problema del caballo.
Si bien se conocían muchas soluciones, nadie había logrado estimar el número de
ellas que existían ni un algoritmo que permitiese generarlas sin dificultad.
Los que habían abordado el problema sabían que
encontrar una solución simplemente moviendo el caballo “al tanteo” era
prácticamente imposible, pero tampoco eran capaces de encontrar un método que
facilitase el proceso.
Siendo así las cosas,
Euler encaró el problema y encontró que existían varios recorridos cerrados que
ofrecían la ventaja de permitir comenzar por una casilla cualquiera del tablero
y completar el recorrido a partir de ella. Lamentablemente, en el momento en
que publicó su trabajo, Euler se desempeñaba como Director de Matemáticas de la
Academia de Berlín, por lo que por una cuestión ética no pudo cobrar el premio.
Hace 15 años, en 1995,
Martin Löbbing e Ingo Wegener pusieron a trabajar 20 ordenadores Sun (potentes para la época) durante
cuatro meses y publicaron un documento en el que proclamaban que el número
de recorridos posibles en un tablero de 8x8 era 33.439.123.484.294. Dos
años más tarde, en 1997, Brendan McKay encaró el problema del caballo
dividiendo el tablero en dos mitades y llego a un resultado algo menor: “solo”
existirían 13.267.364.410.532 recorridos posibles. Para tener una idea de
lo que significan estos números, basta saber que si un robot fuese capaz de
mover el caballo para que complete un recorrido por segundo, demoraría más de
420 años en probarlos a todos.
Se han diseñado
muchas soluciones a este problema y de hecho no se sabe con seguridad de
cuántas maneras diferentes es posible solucionarlo."
Algunas
variaciones de este problema han sido estudiadas por los matemáticos, algunas
son:
§ Buscar
soluciones cíclicas, en la cual se debe llegar a la misma casilla de la cual se
partió.
§ Tableros de diferente
número de columnas o diferente número de filas.
§ Juegos de dos
jugadores basados en la idea.
§ Problemas usando
ligeras variaciones en la forma de moverse el caballo.
Es un tema de
conocimiento mundial, y muy interesante de evaluar. Se describe el marco de
referencia en el apartado Bibliografía de este documento.
2.2 Análisis
del problema
Nuestro objetivo
es poder encontrar las posibles soluciones eficientes e inteligentes al juego
de inteligencia propuesto.
Proponemos
tratar la problemática como un problema de satisfacción de restricciones (CSP),
en donde lo definimos formalmente a continuación:
·
Variables: cada una de
las casillas del tablero de ajedrez, Xij en donde los valores i (valor de
fila), j (valor de columna), varían según el tamaño del tablero de ajedrez deseado.
·
Dominio:
O =
determina si existe en la casilla un obstáculo
V o L
= toma estos valores en el caso que una casilla fue encuentre visitada o libre cuando
nunca fue visitada.
·
Restricciones:
1.
El
caballo sólo puede moverse en L.
2.
Xij
≠ Xi1 …. Xin = Restricción movimiento de columnas en la
misma fila
3.
Xij
≠ X1j …. Xnj = Restricción movimiento de filas en la
misma columna
4.
Xij
≠ Xi±k j±P (K = 0, 1, 2.. n, P= 0,1,2...n) Λ (K = P) – Restricción
movimiento en diagonal
5.
Xij
≠ Xi±k j±K (K = 0…n) Λ (i ≠ j) Λ (K > 2 ˅ K < 1) – Restricción
movimientos que no sean en L
1.
El
caballo no puede posicionarse sobre un obstáculo. (Xij != O)
2.
El caballo no puede posicionarse en una
casilla ya visitada. (Xij != V)
No hay comentarios:
Publicar un comentario