# Automata-theoretic algorithms in online gaming

A long time ago, I did some research on reset sequences, words that, when given as input to a finite automaton in an unknown state, force it into a known state. The supposed application involved the design of factory machinery, and these sequences can also be used to synchronize transmitters and receivers using certain kinds of communication codes (so they're also called synchronizing sequences).

I recently found that

Anyway, apparently using actual algorithms to find these sequences leads to a two-order-of-magnitude speedup over a heuristic search. Always gratifying when that happens.

There's still some interesting unsolved math related to these sequences, by the way: Černý's conjecture states that every automaton that has a reset sequence at all has one with length quadratic in its number of states, but this is still not proven.

I recently found that

**atheorist**is using them for a different and interesting purpose: exploring from an unknown location in a known environment. Specifically, automating dungeon exploration in online adventure games. I guess for these purposes these games can be viewed abstractly as automata: you tell it to do something, you end up in a different state. So if you can find a reset sequence, you can program it as a sequence of actions to be performed to get you through the boring parts that you already know how to handle so you can get to where you actually want to go, even if you're teleported to some random spot in the dungeon. If you were entering the actions manually you might adapt to what you see, rather than blindly following a preset sequence of actions, but apparently programmed actions aren't allowed to be so sophisticated, so reset sequences are the right solution.Anyway, apparently using actual algorithms to find these sequences leads to a two-order-of-magnitude speedup over a heuristic search. Always gratifying when that happens.

There's still some interesting unsolved math related to these sequences, by the way: Černý's conjecture states that every automaton that has a reset sequence at all has one with length quadratic in its number of states, but this is still not proven.