MarkovJunior - MarkovJuniorは確率的プログラミング言語であり、プログラムは書き換えルールの組み合わせであり、推論は制約伝播を介して実行されます。

(Probabilistic PL based on pattern matching and constraint propagation, 148 examples)

Created at: 2022-06-01 20:27:02
Language: C#
URL: https://github.com/mxgmn/MarkovJunior
License: MIT

マルコフジュニア

MarkovJuniorは確率的プログラミング言語であり、プログラムは書き換えルールの組み合わせであり、推論は制約伝播を介して実行されます。MarkovJuniorは、現在マルコフアルゴリズムと呼ばれているものを定義および研究した数学者AndreyAndreyevichMarkovにちなんで名付けられました。

基本的な形式では、MarkovJuniorプログラムは、書き換えルールの順序付きリストです。たとえば、MazeBacktracker（左下のアニメーション）は、2つの書き換えルールのリストです。

  1. RBB=GGR
    または「赤-黒-黒を緑-緑-赤に置き換えます」。
  2. RGG=WWR
    または「赤-緑-緑を白-白-赤に置き換えます」。

各実行ステップで、MJインタープリターは、グリッド上で一致するリスト内の最初のルールを検索し、そのルールに一致するものをすべて検索し、そのルールをランダムな一致に​​適用します。迷路バックトラッカーの例では、インタプリタは最初に一連の

RBB=GGR
ルールを適用します。しかし、最終的には緑の自己回避歩行が行き詰まります。この時点で、最初のルールに一致するものがないため、インタープリターは
RGG=WWR
、ウォークがスタックから外れるまで2番目のルールを適用します。その後、最初のルールを再度適用できます。ルールに一致するものがない場合、インタプリタは停止します。

MarkovJuniorの確率的推論により、将来の状態に制約を課し、制約された将来につながる実行のみを生成できます。たとえば、倉庫番のルールで推論

{RWB=BRW RB=BR}
すると、（赤の）エージェントのグループが（白の）木枠を指定された形に編成します。

これらのアイデアを使用して、ダンジョン、建築、パズル、楽しいシミュレーションの多くの確率的ジェネレーターを構築します。

高解像度のスクリーンショットとより多くのシード：ModernHouse、SeaVilla、Apartemazements、CarmaTower、Escheresque、PillarsOfEternity、Surface、Knots。

マルコフアルゴリズム

アルファベットに対するマルコフアルゴリズム

A
は、規則の順序付きリストです。各ルールは、の形式の文字列です
x=y
。ここで、
x
および
y
はの単語で
A
あり、一部のルールは停止ルールとしてマークされる場合があります。単語へのマルコフアルゴリズムの適用は、次の
w
ように進行します。

  1. の部分文字列である
    x=y
    最初のルールを見つけます。そのようなルールがない場合は、停止します。
    x
    w
  2. 左端
    x
    を。
    w
    に置き換え
    y
    ます。
  3. 見つかったルールが停止ルールであった場合は、停止します。それ以外の場合は、手順1に進みます。

たとえば、アルファベットのこのマルコフアルゴリズムを考えてみましょう

{0, 1, x}
（εは空の単語です）。

1=0x
x0=0xx
0=ε

これを文字列に適用すると、次の文字列

110
のシーケンスが得られます。

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

一般に、このアルゴリズムは、数値の2進表現を1進表現に変換します。

マルコフの学生であるVilnisDetlovs は、どのチューリングマシンにも、同じ関数を計算するマルコフアルゴリズムが存在することを証明しました。対照的に、文法は順序付けられていない書き換えルールのセットであり、Lシステムは並行して適用される書き換えルールです。マルコフアルゴリズムのより興味深い例については、マルコフの本を確認するか、ウィキペディアのコメントセクションまたは乗算の例で最大公約数の例を参照してください。

マルコフアルゴリズムを複数の次元に一般化するにはどうすればよいでしょうか。まず、多次元では、文字列を別の文字列に挿入する自然な方法がないため、書き換えルールの左と右は同じサイズである必要があります。第二に、左端の一致を選択する自然な方法はありません。可能なオプションは次のとおりです。

  • ランダムに一致するものを選択してください。これは、MJの
    (exists)
    ノードが行うことです。
  • すべての一致を選択してください。ただし、このオプションには問題があります。これは、異なる一致が重複して競合する可能性があるためです。考えられる解決策は次のとおりです。
    • 競合しない一致の最大サブセットを貪欲に選択します。これは、MJの
      {forall}
      ノードが行うことです。
    • 重ね合わせのすべての一致を考慮してください。つまり、個別の値の代わりに、各グリッドセルに波を保持します。これは、どの時空パターンが禁止され、どの時空パターンが禁止されているかを示すブールベクトルです。そして、これがMJが推論を実行する方法です。

新しい手順は決定論的ではないため、チューリング完全性は失われますが、実践では、この形式によって、興味深いランダムプロセスの膨大な範囲を記述できることが示されています。

ルールを書き換える

最も単純なMarkovJuniorプログラムはおそらく

(B=W)
です。含まれているルールは1つだけ
B=W
です。各ターンで、このプログラムはランダムな黒い四角を白い四角に変換します。


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

成長モデル

(WB=WW)
はもっと興味深いものです。各ターンで、隣接するセルの白黒のペアが白と白のペアに置き換えられ
BW
ます
WW
。言い換えれば、各ターンで、いくつかの白いセルに隣接するランダムな黒いセルを選び、それを白に着色します。このモデルは、エデン成長モデルとほぼ同じです。各ターンで、両方のモデルが同じ黒いセルのセットから選択します。それらは確率分布のみが異なります。白いセルに隣接する黒いセル全体の均一な分布は、隣接する黒いセルと白いセルのペア全体の均一な分布と同じではありません。

モデル

(WBB=WAW)
は、1行のコードで迷路を生成します！従来の言語での実装と比較してください。MarkovJuniorモデルは、変更せずに任意の数の次元で実行できます。右側には、MagicaVoxelでレンダリングされた3DでのMazeGrowthの最終結果が表示されます。デフォルトでは、PICO-8パレットを使用します。

モデル

(RBB=WWR)
は自己回避ランダムウォークです。3Dでの自己回避歩行は、2Dよりも平均して長いことに注意してください。一般に、異なる次元での同様のランダムプロセスの動作を比較することは、魅力的なトピックです。GeorgePólyaの古典的な結果によると、2Dでのランダムウォークは、確率1で初期位置に戻りますが、3Dではこれはもはや当てはまりません。


（RBB = WWR）| LoopErasedWalk | （RB = WR RW = WR）

複数のルールを1つのルールノードに入れることができます。たとえば、

(RBB=WWR RBW=GWP PWG=PBU UWW=BBU UWP=BBR)
はループ消去されたランダムウォークです。トレイルモデルは、まともな接続された洞窟
(RB=WR RW=WR)
を生成します。

モデルは、 Aldous-Broder迷路生成アルゴリズム

(RBB=WWR R*W=W*R)
として知られています。入力のワイルドカード記号は、任意の色を正方形に含めることができることを意味します。出力のワイルドカード記号は、ルールの適用後に色が変更されないことを意味します。たとえば、Aldous-Broderアルゴリズムは、MazeGrowthよりも平均してはるかに多くのターンで迷路を生成しますが、MazeGrowthにはない優れた特性があります。つまり、各迷路は同じ確率で生成されます。言い換えると、MazeTrailは、偏りのない迷路生成アルゴリズムであるか、均一な分布で迷路（またはスパニングツリー）をサンプリングします。Wilsonのアルゴリズムは、より効率的なバイアスのない迷路生成アルゴリズムです。その比較
*
従来の言語での実装によるMarkovJuniorの実装！

ルールノードの組み合わせ

複数のルールノードをシーケンスノードに配置して、次々に実行することができます。河川モデルでは、最初に2つのソースを使用して確率的ボロノイ図を作成し、形成された領域間の境界を河川のベースとして使用します。次に、ボロノイシードをさらに2つスポーンして、森を育て、同時に川から草を育てます。その結果、ランダムな川の谷ができます！

Apartemazementsでは、WFCノードから始めて、ルールノードを使用して建設的な後処理を行います。

  1. 制約を準備します。下部のセルを個別の下部の色でマークし、残りの境界線セル（側面と上部）を個別の境界線の色でマークします。境界線のセルは空にマップする必要があり、下のセルは下を除くすべてのタイルにマップする必要があります。
  2. WFCパスタイルセットを実行して、閉じた階段状のサイクルを生成します。
  3. 光源をランダム化します。
  4. 平らなタイルの角から柱を落とします。
  5. ターンタイルの角から伸びる柱を除いて、二重柱、地面に接する柱、階段に接する柱を撤回します。
  6. 隣接する列の間にウィンドウを拡大します。
  7. ウィンドウをより大きな長方形にマージします。これはいくつかのステップで行います。
    1. ウィンドウの角がウィンドウの中点に接触したときに、ウィンドウの不均一なパターンを検出します。
    2. これらのパターンに印を付け、窓の側面の全長に印を付けます。
    3. マークされていないウィンドウサイドのペアをマージします。
  8. 残りの1x1ウィンドウを壁に変えます。

ノードを組み合わせるさらに興味深い方法は、ノードをマルコフノードに配置することです。マルコフノードは、過去のノードに戻ることができるため、私たちができることを大幅に拡張します。マルコフノードがアクティブな場合、インタープリターはそれに一致する最初の子ノードを見つけて適用します。次のターンで、リスト内で最初に一致するノードが再び検索され、以下同様に続きます。マルコフノードの使用の最も簡単な例は、上部のセクションで説明したMazeBacktrackerです。

MarkovJuniorの開発の動機となった私のお気に入りの例の1つは、BobNystromのダンジョン生成アルゴリズムです。それは次のようになります：

  1. グリッドを描画し
    {PBB=**P}
    ます。
  2. たくさんの部屋をスポーンします
    (room.png)
    。
  3. グリッドの残りの部分に迷路を生成します。任意の迷路生成アルゴリズムを使用できますが、生成される分岐点が少ないため、 MazeBacktrackerが推奨されます。
  4. 結果として得られる部屋と廊下の構成を接続します。これは、マルコフノードを使用してエレガントに実行できます
    ({GWW=**G}(GBW=*WG))
    。
  5. いくつかの追加の接続
    (GBG=*W* #5)
    を作成して、結果のダンジョンにサイクルができるようにします。プレイヤーはすでに探索されたゾーンを通り抜けなければならないので、サイクルのないダンジョンはかなり退屈です。
  6. 行き止まりを撤回します
    {BBB/BWB=BBB/BBB}
    。

REFALの場合と同様に、マルコフノードはネストできます。子ノードに入ると、子ブランチが完了するまで外部ノードを無視します。

推論

MarkovJuniorの確率的推論により、将来の状態に制約を課し、制約された将来につながる実行のみを生成できます。言い換えると、推論は、2つの指定された状態（または部分的に観察された状態）を一連の書き換えルールに接続します。

推論の使用の最も簡単な例は、2つのポイントをパスで接続することです。自己回避歩行モデルでは、グリッド上の特定の正方形が赤くなるのを観察

(RBB=WWR)
できます。次に、通訳者は、観察された正方形につながる歩行のみを生成します。温度パラメータを変更することで、より厳密に、またはより厳密に目標に従わないようにインタプリタを設定できます。デフォルトでは、温度はゼロに設定されています。
R


最も寒い| 寒い| ホット| 最も暑い

私たちができるもう1つのことは、すべての奇数のグリッドの正方形が白または赤になるのを観察することです。次に、通訳者はグリッド全体をカバーする自己回避歩行を生成します。

あらゆる書き換えルールについて推論を行うことができます。たとえば、階段描画ルールの推論は、2つのポイントを階段パスに接続します。ルールの推論

R**/**B=B**/**R
により、チェスの騎士がたどることができるパスが生成されます。CrossCountryモデルの推論は、地形コストを考慮したパスで2つのポイントを接続します。倉庫番ルールセットの推論は、倉庫
{RB=BR RWB=BRW}
番パズル、さらにはマルチエージェント倉庫番パズルを解決します！

MarkovJuniorでの推論は、単方向（高速）または双方向（低速ですが、より強力）の制約伝播を介して行われます。リライトルールの単方向制約伝播は、任意のリライトルールのダイクストラフィールドを一般化するルール伝播フィールドの観点から同等に説明できます。ダイクストラフィールドは、グリッドベースの手続き型生成（1、2、3 ）で一般的な手法です。次に、コンピュータグラフィックスで使用される距離フィールドを一般化します。

制約の伝播が完了した場合、それは必ずしも目標状態が達成可能であることを意味するわけではありません。しかし、伝播が失敗した場合、目標が達成できないことは確かです。これにより、倉庫番の間違った壁に木枠が押し込まれたり、グリッドを覆うウォークがグリッドを2つの切断された部分に分割したりする状態をキャッチできます。このブールヒューリスティックに加えて、制約の伝播が完了するために必要な最小ターン数を確認する価値があります。この整数値のヒューリスティックは許容され、A *検索で使用して、2つの指定された状態間の書き換えルールで作成されたパスをサンプリングします。

開かれた問題

  1. 手続き型生成のためのプログラム合成。William Chyrの講演「不可能な幾何学におけるレベルデザイン」は、手続き型生成に関するものではありませんが、1つのスライドがpcgの実践に非常に特徴的であることがわかりました。ウィリアムは、レベルデザインに対する彼の以前のアプローチと後のアプローチを比較します。前者は混沌としたレベルを生み出しましたが、後者のアプローチは1つの中心的なアイデアに基づいて、より構造化された、より意図的なレベルを生み出しました。後のレベルは単純ではありませんでしたが、プレイヤーにとってより記憶に残り、知覚しやすくなりました。私には、左のレベルは手続き的に生成されたように見えます！それは私の手続き型ボクセルパズルと非常によく似た感触を持っています。右のようなレベルを生成するジェネレーターを作成できますか？この問題はAI完全に見えるかもしれません。しかし、それはコザの芝刈り機の問題のような古典的な遺伝的プログラミングの問題と非常に似ていると私は主張します。たとえば、グリッド上にハミルトンパスを生成する単純なprocgenタスクを取ります。29x29のような小さなグリッドサイズの場合でも、このタスクはすでに計算量が多くなります。しかし、実際には、考えられるすべてのパスから実際にサンプリングする必要がありますか？このタスクを人間に与えると、おそらくスパイラルまたはジグザグ曲線を描くことになります。これらは、ランダムなハミルトンパスよりもはるかに記憶に残る意図的なデザインであり、さらに任意のグリッドサイズに一般化されます。要約すると、ランダムなハミルトンパスを見つけるか、ハミルトンパスを生成する短いプログラムを見つけるようにシステムに要求できます。最初のケースでは、結果はスライドの左のレベルのようになり、2番目のケースでは右のレベルのようになります。後者のプログラム合成の問題を解決すると、より記憶に残る意図的なジェネレーターが作成されます。
  2. 例からのモデル合成。マルコフアルゴリズムは、プログラム/モデル合成に最適な環境のようです。変数がなく、ifまたはwhileがなく、ノードは正確さを損なうことなく簡単に移動でき、モデルは簡単に微分可能になります。ランダムなMJプログラムは楽しいことが多く、人間に関係のある結果と行動を生み出すことができます。
    1. 結果または一連の結果からMJモデルを合成できますか？
    2. 迷路が与えられた場合、それがMazeGrowthまたはMazeBacktrackerのどちらによって生成されたかを判断（または確率を割り当てる）することは可能ですか？
    3. MarkovJuniorモデルを推測して、抽象化と推論の課題を解決します。随伴問題：ARCチャレンジからの洞察を使用して、グリッド上で手続き型生成のためのより優れたDSLを構築します。
  3. 波空間で実行されるカスタムアルゴリズム。建設的で制約に基づく手続き型生成の利点を統合すること。関連：イジングエネルギーやConvChainエネルギーなどのカスタムエネルギー関数を使用したカスタムアルゴリズム（MJ書き換えルール）。
  4. パターンの概念を一般化します。
  5. 他の（おそらく非規則的な）グリッドまたは任意のグラフでMJのようなプロセスを調査します。
  6. マルコフアルゴリズムのインタラクティブな拡張を試してください。キーを押すと特定の書き換えルールまたはノードを割り当てることで、MJモデルをゲームに変えることができます。
  7. グリッドベースの手続き型生成で最先端の技術を推進します。ModernHouseは、 Sims2の家のような人間が設計した家の構造の多様性にはまだ到達していません。より微妙な制約を使用します。

コメントコメント

チューリングマシンやラムダ計算と比較すると、マルコフアルゴリズムは、アルゴリズムが何であるかを厳密に定義するための最短かつ最も簡単な方法です。

演習：次のマルコフアルゴリズムが、一進表現で書かれた2つの数の最大公約数を見つけることを証明します。たとえば、これを適用すると、

111111*1111111111
が得られ
11
ます。

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

高速パターンマッチング。MarkovJuniorインタープリターのサンプルは均一に一致しますが、グリッド全体を毎ターンスキャンするわけではありません。パターンマッチングを高速に保つために、インタプリタは以前に見つかった一致を記憶し、変更された場所の周りのみを検索します。ルールノードに初めて遭遇したとき、MJインタープリターはボイヤームーアアルゴリズムの多次元バージョンを使用します。

Stochastic relaxation. Markov nodes have a very nice representations as limits of differentiable nodes. Consider an unordered set of rewrite rules where each rule 

r
is assigned a weight 
w(r)
. On each step the interpreter finds all matches for all rules and chooses a random match according to the Boltzmann distribution 
p(r) ~ exp(-w(r)/t)
. Then in the freezing limit 
t->0
we get a Markov node, ordered by weights. What's good about this construction, is that for any 
t>0
and for a typical score function, score's average on multiple runs would be a continuous (and smooth for practical purposes) function of weights. This means that one can find the optimal weights by gradient descent and then freeze the system to get the final discrete program.

Read this essay by Boris Kushner about A. A. Markov and his work in constructive mathematics.

Used work

Main used work:

  1. Andrey A. Markov, The Theory of Algorithms, 1951. Markov used these ideas earlier in 1947 in his proof of the algorithmic undecidability of the word problem in semigroups. See also a later book with a more detailed treatment. I would be grateful for links to English translations in open access.
  2. Guilherme S. Tows, Imagegram, 2009. MarkovJunior takes forall-nodes from Imagegram.
  3. Valentin Turchin, REFAL language, 1968. MJ takes the idea of nested Markov nodes from REFAL.
  4. Brian Walker et al., The incredible power of Dijkstra maps, 2010. A discussion in the the roguelike community that contains many techniques of using Dijkstra maps/distance fields for procedural generation and NPC AI. Later writeups: 1, 2. We generalize Dijkstra maps to arbitrary rewrite rules.
  5. Pavlos S. Efraimidis, Paul Spirakis, Weighted Random Sampling, 2005.
  6. Work used in custom nodes: Model Synthesis, Wave Function Collapse Algorithm, ConvChain Algorithm.
  7. Classic algorithms: constraint propagation, constraint solving algorithms, graph traversal, A* search.

関連作業：

  1. Daniel Ritchie、手続き型モデリングと設計のための確率的プログラミング、2016年。
  2. Lingfeng Yang、実行トレースから特殊な推論まで、2015年。

例のソース：

  1. BasicKeysとKeysは、Joris Dormans、Engineering Emergence：Applied Theory for Game Design、2012年に作成されたグラフ文法を応用したものです。これは、David Adamsによる初期の作品、コンピュータゲーム用ダンジョンの自動生成、2002年の開発です。 SeaVillaでキーロックブリッジパズルを生成するためのこれらのモデルのバリエーション。
  2. CarmaTowerは、 AntoineLendrevieによるボクセルシーンの手続き化です。
  3. NystromDungeonモデルは、BobNystromのダンジョンジェネレーターのMarkovJuniorポートです。
  4. ハミルトンパスアルゴリズムは、この記事から採用されています。従来の言語での実装と比較してください。
  5. DungeonGrowthの部屋の形状は、 r/proceduralgenerationポストから取得されます。MJインタープリターは、投稿で説明されている最適化を自動的に実行することに注意してください。
  6. Wilsonモデルは、 Wilsonのアルゴリズムの書き換えルールの定式化です。従来の言語での実装と比較してください。
  7. MazeGrowthモデルは、ランダムトラバーサルによる迷路生成としても知られています。従来の言語での実装と比較してください。
  8. 成長は、エーデン成長モデルと密接に関連しています。
  9. BernoulliPercolationは、パーコレーション理論でよく研究されているモデルです。
  10. NestedGrowthはImagegramから取得されます。
  11. SmoothTrailは、128_mhzのツイートを基にしています。
  12. 倉庫番レベル1は今林博之の倉庫番パズルの最初のレベルのようです。SokobanLevel2は、IonicCatalystsXIセットのレベル452です。

ボクセルシーンは、MagicaVoxelでephtracyによってレンダリングされました。ローグライクレベルの生成でダイクストラフィールドの力を示してくれたBrianBucklewと、多くの良い提案をしてくれたKevinChapelierに特に感謝します。GUIで使用されるフォントはTamzenです。

構築する方法

MarkovJuniorインタプリタは、標準ライブラリのみに依存するコンソールアプリケーションです。.NET Core for Windows、Linux、またはmacOSを入手して、

dotnet run --configuration Release MarkovJunior.csproj

または、Windows用の最新リリースをダウンロードして実行します。

生成された結果はフォルダに入れられ

output
ます。編集
models.xml
してモデルパラメータを変更します。MagicaVoxel
.vox
でファイルを開きます。

資金調達

マルコフジュニア開発はによって資金を供給されました

  1. 乗船スタジオ
  2. オスカー・ストールベルグ
  3. フリーホールドゲーム
  4. ボブバロウ

About

Author：mxgmn

Watch
Star
Fork