9

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.

  • 1
    I can't speak about praxis, but two things come to my mind from Haskell: zippers, allowing constant-time "steps" over data structures, and comonads, which are related to zippers by some theory which I neither remember nor properly understand ;) – phg Jun 15 '16 at 20:44
  • How big is this playing board? Big O characterizes how an algorithm scales, not how fast it is. On a small board (say, less than 100 in each direction), O(1) vs. O(n) is unlikely to matter much, if you only touch each square once. – Robert Harvey Jun 15 '16 at 21:09
  • @RobertHarvey It will vary. But to give an example: In Chess, we have a 64x64 board, but all computations to check for what moves are possible, and to determine the current position's heuristic value (difference in material, king in check or not, passed pawns, etc) all need to access squares of the board. – Qqwy Jun 15 '16 at 21:33
  • 1
    You have an 8x8 board in chess. In a memory-mapped language like C, you can make a mathematical calculation to get the exact address of a cell, but that's not true in memory-managed languages (where ordinal addressing is an implementation detail). It wouldn't surprise me if jumping across (a maximum of) 14 nodes takes roughly the same amount of time as addressing an array element in a memory-managed language. – Robert Harvey Jun 15 '16 at 21:42
  • See also stackoverflow.com/q/9611904/124319 – coredump Jun 15 '16 at 22:38
6

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.

4

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.

  • Hello, do you have the code published somewhere? I am currently working on a chess-like game in F# (a for fun project), and even tho I am using a Map<Square,Piece> to represent the board, I'd love to see how you encapsulated it into a Board type and module. – asibahi Oct 12 '16 at 14:47
  • No, it's not published anywhere. – Kasey Speakman Oct 12 '16 at 14:48
  • so would you mind taking a look at my current implementation and advise how I could improve it? – asibahi Oct 12 '16 at 14:52
  • Glancing at the types, I settled on a very similar implementation until I got to the Position type. I will do a more thorough analysis on Code Review later. – Kasey Speakman Oct 12 '16 at 15:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.