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

39 11014 16

2016-06-24 22:07:02 UTC

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 #6

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 #14

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 #12