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

von Lauri Hartikka

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

move-Generation
Board-Evaluierung
Minimax
und Alpha-Beta-Beschneidung.

Bei jedem Schritt verbessern wir unseren Algorithmus mit einer dieser bewährten Schachprogrammiertechniken. 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: Move-Generierung und Board-Visualisierung

Wir verwenden das Schach.js-Bibliothek für die Bewegungsgenerierung und Schachbrett.js zur Visualisierung des Boards. Die Move Generation Library implementiert grundsätzlich alle Regeln des Schachs. Auf dieser Grundlage können wir alle rechtlichen Schritte für einen bestimmten Board-Status berechnen.

Eine Visualisierung der Bewegungsgenerierungsfunktion. Die Startposition wird als Eingabe verwendet und die Ausgabe sind alle möglichen Bewegungen von dieser Position aus.

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:

Schwarz spielt zufällige Züge. Klicken Sie auf https://jsfiddle.net/lhartikk/m14epfwb/4

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 mit der höchsten Bewertung auswählt:

Die einzige spürbare Verbesserung ist, dass unser Algorithmus wird nun ein Stück erfassen, wenn es kann.

Schwarz spielt mit Hilfe der einfachen Auswertefunktion. Basierend auf https://jsfiddle.net/lhartikk/m5q6fgtb/1/

Schritt 3: Suchbaum mit Minimax

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

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

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

Eine Visualisierung des Minimax-Algorithmus in einer künstlichen Position. Der beste Zug für Weiß ist b2-c3, da wir garantieren können, dass wir eine Position erreichen können, an der die Bewertung -50 beträgt

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

Minimax mit Tiefenstufe 2. Spielbar auf: https://jsfiddle.net/k96eoq0q/1/

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

Schritt 4: Alpha-Beta-Beschneidung

Alpha-Beta-Beschneidung 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 und dabei die gleichen Ressourcen zu verwenden.

Das Alpha-Beta-Beschneiden basiert auf der Situation, in der wir einen Teil des Suchbaums nicht mehr auswerten können, wenn wir einen Zug finden, der zu einer schlechteren Situation führt als ein zuvor entdeckter Zug.

Das Alpha-Beta—Pruning beeinflusst das Ergebnis des Minimax-Algorithmus nicht – es macht ihn nur schneller.

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

Die Positionen, die wir nicht erforschen müssen, wenn Alpha-Beta-Beschneidung verwendet wird und der Baum in der beschriebenen Reihenfolge besucht wird.

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

Die Anzahl der Positionen, die zur Auswertung erforderlich sind, wenn wir eine Suche mit einer Tiefe von 4 durchführen möchten und die „root“ -Position angezeigt wird.

Folgen Sie diesem Link, um die verbesserte Alpha-Beta-Version der Schach-KI auszuprobieren.

Schritt 5: Verbesserte Bewertungsfunktion

Die anfängliche Bewertungsfunktion ist ziemlich naiv, da wir nur das Material zählen, das sich auf der Platine 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 verwenden eine leicht angepasste Version von Stück-Quadrat-Tabellen, die ursprünglich im chess-programming-wiki beschrieben wurden.

Das visualisierte Stück-quadratische Tabellen visualisiert. Wir können die Bewertung verringern oder erhöhen, abhängig von der Position des Stücks.

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

Verbesserte Auswertung und Alpha-Beta-Bereinigung mit einer Suchtiefe von 3. Spielbar auf https://jsfiddle.net/q76uzxwe/1/

Schlussfolgerungen

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

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

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

Zugreihenfolge
schnellere Zuggenerierung
und endspielspezifische Auswertung.

KGSAU