How to make proper two-dimensional data structures in Elixir

[Qqwy]

I am creating a small implementation of a MiniMax algorithm, that can, when finished, predict good moves in multiple perfect-information games. It is a good exercise to learn both Elixir and OTP better, as there are many improvements (alpha-beta pruning, transposition tables, heuristics, evaluation functions, iterative deepening, etc) that can be added, as well as the problem being inherently paralellizeable.

However, these games have a current game state, usually involving a two-dimensional game board (chess, checkers, connect-four, tic tac toe, etc). I am having trouble to come up with a good data structure to store this board in.

I would ‘simply’ use a two-dimensional array in an Imperative language, but I am not so sure what to use in Functional land.

• lists: Have O(n) (linear) lookup time, as they are actually linked lists.
• tuples: Constant-time lookup, but it is hard to create a new game state from the current in a dynamic way using tuples.
• maps: Constant-time lookup. However, these are single-dimensional and do not preserve order.

Right now, for the TicTacToe variant I use a map where the key is a {x, y} tuple for the position.(This ‘board’ is then wrapped in a struct so you can use protocols properly). An example of a board would be:

 x = %TicTacToe{board:    %{{0, 0} => 1, {0, 1} => 1, {0, 2} => 1, 
                            {1, 0} => 0, {1, 1} => 0, {1, 2} => 0, 
                            {2, 0} => 0, {2, 1} => 0, {2, 2} => 0}}

This is the following state:

┌─┬─┬─┐
│X│X│X│
├─┼─┼─┤
│ │ │ │
├─┼─┼─┤
│ │ │ │
└─┴─┴─┘

This ‘works’, but I am wondering if there is maybe a better solution.

[NobbZ]

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

[ctrlshiftbryan]

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?

[Qqwy]

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.

[NobbZ]

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…

[peerreynders]

@Qqwy

I would ‘simply’ use a two-dimensional array in an Imperative language, but I am not so sure what to use in Functional land.

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

@Qqwy

for the TicTacToe variant

… 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

[uranther]

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

[NobbZ]

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.

[peerreynders]

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.

[Qqwy]

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 (|||).

[NobbZ]

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

[peerreynders]

@NobbZ

Trading memory by CPU, some thing you have to do all the time as a programmer.

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.

@NobbZ

I’d expect more of a “OutOfRange” or “InvalidInput” when trying to do such move, instead of “FieldNotFree”.

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.

@Qqwy

MapSets are a really nice way to solve a problem where a board is filled with pieces.

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.

[bbense]

FWIW, there is an online talk at the Erlang Central site about implementing a board game in Elixir in which the cells of the board game are processes.

https://erlangcentral.org/explore-elixir-using-board-game-logic-torben-hoffmann/#.V2hIiFeG_Aw

[OvermindDL1]

@NobbZ

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…

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.

[NobbZ]

Were you so kind to publish the source of the benchmark?

[uranther]

This is excellent! It reminds me of that quote from Joe Armstrong about modeling an elevator bank with a process for each elevator and how this is a good (best?) representation of the real world. This talk definitely shows the Elixir/BEAM way of doing things and it seems to make reasoning about the code a lot easier. I want to give this a shot for my chess program and see how it simplifies things. The presenter’s Elixir code is here: https://github.com/lehoff/acquirex

[OvermindDL1]

The file I use is just the wagerlabs array test with maps added in, all erlang, but it is here[0] if you want to try it yourself. If you load it in iex just :arr.test(n) for some number of iterations in n that you want to test.

0. https://github.com/OvermindDL1/benchmark_elixir/blob/master/arr.erl