markovjunior

MarkovJunior 是一种概率编程语言，程序由重写规则组合而成，推理通过约束传播执行。它以定义马尔可夫算法的数学家 Andrey Andreyevich Markov 命名。在基本形式中，MarkovJunior 程序是一个有序的重写规则列表。例如，MazeBacktracker 模型使用两条规则：`RBB=GGR` 和 `RGG=WWR`。在每个执行步骤中，解释器在网格上找到第一条存在匹配的规则，找出所有匹配，并随机应用其中一个。当没有规则匹配时，解释器停止。 概率推理允许对未来状态施加约束，只生成那些会通向受约束未来的运行。例如，Sokoban 规则中的推理使智能体将板条箱整理成指定形状。该仓库包含许多用于地牢、建筑、谜题和模拟的概率生成器。 关键概念包括： - 重写规则：像 `(B=W)` 这样的简单规则会将随机黑格转换为白格。像 `(WBB=WAW)` 这样更复杂的规则可用一行代码生成迷宫。通配符 `*` 允许输入中为任意颜色，或在输出中保持不变。 - Rulenodes：组合多条规则，例如用于环路消除随机游走或 Aldous-Broder 迷宫生成。 - Sequence nodes：依次运行 rulenodes，例如为河谷构建 Voronoi 图。 - Markov nodes：允许返回过去的节点，从而支持 Bob Nystrom 的地牢生成等算法。 - 推理：使用约束传播（单向或双向）连接状态，并通过 temperature 参数控制严格程度。它可以求解 Sokoban 等谜题，或生成哈密顿路径。 附加材料包括 XML 语法概述、更高分辨率的屏幕截图和非官方技术说明。该项目讨论了一些开放问题，例如面向程序化生成的程序综合，以及从示例进行模型综合。它引用了来自马尔可夫算法、Imagegram、REFAL、Dijkstra maps 以及 A* 搜索等经典算法的影响。解释器使用多维 Boyer-Moore 算法进行快速模式匹配，并支持用于基于梯度优化的随机松弛。