Datenstruktur für zweidimensionale Brettspiele in funktionalen Sprachen

Ich erstelle eine einfache MiniMax- Implementierung in der funktionalen Programmiersprache Elixir. Da es viele Spiele mit perfektem Wissen gibt (Tic Tac Toe, Connect-Four, Dame, Schach usw.), könnte diese Implementierung ein Framework für die Erstellung von Spiel-AIs für jedes dieser Spiele sein.

Ein Problem, mit dem ich konfrontiert bin, ist jedoch, wie ein Spielstatus in einer funktionalen Sprache richtig gespeichert wird. Diese Spiele befassen sich hauptsächlich mit zweidimensionalen Spielbrettern, bei denen die folgenden Operationen häufig sind:

• Lesen Sie den Inhalt einer bestimmten Platinenposition
• Aktualisieren Sie den Inhalt eines bestimmten Board-Standorts (wenn Sie eine neue Verschiebungsmöglichkeit zurückgeben).
• Berücksichtigung des Inhalts eines oder mehrerer Standorte, die mit dem aktuellen Standort verbunden sind (dh des nächsten oder vorherigen horizontalen, vertikalen oder diagonalen Standorts)
• Berücksichtigung des Inhalts mehrerer verbundener Standorte in eine beliebige Richtung.
• Berücksichtigung des Inhalts ganzer Dateien, Ränge und Diagonalen.
• Drehen oder Spiegeln der Platine (um nach Symmetrien zu suchen, die das gleiche Ergebnis liefern wie bereits berechnete).

Die meisten funktionalen Sprachen verwenden verknüpfte Listen und Tupel als Grundbausteine ​​für Datenstrukturen mit mehreren Elementen. Diese scheinen jedoch sehr schlecht für den Job gemacht zu sein:

• Verknüpfte Listen haben eine O (n) (lineare) Suchzeit. Da wir das Board nicht in einem einzigen Durchlauf scannen und aktualisieren können, erscheint die Verwendung von Listen sehr unpraktisch.
• Tupel haben eine O (1) (konstante) Suchzeit. Die Darstellung der Tafel als Tupel mit fester Größe macht es jedoch sehr schwierig, über Ränge, Dateien, Diagonalen oder andere Arten aufeinanderfolgender Quadrate zu iterieren. Außerdem fehlt sowohl Elixir als auch Haskell (die beiden mir bekannten Funktionssprachen) die Syntax zum Lesen des n- ten Elements eines Tupels. Dies würde es unmöglich machen, eine dynamische Lösung zu schreiben, die für Boards beliebiger Größe funktioniert.

Elixir verfügt über eine integrierte Map- Datenstruktur (und Haskell Data.Map), die O (log n) (logarithmisch) Zugriff auf Elemente ermöglicht. Im Moment verwende ich eine Karte mit x, yTupeln, die die Position als Schlüssel darstellen.

Das funktioniert, aber es fühlt sich falsch an, Karten auf diese Weise zu missbrauchen, obwohl ich nicht genau weiß, warum. Ich suche nach einer besseren Möglichkeit, ein zweidimensionales Spielbrett in einer funktionalen Programmiersprache zu speichern.

A Mapist hier genau die richtige Basisdatenstruktur. Ich bin mir nicht sicher, warum es dich unruhig machen würde. Es hat gute Such- und Aktualisierungszeiten, eine dynamische Größe und es ist sehr einfach, abgeleitete Datenstrukturen daraus zu erstellen. Zum Beispiel (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

Die andere Sache, die für Programmierer häufig schwer zu verstehen ist, wenn sie zum ersten Mal mit voller Unveränderlichkeit programmieren, ist, dass Sie sich nicht nur an eine Datenstruktur halten müssen. Normalerweise wählen Sie eine Datenstruktur als "Quelle der Wahrheit", aber Sie können so viele Ableitungen erstellen, wie Sie möchten, sogar Ableitungen von Ableitungen, und Sie wissen, dass sie so lange synchronisiert bleiben, wie Sie sie benötigen.

Das heißt, Sie können a Mapauf der obersten Ebene verwenden, dann zu Listsoder Arraysfür Arraysdie Zeilenanalyse wechseln und dann für die Spaltenanalyse in die andere Richtung indizieren, dann Bitmasken für die Musteranalyse und dann Stringsfür die Anzeige. Gut gestaltete Funktionsprogramme geben keine einzige Datenstruktur weiter. Es handelt sich um eine Reihe von Schritten, bei denen eine Datenstruktur aufgenommen und eine neue ausgegeben wird, die für den nächsten Schritt geeignet ist.

Solange Sie mit einer Verschiebung in einem Format, das die oberste Ebene verstehen kann, auf die andere Seite kommen können, müssen Sie sich keine Sorgen machen, wie stark Sie die Daten dazwischen umstrukturieren. Es ist unveränderlich, so dass es möglich ist, einen Weg zurück zur Quelle der Wahrheit auf der obersten Ebene zu verfolgen.

Ich habe dies kürzlich in F # getan und am Ende eine eindimensionale Liste verwendet (in F # ist das eine einfach verknüpfte Liste). In der Praxis ist die Geschwindigkeit des O (n) -Listenindexers kein Engpass für vom Menschen verwendbare Boardgrößen. Ich habe mit anderen Typen wie 2d-Arrays experimentiert, aber am Ende war es der Kompromiss, entweder meinen eigenen Code zur Überprüfung der Wertgleichheit zu schreiben oder eine Übersetzung von Rang und Datei in Index und zurück. Letzteres war einfacher. Ich würde sagen, dass es zuerst funktioniert und dann später Ihren Datentyp bei Bedarf optimiert wird. Es wird wahrscheinlich keinen großen Unterschied machen, um eine Rolle zu spielen.

Am Ende sollte Ihre Implementierung nicht so wichtig sein, solange Ihre Board-Operationen ordnungsgemäß nach Board-Typ und -Operationen gekapselt sind. So sehen einige meiner Tests zum Beispiel aus, um ein Board einzurichten:

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)
    |> ...

Für diesen Code (oder einen aufrufenden Code) wäre es egal, wie die Tafel dargestellt wird. Der Vorstand wird durch die Operationen auf ihm mehr vertreten als durch seine zugrunde liegende Struktur.