Un motor de ajedrez minimax de 2 plies implementado con 84,688 expresiones regulares

• Regex Chess es un motor minimax de 2 plies que elige una jugada legal y “no completamente terrible” en un tablero de ajedrez ejecutando en orden solo 84,688 sustituciones con expresiones regulares
• El estado combina pila y variables dentro de una sola cadena, y comandos como push, pop, consulta y asignación de variables se procesan mediante sustituciones con expresiones regulares
• La ramificación condicional se imita cambiando el marcador %%, que indica el estado activo, y gracias a la sustitución global se vuelve posible una ejecución paralela estilo SIMD que procesa varios estados a la vez
• El motor crea todas las jugadas legales como estados paralelos y evalúa incluso las respuestas del rival, pero no realiza una búsqueda depth-3 que verifique por completo la legalidad de esas respuestas
• Al principio tardaba unos 30 minutos en responder a una jugada, pero con eliminación de variables intermedias, optimización de matching, comandos de propósito específico y paralelización, la implementación final bajó a alrededor de 1 a 10 segundos según la posición

---

Estructura básica de Regex Chess

• Regex Chess compone todo el motor de ajedrez como una lista de 84,688 expresiones regulares
• Su estructura de ejecución es simple
  • Recorre la lista de expresiones regulares en orden
  • Aplica cada patrón y cadena de sustitución a la cadena que representa el estado actual del tablero
  • Muestra en pantalla el estado final
• La entrada no es PGN, sino un formato de coordenadas que concatena la casilla de origen y la de destino, como e2e4
• El código del proyecto está publicado en GitHub

Una CPU de expresiones regulares

• En lugar de escribir directamente las reglas del ajedrez con expresiones regulares, primero se construye una pequeña computadora que funciona con expresiones regulares
• Esta computadora usa un conjunto de instrucciones con ejecución condicional sin ramas, ejecución de una sola instrucción sobre múltiples datos, y manipulación de pila y variables
• El estado actual se representa como una sola cadena
  • %% indica el inicio del estado de ejecución activo
  • Debajo de #stack: se apilan los elementos de la pila
  • Las variables se guardan con el formato #variable: value

• Manipulación de pila y variables

  • push busca el encabezado %%\n#stack:\n e inserta un valor debajo de él para ponerlo en la cima de la pila
  • pop elimina una línea justo debajo de #stack: para quitar el valor en la cima de la pila
  • La consulta de variables busca #nombre_de_variable: dentro de la cadena de estado, copia el valor y lo agrega a la cima de la pila
  • La asignación de variables maneja tanto el caso en que la variable ya existe como el caso en que no existe
    • Si ya existe, reemplaza el valor anterior de la variable por el valor de la pila
    • Si no existe, agrega una nueva línea de variable
  • Usa marcadores temporales, como backticks, para evitar que la misma instrucción se vuelva a aplicar en un orden incorrecto

Ejecución condicional sin ramas y límite de bucles

• La ejecución condicional se implementa con cond(tag) y reactivate(tag)
• Si la cima de la pila es False, el marcador activo %% cambia a la forma %tag, por lo que las instrucciones posteriores no se aplican a ese estado
• Más adelante, reactivate(tag) vuelve a cambiar %tag a %% y activa ese estado
• Así se imita la ejecución condicional sin ramificación explícita
• Como el programa es una lista secuencial de expresiones regulares, no puede ejecutar bucles directamente
  • No puede realizar cómputo Turing-completo
  • Sin embargo, los cálculos acotados, como calcular la siguiente jugada en ajedrez, pueden manejarse desplegando los bucles

Ejecución paralela con sustitución global

• Como las sustituciones con expresiones regulares se aplican globalmente a toda la cadena, si se colocan varios estados de ejecución %% dentro de una misma cadena de estado, la misma instrucción se aplica a varios estados al mismo tiempo
• Por ejemplo, si hay dos enteros en cada una de dos pilas, al ejecutar binary_add() las dos sumas se realizan simultáneamente
• fork_inactive(tag) duplica el estado activo actual y deja la copia en un estado etiquetado inactivo
• fork_bool(variable) divide un estado en dos estados con valores True y False
• Esta estructura se usa en ajedrez para evaluar simultáneamente varios estados de tablero posibles, en vez de procesarlos uno por uno de forma iterativa

Macroensamblador y ejecución simbólica

• El motor no escribe a mano solo expresiones regulares directamente; usa un macroensamblador que convierte programas estilo Python en pequeñas secuencias de instrucciones
• Código estilo Python como fib() se transforma en una lista de instrucciones como push, lookup, binary_add y assign_pop
• En lugar de un parser y generación de código tradicionales, usa ejecución simbólica (symbolic execution)
  • Los objetos de variable no son diccionarios reales, sino objetos especiales que registran las operaciones realizadas
  • a = b + 1 se registra como lookup('b'), push(1), binary_add(), assign_pop('a')
• Las sentencias if registran tanto la ruta en que la condición es verdadera como la ruta en que es falsa, y luego las fusionan
  • Al encontrar una rama condicional, se crean dos rutas en el árbol de llamadas
  • Al rastrear varias veces, se elige la rama menos visitada para completar ambas rutas
  • El punto de fusión se convierte en una instrucción reactivate

Cómo se generan las jugadas de ajedrez

• Escribir el motor de ajedrez en sí se parece a escribir un motor de ajedrez en un lenguaje común, pero la clave es que procesa varios estados en paralelo
• La generación de movimientos de peones sigue este flujo
  • Encuentra todas las posiciones de peones blancos
  • Crea un estado paralelo para cada peón
  • Detiene el estado principal original y activa los estados por peón
  • Revisa simultáneamente, en todos los estados de peón, los candidatos de avanzar una casilla, avanzar dos casillas y capturar en diagonal
  • Vuelve a combinar la lista de jugadas candidatas de cada estado
• El ejemplo explicativo manipula directamente cadenas FEN, pero la implementación real expande el tablero de ajedrez en 64 variables, una por casilla, para leerlas y escribirlas
• Las piezas deslizantes como alfiles, torres y damas, así como el enroque y la captura al paso, también están implementadas por separado
• Los detalles de implementación están en chess_engine.py

Procesamiento de un turno y verificación de jugadas

• Un turno se procesa leyendo la jugada ingresada por el humano, verificando que sea legal y luego generando la respuesta de la computadora
• from_pretty_utf8_to_fen() convierte la visualización Unicode del tablero de ajedrez a notación FEN y extrae las casillas de origen y destino de la entrada
• La legalidad de la jugada humana no se verifica con código de reglas separado, sino generando todos los tableros legales siguientes y comparándolos
  • make_move crea un tablero aplicando la jugada ingresada
  • compute_legal_boards genera todos los tableros legales posibles desde la posición actual
  • fork_on_list separa cada tablero en un estado paralelo
  • Los estados distintos del resultado de aplicar la jugada ingresada se eliminan con destroy_active_thread()
• Si no hay jugada legal, toda la salida se reemplaza por el texto hardcodeado "Illegal Move"
• Para la respuesta de la computadora, crea los tableros de respuesta posibles de las negras y sus puntuaciones, y luego deja solo el tablero con mejor puntuación mediante keep_best_scoring_board(score)

Minimax de 2 plies y simplificación intencional

• compute_and_score_legal_boards cumple el papel central en la búsqueda minimax de profundidad 2
• Primero genera las jugadas candidatas que puede hacer la computadora y luego crea las posibles respuestas del rival para verificar si el rey podría ser capturado
• Como la verificación de jaque exige generar también las respuestas del rival, ya se forma una estructura de búsqueda de profundidad 2
• Cada posición candidata se evalúa con la puntuación que tendría si el rival hiciera su mejor respuesta
• No es un minimax completo de profundidad 2
  • No verifica si las respuestas del rival son jugadas ilegales por dejar a su propio rey en jaque
  • Para manejar eso por completo haría falta una búsqueda de profundidad 3, lo que aumentaría mucho el costo
• Las respuestas que genera la computadora en sí no son jugadas ilegales, pero en algunos casos puede elegir una respuesta más débil de lo real al considerar jugadas que el rival no podría hacer

Optimización de rendimiento

• La implementación inicial tardaba unos 30 minutos en generar una respuesta a una jugada humana
• La implementación final tarda alrededor de 1 a 10 segundos, según la posición, en la máquina del autor
• La mejora de unas 100 veces en velocidad es resultado de varias optimizaciones

• Eliminación de variables intermedias

  • Consultar una variable cuesta O(n) porque hay que buscar su valor en toda la cadena de estado
  • Al hacer fork de un estado de ejecución, las variables también se copian, aumentando el uso de memoria
  • Se reducen tiempo y memoria eliminando de forma agresiva las variables que ya no se necesitan y reutilizando nombres de variables
  • El estado interno de la evaluación de una jugada bajó de 10 GB antes de la optimización a unos 300 MB

• Optimización del matching de expresiones regulares

  • Solo incluir el carácter de nueva línea anterior en la expresión regular de limpieza de una instrucción condicional hizo que esa instrucción fuera aproximadamente 2 veces más eficiente
  • Como dentro del estado aparecen muchas cadenas True y False, los patrones deben limitarse para encontrar rápidamente solo el valor en la cima de la pila
  • Pequeñas diferencias en los patrones que reducen matches candidatos innecesarios afectan el tiempo total de ejecución

• Comandos de propósito específico y paralelización

  • Las partes lentas, como los bucles para encontrar posiciones de piezas, se combinaron en una sola instrucción especial de expresión regular en lugar de componer instrucciones existentes
  • En la generación de movimientos de torre, no revisa cada dirección secuencialmente, sino que crea varios estados paralelos para procesarlas de una vez
  • La evaluación de posiciones también se realiza creando estados paralelos para cada tablero candidato y ejecutándolos al mismo tiempo
  • La ejecución paralela es especialmente efectiva en tareas donde la misma operación se repite en muchos estados, como calcular el valor de las piezas

Implementaciones adicionales incluidas en el código fuente

• El código fuente también incluye elementos de implementación que no se explican en profundidad en el texto
  • Generación paralela de jugadas para piezas deslizantes como alfiles, torres y damas
  • Procedimiento para determinar “si una casilla está atacada” para el enroque
  • Conversión entre el tablero FEN y la representación con variables por casilla
  • Detección de derechos de enroque mediante el seguimiento de las posiciones del rey y las torres
  • Detección y seguimiento de la captura al paso
  • Alrededor de 2000 líneas de pruebas que verifican la precisión del motor a lo largo de miles de partidas
• Cierra diciendo que estos proyectos sin propósito práctico ayudan a aprender varios temas de ciencias de la computación fuera del propio campo
• También menciona como proyectos relacionados printf-tac-toe, que juega ta-te-ti con printf de C, y un clon de Doom en JavaScript de 13 kB

[GN⁺]

Opiniones de Hacker News

• Esto lo hizo la misma persona que demostró que printf() es Turing completo y que creó un shooter en primera persona en 13 kB de JavaScript
  https://github.com/HexHive/printbf
  https://github.com/carlini/js13k2019-yet-another-doom-clone

  • Al leer la frase “demostró que printf() es Turing completo y creó un shooter en primera persona…”, sinceramente pensé que iba a terminar diciendo que ese shooter también estaba implementado con printf
  • El diario de desarrollo de Doom es interesante por la cantidad de detalles: https://nicholas.carlini.com/writing/2019/javascript-doom-cl...
    El plazo para terminarlo en el concurso era de un mes, pero parece que pudo reutilizar código existente
    El trabajo en sí debe haber sido bastante divertido, y me da un poco de tristeza pensar que ahora, por la familia y el trabajo, jamás podría sacar un mes entero de tiempo libre para algo así
  • Me entusiasmé al leer “un shooter en primera persona en 13 kB de JavaScript”, pero me decepcioné un poco al enterarme de que usaba WebGL para renderizar los gráficos

• En este punto sentí que este trabajo pasó de ser una locura divertida a algo completamente extraordinario. El cálculo de múltiples posiciones posibles ocurría todo en paralelo, ejecutando expresiones regulares sobre un conjunto creciente de estados y variables; es decir, sobre hilos
  “Ahora viene mi parte favorita del lenguaje que creamos. ¡Gracias a la magia de las expresiones regulares y al hecho de que hacemos sustituciones globales sobre toda la cadena, podemos ejecutar múltiples hilos al mismo tiempo!”
  La conclusión también fue buena: “¿Qué esperas como conclusión de una entrada de blog como esta? No hay una conclusión en particular. Solo me gustaría que más gente hiciera cosas completamente inútiles como esta. Es realmente divertido, a nadie le importa cuánto tardes en terminarlo, a nadie le importa si funciona o no, y, de paso, terminas aprendiendo más de lo que querías sobre varias áreas de la informática fuera de tu campo.”
  Una actitud realmente genial

  • Cuando aparto todas las demás preocupaciones, me pregunto si yo también podría lograr algo así
    Lo que se obtiene aquí es la sensación de poder de no saber hasta dónde se puede llegar al sentarse y concentrar la mente en una sola cosa; y, al mismo tiempo, queda claro que el autor es una persona muy talentosa, hábil y creativa

• Parece que hay un bug en algún lado. La partida de abajo termina con “Illegal move, you lose” aunque no hay ninguna jugada ilegal

  1. e2e4, e7e5
  2. d2d4, e5d4
  3. d1d4, a7a5
  4. g1f3, b7b5
  5. b1c3, a5a4
  6. c3b5, a4a3
  7. b5a3, a8a3
  8. b2a3 -->
     Illegal Move
     You Lose.
     Game over.
     FEN de la partida anterior:
     1nbqkbnr/2pp1ppp/8/8/3QP3/P4N2/P1P2PPP/R1B1KB1R b KQk - 0 8
  • Si haces a2a3 como primera jugada, o a2a3 como segunda jugada después de e2e4, también aparece como jugada ilegal
    Pero ambas son legales, así que efectivamente es un bug
  • Lo mismo pasa incluso si solo haces a2a4 como primera jugada

• No le temo a quien juega ajedrez con 84,688 expresiones regulares, sino a quien juega ajedrez con una sola expresión regular

  • Si existe una heurística general para convertir en una forma lineal expresiones regulares aplicadas secuencialmente, es decir, una forma de combinar dos expresiones regulares arbitrarias en una sola, parece que podría aplicarse aquí
    Ayuda, me están haciendo nerd sniping
    El posible problema que se me ocurre de inmediato son las referencias inversas
    La expresión regular sería larguísima, pero en la práctica estaría codificando un motor de ajedrez, así que…

• Al ver cosas así, dan ganas de quitarse el sombrero y expresar un agradecimiento solemne a los verdaderos héroes de la humanidad

• Se corrigió el bug de movimiento en la columna a: https://github.com/carlini/regex-chess/issues/1

• Caso anterior: ajedrez escrito en sed https://news.ycombinator.com/item?id=6261314
  Claro que la versión en sed usa los comandos de flujo de control de sed y probablemente solo busca 1 jugada hacia adelante, así que en ese aspecto es bastante distinta de esta versión

• Esto no es solo un motor de ajedrez; también es haber creado una computadora y un lenguaje ensamblador usando únicamente expresiones regulares

• ¡Normalmente no pierdes tan rápido por empezar con a2a4!

  • Yo también encontré un bug parecido en la columna a. La secuencia fue e2e4-d2d4-d1d4-g1f3-f1b5-d4e5-e5c5-e1g1-b2a3

• Esto también vale la pena compararlo: https://codegolf.stackexchange.com/q/3503/32575

  • Todas las reglas para determinar divisibilidad son necesariamente lenguajes regulares, así que no es tan sorprendente. Si fueran más complejas, dejarían de ser “reglas” que una persona pueda ejecutar