Maackesgeist: Un Motor de Ajedrez para el Raumschach
Versión 2 — Un Motor Completamente Documentado con Búsqueda de Quietud, Tabla de Transposición, Profundización Iterativa, Búsqueda sin Asignación, Hash Incremental, Ventanas de Aspiración y Poda de Movimiento Nulo
El Raumschach — literalmente “ajedrez espacial” en alemán — fue inventado por Ferdinand Maack de Hamburgo y publicado por primera vez en 1907. Se juega en un tablero de 5×5×5 compuesto por cinco niveles de 5×5 apilados, e introduce dos piezas ausentes del ajedrez ortodoxo: el Alfil, restringido a las diagonales de cara, y el Unicornio, restringido a las diagonales espaciales (triagonales). La Reina combina las tres direcciones de deslizamiento del espacio tridimensional. A pesar de más de un siglo de atención teórica — documentada de manera más autorizada por Anthony Dickins (1914–1987) en A Guide to Fairy Chess (1969–71) — la oposición informática para el Raumschach ha permanecido subdesarrollada e infradocumentada.
Maackesgeist es el componente de IA de una implementación de Raumschach basada en el navegador, escrita íntegramente en JavaScript y ejecutable sin infraestructura de servidor. Este artículo documenta la Versión 2 del motor, una revisión sustancial del original. Se organiza de la siguiente manera: §2 corrige una afirmación de prioridad de la documentación de la Versión 1; §3 describe la representación del tablero y la geometría; §4 cubre la generación de movimientos; §5 presenta el algoritmo completo con pseudocódigo; §6 describe la función de evaluación; §7 identifica las debilidades actuales; y §8 propone mejoras para la Versión 3.
Maackesgeist Versión 1 no fue el primer oponente de IA públicamente jugable para el Raumschach. La mayoría han sido descritos como utilizadores de minimax con poda alfa-beta, y al menos uno fue presentado como usando un algoritmo personalizado para el Raumschach. Según el mejor conocimiento del autor, todos fueron introducidos sin publicar detalles de implementación, funciones de evaluación ni pseudocódigo.
En contraste, Maackesgeist es — según el mejor conocimiento del presente autor — el motor de Raumschach más completamente documentado, y el primero para el que se ha puesto a disposición pública una descripción técnica completa (incluyendo representación del tablero, geometría de direcciones, generación de movimientos legales, función de evaluación y el algoritmo de búsqueda completo con pseudocódigo). No se conoce ningún informe publicado sobre los internos de ningún otro motor de Raumschach. La ausencia de tal documentación en otras implementaciones hace imposible una comparación significativa de la fuerza de juego o la novedad algorítmica; Maackesgeist Versión 2 se presenta aquí en el espíritu de la reproducibilidad y el conocimiento abierto.
Cabe señalar también que Maackesgeist Versión 2 va considerablemente más lejos que el mero minimax con poda alfa-beta. Las incorporaciones de búsqueda de quietud, una tabla de transposición de Zobrist con hash incremental, profundización iterativa con ventanas de aspiración, poda de movimiento nulo, un árbol de búsqueda sin asignación (make/unmake a lo largo de todo el proceso, incluida la generación de movimientos legales), heurísticas de movimientos asesinos, una heurística de historial y evaluación de movilidad representan colectivamente un avance sustancial en la técnica documentada para este juego, independientemente de lo que los motores no documentados puedan haber implementado.
El tablero es un array JavaScript tridimensional board[l][r][f], donde l ∈ {0–4} indexa el nivel (A a E), r ∈ {0–4} la fila (1–5), y f ∈ {0–4} la columna (a–e). Cada celda ocupada contiene un objeto plano { type, color }. Para la lógica del juego (renderizado, ejecución de movimientos, verificación de legalidad), el tablero sigue clonándose mediante copia profunda. Dentro del árbol de búsqueda, sin embargo, la Versión 2 reemplaza todo el clonado con make/unmake en el lugar, como se describe en §5.1.
| Nombre | Cantidad | Descripción | Piezas |
|---|---|---|---|
| Ortogonal (RD) | 6 | ±1 a lo largo de exactamente un eje | Torre, Reina |
| Diagonal de cara (BD) | 12 | ±1 a lo largo de exactamente dos ejes | Alfil, Reina |
| Diagonal espacial (UD) | 8 | ±1 a lo largo de los tres ejes | Unicornio, Reina |
| Todas (QD) | 26 | Unión de las anteriores | Reina, Rey |
El Caballo se extiende a tres dimensiones mediante todas las permutaciones de (±2, ±1, 0), produciendo 24 direcciones de salto distintas. Todos los conjuntos de direcciones se precomputan como arrays constantes al inicio.
La generación de movimientos no ha cambiado respecto a la Versión 1 a nivel pseudolegal. pieceMoves genera movimientos pseudolegales para una sola pieza mediante ray-casting (piezas deslizantes) o enumeración de paso único (Rey, Caballo, Peón). allPseudo agrega sobre todas las piezas de un color dado. legalMoves filtra los movimientos pseudolegales usando make/unmake — aplica cada movimiento candidato en el lugar, comprueba si el Rey del bando que mueve está en jaque, y deshace el movimiento inmediatamente, sin producir asignaciones en el montón. isAttacked realiza un rastreo de rayos inverso para determinar si una casilla dada está atacada por un color dado. Todo el árbol de búsqueda, desde la raíz hasta la hoja de quietud, está ahora libre de asignaciones.
La Versión 2 reemplaza la copia del tablero basada en clonado dentro de la búsqueda por operaciones de make y unmake en el lugar. makeMove mueve el objeto pieza directamente en el array del tablero y devuelve un registro de deshacer {captured, origType, piece} suficiente para revertir la operación. unmakeMove restaura el tablero a su estado anterior usando ese registro. La promoción se gestiona reemplazando el objeto pieza; unmake restaura el original.
Un generador lineal congruente determinista (semilla 0xDEADBEEF, multiplicador 1664525, sumando 1013904223) produce 1.750 claves pseudoaleatorias de 32 bits: una por triple (tipo de pieza × color × casilla), más una para el bando que mueve. El hash raíz se calcula desde cero una vez por decisión de movimiento iterando las 125 celdas. Todos los hashes subsiguientes dentro del árbol de búsqueda se actualizan incrementalmente en O(1): hashMove elimina mediante XOR la pieza que mueve en su origen, elimina mediante XOR cualquier pieza capturada en el destino, incorpora mediante XOR la pieza que mueve (o su promoción) en el destino, y conmuta la clave del bando. Unmake no requiere trabajo de hash porque el hash padre simplemente se pasa hacia abajo en la pila de llamadas y el hash hijo se descarta cuando la llamada recursiva retorna.
Un array plano de 131.072 entradas (217) sirve como tabla de transposición, indexado por hash & TT_MASK. Cada entrada almacena el hash, la profundidad de búsqueda, la puntuación, un indicador (EXACT / LOWER / UPPER) y el mejor movimiento encontrado en ese nodo. La política de reemplazo es por profundidad preferida: una nueva entrada reemplaza a una existente solo si fue calculada a una profundidad mayor o igual.
Los movimientos se puntúan y ordenan en orden descendente antes de ser explorados. La pila de prioridades es:
| Prioridad | Condición | Puntuación |
|---|---|---|
| 1 | Mejor movimiento de la TT | 2.000.000 |
| 2 | Captura (MVV/LVA: valor víctima × 10 − valor atacante) | 1.000.000 + Δ |
| 3 | Movimiento asesino ranura 0 en la capa actual | 900.000 |
| 4 | Movimiento asesino ranura 1 en la capa actual | 890.000 |
| 5 | Heurística de historial (profundidad² acumulada en cortes beta) | 0 – 32.000 |
Los movimientos asesinos se almacenan por capa en un array de dos ranuras; cada corte beta en un movimiento tranquilo promueve ese movimiento a la tabla de asesinos e incrementa su puntuación de historial. La tabla de historial se envejece (se divide a la mitad) entre llamadas a la raíz para favorecer la experiencia de búsqueda reciente.
En profundidad cero, en lugar de llamar directamente a evalBoard, la búsqueda entra en quietud. La búsqueda de quietud calcula una puntuación stand-pat a partir de la evaluación estática, luego extiende la búsqueda a través de todas las capturas disponibles (hasta 6 capas adicionales) hasta que no queden capturas. Esto elimina el efecto horizonte: el motor ya no confunde una posición tácticamente inestable con una tranquila simplemente porque se encuentra en el límite nominal de búsqueda.
La búsqueda recibe el hash del tablero actual como parámetro en lugar de recalcularlo en cada nodo. Cada llamada recursiva deriva el hash hijo mediante hashMove (O(1)). La poda de movimiento nulo se aplica antes del bucle de movimientos: si la posición no está en jaque, no es solo Rey-y-Peones (lo que arriesgaría un corte de zugzwang espurio), y la profundidad restante es al menos 3, el motor concede al adversario un movimiento gratuito conmutando la clave del bando sin alterar el tablero, luego busca a profundidad−3 con una ventana de ancho de un movimiento. Un corte a esta profundidad reducida indica que la posición ya es suficientemente fuerte para que la búsqueda completa sea innecesaria. El indicador nullOk previene movimientos nulos consecutivos.
Cada pasada de profundidad está envuelta en una ventana de aspiración estrecha centrada en la puntuación devuelta por la pasada anterior. Para profundidad 1, se usa una ventana completa [−∞, +∞] dado que no existe puntuación previa. Para profundidad 2 en adelante, la ventana es [puntuaciónAnterior−50, puntuaciónAnterior+50]. Si la búsqueda devuelve una puntuación fuera de esa ventana (un fallo bajo o fallo alto), la pasada se vuelve a buscar inmediatamente a ancho completo. La búsqueda a ancho completo se beneficia del mejor ordenamiento de movimientos y las entradas de la TT depositadas por la búsqueda estrecha fallida, por lo que su coste es modesto. El hash raíz se calcula una vez desde cero; todas las llamadas recursivas derivan los hashes hijos incrementalmente mediante hashMove.
| Nivel | Nombre | Profundidad Máx. | Característica |
|---|---|---|---|
| 0 | Principiante | 0 | Movimiento legal aleatorio; sin búsqueda |
| 1 | Débil | 2 | Profundización iterativa a 2 capas + quietud |
| 2 | Intermedio | 3 | Profundización iterativa a 3 capas + quietud |
| 3 | Fuerte | 4 | Profundización iterativa a 4 capas + quietud |
| 4 | RSM | 5 | Profundización iterativa a 5 capas + quietud |
| 5 | GRSM | 6 | Profundización iterativa a 6 capas + quietud |
La función de evaluación devuelve una puntuación en unidades de centipeones desde la perspectiva de Blancas. Combina material, bonificaciones de centralidad, ajustes posicionales específicos de cada pieza y un término de movilidad.
El hash de Zobrist verdadero, tal como se describe en el artículo original de 1970, usa claves aleatorias de 64 bits para hacer que las colisiones de hash sean negligiblemente raras. Maackesgeist usa claves de 32 bits porque los enteros nativos de JavaScript son de 32 bits. Con una tabla de 217 entradas y claves de 32 bits, la probabilidad de una colisión espuria — donde dos posiciones diferentes comparten el mismo índice de hash y el mismo fragmento de clave de 32 bits — no es despreciable a lo largo de una partida larga. Las colisiones hacen que el motor devuelva una puntuación en caché para la posición incorrecta, potencialmente corrompiendo la búsqueda. La emulación de 64 bits mediante dos enteros de 32 bits (como la usada por motores como Stockfish en sus puertos JavaScript puros) reduciría dramáticamente el riesgo de colisiones.
La política de reemplazo actual (preferencia por profundidad: reemplazar solo si la nueva entrada es al menos tan profunda) tiene una patología conocida: permite que entradas antiguas y profundas de posiciones anteriores persistan y bloqueen entradas más nuevas, más superficiales pero más relevantes para la posición actual. En la práctica, los motores usan esquemas de reemplazo híbridos — por ejemplo, un sistema de dos cubos con una ranura de reemplazo siempre y una ranura de profundidad preferida — para garantizar que la TT permanezca actualizada sin descartar resultados profundos valiosos.
Las reducciones de movimientos tardíos (LMR) aplican una profundidad de búsqueda reducida a los movimientos que aparecen tarde en la lista de movimientos ordenada, bajo el razonamiento de que los movimientos bien ordenados dejan solo movimientos pobres o irrelevantes hacia el final y estos no requieren verificación de profundidad completa. LMR es una de las técnicas individuales más efectivas en el diseño de motores de ajedrez modernos y está ausente de Maackesgeist.
La búsqueda de quietud en la Versión 2 se extiende solo en capturas. Las evasiones de jaque y los movimientos de jaque, que pueden ser tan tácticamente forzados como las capturas, no se exploran en la búsqueda de quietud. Esto significa que una posición en la que el adversario se ve obligado a lidiar con un jaque inmediato — pero donde no hay capturas involucradas — puede ser evaluada erróneamente en la hoja. Extender la quietud en los jaques (con un límite de profundidad para prevenir la explosión) mejoraría la precisión en posiciones tácticas que involucran sacrificios y secuencias de jaque forzado.
La poda delta es una optimización específica de la quietud: si incluso capturar la pieza disponible más valiosa no puede elevar la puntuación por encima de alfa, la posición es desesperada y se omite la búsqueda de capturas adicionales. Sin la poda delta, la búsqueda de quietud explora capturas que no tienen ninguna posibilidad de mejorar la puntuación, desperdiciando tiempo en intentos de captura claramente perdedores.
La función de evaluación ahora incluye material, centralidad, bonificaciones específicas de piezas y movilidad, pero sigue siendo ciega a la seguridad del Rey, la estructura de peones y la conciencia de la fase del juego. El motor no tiene incentivo para evitar exponer a su Rey más allá de lo que impone la detección de jaque en las hojas. Los peones doblados, aislados y pasados no son reconocidos. Los valores y pesos de las piezas no se ajustan a medida que el juego transita de la apertura al mediojuego y al final.
El motor juega la apertura desde cero en cada partida, sin una biblioteca de secuencias de apertura sólidas. Esto hace que su juego inicial parezca aleatorio y a menudo sea estructuralmente débil respecto a incluso un modesto libro de aperturas. En el final, las tablas de finales podrían proporcionar juego perfecto en posiciones con pocas piezas; el motor depende actualmente completamente de la búsqueda, que a 4 capas de profundidad puede no encontrar el plan ganador correcto en posiciones que requieren técnica precisa.
Los niveles de dificultad corresponden a profundidades de búsqueda fijas. El motor no se adapta a la cantidad de tiempo que queda en el reloj. Un jugador que usa el control de tiempo Clásico (90+30) puede enfrentarse al motor Fuerte y experimentar reflexión lenta; un jugador en Rápidas (5+3) se enfrenta al mismo motor Fuerte jugando a la misma profundidad, independientemente de la presión de tiempo. Una capa de gestión del tiempo que asigne una fracción del tiempo restante del reloj a cada movimiento, y termine la profundización iterativa cuando ese presupuesto se agote, sería una mejora práctica sustancial.
Las mejoras están ordenadas por impacto estimado.
Prioridad 1 (máxima): Tabla de transposición de dos cubos. Mantener dos entradas por ranura de la TT: una de profundidad preferida (el comportamiento actual) y una de reemplazo siempre. Esto mantiene la tabla ágil sin sacrificar resultados profundos.
Prioridad 2: Poda delta en la búsqueda de quietud. Antes de explorar una captura, comprobar si incluso la ganancia material máxima posible puede elevar la puntuación por encima de alfa; si no, omitir el movimiento. Esto elimina las búsquedas de captura claramente inútiles.
Prioridad 3: Extensiones de jaque en la búsqueda de quietud. Extender la búsqueda de quietud cuando el bando que mueve está en jaque, hasta una pequeña profundidad adicional (2 capas). Esto previene la evaluación errónea de posiciones donde la única secuencia forzada implica jaques sin capturas.
Prioridad 4: Reducciones de movimientos tardíos. Después de los primeros movimientos en cada nodo, reducir la profundidad de búsqueda para los movimientos clasificados bajo en la lista ordenada. Volver a buscar a profundidad completa solo si la búsqueda reducida eleva alfa. LMR es una de las técnicas más efectivas en el diseño de motores modernos y escala bien con el alto factor de ramificación del árbol de búsqueda 3D del Raumschach.
Prioridad 5: Gestión del tiempo. Reemplazar la búsqueda de profundidad fija por un bucle de profundización iterativa que termine cuando se agote el presupuesto de tiempo por movimiento. Asignar tiempo dinámicamente en función del reloj restante y los movimientos estimados hasta el control, con tiempo adicional para posiciones donde la puntuación de la iteración anterior fluctuó significativamente.
Prioridad 6: Claves de Zobrist de 64 bits. Emular enteros de 64 bits usando pares de valores de 32 bits (o adoptar BigInt) para reducir la probabilidad de colisión de hash a niveles despreciables.
Maackesgeist Versión 2 representa un avance sustancial sobre la Versión 1. La incorporación de la búsqueda de quietud elimina la clase más grave de errores tácticos. La tabla de transposición de Zobrist previene la computación redundante entre transposiciones, y su hash se mantiene ahora incrementalmente en O(1) por nodo en lugar de recalcularse desde cero. La profundización iterativa con ventanas de aspiración proporciona un mejor ordenamiento de movimientos en cada profundidad mientras poda sustancialmente más nodos en las pasadas estrechas. La poda de movimiento nulo entrega un bono aproximado de profundidad efectiva de dos capas con un coste mínimo. El sistema de ordenamiento de tres niveles (MVV/LVA, movimientos asesinos, heurística de historial) mejora adicionalmente la eficiencia de la poda alfa-beta. El término de movilidad añade una señal posicional significativa más allá del material y la centralidad. El make/unmake en el lugar — ahora aplicado a lo largo de toda la búsqueda, incluida la generación de movimientos legales — hace que el árbol de búsqueda sea completamente libre de asignaciones.
Al mismo tiempo, las debilidades identificadas en §7 son reales. Las más urgentes son la ausencia de reducciones de movimientos tardíos, poda delta en la búsqueda de quietud y extensiones de jaque. Más allá de eso, la ausencia de gestión del tiempo, una tabla de transposición de dos cubos y claves de Zobrist de 64 bits deja a la Versión 2 por debajo de lo que es alcanzable dentro de las restricciones de una implementación en un solo archivo nativa del navegador. La Versión 3 debería abordar al menos las primeras cuatro prioridades de §8.
Entre los motores de Raumschach documentados — la única clase sobre la que es posible la comparación — Maackesgeist sigue siendo la implementación técnicamente más detallada en el registro público. Se ofrece con la esperanza de que una mayor documentación de la computación del Raumschach, por este y otros autores, traiga finalmente al ajedrez tridimensional el rigor analítico que una centuria de literatura teórica siempre ha merecido.