markovjunior

MarkovJuniorは、プログラムが書き換え規則の組み合わせで構成され、推論が制約伝播によって実行される確率的プログラミング言語です。数学者アンドレイ・アンドレイエヴィッチ・マルコフにちなんで名付けられており、彼はマルコフアルゴリズムを定義しました。基本的な形式では、MarkovJuniorプログラムは書き換え規則の順序付きリストです。例えば、MazeBacktrackerモデルは`RBB=GGR`と`RGG=WWR`の2つの規則を使用します。各実行ステップで、インタプリタはグリッド上で一致する最初の規則を見つけ、すべての一致を見つけ、ランダムなものを適用します。インタプリタは一致する規則がなくなると停止します。 確率的推論により、将来の状態に制約を課すことができ、制約された未来につながる実行のみを生成します。例えば、Sokoban規則での推論により、エージェントがクレートを指定された形状に整理します。リポジトリには、ダンジョン、建築、パズル、シミュレーション用の多くの確率的生成器が含まれています。 主要な概念は以下の通りです： - **書き換え規則**：`(B=W)`のような単純な規則は、ランダムな黒い正方形を白に変換します。`(WBB=WAW)`のようなより複雑な規則は、1行のコードで迷路を生成します。ワイルドカード（`*`）は、入力または変更されない出力で任意の色を許可します。 - **ルールノード**：複数の規則を組み合わせます。例えば、ループ消去ランダムウォークやAldous-Broder迷路生成などです。 - **シーケンスノード**：ルールノードを順番に実行します。例えば、川の谷のボロノイ図を構築します。 - **マルコフノード**：過去のノードに戻ることを可能にし、Bob Nystromのダンジョン生成のようなアルゴリズムを実現します。 - **推論**：制約伝播（一方向または双方向）を使用して状態を接続し、厳密さのための温度パラメータがあります。Sokobanのようなパズルを解いたり、ハミルトン経路を生成したりできます。 追加資料には、XML構文の概要、高解像度のスクリーンショット、非公式の技術ノートが含まれます。プロジェクトは、プロシージャル生成のためのプログラム合成や、例からのモデル合成などの未解決問題について議論しています。マルコフアルゴリズム、Imagegram、REFAL、Dijkstraマップ、A*探索などの古典的アルゴリズムからの影響を挙げています。インタプリタは、多次元Boyer-Mooreアルゴリズムを使用した高速パターンマッチングを使用し、勾配ベースの最適化のための確率的緩和をサポートしています。