A TADS3/adv3 module for implementing discrete Markov chains

Authoring TADS
1

Here’s a TADS3/adv3 module for implementing simple, discrete Markov chains: markovChain github repo.

In this module Markov chains are simple directed graphs, states are vertices, and edge lengths are used to represent transition weights.

Jumping in with an example, here’s a simple three-state model:

myChain: MarkovChain @foo;
+foo: MarkovState 'foo';
++MarkovTransition ->bar +0.75;
++MarkovTransition ->baz +0.25;
+bar: MarkovState 'bar'; 
++MarkovTransition ->foo +300;
++MarkovTransition ->baz +100;
+baz: MarkovState 'baz';
++MarkovTransition ->foo +100;
++MarkovTransition ->bar +100;

This defines:

  • a chain called myChain (the myChain: in the first line)
  • that myChain starts out in the state foo (the @foo in the first line)
  • a state foo that transitions to bar 75% of the time and baz 25% of the time (next three lines)
  • a state bar that transitions to foo 75% of the time and baz 25% of the time (next three lines)
  • a state baz that transitions to foo and bar with equal probability (last three lines)

The thing worth noticing is that you can declare transition weights two ways: as decimal probabilities or integer weights. Interally decimal probabilities are converted to integer weights during preinit (by default by multiplying them by 1000 and converting the result into an integer).

Having declared a chain, you can get a random transition via:

        id = myChain.pickTransition();

…which will pick a random transition (from the current chain state), returning the state ID for the new state and updating its internal state appropriately.

Transitions are picked by adding up the integer weights for all allowed transtions (given the current state) and picking a random integer between 1 and the sum (inclusive).

This is all pretty simple stuff, but something I wanted for a couple of different things (modelling random weather, randomizing NPC idle behaviors, and so on) so here’s another little module.

9 Likes
2

Hell yeah!! always wanted to get into markov chains

3 Likes
3

Cool.

The module itself is pretty simple in and of itself, but it does pull in a number of dependencies (the simpleGraph, intMath, and notReallyRandom modules). You could definitely do a simpler module with less deps if you just wanted do to probabilistic discrete state transformations without hysteresis.

Basically I used simpleGraph as a base because I wanted to use graph traversal tools for e.g. NPC AI stuff (to be able to basically cross-fade between hardcoded scripted behavior and random, probabilistic idle behaviors, for example).

And the notReallyRandom dependency is to allow for instancable PRNGs (for random-ish-but-actually-deterministic procgen stuff, being able to reset and repeat pseudorandom sequences, and so on) . Which is almost certainly not something most people are going to be worried about.

I’ll probably have some concrete usage examples fairly soon, as soon as I get around to refactoring this into my existing code.

2 Likes
4

I’ll look on it; if I post an adv3Lite port, this means that has got angelic and daemonic stamp of approval :wink: :smiley:

Jokes aside, an interesting module…

Best regards from Italy,
dott. Piergiorgio.

5

The only Markov I know is the old IFMud bot. There, that’s for the IF community lifers right there. :smiley: In any case, I’ll probably check this out at some point.

1 Like
6

Just pushed an update that adds an alternate syntax for declaring Markov chains. Example:

myChain: MarkovChain
        @[      'foo',  'bar',  'baz'   ]
        @[
                0,      0.75,   0.25,
                0.67,   0,      0.33,
                0.5,    0.5,    0
        ]
        ->[     0.34,   0.34,   0.32    ]
;

That’s

  • @[ state list ]
    The first bit is just a List of the state IDs, in this case “foo”, “bar”, and “baz”.
  • @[ probability matrix ]
    The next bit is another List formatted like a 2d matrix. In that view, the row indicates the state being transitioned from and the column the state being transitioned to, with the value being a decimal probability for that transition. So the first element in the List above is 0, indicating that the foo → foo transition has a probability of 0, the next element is the probability of foo → bar, which is 75%, then foo → baz (25%), then bar → foo (67%), and so on.
  • ->[ initialization vector]
    The last bit is the probability of each state being the initial state. If no IV is declared the first state in the state list (above) will always be used

This is mostly equivalent to the syntax described in the OP. This might be easier for some people to work with/visualize. And it might be more convenient for important data from a CSV or whatever.

I also added some linter checks for MarkovChain declarations. They’re disabled by default. To use them, compile with -D LINTER. If you do that you’ll also need the linter module.

4 Likes