Elixir Connect4

elixirConnect4 repository

At work, we use Connect4 as our technical test, which we send out to possible candidates. The candidate must write a working implementation of Connect4 as a console application. So there is no real focus on graphics, and to limit complexity (and the time it takes to build) the computer player doesn't have to be very clever either.

It has worked out to be a great task to get stuck into Elixir. Sure it doesn't really offer the opportunity to use many of the language's strengths (concurrency; distribution...), but it certainly forces you to use many of it's syntax and think about how you would structure an application in Elixir.

Any reasonable amount of complexity in this game can be broken down into 2 distinct parts; Detection (win; draw detection) and AI using the minimax algorithm. So I'll focus mostly on those, but first I want to walk through the project setup and mix in some things about Elixir, which I think need explaining.

note: I use Erlang and Elixir almost interchangeably throughout. Elixir is Erlang under the hood, so how the language works and many of the core features are products of the Erlang VM - BEAM.

Game Overview

Project creation is easy using mix (which comes bundled with Elixir).

> mix new elixirConnect4 --module ElixirConnect4

The --module ElixirConnect4 argument is optional here, by default, on creation; mix will define a module named after the project. In this case, it would of been camel case elixirConnect4 - I wanted pascal case.

Mix will create you a default structure; along with some essential files we will need to work with mix, such as the mix.exs and mix.lock files.

This is the structure of the finished game.

elixirConnect4
├── lib
    ├── elixirConnect4.ex
    ├── ai.ex
    ├── board.ex
    ├── detector.ex
    ├── game.ex
    ├── game_settings.ex
    ├── player.ex
    ├── renderer.ex
├── test
    ├── ai_test.exs
    ├── board_test.exs
    ├── detector_test.exs
    ├── game_test.exs
    ├── player_test.exs
    ├── renderer_test.exs
    ├── test_helper.exs

It should be pretty obvious what most modules are doing. Only a couple need explaining.

elixirConnect4.ex - is the root file which is generated from the mix new command we ran earlier. It contains our basic game functions such as start(), end_game() and the game_loop()
game.ex - is a little more specific. Functions like take_turn() are held under the game module.

Testing

Testing using ExUnit is pretty straight forward, providing you remember to add _test to the end of your test script filenames, this is a convention mix uses by default to pick up your tests when you run mix test from the prompt.

I pretty much started with the board tests, so let’s look at a few of those:

defmodule BoardTests do
   use ExUnit.Case
   alias GameSettings, as: GS

   test "a connect4 board should have 7 columns" do
      board = Board.create_new()
      columnCount = length board
      assert columnCount == GS.no_columns
   end

   test "a connect4 board should have 6 rows" do
      board = Board.create_new()
      rowCount =
         board
         |> List.first
         |> length
      assert rowCount == GS.no_rows
   end

   test "a board should be initialised full of :empty" do
      board = Board.create_new()
      allEmpties =
         board
         |> List.flatten
         |> Enum.all? &(&1 == :empty)
      assert allEmpties
   end
end

Tests are really easy to define, and asserts are straightforward too. assert is a macro, it tries to be smart and provide good reporting for failing tests while keeping the api simple.
Let's make one of the board tests fail so we can see an example of the output.

test a connect4 board should have 7 columns (BoardTests)
     test/board_test.exs:5
     Assertion with == failed
     code: 1 == GS.no_columns()
     lhs:  1
     rhs:  7
     stacktrace:
       test/board_test.exs:8

Mock

I plugged in the mock library, as I needed to mock the IO module, specifically IO.gets/2 so that I can simulate user input. Mock includes a bunch of macro's which can directly replace ExUnit.test, such as test_with_mock/5.

test_with_mock "when an out of range input is given, status returns :error and an appropriate message",
      IO, [gets: fn(_prompt) -> "8\n" end] do
      {board, _player} = Game.start_new()
      {:error, msg} = Game.take_turn board, %Player {type: :human, colour: :red}
      assert msg == "That is out of range, please try again\n"
end

test_with_mock essentially extends the test macro. We still give the test a description, but we also need to pass in the module we want to mock, and a keyword list; where the key is the name of the function within the module, the value is a function with the same arity as the one you wish to mock.

note: in Erlang, functions are represented and identified together by their name, and their arity.
So you will see them commonly referred to like this {name}/{# of args}

Shorthand functions

&(&1 + &2) is the same as fn (x, y) -> x + y end, where &1 is the first argument, &2 the second etc. These are pretty useful except you should use them sparingly - Readability quickly declines when these functions have too much going on. I've found sticking to really simple expressions is key, like the one I use in the unit test above: &(&1 == :empty).

Using hex

To use Mock, first I needed to register it as a dependency in the application.

## elixirConnect4/mix.exs

defp deps do
    [{:mock, git: "https://github.com/jjh42/mock.git", only: :test}]
end

Then to fetch any missing dependencies just run > mix deps.get

Hex is a package manager for the erlang ecosystem, similar to the likes of npm et al.

The Detector

Okay, the game needs to be able to detect if a given move results in a win or a draw. First thing we need is is_group_a_winner?(row, colour). This is the bread and butter function the detector builds on. Given a list of coins/moves, we need to be able to detect a win, which is consecutively 4 or more of the same colour. For now, lets forget about vertical vs. horizontal vs. diagonal detection.

def is_group_a_winner?(row, colour) do
     winning_count = row |> List.foldl 0, fn (entry, acc) ->
       case {entry, acc} do
         {_, 4} -> 4
         {^colour, _} -> acc + 1
         _ -> 0
       end
     end
     winning_count == 4
end

So, this function takes a row (a list of colours) and a colour in which to test against.
We then fold over the row and run a function against each item, passing in an accumulator. A left fold is essentially a reduce.
The function pattern matches against both the entry item and the accumulator and works like this:

If the accumulator is 4, return 4.
If the entry matches the colour we are looking for, increment the accumulator.
Catch all - Reset the accumulator to 0 because we have encountered a colour, which does not match.
Finally, if the accumulator is 4, return true - we have a win.

Note: the caret (^) in ^colour allows us to match against an already existing name. So {^colour, _} is matching against our colour argument we passed into the function.

The diagonal win

Vertical and horizontal wins are fairly straightforward and pretty uninteresting, so I’ll spare you the details. I do want to talk about the diagonal detection though.

def diagonal_win?(board, colour, coord) do
      {move_column_index, move_row_index} = coord
      flat_board = List.flatten board
      max_grid_index = length(flat_board) - 1
      starting_index = (move_column_index * GS.max_column_index) + move_row_index

      [7,9,-7,-9]
      |> get_all_indexes(starting_index, max_grid_index)
      |> indexes_to_grid_entries(flat_board, [])
      |> is_any_row_a_winner?(colour)
end

It works like this:

Flatten the board. Now instead of having a list of lists, we just have a single long list.
[7,9,-7,-9] - These values represent the increment which will allow us to build all our diagonal groups for the given move.
For example, taking every seventh coin in the flattened board will give me the diagonal from the players move; up to the top left of the board. Taking every ninth coin... The top right etc..
get_all_indexes() - Get us a list of all the indexes we need to get those coins from the flattened board.
indexes_to_grid_entries() - Actually return the coins, which will be a list of lists, varying in size of course because these are diagonal rows, but our is_group_a_winner? function doesn't care.
is_any_row_a_winner? - Then finally, this function simply runs all the diagonals through is_group_a_winner?.

There are a few ways I could improve on this function, the biggest of which being [7,9,-7,-9] should come from a function which takes into account the possible varying size of the board. And I’m pretty sure I could of used Enum.take_every/2 somewhere...

It didn't make sense to check every diagonal possible on the board, that isn't very efficient, and we need this to be as efficient as possible for the AI.

More misc on Elixir

Missing multi dimensional collection

I found it difficult to find the correct data type to model the game board with. Lists seem like the perfect type except they are slow and clumsy to access by index - and the tuple is great to access by index but no good for iteration.
Erlang does have an :array type, but it doesn't have any where near as many helper functions as List (an Enum) has, which I knew would be valuable. On the plus side, array's normally aren't immutable, so even if I chose to model the game board in an array I would have to make sure I return copies/clones of the array rather than mutate it.

Naming

I like the Elixir convention to suffix functions which return a bool with a ? (a Ruby-ism i guess?). Nice for languages which don't have a prominent type system or the tooling to support it.

I'm also partial to the underscore naming over the pascal/camel case name too. i.e. this_is_a_function is much more readable than thisIsAFunction I find.

I will cover the minimax implementation in the next post...