Baseball is a State Machine

A common pattern that emerges in software development is the need to represent data that has a discrete known value. In Kotlin we use tools like enumerations and sealed classes to show that a complex value exists as one of some known set of types. However, it may also happen that one needs to model how a piece of data might transition between its known types. To pile on the complexity, the system might also need to react to these changes in a predictable way. This is where a more complex pattern must be introduced. One pattern that can handle this complexity is a Finite State Machine.

Finite State Machine #

A finite state machine (shortened simply as state machine going forward) is a pattern for modeling data that exists in discrete states and has well defined transitions between those states. A simple abstract example is a light switch. A light switch can be either "off" or "on" but not both, it's discrete states. The light switch can be "toggled", its transition, to change between those states.

While this example is informative in its simplicity, it lacks real world application. A more concrete example would be to model a simplified version of baseball. The example will be taken step by step below, but if you wish to follow along, the code is available in this repository.

Example - Baseball #

This example could scale to cover the full complexity of a real life baseball game but would quickly become too unwieldy to describe in a single article. So this example will focus on the game at a high level by tracking score, outs, and the current inning. It will handle at bats as a single event instead of tracking individual strikes and balls. Finally, it will ignore play results outside of a standard hit and out; so no balks, no double plays, and no hit by pitch situations.

To start this example, the state machine will be modeled in the abstract and then applied to code. This has the primary benefit of creating a system that more accurately reflects the expected behavior for the model of the state. Conversely, if the system was built in code first, there would be a constant tension to force the model of the system to reflect what was built and not the intended behavior.

States #

The system starts in the "Game Started" state, which represents a game that has begun, but no players have taken any action. This is the state right before the umpire cries "Play Ball!". The next and primary state is "Batter Up". This represents a batter during their at bat but before they strikeout, walk, or get contact with the ball. If the batter gets contact, the state is now a "Live Ball". Then depending on the result of the "Batter Up" or "Live Ball" states, eventually the game ends and goes to the "Game Over" state. Note*

Events #

Defined next are the events that can occur at each state in the state machine.

• "Game Started"
  • "on Play Ball" - Represents the umpire starting the game
• "Batter Up"
  • "on Batter Contact" - Represents the batter making contact with the ball
  • "on Batter Walk" - Represents the batter getting a base on balls, a walk
  • "on Batter Out" - Represents the batter out at the plate, perhaps through a strikeout
• "Live Ball"
  • "on Hit" - Represents a successful hit by the batter
  • "on Defensive Out" - Represents an out by the defending team's fielders
• "Game Over"
  • "on New Game" - Represents starting a new game after the completion of a previous game

Transitions #

The events and states can now be coordinated to understand the transitions that can occur in the state machine. This includes the conditional logic that determines what transitions are intended to occur.

• "Game Started"
  • "on Play Ball" - Transitions to "Batter Up"
• "Batter Up"
  • "on Batter Contact" - Transitions to "Live Ball"
  • "on Batter Walk" - Transitions to "Game Over" if the winning run scores. Otherwise return to "Batter Up".
  • "on Batter Out" - Transitions to "Game Over" if the final out was recorded. Otherwise return to "Batter Up" for either the next batter or for the next team if the side is out.
• "Live Ball"
  • "on Hit" - Transitions back to "Batter Up" unless the game is over, in the case of a walk-off win, then it transitions to "Game Over"
  • "on Defensive Out" - Same as "on Batter Out" above, Transitions to "Game Over" if the final out was recorded or "Batter Up" for the next batter or advance the inning side and return to "Batter Up"
• "Game Over"
  • "on New Game" - Transitions to "Game Started"

Side Effects #

As with any pure functional data structure, there must be a mechanism for interacting with the rest of the system through side effects. In the example system, there will be a single side effect called "Announce Home Run" to notify users that a home run has occurred.

State Diagram #

Bringing all these parts together, we can use a State Diagram to visualize the states, events, and transitions. In this version the conditionals and data updates are omitted to simplify the diagram but could be included if needed.

See it in code #

Switching to code, this example uses the StateMachine library from Tinder which can be found on their GitHub here. It is a simple implementation of a state machine that provides what is needed for a state machine without a lot of bells and whistles. Another alternative in the space that has many more features including coroutine and KMP support is KStateMachine which can be found here on GitHub.

The state is defined as a sealed class with a shared "GameState" property that is a data class containing the state of the baseball game such as outs and score.

sealed class State(val gameState: GameState) {
    data class GameStarted(
      private val initialState: GameState
    ) : State(initialState)

    data class BatterUp(
      private val updatedState: GameState
    ) : State(updatedState)

    data class LiveBall(
      private val updatedState: GameState
    ) : State(updatedState)

    data class GameOver(
      private val updatedState: GameState
    ) : State(updatedState)
}

data class GameState(
    val inning: Inning = Inning(1, InningSide.TOP),
    val homeScore: Int = 0,
    val awayScore: Int = 0,
    val outs: Int = 0,
    val bases: Bases = Bases(
      onFirst = false, 
      onSecond = false, 
      onThird = false
    ),
)

Next define the events also as a sealed class. Additionally, HitType is defined as an enumeration to pass with the OnHit event.

sealed class Event {
    object OnPlayBall : Event()
    object OnBatterOut : Event()
    object OnBatterWalk : Event()
    object OnBatterContact : Event()
    data class OnHit(val hitType: HitType) : Event()
    object OnDefensiveOut : Event()
    object OnNewGame : Event()
}

enum class HitType { SINGLE, DOUBLE, TRIPLE, HOME_RUN } 

For the last setup step, define the SideEffects. The example uses a sealed class but in this case could also use an enumeration.

sealed class SideEffect {
    object AnnounceHomeRun : SideEffect()
}

Finally, bring all the parts together using the StateMachine.create function. initialState defines the state the state machine will start in. Then the state<State> blocks define the valid states for the state machine. Inside the state blocks, the on<Event> blocks define the events that can be handled for a given state. Within the on block any necessary logic can be run.

For example within the state<State.LiveBall> in on<Event.OnHit> a new game state is created using recordHit to update the bases and scores, a side effect is created if the hit was a home run, and finally a transition is requested to GameOver or BatterUp conditionally after checking if isGameOver.

In the below code snippet the BatterUp and GameOver states are omitted, you can see the StateMachine.create in its entirety here in the example project.

val baseballstatemachine =
  StateMachine.create<State, Event, SideEffect> {
      initialState(State.GameStarted(GameState()))

      state<State.GameStarted> {
          on<Event.OnPlayBall> {
              transitionTo(State.BatterUp(gameState))
          }
      }

    ...

      state<State.LiveBall> {
          on<Event.OnHit> {
              val newState = 
                  recordHit(gameState, it.hitType)

              val sideEffect =
                  if (it.hitType == HitType.HOME_RUN) {
                      SideEffect.AnnounceHomeRun 
                  } else {
                      null
                  }

              if (isGameOver(newState)) {
                  transitionTo(
                      State.GameOver(newState),
                      sideEffect
                  )
              } else {
                  transitionTo(
                      State.BatterUp(newState),
                      sideEffect
                  )
              }
          }
          on<Event.OnDefensiveOut> {
              val newGameState = recordOut(gameState)

              if (isGameOver(newGameState)) {
                  transitionTo(
                      State.GameOver(newGameState)
                  )
              } else if (isSideOut(newGameState)) {
                  val switchSidesGameState = 
                    advanceInningSide(gameState)
                  transitionTo(
                    State.BatterUp(switchSidesGameState)
                  )
              } else {
                  transitionTo(
                      State.BatterUp(newGameState)
                  )
              }
          }
      }

      ...
  }

The state machine is ready to use! The current state of the state machine can be accessed using baseballStateMachine.state. Events can be passed to the machine using val result = baseballStateMachine.transition(EVENT) where result is a type StateMachine.Transition which can be valid or invalid and will contain the SideEffects, new State, and previous State. That's all that is required to set up and use a state machine using the StateMachine library.

Testability #

A brief note on testing. So long as only deterministic actions are managed within the state machine, the well defined states and transitions are intuitive to test. Shown below is a simple test covering a home run and the accompanying state changes and side effects.

@Test
fun `inning with home run has correct flow`() {
    assertTrue(
      baseballStateMachine.state is State.GameStarted
    )

    // Start Game
    baseballStateMachine.transition(Event.OnPlayBall)
    assertTrue(
      baseballStateMachine.state is State.BatterUp
    )

    // Home Run
    baseballStateMachine.transition(Event.OnBatterContact)

    assertTrue(
      baseballStateMachine.state is State.LiveBall
    )

    val result = baseballStateMachine.transition(
      Event.OnHit(HitType.HOME_RUN)
    )
    assertTrue(
      baseballStateMachine.state is State.BatterUp
    )
    assertEquals(
      baseballStateMachine.state.gameState,
      GameState(awayScore = 1)
    )

    assertTrue(result is StateMachine.Transition.Valid)
    assertEquals(
      (result as StateMachine.Transition.Valid)
          .sideEffect,
      SideEffect.AnnounceHomeRun
    )
}

Conclusion #

State machines are a valuable tool when designing and building software systems that are well defined, correct, and testable. As always, be sure to choose the right tool for the job. If that job is modeling discrete states with known transitions, a state machine is likely a great choice. Until next time, thanks!

Footnotes #

• Note that in the example, states that would have only one correct transition have been omitted, (e.g. there is no "Inning Side Started" at which the only options would be to transition to "Batter up". This excludes the "Game Started" and "Game Over" states as it is useful to have an initial and final state to our model for completeness). Additionally there are no states that would requires the consumer to request the correct transition or request a generic transition (e.g. there is no "Inning Side Out" during which the consumer would need to request transitioning to either "Game Over" or "Batter Up" or would have to use a generic continue type event). This decision is two fold as it both streamlines the example while also allowing the states and events to be both descriptive and correct. In the given example, the known transition logic belongs to the state machine and not the consumer. The example can be expanded to include these additional states as can be seen on this branch if desired.

Did you find this content helpful?

Please share this post and be sure to subscribe to the RSS feed to be notified of all future articles!

Want to go above and beyond? Help me out by sending me $1 on Ko-fi. It goes a long way in helping run this site and keeping it advertisement free. Thank you in advance!

• Previous: Dependency Injection vs Service Location
• Next: Manage Dependencies with Gradle BOMs