Ich setze gerade etwas ein, das den Kontrolleuren ziemlich ähnlich ist. Also, ich habe dieses Tischspiel und es gibt sowohl weiße als auch schwarze Stücke. Wo es keine weißen oder schwarzen Stücke gibt, haben Sie keine Stücke.
Ich mache gerade die Methode GetValidMoves() , die alle aktuellen Bewegungen zurückgibt, die man mit der aktuellen Karte machen kann.
Ich frage mich daher, was der beste Weg ist, das Board zu repräsentieren. Der naive Ansatz wäre eine Matrix mit Nullen 1 und 2 (für kein Stück, weißes Stück und schwarzes Stück).
Andere Idee wäre, statt einer Matrixdarstellung der Platine, 2 Listen (oder jede andere Datenstruktur): eine für schwarze Stücke, andere für Weiß.
Ich implementiere dieses Spiel, um einige AI-Algorithmen zu testen, also geht es mir hauptsächlich um Geschwindigkeit. Ich werde grundsätzlich 2 KI-Spieler gegeneinander spielen lassen, für jede Runde sollte jeder Spieler eine Liste aller seiner gültigen Züge haben und dann wird er entscheiden, was zu tun ist, bis das Spiel endet (ein Spieler gewinnt oder es gibt einen Krawatte).
PS: Ich frage nicht nach dem AI-Algorithmus, ich möchte nur wissen, welche die beste Datenstruktur für den Umgang mit dem Board ist, damit es einfach zu
wird Verwenden Sie eine Bitmap: zwei 64-Bit-Integer ohne Vorzeichen, einen für Weiß und einen für Schwarz. Dann können Sie Moves und Boardpositionen als Funktion von (W x B) -> (W x B) darstellen, wobei W , B die Menge der möglichen weißen bzw. möglichen Schwarzpositionen darstellt.
Dann können die meisten Dinge auf der Board-Position mit Integer-Arithmetik erledigt werden, was ungefähr so schnell wie möglich ist.
Eine gängige Methode hierfür ist die binäre Darstellung von long type für jeden Player.
(da sind 64 Quadrate auf dem Brett) .. Wie Charlie bereits gesagt hat ..
Hier ist ein sehr guter (aber genereller) Wiki-Artikel .
Die Verwendung ist einfach - wenn du zum Beispiel prüfen möchtest, ob sich alle Teile nach oben und rechts bewegen, verschiebe die Spielfiguren des Spielers um 7 Bits nach links und überprüfe, ob dort Gegnerstücke sind, dann verschiebe sie 7 Bits wieder verlassen, und prüfen, ob diese Quadrate frei sind ...
Ich habe es einmal in einem Reversi-Wettbewerb verwendet und kann sagen, dass die Implementierung nicht zu schwierig war.
HTH.
Ich würde dafür auch eine Bitmap verwenden. Die Funktionen, die auf 1, 2 und 3 überprüft werden, sind ein wenig unintelligent zum Schreiben, sollten aber sehr schnell sein.
Sie müssen natürlich auf die Edge-Fälle achten, und eine schnelle Lösung wird wahrscheinlich eine ganzzahlige und modulare Arithmetik für die Indizes beinhalten.
Zuallererst ist es wichtig zu erwähnen, dass die Hälfte der Quadrate auf den Spielbrettern niemals benutzt werden kann. Sie brauchen also nur 32 statt 64 Felder. Unter Berücksichtigung der Könige erhalten Sie Möglichkeiten von 0 bis 4 statt 0 bis 2 (obwohl, wenn ich es tat, fand ich es einfacher, -3 bis +3 stattdessen zu verwenden, so dass die Werte für Rot und Schwarz die gleiche Größe und entgegengesetzte Vorzeichen haben).
Im Hinblick auf Listen würde ich dringend davon abraten, in dieser Situation eine Struktur zu verwenden, die verknüpfte Listen verwendet. Wahrscheinlich kennen Sie bereits die Positionen, die Sie untersuchen möchten (x-y-Koordinaten), und daher würde eine verkettete Liste O(n) time erfordern, um einfach den Wert des Schachbrettraums zu erfassen. Wie andere Antworten erwähnt haben, wäre eine Bitmap oder ein langer Ansatz ideal.
Was die Organisation der Daten angeht, würde ich mir vorstellen, dass eine Implementierung, bei der sowohl Schwarz als auch Weiß in derselben Struktur gespeichert sind, ideal wäre. Sie haben einen gewissen Overhead, da das Speichern von 2 und 3 in Binärdateien die gleiche Menge an Speicher erfordert. Wenn Sie jedoch Checker schreiben, müssen Sie wahrscheinlich sowieso "kinged" -Daten speichern. Die Möglichkeit, durch eine einzelne Suche zu prüfen, ob ein Speicherbereich offen ist, sollte einen erheblichen Leistungsvorteil bieten.
Hoffe, das hilft.
Es hängt davon ab, was Ihre AI-Algorithmen tun werden. Die meisten KI-Algorithmen würden eine Art Suche nach den möglichen Bewegungen in mindestens mehreren Schritten durchführen. In diesem Fall werden Sie viele Kopien Ihrer Vorstandsdarstellung machen und es ist sinnvoll, sie klein zu halten, da die Zeit zum Kopieren Ihrer Datenstruktur die Zeit beherrschen wird, um eine Liste möglicher Bewegungen zu erhalten und die Tiefe zu begrenzen was du suchen kannst.
Wenn Sie jedoch nicht suchen, würde ich eine Klasse Stück erstellen und die Farbe, den Ort und ob das Stück ein König ist. Ich hätte dann ein zweidimensionales 8 mal 8 Array von Referenzen auf Pieces und eine verknüpfte Liste von schwarzen Stücken und eine verknüpfte Liste von roten Stücken. Jedes Element des Arrays würde entweder auf ein Stück aus der roten oder schwarzen Liste oder auf ein "leeres" Stück zeigen (null würde dafür funktionieren). Wenn Sie ein Stück bewegen, aktualisieren Sie einfach das Objekt Stück in der Liste und verschieben die Referenz von ihrem aktuellen Ort an den neuen Ort, wobei Sie den alten Ort auf das leere Stück setzen. Für eine leichte Erhöhung der Kosten eines Updates erhalten Sie eine effiziente Möglichkeit, über beide Seiten zu iterieren und den Zustand eines bestimmten Punkts auf dem Board ständig nachzuschauen.
Sie müßten über die vollständige Liste iterieren, um ein totes Stück zu entfernen, aber dies kann auch mit einer kleinen Änderung am Stück effizient gemacht werden. Sie können ein Bool "tot" im Objekt "Objekt" speichern. Wenn ein Gegenstand getötet wird, setze ihn auf "wahr" und entferne ihn von der Tafel, indem du die Referenz darauf durch das leere Stück ersetzt. Wenn du durch eine Liste von Stücken iterierst, entferne einfach jedes Stück, das als tot markiert ist, aus der Liste.
Tags und Links algorithm artificial-intelligence