Datenstruktur zum Verfolgen eines Spielbretts in OCaml

Question

Ich bin ziemlich neu in OCaml und möchte ein Spiel implementieren, das dem Vier-in-einer-Linie ähnlich ist. Was ich brauche, ist eine Datenstruktur, um das Spiel zu halten. Das Spielbrett ist ein 4x4-Quadrat mit insgesamt 16 Spielsteinen. Ich bin auf der Suche nach einer Darstellung in OCaml, die es einfach und schnell macht, alle Elemente in der gesamten Spalte, Zeile oder Diagonale abzurufen (oder einige Operationen auszuführen). Ich werde in diesem Spiel Minimax-Suche machen, weshalb Geschwindigkeit wichtig ist.

Bisher habe ich eine eindimensionale Liste betrachtet. Das Problem mit einer Liste ist, dass es schwierig ist, herauszufinden, welche Elemente zu jeder Zeile/Spalte/Diagonale gehören, und sie dann zum Beispiel mit einem List.map abzurufen.

Ich dachte über die Verwendung von Array.make 4 (Array.make 4 Empty);;. Dies ist absolut perfekt, wenn es um Reihen geht. Es ist einfach, sie zu bekommen und ein Muster-Match zu machen. Aber es ist mühsam, Mustervergleiche an einzelnen Spalten und Diagonalen vorzunehmen.

Was ich möchte, ist eine Funktion, die ein Spielbrett nimmt und eine Liste von Listen zurückgibt, die alle Zeilen/Spalten/Diagonalen enthalten. Ich würde dann beispielsweise gerne match (rows,columns,diagonals) with (Empty, Empty, Empty, Empty) -> something machen.

Answer 1

Manchmal stimmt die Übereinstimmung nicht. Hier, ich denke, Sie sollten versuchen, Funktionen so viel wie möglich zu verwenden, und dann Ihre Zellen Zeile zuerst oder Spalte zuerst zu bekommen wird nicht so komplex sein, und Sie könnten sogar von einer Darstellung zum anderen bewegen, indem Sie die Reihenfolge der Indizes.

Wenn ich verwendet den folgenden Typ:

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

und zuerst für die Spalte entscheiden, dann werden die folgenden Funktionen werden mich Zeilen oder Spalten erhalten:

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

Für die Diagonalen gibt es 2 Sätze von ihnen, wobei einer nach oben links in Richtung nach unten rechts und der andere in die andere Richtung (oben rechts nach unten links) geht:

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) 

Dann denke ich, dass das Überprüfen einer Zeile, Spalte oder Diagonale nur eine Frage der Überprüfung der 4 Zellen dieser Zeile ist.

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) 

dann zum Beispiel überprüft, ob es eine Diagonale von rot ist:

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 2

Da die Länge festgelegt ist, bevorzugen Arrays Arrays über Listen: Sie benötigen weniger Speicher und sind schneller zu lesen und zu schreiben.

Ich fürchte, Sie müssen eine Funktion schreiben, um Diagonalen zu bekommen, gibt es keine einfache Mustererkennung. Wenn Sie schreiben "etwas Operation auf [eine Diagonale]", nehme ich an, dass Sie über eine Funktion f denken, die ein Array der Länge 4 nimmt, die die Elemente speichert, zum Beispiel [|Empty;Empty;Empty;Empty|]. Vielleicht f könnte statt als Argumente die Position p nehmen, und ein Array von Indizes innerhalb der Position: f p [|x1,y1; x2,y2; x3,y3; x4,y4|] würde die Quadrate p.(x1).(y1) ... p.(x4).(y4) extrahieren. Dann pass einfach verschiedene x 's und y' s auf f arbeiten auf Zeile/Spalten/Diagonalen.

Sobald der Code funktioniert und Sie zur Optimierung gehen, möchten Sie vielleicht einen Blick auf bitvectors werfen: Wenn es viele Positionen in der Struktur von Ihnen minmax Suche gespeichert ist, bedeutet die Reduzierung des Speicherbedarfs mehr Cachetreffer und schnellere Ausführung. Eventuell möchten Sie eine Position in einem einzelnen int selbst codieren, aber das ist eine knifflige Arbeit, Sie wollen es nicht zu früh machen.

Answer 3

Wie können Sie Ihre Kacheln mit der entsprechenden Koordinate indizieren?So würden die Elemente auf Ihrer one-d Liste der Form:

(int * int * ref tile) 

Dann können Sie filtern Zeilen/Spalten/Diagonalen wie folgt aus:

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

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

Spalte n:(Voraussetzung: 0 < = n, u, v < = 3)

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

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

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

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

Es sollte auch möglich sein, die Kacheln mit nur einer ganzen Zahl (dem Index der Kachel innerhalb der Ein-D-Liste) zu indizieren, aber das würde einige Berechnungen in der Filterfunktion erfordern (gegebener Index, finde die koordiniere und entscheide dann, ob es zur gewünschten Zeile/Spalte/Diagonale gehört).