Game tree or state machine? How to explain the narrative flow for collaborators?

Hi there, friends and foes of democracy, 

I am currently preparing the ground for the contribution of artists, musicians and script consultants. While the game is kind of clear in my head, I need to put on paper all of my thoughts in a way that they can understand. I learned last year how hard this task is. Thankfully, I also find it incredibly enjoyable. 

All my contributors seem to agree on one thing: I should express clearly how the story evolves. I should make an ordered list of scenes, or, if the story is nonlinear, explain how each decision leads to this or that path and ultimately, which outcome. 

Unfortunately, knowing my prototype and the future game, I know I can't do that. I can at most offer an approximate sequence of decisions and scenes of the winning strategy. But the winning strategy is probably just about 30% of the game. The game is not linear and not very representable by a game tree chart. Instead, the correct tool to understand the game is a finite state machine.

I decided to sit and spend a day writing an explanation why I can't describe how the game evolves, what is a state machine and how it is useful in this project. Even although my academic side cries for the lack of references in this writing, I decided to share with you all, hoping it is cool and that you may share your thoughts on it.

Game trees and state machines

Games are branching structures. Each decision made by the player, and each random draw of luck, makes the story branch into different paths. A game with just two binary decisions could look like this:

I love these charts. Indeed, I teach game theory at my university. I know game trees are helpful to visualize games. However, they are only the best tool in games that have few possible choice nodes and endings. 

Game trees are also important when the path taken by a player matters. Sometimes, however, they are not very useful, but confusing.

When game trees get confusing: a simple trading game example

While this structure can represent games of any kind, it is less useful to represent games that are more complex. Consider, for instance, Chess. The current position of pieces and whose turn it is, is almot all that matters. There are exceptions to this rule, but only two (tie conditions and castling). Other than that, the path taken is of no interest, only the state of the game.

Suppose, now, that we have a game where a player can buy wheat in city A to sell in city B and can buy wine in B to sell in A; she can do this repeatedly, if she has money. The player can also go to C for a vacation, provided she has enough money. A game tree here would not help understand this game, for a number of reasons:

• Representing just a few turns of this game would create a massive game tree. For instance, if this game has 10 traveling turns, it will have 1024 endings, and about twice as many branches. 
• If the game tree includes other details, such as how much money was spent buying goods, how many of the goods were sold, decisions are more complex than binary and the game can easily have tens of millions of branches in just 10 rounds.
• Knowing the path will not be as important, as several branches and endings will look similar. The game tree diagram is not very useful.

For this reason, many game designers do not care as much about decision paths, caring instead for the state of the game. They don’t care whether the player was in city A, B or C three rounds ago. What they care is where she is now, how much time has passed, what the player is carrying, how rich she is, etc. If a particular past event matters, such as, “was in B when the plague began”, game designers just add a variable to account for that state. But unimportant past events can be forgotten. The sequence of choices does not matter directly, but only indirectly, through its effect on game states.

State machine

Game designers use the metaphor of a “finite state machine”. The game is understood as a machine whose current state can be fully described by a set of predefined variables. Whatever matters for the game can be captured by one of those variables or a combination of them.

Think of a food processor. It can be connected to electricity or not. If it is connected, it can be: off, operating in bursts or operating continuously. It can be configured to blend or grate. Inside it, one can put a cheese or cake mixture. Given its current state, one can predict what will happen. A machine that is powered and operating continuously grating cheese will grate it all in a few seconds. It does not matter whether the cheese was put in the machine before or after it was connected to the power source (although, for safety concerns, it could matter). Its current state will determine its next state. Cooks manipulate states to produce the food they want.

In a similar vein, a game state may be defined by a finite number of variables. When a player comes to a battle, it may not matter whether the weapon and armor she uses was bought or stolen; for that task, what matters is the quality of these tools. Players select strategies to manipulate game states, just like cooks.

Using state machines to understand the simple trade game

The trade game described before could have the following states:

• Geographical description: Where the player is, where is she going, at what speed.
• Inventory, that is, how much it carries of: wheat, wine, money, food supplies.
• Time: How many rounds have passed, how many rounds since last vacation in C.
• Player stats: Health, victory points.

Machine state games do not record the path, and do not need to know the map of possible paths. Instead, when events or encounters occur, they check the game’s state to find what will happen. Here are some examples:

• Burnout.
  • At night, check if the player is for more than 3 traveling rounds without rest.
  • If so, the player gets burnout. Lose 1 health and 2 points.
• Pirate attack:
  • Check if the player is carrying 20 tons of cargo or more.
  • If she is, her ship is slow and will be captured by the pirates. If less, she escapes.
  • If the ship is captured by the pirates, check how far from the coast it is.
  • If near, the player jumps and swims to escape the pirates. If not, game over.
• Rat infestation:
  • When leaving B, check if the player still has wheat in cargo.
  • If so, she gets a rat infestation. Decrease health by 3. Lose all wheat.
• Starvation:
  • At night, check if the player has 0 meals left.
  • If so, it is game over because of starvation.
• Selling cargo:
  • Check how much cargo the player is selling.
  • Check it has enough cargo to sell this quantity.
  • Check price of the object been sold.
  • Calculate revenue value as price*quantity sold.

Moreover, events and their effects can depend on combined states.

The video Narrative Sorcery: Coherent Storytelling in an Open World shows how a few machine state variables can easily support several different narrative paths. Games based on state machines can allow for emergent narratives, where the creator himself is not fully aware of all the paths that players will end up taking.

Combining state machine and game trees: Mario Bros 3

Most games have aspects that are better understood with a state machine and other aspects that are better understood with a game tree. Take Mario Bros 3 for example. While playing a level, the game is mostly a finite state machine. The game can be described by the following variables:

• Which level is been played.
• Location and two-dimensional speed of Mario in this level.
• How many lives and coins Mario has.
• What size is Mario now (small or large).
• Whether Mario has a superpower (tail, fireball, star acceleration)
• Which enemies have been killed.
• Which objects have been extracted.
• How much time has passed.

To know whether Mario can fly, the game must check his speed, and whether he has the tail superpower. To check if Mario will die upon colliding with an enemy, the game checks Mario’s size (small will result in death, large will result in downsizing). A mushroom will make Mario grow if he is currently small, but otherwise have no effect.

At the same time, it is useful to think of Mario Bros 3’s map system as a game tree. At any point in time, Mario has only a few choices to make with regards to the next level he will play. And upon completing a level, new paths may open.

Other games, such as Witcher 3, offer an open world that allows players to complete side missions in almost any order, requiring a game state structure. However, missions themselves work as mini games that are linear or can be understood with a very simple and small game tree.

An example from Socratic Democracy

In Socratic Democracy, the path is often less important than the state. For instance, Leonidas can be ostracized if the following conditions apply:

• It is spring.
• Bion is alive.
• Leonidas has asked Bion to investigate corruption in the past.
• Bion has already investigated Drakon and Charon, so it is now targeting Leonidas.
• Bion is not busy being a general.
• Leonidas has been corrupt in the past, by performing one of the following acts:
  • Using state money for private uses.
  • Stealing objects from expropriated oligarchs.
  • Increasing his guard beyond 5 individuals.

If all these states are true, Leonidas will be put to a judgement. It doesn’t matter how many years have passed, how many oligarchs have been expropriated, or whether Leonidas won or lost the last election. Ostracism can occur in the third year as well as the tenth. The conditions can be met in different order.

Even when it would be fair for Leonidas to be ostracized, he can escape this punishment in several ways:

• Leonidas may never select “investigate corruption” as a policy, so that Bion does not begin his investigation.
• Leonidas may start a war and select Bion as general to keep him busy and unable to investigate corruption.
• Leonidas can re-appoint Bion as general, in hopes he will get killed in the war.
• Leonidas may subsidize the theater every year, increasing his popularity to such an extent that the people do not ostracize him, even if given a chance to do so.

Each strategy will produce a different narrative. Players who decide not to investigate corruption will be unable to ostracize Charon before he turns against Leonidas. Players who use the war to kill Bion will be accused of doing so by Achilles. And subsidizing the theater creates a long-term problem, as theater plays are constantly satirizing Leonidas, harming his reputation permanently.

Conclusion

Game trees are often an inadequate tool to understand and map complex narrative games. While it would be nice to create a chart that fully explains how the story goes, Socratic Democracy's is too complex for that. The game branches combinatorially. There are easily a few thousands of ways to play it. 

I hope that you, my reader, had an enjoyable reading. And I hope my collaborators will both enjoy the concepts and understand how to make them work. I am currently writing additional materials to make that a real possibility, including a tentative list of all game state variables.

Cheers,

Pedro