How to make proper two-dimensional data structures in Elixir

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.

16 comments

#data-structures #structs #machine-learning

3 11103 16

2016-06-24 22:07:02 UTC

First Post!

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

Post #1

Most Liked

peerreynders

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

Post #5

OvermindDL1

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.

Post #13

peerreynders

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.

Post #11

Last Post!

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.