Wie implementiere ich KI für Checker / Entwürfe?

Ich habe dieses Dame-Spiel gesehen und mich gefragt, wie die KI implementiert wurde.

Wie soll ich eine KI für Dame (Drafts, Dama, Dame) implementieren ? Gibt es bekannte Algorithmen?

Vielen Dank an alle. Ich wundere mich sehr, dass ich diesen Blog-Beitrag mit dem Tic Tac Toe -Tutorial sehe .

Also, ich möchte Dama-Spiel- Algorithmus Open Source-Code und Blog-Post. Gibt es einen hilfreichen Link oder eine Doc-Datei? Lass es mich wissen, bitte..

Oh, ich liebe diese Spiele!

Das Wichtigste, damit ein Computer ein Spiel spielen kann, ist:

1. eine Struktur, mit der man arbeiten kann
2. Regeln zum Spielen
3. eine Gewinnbedingung, auf die man hinarbeiten kann

Lassen Sie uns dies Stück für Stück angehen.

Struktur

Da es sich bei der Karte um ein 8x8-Gitter handelt (das sich jedoch leicht skalieren lässt) und jeder Gitterbereich möglicherweise nur in einem von fünf Zuständen existiert, definieren wir diese Zustände:

[EMPTY, WHITE_PIECE, BLACK_PIECE, WHITE_PIECE_PROMOTED, BLACK_PIECE_PROMOTED]

Jeweils ENUM'd an:

[0, 1, 2, 3, 4]

Jetzt, da wir wissen, was jedes Feld sein kann, brauchen wir eine Möglichkeit, alle Felder oder die Tafel darzustellen, wenn Sie so wollen. Fast jede starke Sprache unterstützt ein mehrdimensionales Array (ein Array, in dem jedes Element ein Array mit Daten ist). Verwenden Sie also den folgenden Slack-Code, um unser Array zu definieren:

BOARD_ARRAY = array(8, 8)

Dadurch erhalten wir ein 8 x 8-Array, in dem wir ganze Zahlen (unsere vorherigen Aufzählungen) speichern können:

(
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
)

Jetzt können Sie bereits sehen, wie dies anfängt, wie ein Brett auszusehen! Ich habe die im Youtube-Video erwähnte Variante noch nie gespielt, aber sie beginnt anscheinend mit zwei Reihen weißer Teile, eine Reihe von unten, und zwei Reihen schwarzer Teile, eine Reihe von oben. Wenn wir ein Spiel starten, sollte unser Array folgendermaßen aussehen:

(
[0, 0, 0, 0, 0, 0, 0, 0],
[2, 2, 2, 2, 2, 2, 2, 2],
[2, 2, 2, 2, 2, 2, 2, 2],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[1, 1, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 1, 1],
[0, 0, 0, 0, 0, 0, 0, 0],
)

(Denken Sie daran, dass 2 'BLACK_PIECE' und 1 'WHITE_PIECE' darstellt.)

Nun hat der Computer eine Struktur, mit der er arbeiten kann. Schritt 1 abgeschlossen!

Regeln

Stellen wir uns vor, Sie hätten ein echtes Brett vor sich, das gegen einen Master-Spieler spielt. Wenn Sie versuchen, eines seiner Teile zu bewegen, bekommen Sie eine Ohrfeige. Wenn Sie versuchen würden, ein Teil so zu bewegen, wie Sie es nicht könnten, würden Sie eine Ohrfeige bekommen. Wenn Sie versucht haben, gut zu schummeln, haben Sie die Idee. Das Problem ist jedoch, dass Computer dies nicht tun. Es ist daher unsere Aufgabe, strenge Regeln für das Spielen einzuhalten.

Wir müssen einen Weg finden, um zu überprüfen, ob ein bestimmter Schritt „legal“ ist. Was bedeutet, dass wir zuerst einen Weg brauchen, um einen „Zug“ darzustellen. Eine Möglichkeit wäre, Array-Positionen zu verwenden. Um beispielsweise eine Figur von [0, 0] nach [0, 1] zu verschieben, könnten wir eine Funktion erstellen, die das Brett bei diesem Zug aktualisiert. Also zurück zum Faulenzen:

MY_MOVE = array( [0, 0], [0, 1] )

Das Obige stellt eine Figur dar, die sich von der oberen Ecke der Tafel aus um ein Feld nach unten bewegt (vorausgesetzt, 0 ist die obere linke Ecke). Möglicherweise bemerken Sie auch, dass ich mich für die Verschiebung für ein mehrdimensionales Array entschieden habe. Dies liegt daran, dass sich Teile theoretisch sehr oft in einer Runde bewegen können (um andere Teile zu "springen"). Stellen wir uns also vor, bei 0, 1 gäbe es ein gegnerisches Teil, was bedeutet, dass wir bei 0, 2 landen würden:

MY_MOVE = array( [0, 0], [0, 2] )

Ziemlich einfach, was? Das Programm sollte verstehen, dass, wenn wir ein Leerzeichen überspringen, wir ein anderes Stück springen (oder es ist ein illegaler Zug und sollte einen Fehler auslösen). Lassen Sie uns nun zwei Teile überspringen:

MY_MOVE = array ( [0, 0], [0, 2], [0, 4] )

Dies gibt uns die Möglichkeit, jede Bewegung auf dem Brett zu beschreiben. Yay! Da ich die Regeln des jeweiligen Spiels nicht vollständig verstehe (obwohl ich zu meiner Zeit einige kanadische Dame gespielt habe), muss die genaue Zug-Legalität von Ihnen festgelegt werden. Ein guter Fluss bis zu diesem Punkt würde so aussehen:

FUNCTION_FIND_ALL_LEGAL_MOVES( MY_BOARD ) Returns: array ALL_LEGAL_MOVES
FUNCTION_FIND_BEST_MOVE( MY_BOARD, ALL_LEGAL_MOVES ) Returns: array MY_MOVE
FUNCTION_DO_MOVE( MY_BOARD, MY_MOVE ) Throws: error ILLEGAL_MOVE Updates: MY_BOARD
repeat from start for each turn

Das Obige setzt voraus, dass Sie durch jedes Stück radeln können, um alle seine legalen Züge zu finden, und dann mit einer Sammlung aller legalen Züge irgendwie den besten auswählen (Strategie hier). Der Zug wird dann auf das Brett angewendet oder wirft einen Fehler aus. Dann ist der nächste Spieler an der Reihe. Wir haben also eine KI, die weiß, wie man spielt! Freude! Weitermachen.

Gewinnen

Einfache Spiele sind wundervoll, weil das Gewinnen durch einen sehr einfachen Zustand definiert wird. Sind keine weißen Steine ​​auf dem Brett? Nun, ich denke du hast gewonnen! Dies wird in Schritt 2 implementiert, wenn wir den besten Schritt wählen, um uns der Gewinnbedingung zu nähern.

Um eine sehr intelligente KI zu erstellen, könnten Sie eine Datenbank führen, in der alle möglichen Bretter als Status gespeichert sind, mit jedem möglichen Schritt aus jedem möglichen Status, um Ketten zum Gewinnen zu finden.

Sie können auch Strategien erstellen, z. B .: Wenn ein Teil gesprungen wird, speichern Sie das Teil, oder wenn ein Teil mehr als ein anderes Teil springen kann, springen Sie.

Das sollte Ihnen einen guten Ausgangspunkt bieten, es ist nur eine Methode mit buchstäblich unbegrenzten Möglichkeiten. Sie könnten theoretisch einen riesigen Roboter bauen, um mit Buntstiften zu zeichnen, und dann eine Spektralanalyse der Zeichnung durchführen, um Bewegungen auszuwählen ... aber es würde nicht sehr gut oder schnell funktionieren. Dieser Weg hat in der Vergangenheit funktioniert und hat gut funktioniert (: Hoffe das hilft!

Ein paar Worte zur Implementierung

Checkers ist ein so genanntes "gelöstes" Spiel, bei dem wir jeden Zug ohne Unbekanntes berechnen können. Aber das ist eine ganze Reihe von Zügen! Es gibt also keine Möglichkeit, alles manuell zu machen ... wenn es nur einige gäbe ... ach ja, wir sind Programmierer. Faustpumpe

SQL ist ein wunderbares Werkzeug, um all diese scheinbar endlosen Bewegungen zu speichern. Für diejenigen, die noch keine Erfahrung mit SQL haben, ist mySQL ein kostenloser (ziemlich benutzerfreundlicher) und Open-Source-SQL-Server. SQL wird zum Verwalten von Datenbanken verwendet und ähnelt einer Tabelle mit Steroiden. Es ist auch in der Lage, sehr große Datenmengen zu speichern und sehr schnell damit zu arbeiten.

Wie können wir das nutzen? Da wir wissen, dass, wenn sich das Brett in einem exakten Zustand befindet (jedes Teil an einer bestimmten Position), wir alle verfügbaren Züge berechnen und speichern können. Beispielsweise:

+Board State+          +All Possible Moves+               +Best Move+
([0,0,1,2,3],[3..)     ([0,1],[0,2]), ([7,6],[7,7],[5..)  ([7,6],[7,7])
([0,0,2,2,3],[3..)     ([0,1],[0,2]), ([7,6],[7,7],[5..)  ([5,5],[5,4])
([0,0,1,3,3],[3..)     ([0,1],[0,2]), ([7,6],[7,7],[5..)  ([4,4],[4,3])
etc...

Wenn der Computer also einen Zug ausführen muss, schlägt er einfach den Board-Status (der als Primärschlüssel gespeichert ist) in der Datenbank nach und kann entweder den besten Zug (der unschlagbar sein sollte) oder einen der anderen Züge auswählen, um einen freundlicheren zu gestalten AI.

Großartig, jetzt wollen wir diese Datenbank erstellen. Zuerst müssen wir jeden Boardstatus berechnen. Was mit einer großen, fiesen Schleife gemacht werden kann, wenn jemand etwas Zeit verbringen und es herausfinden möchte, wäre das fantastisch. Betrachten Sie das Array als eine große Zahl und zählen Sie dann aufwärts, mit Ausnahme von Basis 5 (0, 1, 2, 3, 4) und der Bedingung, dass jeder Spieler nur 16 Teile haben darf.

Zu diesem Zeitpunkt sollten wir jeden Board-Status gespeichert haben und alle möglichen Züge berechnen können.

Sobald alle möglichen Züge berechnet sind, macht es Spaß, die bestmöglichen Züge zu finden. Hier fängt mein Wissen an zu scheitern und Dinge wie Minimax oder A * fangen an ins Spiel zu kommen. Entschuldigung, ich kann dir nicht weiterhelfen: /

Zu jedem Zeitpunkt im Spiel ist die Anzahl der möglichen Züge für einen Spieler ziemlich gering * (um die 5). Dies bedeutet, dass man ein paar Züge vorausdenken, jeden möglichen Zug bewerten und den besten Zug auswählen kann.

Diesen Ansatz nennt man Minimax (Wikipedia) .

Um Minimax zu implementieren, benötigen Sie eine Bewertungsfunktion, die eine Punktzahl für ein bestimmtes Brettlayout und einen bestimmten Spieler zurückgibt. Für Entwürfe wäre eine naive Implementierung eine Funktion, die für jedes Stück, das der Spieler am Leben hat, einen Punkt zurückgibt.

Eine Visualisierung eines Minimax-Entscheidungsbaums (aus dem Wikipedia-Artikel). Unten auf der linken Seite befindet sich die Abbiegungsnummer. Die Blattknoten haben jeweils eine ausgewertete Punktzahl, die dem Baum zur Entscheidungsfindung zugeführt wird.

*Drafts ist jedoch das Spiel mit dem höchsten Verzweigungsfaktor, der vollständig gelöst wurde .

Alpha-Beta-Bereinigung ist ein Suchalgorithmus, der versucht, die Anzahl der Knoten zu verringern, die vom Minimax-Algorithmus in seinem Suchbaum ausgewertet werden. Es handelt sich um einen gegnerischen Suchalgorithmus, der häufig zum maschinellen Spielen von Spielen für zwei Spieler (Tic-Tac-Toe, Schach, Go usw.) verwendet wird. Eine Bewegung wird nicht mehr vollständig ausgewertet, wenn mindestens eine Möglichkeit gefunden wurde, die beweist, dass die Bewegung schlechter ist als eine zuvor untersuchte Bewegung. Solche Bewegungen müssen nicht weiter ausgewertet werden. Bei Anwendung auf einen Standard-Minimax-Baum wird derselbe Zug wie bei Minimax zurückgegeben, jedoch werden Zweige entfernt, die möglicherweise keinen Einfluss auf die endgültige Entscheidung haben.