You didn’t list MapSets. They are especially handy when order doesn’t matter …

… and here board locations are unique. So, for example, the board could be represented as a map containing three sets, one each for the fields owned by each player and a “free” set for the fields that aren’t owned yet.

In general the “optimal” data structure really depends on the characteristics of the game and the nature of the analysis. Quite often representing a 2D game board as a 2D array is somewhat “brute force”.

# Represent board state as a map with sets as values
iex> state0 = %{ 
...>   :free => MapSet.new([{1,1},{1,2},{1,3},{2,1},{2,2},{2,3},{3,1},{3,2},{3,3}]),
...>   :x => MapSet.new,
...>   :o => MapSet.new 
...> }
%{free: #MapSet<[{1, 1}, {1, 2}, {1, 3}, {2, 1}, {2, 2}, {2, 3}, {3, 1}, {3, 2}, {3, 3}]>, 
     o: #MapSet<[]>, 
     x: #MapSet<[]>} 

# For move delete from free set and put into player set
iex> move = fn state, field, player -> 
...>   %{state | 
...>     :free => MapSet.delete(state.free, field), 
...>     player => MapSet.put(state[player], field) } 
...> end
 
iex> state1 = move.(state0, {2,2}, :x)
%{free: #MapSet<[{1, 1}, {1, 2}, {1, 3}, {2, 1}, {2, 3}, {3, 1}, {3, 2}, {3, 3}]>, 
     o: #MapSet<[]>, 
     x: #MapSet<[{2, 2}]>}

iex> state2 = move.(state1, {1,1}, :o)
%{free: #MapSet<[{1, 2}, {1, 3}, {2, 1}, {2, 3}, {3, 1}, {3, 2}, {3, 3}]>,
     o: #MapSet<[{1, 1}]>, 
     x: #MapSet<[{2, 2}]>}

iex> state3 = move.(state2, {1,2}, :x)
%{free: #MapSet<[{1, 3}, {2, 1}, {2, 3}, {3, 1}, {3, 2}, {3, 3}]>,
     o: #MapSet<[{1, 1}]>, 
     x: #MapSet<[{1, 2}, {2, 2}]>}

iex> state4 = move.(state3, {3,2}, :o)
%{free: #MapSet<[{1, 3}, {2, 1}, {2, 3}, {3, 1}, {3, 3}]>,
     o: #MapSet<[{1, 1}, {3, 2}]>, 
     x: #MapSet<[{1, 2}, {2, 2}]>}

iex> state5 = move.(state4, {3,1}, :x)
%{free: #MapSet<[{1, 3}, {2, 1}, {2, 3}, {3, 3}]>, 
     o: #MapSet<[{1, 1}, {3, 2}]>,
     x: #MapSet<[{1, 2}, {2, 2}, {3, 1}]>}

iex> state6 = move.(state5, {2,3}, :o)
%{free: #MapSet<[{1, 3}, {2, 1}, {3, 3}]>, 
     o: #MapSet<[{1, 1}, {2, 3}, {3, 2}]>,
     x: #MapSet<[{1, 2}, {2, 2}, {3, 1}]>}

iex> state7 = move.(state6, {1,3}, :x)
%{free: #MapSet<[{2, 1}, {3, 3}]>, 
     o: #MapSet<[{1, 1}, {2, 3}, {3, 2}]>,
     x: #MapSet<[{1, 2}, {1, 3}, {2, 2}, {3, 1}]>}

# To determine win simply check if any winning field set
# is a subset of the player's field set
# 
# Winning field sets can be generated dynamically 
iex> rows = 1..3
iex> cols = 1..3
iex> max_row = Enum.max(rows)
iex> max_col = Enum.max(cols)
iex> diagonal_length = min(max_row, max_col)
iex> winning_lists = 
...>   [ (for i <- 1..diagonal_length, do: {i, max_col - i + 1}) |
...>   [ (for i <- 1..diagonal_length, do: {i,i}) |
...>     ((for r <- rows, do: for c <- cols, into: [], do: {r,c}) ++ 
...>       for c <- cols, do: for r <- rows, into: [], do: {r,c})]]
[[{1, 3}, {2, 2}, {3, 1}], [{1, 1}, {2, 2}, {3, 3}], [{1, 1}, {1, 2}, {1, 3}],
 [{2, 1}, {2, 2}, {2, 3}], [{3, 1}, {3, 2}, {3, 3}], [{1, 1}, {2, 1}, {3, 1}],
 [{1, 2}, {2, 2}, {3, 2}], [{1, 3}, {2, 3}, {3, 3}]]

iex> winning_sets = Enum.map winning_lists, &MapSet.new/1
[#MapSet<[{1, 3}, {2, 2}, {3, 1}]>, #MapSet<[{1, 1}, {2, 2}, {3, 3}]>,
 #MapSet<[{1, 1}, {1, 2}, {1, 3}]>, #MapSet<[{2, 1}, {2, 2}, {2, 3}]>,
 #MapSet<[{3, 1}, {3, 2}, {3, 3}]>, #MapSet<[{1, 1}, {2, 1}, {3, 1}]>,
 #MapSet<[{1, 2}, {2, 2}, {3, 2}]>, #MapSet<[{1, 3}, {2, 3}, {3, 3}]>]

iex> has_won = fn win_sets, state, player -> 
...>   Enum.any? win_sets, &(MapSet.subset? &1, state[player]) 
...> end

iex> has_won.(winning_sets, state7, :o)
false
iex> has_won.(winning_sets, state7, :x)
true

I actually have, the old array benchmark that was done at wagerlabs back in 2008 or so I updated to have maps tested as well a little bit back, running it again (Erlang 18, ran right now), the results:

3> arr:test(10000).
Fixed-size array: get:     2963us, set:     5206us
Extensible array: get:     2958us, set:     5332us
Tuple:            get:     1246us, set:   249436us
Tree:             get:     5396us, set:    49664us
Maps:             get:     1574us, set:     4340us
ok

4> arr:test(50000).
Fixed-size array: get:    18161us, set:    47902us
Extensible array: get:    18158us, set:    41749us
Tuple:            get:     4167us, set: 11626792us
Tree:             get:    21717us, set:   288593us
Maps:             get:    11074us, set:    42079us
ok

5> arr:test(100000).
Fixed-size array: get:    34579us, set:    77049us
Extensible array: get:    37854us, set:    74268us
Tuple:            get:    22168us, set: 55975496us
Tree:             get:    50261us, set:   809286us
Maps:             get:    37553us, set:   142472us
ok

And egadstreestakeforevertoset, but it looks like maps are in general on par or better than the :array module up to somewhere between 50_000 and 100_000 entries, at which point the :array module gets better.

Too true. Personally I find that I have to remind myself constantly to not be too much of a memory miser as modern immutability takes advantage of persistent data structures. That said it makes no sense to keep the “free” set around if it doesn’t earn it’s keep (e.g. for a simple is_available and is_draw query), especially as it has to be maintained (i.e. move has to delete taken fields from it). At the time I just liked the fact that all the information seemed to be self contained and I wanted to minimize dependencies of the game state on external, “global” information.

Sure. And you can use the initial game state for that:

• MapSet.member? state0.free, field can be used for/as part of the “OutOfRange” or “InvalidInput” check because if the field isn’t available on an empty board then it must be illegal.

• MapSet.member? stateN.free, field is used on the current game state as the “FieldNotFree” check - essentially different responses require distinct checks.

Carin Meier’s test for the Clojure fox-goose-bag-of-corn kata has to take the the blame for that. It demonstrated to me how useful sets are.

You can even omit one of the sets, since the game system has the following properties:

• We have the set of tiles, this is fixed and has 9 elements
• We have three changing sets, free, x, and o. The union of all 3 of this is equal to the set of tiles.
• So if an element is not in the first two of the sets, it has to be in the third.

So iff a tile neither belongs to x nor to o, it has to be free.

It really depends on what you want to achieve with your datastructure…

If you can write your logic in a way that you are able to traverse nested lists by “row” and “cell”, definitively go for that solution!

I woul not really favor tuples in any way for this, even when you have random access in O(1) there, You can’t dynamically pattern match, but need to know the exact size of the tuple before hand. When I tried to use tuples as array replacement in an erlang project, I was constantly converting to and from lists until some point when I found the array module (:array from elixir). which I’ve chosen then.

But last but not least, the datastructure I had choosen when it had been available on OTP 16 (which I had to use) were maps. Use a tuple of x and y as key, and you have filled it rather quick and have random access with O(1). Just as you did with your tic tac toe example.

The reason I’d prefer lists whenever possible is because destructuring them is one of the fastest operation we can imagine in BEAM, right after spawning a process and doing nothing in a process… If I really (think) to need random access because I can not think of a way that works with linear scanning, I’d go for maps whenever possible because they have some human readable representation when inspected, while an erlang :array with only one dimension and a couple of values is hard to follow *1, don’t want to think about multiple dimensions with many values…

*1:

iex(1)> [1,2,3] |> :array.from_list
{:array, 3, 10, :undefined,
 {1, 2, 3, :undefined, :undefined, :undefined, :undefined, :undefined,
  :undefined, :undefined}}
iex(2)> [[1,2,3],[4,5,6],[7,8,9]] |> Enum.map(&:array.from_list/1) |> :array.from_list
{:array, 3, 10, :undefined,
 {{:array, 3, 10, :undefined,
   {1, 2, 3, :undefined, :undefined, :undefined, :undefined, :undefined,
    :undefined, :undefined}},
  {:array, 3, 10, :undefined,
   {4, 5, 6, :undefined, :undefined, :undefined, :undefined, :undefined,
    :undefined, :undefined}},
  {:array, 3, 10, :undefined,
   {7, 8, 9, :undefined, :undefined, :undefined, :undefined, :undefined,
    :undefined, :undefined}}, :undefined, :undefined, :undefined, :undefined,
  :undefined, :undefined, :undefined}}