Data Structure for Two-Dimensional Board Games in Functional Languages

data structuresfunctional programming

I am creating a simple MiniMax implementation in the functional programming language Elixir. Because there are many perfect-knowledge games (tic tac toe, connect-four, checkers, chess, etc), this implementation could be a framework for creating game AIs for any of these games.

One problem I am facing, however, is how to properly store a game state in a functional language. These games are mostly dealing with two-dimensional game boards, where the following operations are frequent:

  • Read the contents of a specific board location
  • Update the contents of a specific board location (when returning a new move possibility)
  • Considering the contents of one or more locations that are connected to the current location (i.e. the next or previous horizontal, vertical or diagonal locations)
  • Considering the contents of multiple connected locations in any direction.
  • Considering the contents of whole files, ranks and diagonals.
  • Rotating or mirroring the board (to check for symmetries that provide the same result as something already calculated).

Most functional languages use Linked Lists and Tuples as basic building blocks of multi-element data structures. However, these seem very badly made for the job:

  • Linked lists have O(n) (linear) lookup time. Also, as we cannot 'scan and update the board' in a single sweep over the board, using lists seems very impractical.
  • Tuples have O(1) (constant) lookup time. However, representing the board as a fixed-size tuple makes it very hard to iterate over ranks, files, diagonals, or other kinds of consecutive squares. Also, both Elixir, and Haskell (which are the two functional languages I know) lack syntax to read the nth element of a tuple. This would make it impossible to write a dynamic solution that would work for boards of an arbitrary size.

Elixir has a built-in Map data structure (And Haskell has Data.Map) that allow O(log n) (logarithmic) access to elements. Right now I use a map, with x, y tuples that represent the position as keys.

This 'works' but it feels wrong to abuse maps in this way, although I do not know exactly why. I am looking for a better way to store a two-dimensional game board in a functional programming language.

Best Answer

A Map is precisely the right base data structure here. I'm not sure why it would make you uneasy. It has good lookup and update times, it's dynamic in size, and it's very easy to create derivative data structures from. For example (in haskell):

filterWithKey (\k _ -> (snd k) == column) -- All pieces in given column
filterWithKey (\k _ -> (fst k) == row)    -- All pieces in given row
mapKeys (\(x, y) -> (-x, y))              -- Mirror

The other thing that is frequently difficult for programmers to grasp when they first start programming with full immutability is you don't need to stick to only one data structure. You usually choose one data structure as your "source of truth," but you can make as many derivatives as you want, even derivatives of derivatives, and you know they will stay synced as long as you need them to.

That means you can use a Map at the topmost level, then switch to Lists or Arrays for row analysis, then Arrays indexed the other way for column analysis, then bitmasks for pattern analysis, then Strings for display. Well-designed functional programs do not pass a single data structure around. They are a series of steps that take one data structure in and emit a new one that's suited for the next step.

As long as you can come out the other side with a move in a format the top level can understand, you don't need to worry how much you restructure the data in between. It's immutable, so it's possible to trace a path back to the source of truth at the top level.

Related Topic