A bot that answers using Markov chains. A Markov chain is a stochastic model describing a sequence of events where the probability of each event depends only on the state attained in the previous one.

This implementation is order-N: each transition is keyed on the previous N tokens. Order 1 is maximally inventive and usually incoherent; higher orders track the source corpus more closely and diverge less. Order 2 is the default compromise.

Install

go install github.com/zg/markovbot/cmd/markovbot@latest

Use

# train (incremental — training again extends the model)
markovbot train -model m.json -order 2 corpus.txt

# generate
markovbot gen -model m.json -n 40

# reply, seeded with an incoming message
markovbot reply -model m.json "what do you think about go"

Library

c, _ := markov.New(2)
c.TrainAll(lines)
out, _ := c.Generate(rand.New(rand.NewSource(seed)), 40)

Design notes

Sampling is reproducible. Successors are drawn in proportion to observed frequency, walking a sorted key list rather than the map directly. Go randomises map iteration order, so sampling the map in place would make output vary between runs even with a fixed seed. Given the same seed, this chain always produces the same text — which is what makes it testable.

Counts, not repeated lists. Each prefix stores successor counts, so retraining on the same corpus does not grow memory without bound, and sampling stays proportional to what was actually observed.

Saves are atomic. SaveFile writes to a temporary file and renames it into place, so an interrupted save cannot leave a truncated model where a working one used to be. Totals are derived on load rather than trusted from the file, so a hand-edited model cannot desynchronise counts from their sum.

Sentinels cannot be injected. Chain boundaries use \x00-prefixed sentinels and tokenisation strips them, so a corpus containing those strings cannot forge a start or end of sample.

Tests

Beyond the usual table-driven cases, the suite pins the statistical behaviour: training a b 300 times and a c 100 times must yield P(b|a) ≈ 0.75 over 20,000 draws. Determinism is checked by regenerating from the same seed; concurrency safety is checked under -race with training and generation running simultaneously.

go test -race ./...
go test -bench=. ./...