README

MarkovJunior
MarkovJunior is a probabilistic programming language where programs are combinations of rewrite rules and inference is performed via constraint propagation. MarkovJunior is named after mathematician Andrey Andreyevich Markov, who defined and studied what is now called Markov algorithms.





In its basic form, a MarkovJunior program is an ordered list of rewrite rules. For example, MazeBacktracker (animation on the left below) is a list of 2 rewrite rules:
1. RBB=GGR or "replace red-black-black with green-green-red".
2. RGG=WWR or "replace red-green-green with white-white-red".

On each execution step MJ interpreter finds the first rule in the list that has a match on the grid, finds all matches for that rule and applies that rule for a random match. In the maze backtracker example, interpreter first applies a bunch of RBB=GGR rules. But eventually the green self-avoiding walk gets stuck. At this point the first rule has no matches, so interpreter applies the second rule RGG=WWR until the walk gets unstuck. Then it can apply the first rule again, and so on. Interpreter stops when there are no matches for any rule.





Probabilistic inference in MarkovJunior allows to impose constraints on the future state, and generate only those runs that lead to the constrained future. For example, inference in Sokoban rules {RWB=BRW RB=BR} makes a group of (red) agents organize (white) crates into specified shapes.

Using these ideas, we construct many probabilistic generators of dungeons, architecture, puzzles and fun simulations.


Additional materials:
1. Xml syntax overview.
2. Higher resolution screenshots and more seeds: ModernHouse, SeaVilla, Apartemazements, CarmaTower, Escheresque, PillarsOfEternity, Surface, Knots.
3. Unofficial technical notes by Dan Ogles and code documentation by Andrew Kay.



 Markov algorithms
A Markov algorithm over an alphabet A is an ordered list of rules. Each rule is a string of the form x=y, where x and y are words in A, and some rules may be marked as halt rules. Application of a Markov algorithm to a word w proceeds as follows:
1. Find the first rule x=y where x is a substring of w. If there are no such rules, then halt.
2. Replace the leftmost x in w by y.
3. If the found rule was a halt rule, then halt. Otherwise, go to step 1.

For example, consider this Markov algorithm in the alphabet {0, 1, x} (ε is the empty word):

1=0x
x0=0xx
0=ε

If we apply it to the string 110 we get this sequence of strings:

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

In general, this algorithm converts a binary representation of a number into its unary representation.

Markov's student Vilnis Detlovs proved that for any Turing machine there exists a Markov algorithm that computes the same function. In comparison, grammars are unordered sets of rewrite rules and L-systems are rewrite rules that are applied in parallel. For more interesting examples of Markov algorithms check Mar