MarkovJunior

MarkovJunior

MarkovJunior是一种概率的编程语言，其中程序是重写规则的组合，并且通过约束传播执行推理。 MarkovJunior以数学家Andrey Andreyevich Markov的名字命名，后者定义和研究了现在所谓的Markov算法。

MarkovJunior程序以其基本形式是重写规则的有序列表。例如，Mazebacktracker（下面左侧的动画）是2个重写规则的列表：

1. RBB=GGR或“用绿色绿色红色代替红黑色”。
2. RGG=WWR或“用白色红色代替红绿色绿色”。

在每个执行中，步骤MJ解释器都会在网格上找到匹配的列表中的第一个规则，找到该规则的所有匹配项，并将该规则应用于随机匹配。在迷宫回溯示例中，解释器首先应用了一堆RBB=GGR规则。但是最终，绿色的自我避免行走被卡住了。在这一点上，第一个规则没有匹配，因此解释器应用第二个规则RGG=WWR直到步行消除为止。然后，它可以再次应用第一个规则，依此类推。当没有任何规则的匹配项时，解释器会停止。

MarkovJunior中的概率推论允许对未来状态施加限制，并仅生成那些导致未来约束的运行。例如，Sokoban规则中的推断{RWB=BRW RB=BR}使一组（红色）代理组织（白色）板条板成指定形状。

使用这些想法，我们构建了许多概率的发电机，建筑，难题和有趣的模拟。

其他材料：

1. XML语法概述。
2. 更高分辨率的屏幕截图和更多种子：现代房屋，海上，公寓，carmatower，Escheresque，Pillarsofernity，Surface，nots。
3. 丹·奥格尔斯（Dan Ogles）的非正式技术说明和安德鲁·凯（Andrew Kay）的代码文档。

马尔可夫算法

字母A上的Markov算法是规则的有序列表。每个规则都是x=y的字符串，其中x和y是A中的单词，并且某些规则可以标记为停止规则。 Markov算法在一个单词w中的应用如下：

1. 找到第一个规则x=y其中x是w的子字符串。如果没有这样的规则，那就停止。
2. 将最左侧的x替换为w y
3. 如果发现的规则是停止规则，则停止。否则，转到步骤1。

例如，考虑字母{0, 1, x} （ε是空的单词）中的Markov算法：

 1=0x
x0=0xx
0=ε

如果我们将其应用于字符串110我们会得到一系列字符串：

 110 -> 0x10 -> 0x0x0 -> 00xxx0 -> 00xx0xx -> 00x0xxxx -> 000xxxxxx -> 00xxxxxx -> 0xxxxxx -> xxxxxx

通常，该算法将数字的二进制表示形式转换为其一单位表示。

马尔可夫的学生Vilnis Detlovs证明，对于任何图灵机来说，都存在计算相同功能的马尔可夫算法。相比之下，语法是无序的重写规则集，L系统是并行应用的重写规则。有关Markov算法的更有趣的示例，请查看Markov的书，或在Wikipedia上的评论部分或乘法示例中查看最大的常见示例。

一个人如何将马尔可夫算法概括为多个维度？首先，在多个维度上，没有自然的方法将字符串插入另一个字符串中，因此我们重写规则的左侧和权利应具有相同的大小。其次，没有自然的方法可以选择最左边的匹配。可能的选项是：

• 选择一个随机匹配。这就是MJ (exists)节点的作用。
• 选择所有匹配。但是，此选项存在问题，因为不同的匹配可以重叠并有冲突。可能的解决方案是：
  • 贪婪地选择了非冲突匹配的最大子集。这就是MJ的{forall}节点所做的。
  • 考虑叠加中的所有匹配。也就是说，代替单独的值，请在每个网格单元格中保留波浪 – 布尔值向量，这些矢量辨认了哪些时空模式是禁止的，哪些不是。这就是MJ执行推理的方式。

我们失去了整理完整性，因为我们的新程序不是确定性的，但是实践表明，这种形式主义仍然可以描述大量有趣的随机过程。

重写规则

最简单的MarkovJunior程序可能是(B=W) 。它仅包含一个规则B=W 。在每个回合中，此程序都会将一个随机的黑色正方形转换为白色正方形。

（B = W）| （WB = WW）| （WBB = WAW）| （WBB = WAW）

增长模型(WB=WW)更有趣。在每个回合上，它都用白色白对WW代替了黑白对相邻的细胞BW 。换句话说，在每个转弯处，都会选择一个与某些白色细胞相邻的随机黑细胞，并将其染成白色。该模型几乎与伊甸园的增长模型相同：在每个转弯上，两个模型都可以在同一组黑细胞中选择。它们仅在概率分布方面有所不同：与白细胞相邻的黑细胞上的均匀分布与相邻黑白细胞对上的均匀分布不同。

模型(WBB=WAW)生成一个迷宫，并具有一行代码！将其与传统语言的实现进行比较。任何MarkovJunior模型都可以在任何数量的维度上运行，而无需更改。在右边，您可以看到3D中迷宫的最终结果，并在MagicAvoxel中呈现。默认情况下，我们使用PICO-8调色板：

模型(RBB=WWR)是一个自我避免的随机步行。请注意，在3D中的自我避免步行的平均时间比2D中的时间更长。通常，比较不同维度中相似随机过程的行为是一个引人入胜的话题。乔治·波利亚（GeorgePólya）的经典结果说，2D的随机步行以概率为一，而在3D中不再是这种情况。

（RBB = WWR）| LooperasatedWalk | （rb = wr rw = wr）

我们可以将几个规则纳入一个Rulenode 。例如， (RBB=WWR RBW=GWP PWG=PBU UWW=BBU UWP=BBR)是一个基于循环的随机步行。步道模型(RB=WR RW=WR)生成不错的连接洞穴。

模型(RBB=WWR R*W=W*R)被称为Aldous-Broder迷宫生成算法。输入中的通配符符号*意味着任何颜色都可以在正方形中。输出中的通配符符号意味着颜色在应用规则后不会改变。例如，Aldous-Broder算法平均需要更多的弯曲来产生迷宫，例如，它具有迷宫之有的不错的属性，而迷宫的属性没有：每个迷宫都有相同的概率生成的概率。换句话说，Mazetrail是一种无偏见的迷宫产生算法，或者它以均匀分布的形式采样迷宫（或跨越树）。威尔逊的算法是一种更有效的无偏迷宫生成算法。将其MarkovJunior实施与传统语言的实现进行比较！

结合核

我们可以将几个lulenodes放入一个序列节点中，将接一个地运行。在河流模型中，我们首先构建了带有2个来源的随机Voronoi图，并将形成区域之间的边界用作河流的基础。然后，我们产生了更多的Voronoi种子，以种植森林，同时从河中种植草。结果，我们得到了随机的河谷！

在公寓中，我们从WFC节点开始，然后使用rulenodes进行建设性的后处理：

1. 准备约束：标记带有单独的底部颜色的底部单元格，用单独的边框颜色标记剩余的边框单元（侧面和顶部）。边框电池应映射到空，底部单元应映射到除向下以外的所有图块。
2. 运行WFC路径瓷砖以生成封闭的台阶周期。
3. 随机化光源。
4. 从扁平瓷砖的角落掉落柱。
5. 缩回双柱，接触地面的列和触摸楼梯的柱，除了从转弯砖的角生长的柱。
6. 在相邻列之间生长窗户。
7. 将窗户合并为更大的矩形。我们以几个步骤进行操作：
   1. 当窗口拐角触摸窗口中点时，检测窗户的不平衡图案。
   2. 标记这些图案，并通过窗户侧面的整个长度传播标记。
   3. 合并未标记的窗户侧面。
8. 将剩余的1×1窗口变成墙壁。

结合节点的一种更有趣的方法是将它们放入马尔可夫节点。 Markov节点大大扩展了我们可以做的事情，因为它们允许返回过去的节点。当Markov节点处于活动状态时，解释器会找到与它匹配和应用它的第一个子节点。在下一个回合中，它再次找到列表中的第一个匹配节点，依此类推。 Markov节点使用的最简单示例是Mazebacktracker在顶部部分中解释。

鲍勃·尼斯特罗姆（Bob Nystrom）的《地牢世代》算法是我最喜欢的促进MarkovJunior发展的例子之一。如下：

1. 绘制网格{PBB=**P} 。
2. 产生一堆房间(room.png) 。
3. 在其余的网格上产生迷宫。我们可以使用任何迷宫的生成算法，但是迷宫式带路是首选的，因为它产生的分支更少。
4. 使所得的房间和走廊的配置连接。可以使用马尔可夫节点({GWW=**G}(GBW=*WG))优雅地完成。
5. 进行一些额外的连接(GBG=*W* #5) ，因此生成的地牢具有周期。没有循环的地牢非常无聊，因为玩家必须通过已经探索的区域返回。
6. 缩回死端{BBB/BWB=BBB/BBB} 。

像Refal一样，Markov节点可以嵌套：一旦进入子节点，我们就会忽略外部节点，直到子分支完成为止。

推理

MarkovJunior中的概率推论允许对未来状态施加限制，并仅生成那些导致未来约束的运行。换句话说，推理将2个给定状态（或部分观察到的状态）与一系列重写规则联系起来。

推理使用的最简单示例是将2点与路径连接。在自我避免的步行模型(RBB=WWR)中，我们可以在网格上观察一个给定的正方形，以变成R 。然后，口译员只会产生那些通向观察到的正方形的步行。我们可以将解释器设置为更严格或严格地通过改变温度参数来遵循目标。默认情况下，温度设置为零。

最冷|冷|热|最热

我们可以做的另一件事是观察所有奇怪的网格正方形变成白色或红色。然后，口译员将产生避开整个网格的自我避免的步行。

我们可以参与任何重写规则。例如，楼梯绘画规则的推断与阶梯路径连接2分。规则R**/**B=B**/**R的推断产生了国际象棋骑士可以采取的路径。越野模型中的推断将2点与一条路径联系起来，考虑到地形成本。 Sokoban规则集的推断{RB=BR RWB=BRW}解决了索科班难题，甚至是多种索科班拼图！

MarkovJunior中的推论是通过单向（快速）或双向（缓慢但功能更强大）的约束传播进行的。重写规则的单向约束传播可以用规则传播字段等效地描述，这些规则传播字段将dijkstra字段推广到任意重写规则。 Dijkstra Fields是基于网格的程序生成中的一种流行技术（1、2、3）。他们反过来概括了计算机图形中使用的距离字段。

如果约束传播完成，则不一定意味着目标状态是可以实现的。但是，如果传播失败，那么我们可以确定目标是无法实现的。这样可以捕获将板条箱推到索科邦错误墙壁上的状态，或者覆盖网格的步行将网格分成2个断开的部分。除了这种布尔启发式统治外，还值得研究约束传播所需的最少圈。这种整数值得启发性是可接受的，我们将其用于*搜索中，以在2个给定状态之间使用重写规则制成的示例路径。

开放问题

1. 程序生成的程序合成。威廉·夏尔（William Chyr）的演讲“不可能的几何设计水平设计”根本不是关于程序的一代，但是我发现一张幻灯片对于PCG实践非常有特征。威廉比较了他的早期和后来的水平设计方法。较早的一个产生混乱的水平，而后来的方法基于一个中心思想产生了更结构化的，更有意的水平。后来的级别并不简单，但是对于玩家来说，它们更令人难忘，更容易。对我来说，左层看起来像是在程序上生成的！它的感觉与我的步素拼图非常相似。我们可以制造产生更像右侧的水平的发电机吗？这个问题似乎是AI完整的。但是我认为这与诸如Koza的割草机问题之类的经典基因编程问题非常相似。例如，按照在网格上生成哈密顿路径的简单任务。即使对于像29×29这样的小网格尺寸，此任务在计算上也很要求。但是，我们真的需要从实践中的所有可能的路径中采样吗？如果我们将这项任务交给人类，它们可能会绘制螺旋形或锯齿形曲线 – 这些曲线比随机的汉密尔顿路径更令人难忘和有意的设计，再加上它们概括为任何网格尺寸。总而言之，我们可以要求系统找到一条随机的汉密尔顿路径，或者找到生成汉密尔顿路径的简短程序。在第一种情况下，结果看起来像幻灯片上的左级，在第二种情况下，就像正确的级别一样。解决后一个程序的综合问题将创造更多令人难忘和故意的发电机。
2. 示例中的模型合成。 Markov算法似乎是程序/模型综合的理想环境：没有变量，如果或当时可以轻松地移动节点而不破坏正确性，模型易于使可区分。随机的MJ程序通常很有趣，并且可以产生可追溯的结果和行为。
   1. 我们可以从结果或一组结果中合成MJ模型吗？
   2. 鉴于迷宫，是否可以确定（或分配概率）它是由迷迷之或迷宫式导游生成的？
   3. 通过推断MarkovJunior模型来解决抽象和推理挑战。伴随问题：利用ARC挑战中的见解来为网格上的程序生成构建更好的DSL。
3. 在波浪空间中运行的自定义算法。结合基于建设性和受限的程序生成的优势。相关：具有自定义能量功能的自定义算法（MJ重写规则），例如Ising Energy或Convchain Energy。
4. 概括模式的概念。
5. 研究其他（可能是不规则的）网格或任意图上的MJ样过程。
6. 实验Markov算法的交互式扩展。可以通过将特定的重写规则或节点分配给密钥按下来将任何MJ模型变成游戏。
7. 在基于网格的程序生成中推动最新技术。 Modern House尚未达到人类设计的房屋的结构种类，例如Sims 2 Houses。使用更多微妙的约束。

评论

与图灵机和Lambda微积分相比，Markov算法可能是严格定义算法的最短和最简单的方法。

练习：证明以下马尔可夫算法找到了以一单一表示书写的2个数字中最大的共同除数。例如，如果我们将其应用于111111*1111111111我们将获得11 。

 1a=a1
1*1=a*
1*=*b
b=1
a=c
c=1
*=ε (halt)

快速模式匹配。 MarkovJunior解释器样品均匀地匹配，但并不能随时扫描整个网格。为了使模式匹配及时，解释器先前仅在更改的位置周围发现了匹配和搜索。当第一次遇到Rulenode时，MJ解释器使用Boyer -Moore算法的多维版本。

随机放松。 Markov节点具有非常好的表示形式，作为可区分节点的限制。考虑一组无序的重写规则，其中每个规则r均为权重w(r) 。在每个步骤中，解释器都会找到所有规则的所有匹配项，并根据Boltzmann分布p(r) ~ exp(-w(r)/t)选择随机匹配。然后，在冻结极限t->0中，我们得到了一个按权重订购的马尔可夫节点。这种结构的好处是，对于任何t>0 ，对于典型的得分函数，多次跑步的得分平均值将是权重的连续（并且出于实际目的）的连续功能。这意味着可以通过梯度下降找到最佳权重，然后冻结系统以获取最终离散程序。

阅读鲍里斯·库什纳（Boris Kushner）关于AA Markov及其在建设性数学方面的工作。

二手工作

主要二手工作：

1. 安德烈·马克夫（Andrey A.另请参见后来的书，并进行了更详细的待遇。我将感谢开放访问中英语翻译的链接。
2. MarkovJunior S. Tows，ImageGram，2009。Markovjunior从ImageGram中获取forall节点。
3. Valentin Turchin，Refal语言，1968年。MJ从Refal提出了嵌套的Markov节点的想法。
4. Brian Walker等人，《 Dijkstra Maps的令人难以置信的力量》，2010年。《 Roguelike社区》中的讨论，其中包含许多使用Dijkstra地图/距离字段进行程序发电和NPC AI的技术。后来的写入：1，2。我们将Dijkstra地图推广到任意重写规则。
5. Pavlos S. Efraimidis，Paul Spirakis，加权随机抽样，2005年。
6. 自定义节点中使用的工作：模型合成，波函数塌陷算法，弯曲算法。
7. 经典算法：约束传播，约束解决算法，图形遍历，a*搜索。

相关工作：

1. 丹尼尔·里奇（Daniel Ritchie），《程序建模与设计的概率编程》，2016年。
2. Lingfeng Yang，从执行痕迹到专业推论，2015年。

示例的来源：

1. 基本钥匙和钥匙是由Joris Dormans制定的图形语法的改编，《工程出现：游戏设计的应用理论》，2012年。这反过来又是David Adams早期作品的开发，自动生成计算机游戏的地牢，2002年。我使用这些模型的多种模型来产生Seavilla中的钥匙桥桥梁。
2. Carmatower是Antoine Lendrevie的Voxel场景的程序化。
3. Nystromdungeon型号是Bob Nystrom的地牢发电机的MarkovJunior端口。
4. HamiltonianPath算法改编自本文。将其与传统语言的实现进行比较。
5. 地牢中的房间形状取自R/Procentural Generation Post。请注意，MJ解释器会自动执行帖子中描述的优化。
6. 威尔逊模型是对威尔逊算法的重写规则制定。将其与传统语言的实现进行比较。
7. 迷宫学模型也被称为通过随机遍历的迷宫产生。将其与传统语言的实现进行比较。
8. 增长与伊甸园增长模型密切相关。
9. Bernoullipercolation是渗透理论中经过深入研究的模型。
10. NestedGrowth取自ImageGram。
11. SmoothTrail改编自128_MHz的推文。
12. Sokobanlevel1似乎是Hiroyuki imabayashi的索科巴人难题的第一级。 Sokobanlevel2是离子催化剂XI集的452级。
13. Mure提出了彩虹生长。
14. Multiheadedwalk，MultiheedDungeon和MultiheadedWalkDungeon基于Ilya Kudritsky的想法。
15. Island Model是由Guillaume fiette制作的。
16. LostCity，Forest和纹理模型基于Andrew Kay的模型。

素场在magicavoxel中通过ephtracy呈现。特别感谢Brian Bucklew在Roguelike Level Generation和Kevin Chapelier中向我展示了Dijkstra Fields的力量，并提供了许多好的建议。 GUI中使用的字体为Tamzen。

如何构建

MarkovJunior解释器是仅取决于标准库的控制台应用程序。获取Windows，Linux或MacOS的.NET核心并运行

 dotnet run --configuration Release MarkovJunior .csproj

另外，下载并运行Windows的最新版本。

生成的结果放入output文件夹中。编辑models.xml以更改模型参数。使用MagicAvoxel打开.vox文件。

著名的端口，叉子和衍生

• Yuu制作了MarkovJunior的打字稿版本，该版本在网络上运行，扩展了语言并增加了将节点绑定到关键的能力。
• Aseaday将MarkovJunior移植到JavaScript。
• Andrew Kay将XML文档添加到C＃源代码。
• 丹·奥格尔斯（Dan Ogles）撰写了MarkovJunior技术说明，重点是领域和推理。
• 安德鲁·凯（Andrew Kay）设计了MJR，这是一种基于模式重写的编译语言。
• 阿什利（Ashley）正在写下MarkovJunior作为python图书馆的生锈实施。

资金

MarkovJunior开发由

1. Embark Studios
2. 奥斯卡·斯托尔伯格（OskarStålberg）
3. 永久性游戏
4. 鲍勃·伯劳（Bob Burrough）