Building the Go Game in Elixir: Time Travel and the Ko Rule

Welcome back to Elixir Alchemy! Two weeks ago, we started our adventure implementing the Go game in Elixir using Phoenix LiveView. Today, we return to the game to add the ability to undo and redo moves, then we'll implement Go's 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 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 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 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.

# 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.

# 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.

# 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.

# 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.

# 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.

# 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.

# 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.

# 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.

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.

# 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.

# 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.

# 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.

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.

# 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.

# 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.

# 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.

# 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. Until next time, and in the meantime, be careful with your newfound time travel abilities!