Building the Go Game in Elixir: Time Travel and the Ko Rule
Tags: elixir, phoenix, beginners
Published: 2019-07-04 11:53:11

---
title: Building the Go Game in Elixir: Time Travel and the Ko Rule
layout: layout_elixir_alchemy
description: Today, we continue with our Go game to add the ability to undo and redo moves and implement Go's ko rule.
tags: elixir, phoenix, beginners
cover_image: https://blog.appsignal.com/images/blog/2019-07/go-future.jpg
canonical_url: https://blog.appsignal.com/2019/07/04/elixir-alchemy-building-go-in-elixir-time-travel-and-the-ko-rule.html
published: true
---

Welcome back to Elixir Alchemy! Two weeks ago, we started our adventure [implementing the Go game in Elixir using Phoenix LiveView](https://blog.appsignal.com/2019/06/18/elixir-alchemy-building-go-with-phoenix-live-view.html). Today, we return to the game to add the ability to undo and redo moves, then we'll implement Go's [ko](https://senseis.xmp.net/?Ko) rule.

## Onward!

In this article we will mostly focus on the implementation of the game, but still learn about Phoenix LiveView on the way. The [final result](https://hayago.herokuapp.com) of today's article includes undo and redo buttons, and the game prevents you from making moves that would revert the game to a previous state.

The [new starter app](https://github.com/jeffkreeftmeijer/hayago/tree/starter-2) contains the result of the last episode, which is a Phoenix application that uses LiveView to render and update the board. It implements some of Go's rules in its `State` module and keeps track of each player's captured stones. This time, we'll add a `Game` module that keeps the state of the whole game, including the previous moves.

Prefer to skip ahead and read the code? The [master branch](https://github.com/jeffkreeftmeijer/hayago/tree/master) includes all the changes we'll make in this episode, along with test coverage and thorough documentation of all functions.

## Time travel preparations

Before we do some time traveling and let players undo and redo moves, the game needs to keep a history of the moves made since it started. Currently, it keeps one `State` struct, which is accessible as `@state` in the template.

Whenever a player makes a move by clicking one of the invisible buttons on the board, the `GameLive` module handles the event. It uses `State.place/2` to create a new state struct and assigns that as the new state to update the view.

``` elixir
# lib/hayago_web/live/game_live.ex
defmodule HayagoWeb.GameLive do
  # ...

  def handle_event("place", index, %{assigns: assigns} = socket) do
    new_game = Game.place(assigns.game, String.to_integer(index))
    {:noreply, assign(socket, game: new_game, state: Game.state(new_game))}
  end
end
```

Because of this implementation, there's currently no way of jumping back in history, as our game replaces the state with each move, and forgets the previous state.

To retain history, we'll add a struct named `Game`, which keeps a history of states in its `:history` attribute. When the game starts, it has a single, empty state in its history list to represent the empty board.

``` elixir
# lib/hayago/game.ex
defmodule Hayago.Game do
  alias Hayago.{Game, State}
  defstruct history: [%State{}]

  # ...
end
```

We'll add a convenience function to get the current state from a game. The first state in the history list is always the current state, so we can take the list's first element to get the current state.

``` elixir
# lib/hayago/game.ex
defmodule Hayago.Game do
  # ...

  def state(%Game{history: [state | _]}) do
    state
  end

  # ...
end
```

Finally, we'll implement a `place/2` function to the `Game` module. It uses `State.place/2` to create a new state struct, then prepends that to the history list.

``` elixir
# lib/hayago/game.ex
defmodule Hayago.Game do
  # ...

  def place(%Game{history: [state | _] = history} = game, position) do
    %{game | history: [State.place(state, position) | history]}
  end
end
```

Now, let's use the new game struct in the `GameLive` module. The `mount/2` function is used to set up the game. Instead of creating a state struct and assigning it directly to the socket, we'll create a new game struct and assign that to the `:game` assign.

We'll still use the state struct in the template, so we'll preload it in the live view by calling our new `Game.state/1` function and assigning the result as `:state`.

``` elixir
# lib/hayago_web/live/game_live.ex
defmodule HayagoWeb.GameLive do
  alias Hayago.Game
  use Phoenix.LiveView

  # ...

  def mount(_session, socket) do
    game = %Game{}
    {:ok, assign(socket, game: game, state: Game.state(game))}
  end

  # ...
end
```

When placing a stone, we'll now call the `Game.place/2` function to update the current state while retaining the history list. Again, we use `Game.state/1` on the updated game to preload the state.

``` elixir
# lib/hayago_web/live/game_live.ex
defmodule HayagoWeb.GameLive do
  alias Hayago.Game
  use Phoenix.LiveView

  # ...

  def handle_event("place", index, %{assigns: assigns} = socket) do
    new_game = Game.place(assigns.game, String.to_integer(index))
    {:noreply, assign(socket, game: new_game, state: Game.state(new_game))}
  end
end
```

If we try the game again, we won't see any changes. While we're keeping the history of all moves, we aren't doing anything with it yet.


## Time Travel

Although we're now keeping a history of game states, all functions in our `Game` module still only use the first state in the list. As each move prepends a state to the history list, the first in the list is always the latest state.

To allow jumping back and forward, we'll add an attribute named `:index` to the `Game` struct, which defaults to 0.

``` elixir
# lib/hayago/game.ex
defmodule Hayago.Game do
  alias Hayago.{Game, State}
  defstruct history: [%State{}], index: 0

  # ...
end
```

By having an index, we can jump back to a previous state without having to drop states from the front of the list. Instead, we'll update our `state/1` function to take the index into account. Instead of returning the first state in the list, it uses the game's index to find the current state in the list.

``` elixir
# lib/hayago/game.ex
defmodule Hayago.Game do
  # ...

  def state(%Game{history: history, index: index}) do
    Enum.at(history, index)
  end

  # ...
end
```

Now, if we have a game with a three-state history, setting the `:index` attribute to 1 returns the second state in the list, essentially reverting to that state.

To jump to a different index, we'll add a convenience function called `jump/2`, which overwrites a `Game` struct's `:index` attribute.

``` elixir
defmodule Hayago.Game do
  # ...

  def jump(game, destination) do
    %{game | index: destination}
  end
end
```

Now that our game module keeps a history of moves and we can jump between them, let's add buttons to undo and redo moves when playing the game.

``` elixir
# lib/hayago_web/templates/game/index.html.leex
# ...

<div class="history">
  <button phx-click="jump" phx-value="<%= @game.index + 1%>">Undo</button>
  <button phx-click="jump" phx-value="<%= @game.index - 1%>">Redo</button>
</div>
```

We use "jump" as the value for both buttons' `phx-click` attributes, which is the name of a function we'll implement shortly in the `GameLive` module.

The `phx-value` attribute is used to pass the history index we'd like to jump to. The history list reverses because new moves prepend to the history list. So to undo a move, we'll increase the current index by 1, and we'll decrease it by 1 to redo.

In the `GameLive` module, we'll handle the jump event by calling `Game.jump/2` with the current game and the passed index, giving us a new game struct that we'll assign on the socket. Like before, we update the state assign for convenience.

``` elixir
# lib/hayago_web/live/game_live.ex
defmodule HayagoWeb.GameLive do
  # ...

  def handle_event("jump", destination, %{assigns: %{game: game}} = socket) do
    new_game = Game.jump(game, String.to_integer(destination))
    {:noreply, assign(socket, game: new_game, state: Game.state(new_game))}
  end
end
```

If we open our browser and navigate to https://localhost:4000, we can see that the undo and redo buttons work. After placing a few stones, we can click the undo button to get the last one removed, and the redo button to get it back again.

## Branching off in History

However, if we undo a move and try to place a stone, we notice that the new stone doesn't get added to the board. Instead, the stone we just removed by pressing the undo button reappears.

It turns out we have one more step to take before we can place a new stone after pressing the undo button. Let's break down what's happening.

1. We place a stone on the board, which prepends a new state to the history list.
2. We press the undo button to increase the history index to 1, bringing us back to our initial state, giving us an empty board again.
3. We try to place a new stone, which prepends a new state to the history list. The Game's index remains at 1.

The new state is the first in the list, meaning its index is 0, but the Game index is still 1. That index belongs to the move we've undone by pressing the undo button. Essentially, our newly added stones are delayed by one move.

To fix this, we need to slice any undone states from the list whenever we add a new state by placing a new stone. Removing states from the history allows users to branch off in a different direction after undoing moves.

``` elixir
# lib/hayago/game.ex
defmodule Hayago.Game do
  # ...

  def place(%Game{history: history, index: index} = game, position) do
    new_state =
      game
      |> Game.state()
      |> State.place(position)

    %{game | history: [new_state | Enum.slice(history, index..-1)], index: 0}
  end

  # ...
end
```

In the new version of our `place/2` function, we use `Enum.slice/2` to drop the undone moves from the history list. We'll also reset our game's index attribute to 0, which makes sure our newly added stones always immediately appear. Now time travel works, though we are not sure whether this means we need to worry about avoiding the [predestination paradox](https://www.quirkbooks.com/post/classic-time-travel-paradoxes-and-how-avoid-them).

## Disabling Inapplicable Undo and Redo Buttons

Now when there are no moves to undo or redo, we need to make sure the undo and redo buttons are disabled. To do that, we'll implement a function named `history?/2`, which takes a game struct and an index and returns whether that index is part of the game's history.

``` elixir
# lib/hayago/game.ex
defmodule Hayago.Game do
  # ...

  def history?(%Game{history: history}, index) when index >= 0 and length(history) > index do
    true
  end

  def history?(_game, _index), do: false
end
```

Our function checks if the requested index is above 0 to make sure the game doesn't allow jumping forward when there are no moves done yet. Then, it checks if the length of the history list is higher than the index, to make sure we don't overshoot the list when undoing moves.

With our new function in place, we can check if the game can undo and redo to the previous and next move before rendering the button. If it can't, it renders a disabled version.

``` elixir
# lib/hayago_web/templates/game/index.html.leex
<div class="history">
  <%= if Hayago.Game.history?(@game, @game.index + 1) do %>
    <button phx-click="jump" phx-value="<%= @game.index + 1%>">Undo</button>
  <% else %>
    <button disabled="disabled">Undo</button>
  <% end %>

  <%= if Hayago.Game.history?(@game, @game.index - 1) do %>
    <button phx-click="jump" phx-value="<%= @game.index - 1%>">Redo</button>
  <% else %>
    <button disabled="disabled">Redo</button>
  <% end %>
</div>
```

Trying the game again, we'll see that we can't undo further than the list of previous moves, and we can't redo into the future.

## The Ko Rule

Aside from allowing the player to undo and redo moves, keeping history allows us to implement Go's ko rule.

> A play is illegal if it would have the effect (after all steps of the play have been completed) of creating a position that has occurred previously in the game.

Go prevents players from making moves that revert the board to a previous state. In practice, this happens when a player captures a stone, and the other player makes a move that immediately captures the newly added stone.

Currently, we validate moves in the `State.legal?/2` function, which checks if a position is empty, and makes sure placing a stone on that position has liberties.

To implement the ko rule, we need the history of game states, meaning we need access to the `Game` struct. To do that, we add a function named `Game.legal?/2`.

``` elixir
# lib/hayago/game.ex
defmodule Hayago.Game do
  # ...

  def legal?(game, position) do
    State.legal?(Game.state(game), position) and not repeated_state?(game, position)
  end

  defp repeated_state?(game, position) do
    %Game{history: [%State{positions: tentative_positions} | history]} =
      Game.place(game, position)

    Enum.any?(history, fn %State{positions: positions} ->
      positions == tentative_positions
    end)
  end

  # ...
end
```

Our new function takes the game struct as its first argument and the position a new stone is placed as the second. It calls `State.legal?/2` to make sure the already-implemented rules are satisfied. Then, it makes sure the new state hasn't already happened using `repeated_state?/2`, a private function that places the stone and compares the new state to the history list.

Finally, we'll update the template to switch from using `State.legal?/2` directly to using `Game.legal?/2`, which takes the game history into account.

``` elixir
# lib/hayago_web/templates/game/index.html.leex
# ...

<div class="board <%= @state.current %>">
  <%= for {value, index} <- Enum.with_index(@state.positions) do %>
    <%= if Hayago.Game.legal?(@game, index) do %>
      <button phx-click="place" phx-value="<%= index %>" class="<%= value %>"></button>
    <% else %>
      <button class="<%= value %>" disabled="disabled"></button>
    <% end %>
  <% end %>
</div>

# ...
```

Back in the game, we'll see that we can't make a move that reverts the game's state to one that's in the history anymore.

## Time travel and the ko rule

We've improved our game by adding a smart way to revert moves, and through that, we were able to implement the Ko rule. Along the way, we've learned how flexible LiveView is, as we hardly touched the live view code, although we've changed quite a bit in the game.

This concludes part two of our series on implementing the Go game with Elixir and Phoenix LiveView. We'd love to know how you're enjoying it so far, and what you'd like to learn about next.

If you want to have this article in your inbox as soon as it appears, travel back in time and [subscribe to the Elixir Alchemy list](https://blog.appsignal.com/elixir-alchemy). Until next time, and in the meantime, be careful with your newfound time travel abilities!