Data structure for two-dimensional board games in Functional languages

Question

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.

Answer 1

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.

Answer 2

I've done this recently in F# and I ended up using a one-dimensional list (in F#, that's a single-linked list). In practice, the speed of O(n) list indexer is not a bottleneck for human-usable board sizes. I experimented with other types like 2d array, but in the end, it was the trade-off of either writing my own value-equality-checking code or a translation of rank and file to index and back. The latter was simpler. I'd say get it working first, and then optimize your data type later if needed. It's not likely to make a large enough difference to matter.

In the end your implementation should not matter as much so long as your board operations are properly encapsulated by Board type and operations. For instance, here is how some of my tests may look to set up a board:

let pos r f = {Rank = r; File = f} // immutable record type
// or
let pos r f = OnBoard (r, f) // algebraic type
...
let testBoard =
    Board.createEmpty ()
    |> Board.setPiece p (pos 1 2)
    |> ...

To this code (or any calling code), it would not matter how the board was represented. The board is represented by the operations on it more than its underlying structure.