Data structure for keeping track of a game board in OCaml

Question

I am fairly new to OCaml and I want to implement a game which is similar to four-in-a-line. What I need is some data structure to keep the game state. The game board is a 4x4 square with a total of 16 tiles. I am looking for a representation for this in OCaml that will make it easy and fast to retrieve (or do some operation on) all the elements in entire column, row or diagonal. I will be doing minimax search on this game, which is why speed is important.

So far I have considered a one-dimensional list. The problem with a list is that its hard to figure out what elements belong to each row/column/diagonal, and then retrieve them with a List.map for example.

I thought about using Array.make 4 (Array.make 4 Empty);;. This is absolutely perfect when it comes to rows. Its easy to get them and do a pattern match on it. But it is a chore to do pattern matching on individual columns and diagonals.

What I would like to be able to do is have a function that takes a game board and returns a list of lists containing all the rows/columns/diagonals. I would then like to do, for example, match (rows,columns,diagonals) with (Empty, Empty, Empty, Empty) -> something.

Answer 1

Since length is fixed, prefer arrays over lists: they use less memory and are faster to read and write.

I'm afraid you will need to write a function to get diagonals, there is no simple pattern matching. When you write "do some operation on [a diagonal]", I assume you're thinking about a function f that takes an array of length 4 storing the elements, for instance [|Empty;Empty;Empty;Empty|]. Maybe f could instead take as arguments the position p, and an array of indices inside the position: f p [|x1,y1; x2,y2; x3,y3; x4,y4|] would extract the squares p.(x1).(y1) ... p.(x4).(y4). Then just pass different x's and y's to make f operate on row/columns/diagonals.

Once the code is working and you're turning to optimization, you might want to have a look at bitvectors: if there are a lot of positions stored in the tree of you minmax search, reducing the memory footprint means more cache hits and faster execution. You might event want to encode a position in a single int yourself, but this is some tricky work, you don't want to do it too early.

Answer 2

Sometimes matching doesn't work. Here, I think you should try to use functions as much as possible, and then getting your cells row first or column first won't be that complex, and you could even move from one representation to the other by reversing the indices order.

If I use the following type:

type color = Red | Yellow;;
type cell  = Empty | Color of color;;
type board = Array.make 4 (Array.make 4 Empty);;

and decide for column first, then the following functions will get me rows or columns:

let column (b: board) i j = b.(i).(j)
let row (b: board) i j = b.(j).(i)

For the diagonals, there are 2 sets of them, one going top-left toward down-right, and the other one in the other direction (top-right to bottom-left):

let ldiag (b: board) i j = b.((i + j) mod 4).(j)
let rdiag (b: board) i j = b.((i - j + 4) mod 4).(j)

Then I guess that checking a row, column, or diagonal is just a matter of checking the 4 cells of that line.

let check predicate linef k = predicate (linef b k 0) && 
                               predicate (linef b k 1) && 
                               predicate (linef b k 2) && 
                               predicate (linef b k 3)

then for instance, checking if there's a diagonal of red:

let has_line linef b color = 
    let cmp x = x = color in
    let check k = check cmp linef b k in
    check 0 || check 1 || check 2 || check 3

let has_ldiag b color = has_line ldiag b color
let has_rdiag b color = has_line rdiag b color

let has_red_diagonal b = has_ldiag b Red | has_rdiag b Red

Etc.

Answer 3

How about indexing your tiles with the corresponding coordinate? So, the elements on your one-d list would be of the form:

(int * int * ref tile)

Then you can filter rows / columns / diagonals like this:

Row n: (precondition: 0 <= n, u, v <= 3)

List.filter tiles (fun x -> match x with (u, v, _) -> u = n);;

Column n: (precondition: 0 <= n, u, v <= 3)

List.filter tiles (fun x -> match x with (u, v, _) -> v = n);;

Diagonal 1: (precondition: 0 <= u, v <= 3)

List.filter tiles (fun x -> match x with (u, v, _) -> u = v);;

Diagonal 2: (precondition: 0 <= u, v <= 3)

List.filter tiles (fun x -> match x with (u, v, _) -> u + v = 3);;

It should also be possible to index the tiles with just one integer (the index of the tile within the one-d list), but that would need some calculations in the filter function (given index, figure out the coordinate and then decide if it belongs to the desired row / column / diagonal).