How to make proper two-dimensional data structures in Elixir

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}}

Could u just use a map and have a function like dep transform(x,y), do: (x * 2) + y to transform your key before you look it up?

Thank you for your advice, @NobbZ!

There are indeed many common operations in board games that make a single-linked-list such as the ones that the BEAM uses impractical:

• Checking a single position’s(x,y) contents
• Updating a single position’s(x,y) contents with some new value
• Checking the contents of positions connected to the current one horizontally, vertically, or diagonally.
• Checking the contents of a whole file, column or diagonal at once.
• Rotating the board as a whole to account for rotations and reflections of the current board state that will produce the same outcome.

I believe that most of these cannot be done in a simple single traversion operation.

I will read up on :array but it seems a little Archaic to me. I definitely agree that maps provide nicer output.

I have never done benchmarks to actually compare :array vs %{}, but alone that maps have better syntax support and are much nicer when inspected, would make me choose them over :array unless someone really proofs that :array would be much faster in that usecase AND speed really matters…

You can add some more boilerplate to fix an :array in its size, which would remove a lot if not all :undefineds in it. But it is still very uncomfortable to read. You can also specify default values for uninitialized fields when dealing with “dynamically growing” :arrays, but again, function calls that swap some atoms or other values in the nested tuple.

One of the only things that I can see when using :array one could really benefit from is, that erlang can reuse most of the structure and does only need to copy the “spine” (outer most tuple including references tu unchanged subtuples) and the tuple where the actual value has been changed. Depending of the deepth of the wrapping tuples of course there are more spines to copy, but still much faster than to copy everything.

On the downside of this, you do have a random access which is logarithmic. Ive seen already that there are papers about that topic, but I don’t want to link something I haven’t read myself and I am to tired to quickread a scientific paper So All I can suggest is to google a bit for “fucntional array”, perhaps you can find something of interest. But I have to warn that papers around functional programming are most written in some haskell-lish math notation…

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

What an awesome use of functional programming to solve this problem! Thank you for sharing.

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.

My main motivation behind the explicit :free set was to retain a simple capability to verify that a field is available for a move, i.e. MapSet.member? state.free, field can easily determine whether the specified field is:

• valid/legal (e.g. {1,4} isn’t on a {1..3,1..3} board) and
• available (i.e. not owned by either player)

Also Enum.empty? state.free can be used to detect the “game over” condition when the game ends in a draw.

Wow! MapSets are a really nice way to solve a problem where a board is filled with pieces. Your solution rocks!

I have, since opening this topic, asked a question on the Programmers StackExchange as what functional data-abstraction we might use for a two-dimensional game board is of course not Elixir-specific. The end result (thus far; still hoping for more input) is that maps are a fine way to solve two-dimensional boards.

Your MapSet solution is amazing, by the way! For things like TicTacToe where a board is filled up, this makes a lot of sense.
You post made me realize that ‘two dimensional board game’ is still far to vague, as the rules of the game can completely change what internal representation is most useful/performant.

I am working on a connect-four implementation right now using my Map approach, but to check if there are connections of four elements, I actually extract all rows, columns and diagonals, and then use Enum.chunk(list_of_lists, 4, 1) to obtain a final data structure that contains all possible connect-four combinations.

I will then map+reduce a function that scores each of these:

• 0 if the opponent also has a piece in it (regardless of how many spaces you filled)
• pow(1, 2) == 1 if you have one stone
• pow(2, 2) == 4 if you have two stones
• pow(3, 2) == 16 if you have three stones
• a ridiculously high number if you have four, as you’ve won.

This heuristic will mean that spaces in the middle of the board are determined as ‘more important’, as there are more ways to create four-in-a-row with them.

The awesome thing about this solution is that it can be generalized to any connect-n game on an x*y board.

For checkers, where you have a lot of similar pieces but they each have limited moves, I think that a board-as-map representation might also be best. What do you think?

I am still wondering what to do for games like chess. There are three methods I know:

1. a board of squares, where a square might contain a piece of a certain kind.
2. A list of pieces, where each piece stores where it is on the board. Special care needs to be taken to handle things like the promotion of a pawn while there already is a queen! On the other hand, you can disregard the empty squares completely in your calculations for position-checking and move generation.
3. Bitboards: Storing a property about each square on the board as one bit in a 64-bit integer. This is ridiculously fast (at least in C implementations) as many properties can be combined in O(1) instead of O(n) by using the binary and (&&&) or binary or (|||).

{1,4} is not in the global set of available pieces/tiles/whatever and as such has to get filtered out by validation. I’d expect more of a “OutOfRange” or “InvalidInput” when trying to do such move, instead of “FieldNotFree”.

But of course, whenever one omits one of such sets, he needs to split checks for members of that sets into two checks for an element beeing NOT a member of the other two sets. Trading memory by CPU, some thing you have to do all the time as a programmer.