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.