Об этом проекте

MarkovJunior — это вероятностный язык программирования, в котором программы представляют собой комбинации правил перезаписи, а вывод выполняется посредством распространения ограничений. Он назван в честь математика Андрея Андреевича Маркова, который определил алгоритмы Маркова. В своей базовой форме программа MarkovJunior представляет собой упорядоченный список правил перезаписи. Например, модель MazeBacktracker использует два правила: `RBB=GGR` и `RGG=WWR`. На каждом шаге выполнения интерпретатор находит первое правило, которому соответствует фрагмент сетки, находит все совпадения и применяет случайное из них. Интерпретатор останавливается, когда ни одно правило не соответствует. Вероятностный вывод позволяет накладывать ограничения на будущие состояния, генерируя только те прогоны, которые приводят к ограниченным будущим состояниям. Например, вывод в правилах Sokoban заставляет агентов организовывать ящики в заданные формы. Репозиторий включает множество вероятностных генераторов для подземелий, архитектуры, головоломок и симуляций. Ключевые концепции включают: - **Правила перезаписи**: Простые правила, такие как `(B=W)`, преобразуют случайные черные квадраты в белые. Более сложные правила, такие как `(WBB=WAW)`, генерируют лабиринты одной строкой кода. Подстановочные знаки (`*`) позволяют использовать любой цвет на входе или без изменений на выходе. - **Узлы правил**: Объединяют несколько правил, например, для случайных блужданий с удалением петель или генерации лабиринтов Алдуса-Бродера. - **Узлы последовательностей**: Выполняют узлы правил один за другим, например, при построении диаграмм Вороного для речных долин. - **Марковские узлы**: Позволяют возвращаться к прошлым узлам, что обеспечивает такие алгоритмы, как генерация подземелий Боба Нистрома. - **Вывод**: Использует распространение ограничений (однонаправленное или двунаправленное) для связи состояний, с параметром температуры для строгости. Он может решать головоломки, такие как Sokoban, или генерировать гамильтоновы пути. Дополнительные материалы включают обзор синтаксиса XML, скриншоты более высокого разрешения и неофициальные технические заметки. В проекте обсуждаются открытые проблемы, такие как синтез программ для процедурной генерации и синтез моделей из примеров. Он ссылается на влияние алгоритмов Маркова, Imagegram, REFAL, карт Дейкстры и классических алгоритмов, таких как поиск A*. Интерпретатор использует быстрый поиск шаблонов с многомерным алгоритмом Бойера-Мура и поддерживает стохастическую релаксацию для оптимизации на основе градиента.