OCaml Field Tracking Data Structure

Question

I'm new to OCaml and I want to implement a game that looks like a four-in-line. I need a data structure to keep the state of the game. 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 simplify and speed up the extraction (or execution of some operations) of all elements in a whole column, row or diagonal. I will do a minimax search in this game, so speed is important.

So far I have been considering a one-dimensional list. The problem with the list is that it is difficult to determine which elements belong to each row / column / diagonal, and then retrieve them using List.map , for example.

I was thinking about using Array.make 4 (Array.make 4 Empty);; . This is absolutely perfect when it comes to strings. It is easy to get and execute the template. But it is a difficult task to match patterns on separate columns and diagonals.

What I would like to have is to have a function that takes a playing field and returns a list of lists containing all rows / columns / diagonals. Then I would like to do, for example, match (rows,columns,diagonals) with (Empty, Empty, Empty, Empty) -> something .

Answer 1

Sometimes a match does not work. Here, I think that you should try to use the functions as much as possible, and then first call the rows of cells or the columns will not be so complicated at first, and you can even move from one view to another by changing the order of the indices.

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 first decide for the column, then the following functions will get me rows or columns:

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

For diagonals, there are 2 sets of them: one goes from top to bottom, right to bottom, and the other in the other direction (from top to bottom, from right to left):

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

Then I assume that checking a row, column or diagonal is just checking four cells of that row.

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

then, for example, check if there is a diagonal of red:

 let has_line linef b color = let cmp x = x = color in let check k = check cmp linef bk 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 2

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

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

As soon as the code works and you switch to optimization, you may need to look at the bitvectors: if there are many positions in the tree that are stored in the minmax search, a decrease in memory means more cache hits and faster execution. You might want to encode the position in one int int, but this is some kind of complicated work, you do not want to do this too early.

Answer 3

How about indexing your fragments with the appropriate coordinate? Thus, the elements in your one-dimensional list will look like:

 (int * int * ref tile) 

Then you can filter the rows / columns / diagonals as follows:

String 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 tiles with only one integer (tile index within a single-d-list), but this requires some calculations in the filter function (given index, print the coordinate, and then decide whether it belongs to the desired row / column / diagonals).