Yo, jugando al ajedrez con mi hijo, quien suele ganarme
MATE DE ALFIL Y CABALLO
En 1999, programé un solucionador de ajedrez para el mate de alfil y caballo, algo que yo nunca había visto antes. Hablé de eso en un post anterior. Algunas personas me pidieron que hablara un poco sobre el algoritmo que usé, así que trato de explicarlo aquí.
En aquellos días, me llamó la atención que algunos programas de ajedrez, que eran muy fuertes, no resolvían este problema y se tardaban mucho en analizar un final de alfil y caballo. Yo Pensé: "¿por qué?, ¿qué tan difícil puede ser incluir todas las soluciones de los finales conocidos dentro del programa, para no perder tiempo pensando? Obtener todas esas soluciones debería ser fácil si estamos hablando de solo cuatro piezas sobre el tablero".
¿Fácil? ¿En serio?
Sí, por supuesto.
Yo estaba seguro de eso.
Primero, debemos averiguar de cuántas posiciones estamos hablando.
Eso es fácil: Son 64 casillas y 4 piezas:
644 = 64 x 64 x 64 x 64 = 16777216 (un número hermoso para programadores).
Así hemos definido, claramente, los límites de este universo. Ahora sabemos de cuántas maneras distintas se pueden colocar sobre el tablero un rey blanco, un alfil blanco, un caballo blanco, y un rey negro. El valor 16777216 incluye un número aún indeterminado de posiciones no válidas (ejemplo: dos o más piezas en la misma casilla) pero eso podemos manejarlo después.
ESTRUCTURA BÁSICA PARA BUSCAR LAS RESPUESTAS
Observe la imagen:
Esos 24 bits se van a utilizar para recorrer ordenadamente todas las posiciones. Cualquier posición de ajedrez de cuatro piezas se puede representar usando un número entero. Solo necesitamos tres bytes, pero en mi programa usé un número entero de cuatro bytes. La variable Posición es un entero largo de cuatro bytes.
Observe este código, simple pero poderoso:
For Posicion = 0 to 16777215
Marca_Posicion_como(32) 'Aún sin resolver
Next
Do
For Posicion = 0 to 16777215
if No_Valida(Posicion) then Marca_Posicion_como(0): break
if Es_Posible_Ganar(Posicion) then Marca_Posicion_como(Mejor_Jugada): break
if Mate_en_Zero(Posicion) then Marca_Posicion_como(30): break
if Tablas(Posicion) then Marca_Posicion_como(31): break
Next
Repeat Until No_Mas_Cambios_En_Las_Soluciones
El código anterior es la estructura básica que resuelve el problema, encuentra todas las soluciones para el jaque mate de alfil y caballo. Todas las soluciones pueden guardarse en un archivo con un tamaño de 16777216 bytes (un byte por respuesta). Es posible reducir ese tamaño a menos de la octava parte de eso, pero no lo voy a explicar aquí, pues haría esto innecesariamente largo.
Fuera de este código, todo debería ser fácil de inferir. Permítanme explicarles un poco los trabajos que realizan las funciones que usé:
NO_VALIDA
Una posición es no válida cuando:
- Dos piezas están en la misma casilla.
- Los reyes están en casillas adyacentes.
- Las negras están en jaque pero no en jaque mate
(recuerde: siempre es el turno de las blancas).
ES_POSIBLE_GANAR
Aquí comprobamos si alguna de las jugadas disponibles pone al rey negro en jaque mate o lo obliga a ir otra posición ya marcada como Es_Posible_Ganar. A cada jugada disponible se le debe dar un valor. Los valores de Mejor_Jugada van de 1 a 29, siendo 29 el número máximo de jugadas posibles con caballo (8 jugadas), alfil (13 jugadas) y rey (8 jugadas).
MATE_EN_ZERO
En la posición el rey negro ya está en jaque mate.
TABLAS
La posición es tablas cuando:
- El rey negro está ahogado.
- Todas los jugadas disponibles conducen al ahogo del rey negro (empate por ahogo) o a la pérdida de una pieza (empate por insuficiencia de material).
(Ahora sé que solo hay 39 posiciones donde el ahogo o la pérdida de una pieza son inevitables)
Sencillo, simple y en extremo poderoso.
Si observa con cuidado, tal vez descubra que esto se puede usar para resolver cualquier final de cuatro piezas.
Puede ser que omití algo. Traté de mantenerlo corto.
Que vengan las preguntas para lo que no esté claro.
Créditos de texto e imágenes: Amaponian Visitor (