I've been experimenting with player bots for interactive fiction. Besides being a fun exercise, I thought they might be a useful debugging tool. I even thought they might be able to prove the "validity" of a story model, e.g., that the story can never be played into an unfinishable state. I'm not sure that's possible with a non-trivial story, but I figured I'd give it a shot.

My first attempt at a bot took a shotgun approach. It analyzed the game data to plug accessible entities into command templates, executing commands like SIT ON THE COIN and EAT THE LADDER ad infinitum. Occasionally amusing, but not very useful. The most it might accomplish was to stumble across a bug. It wasn't likely to finish a whole game anytime before the heat death of the universe.

Enter the "autosuggest" library. I've been working on a point-and-click interface that allows players to build commands without typing. The story provides a list of available commands, and the interface breaks them into selectable words and phrases. (Picture it like the autocomplete portion of a mobile keyboard, but without the keyboard.) Lots of common commands can be provided automatically; for example, the story knows to include TAKE commands for any portable items in the player's vicinity. Authors can also inject custom suggestions wherever necessary.

Autosuggest makes it easy to refine a bot's behavior, since it limits the set of commands that the bot needs to try. If an item is not edible, autosuggest will not suggest a command to eat it. Already the bot has a significantly better chance of reaching the end of a game.

I added one more feature to make the bot a little smarter. When it executes random commands, it can easily get stuck in ruts where it moves back and forth between two rooms, repeatedly picks up and drops the same object, and so on. To avoid this behavior, the bot keeps track of the story's state by taking a snapshot of the game data for every turn. If it performs an action that would return the game to a previous state (i.e., the current snapshot matches an existing one), it reverts that action and tries something else.

Here's an example of state tracking. Let's say the bot is in a library. It performs TAKE BOOK. This action changes state by moving the book from the library to the bot. The next command it tries is DROP BOOK. This action would place the book back in the library; but looking at the snapshot history, the bot sees it's already been in that state, so it performs GO TO STREET instead. From there, DROP BOOK becomes a valid action again, because it would move the book to the street instead of the library.

Now that the bot was state-aware, I decided to take it one step further. Instead of performing random actions, it performs every available action and branches snapshots for each result, effectively playing through every possible permutation of the story simultaneously. It also detects when a branch reaches a state that another branch has already found, and stops running through the redundant branch.

To test the bot, I wrote a very simple game: a three-room house where the goal is to make breakfast. All of the commands required to win the game can be detected automatically through autosuggest. The shortest possible walkthrough is the following:

• Go to the living room
• Go to the kitchen
• Open the refrigerator
• Take the egg sandwich
• Open the microwave
• Put the egg sandwich in the microwave

The bot played through nine permutations of the game. Two of them resulted in victory. The shorter victory's transcript was about the same as the above. The longer one had one extra move: the bot was thoughtful enough to close the refrigerator after taking the sandwich.

In the other seven games, the bot gave up. The game should never have an unwinnable state, so what was the problem? Here's the shortest failure:

• Go to the living room
• Go to the kitchen
• Open the refrigerator
• Go to the living room
• Go to the bedroom

The bot will not typically return to a previous room, because doing so would return the game to a previous state. But after opening the refrigerator, returning to the living room became valid; the last time the bot had been in the living room, the refrigerator was closed. It followed its tracks back to the bedroom, where it had nothing else to do that would result in a new game state, and decided it had reached a dead end.

So it's far from perfect. It's capable of finding endings, and it's capable of detecting unwinnable states, but it also hits a lot of false positive unwinnables. I don't know if I can do anything about the false positives. It's probably NP-hard if not NP-complete.