That's where a dynamic n-gram comes into play. Train the markov model from 1 to 5 n-grams, and then scale according to the number of potential paths available.

You'll also need a "sort of traversal stack" so you can rewind if you get stuck several plies in.