Eine Schritt-für-Schritt-Anleitung zum Aufbau einer einfachen Schach-KI

Lassen Sie uns einige grundlegende Konzepte untersuchen, die uns helfen, eine einfache Schach-KI zu erstellen:

  • Bewegungsgenerierung
  • Board-Bewertung
  • Minimax
  • und Alpha-Beta-Schnitt.

Bei jedem Schritt werden wir unseren Algorithmus mit einer dieser bewährten Schachprogrammiertechniken verbessern. Ich werde zeigen, wie sich jeder auf den Spielstil des Algorithmus auswirkt.

Sie können den endgültigen AI-Algorithmus hier auf GitHub anzeigen.

Schritt 1: Generierung und Board-Visualisierung verschieben

Wir werden die chess.js-Bibliothek zur Generierung von Zügen und chessboard.js zur Visualisierung des Boards verwenden. Die Move-Generierungsbibliothek implementiert grundsätzlich alle Schachregeln. Auf dieser Grundlage können wir alle rechtlichen Schritte für einen bestimmten Board-Staat berechnen.

Die Verwendung dieser Bibliotheken hilft uns, uns nur auf die interessanteste Aufgabe zu konzentrieren: den Algorithmus zu erstellen, der den besten Zug findet.

Wir beginnen mit der Erstellung einer Funktion, die nur einen zufälligen Zug aus allen möglichen Zügen zurückgibt:

Obwohl dieser Algorithmus kein sehr solider Schachspieler ist, ist er ein guter Ausgangspunkt, da wir tatsächlich dagegen spielen können:

Schritt 2: Positionsbewertung

Versuchen wir nun zu verstehen, welche Seite in einer bestimmten Position stärker ist. Der einfachste Weg, dies zu erreichen, besteht darin, die relative Stärke der Teile auf dem Brett anhand der folgenden Tabelle zu zählen:

Mit der Bewertungsfunktion können wir einen Algorithmus erstellen, der den Zug auswählt, der die höchste Bewertung ergibt:

Die einzige spürbare Verbesserung besteht darin, dass unser Algorithmus jetzt ein Stück erfasst, wenn dies möglich ist.

Schritt 3: Suchbaum mit Minimax

Als nächstes erstellen wir einen Suchbaum, aus dem der Algorithmus den besten Zug auswählen kann. Dies erfolgt mithilfe des Minimax-Algorithmus.

Bei diesem Algorithmus wird der rekursive Baum aller möglichen Bewegungen bis zu einer bestimmten Tiefe untersucht und die Position an den Endblättern des Baums ausgewertet.

Danach geben wir entweder den kleinsten oder den größten Wert des Kindes an den übergeordneten Knoten zurück, je nachdem, ob es sich um ein Weiß oder ein Schwarz handelt. (Das heißt, wir versuchen, das Ergebnis auf jeder Ebene entweder zu minimieren oder zu maximieren.)

Mit Minimax beginnt unser Algorithmus einige grundlegende Taktiken des Schachs zu verstehen:

Die Effektivität des Minimax-Algorithmus hängt stark von der Suchtiefe ab, die wir erreichen können. Dies werden wir im folgenden Schritt verbessern.

Schritt 4: Alpha-Beta-Schnitt

Alpha-Beta-Bereinigung ist eine Optimierungsmethode für den Minimax-Algorithmus, mit der wir einige Zweige im Suchbaum ignorieren können. Dies hilft uns, den Minimax-Suchbaum viel tiefer zu bewerten, während wir dieselben Ressourcen verwenden.

Das Alpha-Beta-Bereinigen basiert auf der Situation, in der wir die Auswertung eines Teils des Suchbaums beenden können, wenn wir einen Zug finden, der zu einer schlimmeren Situation führt als ein zuvor entdeckter Zug.

Das Alpha-Beta-Beschneiden beeinflusst das Ergebnis des Minimax-Algorithmus nicht - es macht es nur schneller.

Der Alpha-Beta-Algorithmus ist auch effizienter, wenn wir zuerst die Pfade besuchen , die zu guten Bewegungen führen.

Mit Alpha-Beta erhalten wir einen deutlichen Schub für den Minimax-Algorithmus, wie im folgenden Beispiel gezeigt:

Folgen Sie diesem Link, um die Alpha-Beta-Version der Schach-KI zu testen.

Schritt 5: Verbesserte Bewertungsfunktion

Die anfängliche Bewertungsfunktion ist ziemlich naiv, da wir nur das Material zählen, das sich auf der Tafel befindet. Um dies zu verbessern, fügen wir der Bewertung einen Faktor hinzu, der die Position der Teile berücksichtigt. Zum Beispiel ist ein Ritter in der Mitte des Bretts besser (weil er mehr Optionen hat und somit aktiver ist) als ein Ritter am Rand des Bretts.

Wir werden eine leicht angepasste Version von Stück-Quadrat-Tabellen verwenden, die ursprünglich im Schach-Programmier-Wiki beschrieben wurden.

Mit der folgenden Verbesserung erhalten wir einen Algorithmus, der zumindest aus Sicht eines Gelegenheitsspielers ein „anständiges“ Schach spielt:

Schlussfolgerungen

Die Stärke eines einfachen Schachspielalgorithmus besteht darin, dass er keine dummen Fehler macht. Trotzdem fehlt es immer noch an strategischem Verständnis.

Mit den hier vorgestellten Methoden konnten wir einen Schachspielalgorithmus programmieren, der einfaches Schach spielen kann. Der „AI-Teil“ (Bewegungsgenerierung ausgeschlossen) des endgültigen Algorithmus besteht aus nur 200 Codezeilen, was bedeutet, dass die grundlegenden Konzepte recht einfach zu implementieren sind. Sie können überprüfen, ob die endgültige Version auf GitHub verfügbar ist.

Einige weitere Verbesserungen, die wir am Algorithmus vornehmen könnten, wären zum Beispiel:

  • Umzugsbestellung
  • schnellere Bewegungsgenerierung
  • und endspielspezifische Bewertung.

Wenn Sie mehr erfahren möchten, lesen Sie das Schachprogrammier-Wiki. Es ist eine hilfreiche Ressource, um über diese grundlegenden Konzepte hinauszugehen, die ich hier vorgestellt habe.

Danke fürs Lesen!