elixir

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

Jeff Kreeftmeijer

Jeff Kreeftmeijer on

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.

1# lib/hayago_web/live/game_live.ex
2defmodule HayagoWeb.GameLive do
3  # ...
4
5  def handle_event("place", index, %{assigns: assigns} = socket) do
6    new_game = Game.place(assigns.game, String.to_integer(index))
7    {:noreply, assign(socket, game: new_game, state: Game.state(new_game))}
8  end
9end

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.

1# lib/hayago/game.ex
2defmodule Hayago.Game do
3  alias Hayago.{Game, State}
4  defstruct history: [%State{}]
5
6  # ...
7end

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.

1# lib/hayago/game.ex
2defmodule Hayago.Game do
3  # ...
4
5  def state(%Game{history: [state | _]}) do
6    state
7  end
8
9  # ...
10end

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.

1# lib/hayago/game.ex
2defmodule Hayago.Game do
3  # ...
4
5  def place(%Game{history: [state | _] = history} = game, position) do
6    %{game | history: [State.place(state, position) | history]}
7  end
8end

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.

1# lib/hayago_web/live/game_live.ex
2defmodule HayagoWeb.GameLive do
3  alias Hayago.Game
4  use Phoenix.LiveView
5
6  # ...
7
8  def mount(_session, socket) do
9    game = %Game{}
10    {:ok, assign(socket, game: game, state: Game.state(game))}
11  end
12
13  # ...
14end

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.

1# lib/hayago_web/live/game_live.ex
2defmodule HayagoWeb.GameLive do
3  alias Hayago.Game
4  use Phoenix.LiveView
5
6  # ...
7
8  def handle_event("place", index, %{assigns: assigns} = socket) do
9    new_game = Game.place(assigns.game, String.to_integer(index))
10    {:noreply, assign(socket, game: new_game, state: Game.state(new_game))}
11  end
12end

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.

1# lib/hayago/game.ex
2defmodule Hayago.Game do
3  alias Hayago.{Game, State}
4  defstruct history: [%State{}], index: 0
5
6  # ...
7end

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.

1# lib/hayago/game.ex
2defmodule Hayago.Game do
3  # ...
4
5  def state(%Game{history: history, index: index}) do
6    Enum.at(history, index)
7  end
8
9  # ...
10end

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.

1defmodule Hayago.Game do
2  # ...
3
4  def jump(game, destination) do
5    %{game | index: destination}
6  end
7end

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.

1# lib/hayago_web/templates/game/index.html.leex
2# ...
3
4<div class="history">
5  <button phx-click="jump" phx-value="<%= @game.index + 1%>">Undo</button>
6  <button phx-click="jump" phx-value="<%= @game.index - 1%>">Redo</button>
7</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.

1# lib/hayago_web/live/game_live.ex
2defmodule HayagoWeb.GameLive do
3  # ...
4
5  def handle_event("jump", destination, %{assigns: %{game: game}} = socket) do
6    new_game = Game.jump(game, String.to_integer(destination))
7    {:noreply, assign(socket, game: new_game, state: Game.state(new_game))}
8  end
9end

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.

1# lib/hayago/game.ex
2defmodule Hayago.Game do
3  # ...
4
5  def place(%Game{history: history, index: index} = game, position) do
6    new_state =
7      game
8      |> Game.state()
9      |> State.place(position)
10
11    %{game | history: [new_state | Enum.slice(history, index..-1)], index: 0}
12  end
13
14  # ...
15end

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.

1# lib/hayago/game.ex
2defmodule Hayago.Game do
3  # ...
4
5  def history?(%Game{history: history}, index) when index >= 0 and length(history) > index do
6    true
7  end
8
9  def history?(_game, _index), do: false
10end

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.

1# lib/hayago_web/templates/game/index.html.leex
2<div class="history">
3  <%= if Hayago.Game.history?(@game, @game.index + 1) do %>
4    <button phx-click="jump" phx-value="<%= @game.index + 1%>">Undo</button>
5  <% else %>
6    <button disabled="disabled">Undo</button>
7  <% end %>
8
9  <%= if Hayago.Game.history?(@game, @game.index - 1) do %>
10    <button phx-click="jump" phx-value="<%= @game.index - 1%>">Redo</button>
11  <% else %>
12    <button disabled="disabled">Redo</button>
13  <% end %>
14</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.

1# lib/hayago/game.ex
2defmodule Hayago.Game do
3  # ...
4
5  def legal?(game, position) do
6    State.legal?(Game.state(game), position) and not repeated_state?(game, position)
7  end
8
9  defp repeated_state?(game, position) do
10    %Game{history: [%State{positions: tentative_positions} | history]} =
11      Game.place(game, position)
12
13    Enum.any?(history, fn %State{positions: positions} ->
14      positions == tentative_positions
15    end)
16  end
17
18  # ...
19end

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.

1# lib/hayago_web/templates/game/index.html.leex
2# ...
3
4<div class="board <%= @state.current %>">
5  <%= for {value, index} <- Enum.with_index(@state.positions) do %>
6    <%= if Hayago.Game.legal?(@game, index) do %>
7      <button phx-click="place" phx-value="<%= index %>" class="<%= value %>"></button>
8    <% else %>
9      <button class="<%= value %>" disabled="disabled"></button>
10    <% end %>
11  <% end %>
12</div>
13
14# ...

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!

Share this article

RSS

AppSignal monitors your apps

AppSignal provides insights for Ruby, Rails, Elixir, Phoenix, Node.js, Express and many other frameworks and libraries. We are located in beautiful Amsterdam. We love stroopwafels. If you do too, let us know. We might send you some!

Discover AppSignal
AppSignal monitors your apps