Motor de ajedrez minimax implementado con expresiones regulares

Motor de ajedrez minimax de 2 capas

• Ajedrez y expresiones regulares: El autor creó un programa para jugar ajedrez usando solo expresiones regulares. Este programa consta de 84.688 expresiones regulares que, a partir de un tablero de ajedrez, generan movimientos válidos.

• Diseño de CPU con expresiones regulares: Diseñó una CPU con expresiones regulares para ejecución sin condiciones y un conjunto de instrucciones SIMD (Single Instruction, Multiple Data). Esto permite escribir un programa que juega al ajedrez.

• Estructura de datos: El estado actual de la computadora se representa como una sola cadena que incluye la pila del programa y todas las variables. Cada instrucción manipula variables de la pila o realiza operaciones de lectura/escritura en una variable específica.

• Operaciones básicas de la pila:

  • Instrucción PUSH: Añade un valor a la parte superior de la pila.
  • Instrucción POP: Elimina el elemento superior de la pila.

• Instrucciones variable <-> pila:

  • Consultar variable: Carga el contenido de una variable en la parte superior de la pila.
  • Asignar variable: Asigna un valor a una variable, actualizándola si ya existe o creando una nueva si no.

• Condicionales: Los condicionales controlan el flujo del programa. Dependiendo de la condición, activan o desactivan partes específicas del programa.

• Imposibilidad de bucles: Como las expresiones regulares por sí solas no permiten implementar bucles, todos los cálculos iterativos deben desplegarse por adelantado.

• Ejecución multihilo: Aprovecha la sustitución global de expresiones regulares para ejecutar varios hilos simultáneamente.

• Creación del motor de ajedrez: El motor de ajedrez se escribe de forma similar a otros lenguajes de programación y funciona con rapidez gracias al procesamiento en paralelo.

• Turno de juego:

  • Leer la jugada del jugador: Lee la jugada ingresada y verifica su validez.
  • Generar la respuesta de la computadora: Genera todas las respuestas posibles y selecciona la mejor jugada.

• Búsqueda minimax: Elige el mejor movimiento mediante una búsqueda minimax de profundidad 2. Este proceso se realiza de forma eficiente con paralelismo.

Este proyecto es un ejemplo de cómo implementar un motor de ajedrez mediante un uso poco común de expresiones regulares, y demuestra tanto el poder de las expresiones regulares como un diseño de cómputo creativo.

[GN⁺]

Opinión en Hacker News

• Este desarrollador es la misma persona que demostró que printf() es Turing-completo y escribió un juego de disparos en primera persona de 13kB en JavaScript

  • Enlace de GitHub: printf() Turing-completo
  • Enlace de GitHub: Juego de JavaScript de 13kB

• Este proyecto destaca por calcular posiciones alternativas en paralelo

  • Puedes ejecutar múltiples hilos al mismo tiempo usando expresiones regulares

• No tengo nada específico para agregar a la conclusión del blog, pero me gustaría que más personas intentaran este tipo de proyectos que parecen una locura

  • Es divertido, no hay presión por el tiempo de entrega ni por si tendrá éxito, y puedes aprender muchísimo sobre muchos campos de la ciencia de la computación

• En el juego de ajedrez hay un error de “movimiento ilegal, derrota”

  • En una partida de ejemplo, el juego termina aunque la jugada no sea ilegal

• Darle al ajedrez con una sola expresión regular da más miedo que hacerlo con 84.688 expresiones regulares

• Este tipo de proyectos me gustaría que se reconozca con respeto

• Se corrigió un error relacionado con movimientos en la columna a

  • Enlace de GitHub: corrección de error

• Este proyecto no es solo un engine de ajedrez, sino una computadora y un lenguaje ensamblador construido solo con expresiones regulares

• Hubo anteriormente un proyecto de ajedrez escrito en sed

  • La versión en sed usa instrucciones de control de flujo y busca solo 1 ply

• No se rinde tan rápido al empezar con a2a4

• Intentar algo sin un objetivo claramente “productivo” puede llevar a descubrir nuevas formas y provocar innovación

  • El motor pierde piezas al inicio
  • Si introduces mayúsculas, se marca como movimiento ilegal

• Estoy en el intento de innovar y convertirlo en algo productivo