markovjunior

MarkovJunior es un lenguaje de programación probabilístico donde los programas son combinaciones de reglas de reescritura y la inferencia se realiza mediante propagación de restricciones. Lleva el nombre del matemático Andrey Andreyevich Markov, quien definió los algoritmos de Markov. En su forma básica, un programa de MarkovJunior es una lista ordenada de reglas de reescritura. Por ejemplo, el modelo MazeBacktracker usa dos reglas: `RBB=GGR` y `RGG=WWR`. En cada paso de ejecución, el intérprete encuentra la primera regla con una coincidencia en la cuadrícula, encuentra todas las coincidencias y aplica una aleatoria. El intérprete se detiene cuando ninguna regla coincide. La inferencia probabilística permite imponer restricciones sobre estados futuros, generando solo ejecuciones que conducen a futuros restringidos. Por ejemplo, la inferencia en las reglas de Sokoban hace que los agentes organicen cajas en formas especificadas. El repositorio incluye muchos generadores probabilísticos para mazmorras, arquitectura, rompecabezas y simulaciones. Los conceptos clave incluyen: - **Reglas de reescritura**: Reglas simples como `(B=W)` convierten cuadrados negros aleatorios en blancos. Reglas más complejas como `(WBB=WAW)` generan laberintos con una sola línea de código. Los comodines (`*`) permiten cualquier color en la entrada o salida sin cambios. - **Rulenodes**: Combinan múltiples reglas, por ejemplo, para caminatas aleatorias sin bucles o generación de laberintos Aldous-Broder. - **Nodos de secuencia**: Ejecutan rulenodes uno tras otro, por ejemplo, construyendo diagramas de Voronoi para valles fluviales. - **Nodos de Markov**: Permiten volver a nodos pasados, habilitando algoritmos como la generación de mazmorras de Bob Nystrom. - **Inferencia**: Utiliza propagación de restricciones (unidireccional o bidireccional) para conectar estados, con un parámetro de temperatura para la rigurosidad. Puede resolver rompecabezas como Sokoban o generar caminos hamiltonianos. Materiales adicionales incluyen una descripción general de la sintaxis XML, capturas de pantalla de mayor resolución y notas técnicas no oficiales. El proyecto discute problemas abiertos como la síntesis de programas para generación procedural y la síntesis de modelos a partir de ejemplos. Cita influencias de algoritmos de Markov, Imagegram, REFAL, mapas de Dijkstra y algoritmos clásicos como la búsqueda A*. El intérprete utiliza coincidencia de patrones rápida con un algoritmo multidimensional de Boyer-Moore y admite relajación estocástica para optimización basada en gradientes.