Wir haben für Sie einen Artikel von Lauri Hartikka über die Erstellung der einfachsten KI für Schach übersetzt. Es wurde im Jahr 2017 geschrieben, aber die Grundprinzipien blieben gleich. Alle von Lori verwendeten Dateien sind ebenfalls verfügbar.
Einfache künstliche Intelligenz, die Schach spielen kann, kann auf der Grundlage von vier Konzepten erstellt werden:
- 1. Bewegen;
- 2. Bewertung des Vorstandes;
- 3. Minimax ;
- 4. Alpha Beta-Clipping . In jeder Phase der Arbeit mit dem Algorithmus wird einer von ihnen verwendet, wodurch die Spielfähigkeiten der KI schrittweise verbessert werden.
Skillbox empfiehlt: Der Python Data Analyst Applied Online-Kurs.
Wir erinnern Sie daran: Für alle Leser von „Habr“ - ein Rabatt von 10.000 Rubel bei der Anmeldung für einen Skillbox-Kurs mit dem Promo-Code „Habr“.
Vorgefertigter Quellcode finden Sie auf
GitHub .
Stufe 1. Visualisierung eines Schachbretts mit der Erzeugung von Zügen
An diesem Punkt werden wir die
chess.js- Bibliotheken verwenden, um Züge zu generieren, und
chessboard.js , um das
Schachbrett zu rendern. In der Bibliothek, die für die Generierung von Zügen verantwortlich ist, können Sie alle Schachregeln anwenden, sodass wir jede Aktion für eine bestimmte Anordnung von Figuren berechnen können.
Wenn Sie auf das Bild klicken, wird es in voller Auflösung geöffnet.
Wenn Sie mit diesen Bibliotheken arbeiten, können Sie sich auf die Hauptaufgabe konzentrieren - das Suchen und Erstellen eines Algorithmus, mit dem Sie den optimalen Zug finden können. Wir beginnen die Arbeit mit dem Schreiben einer Funktion, die einen zufälligen Zug aus einer Liste aller möglichen zurückgibt.
var calculateBestMove =function(game) {
Trotz der Tatsache, dass der Algorithmus kein idealer Schachspieler ist, wird dies für die meisten Spieler seines Niveaus völlig ausreichen.
Schwarz bewegt sich zufällig. (
Quelle und Spiel online )
Stufe 2. Positionsbewertung
Lassen Sie uns nun herausfinden, welche Seite in dieser oder jener Position den Vorteil hat. Am einfachsten ist es, die relative Stärke der Teile auf dem Brett zu berechnen. Dies kann anhand der Tabelle erfolgen.
Mit der Bewertungsfunktion erhalten wir die Möglichkeit, einen Algorithmus zu erstellen, der die Bewegung mit maximaler Bewertung auswählt.
var calculateBestMove = function (game) { var newGameMoves = game.ugly_moves(); var bestMove = null;
Im Prinzip ist das Niveau das gleiche, aber der Algorithmus kann bereits die Figur eines anderen nehmen, wenn eine solche Gelegenheit besteht.
Schwarz hatte die Möglichkeit, weiße Stücke zu nehmen. (Quellen und Spiel sind
hier ).
Stufe 3. Suchbaum mit Minimax
Danach erstellen wir einen Suchbaum. Jetzt kann das Programm den besten Zug daraus auswählen. Dies erfolgt mit dem Minimax-Algorithmus.
Hier wird ein rekursiver Baum mit der Anzeige aller möglichen Bewegungen bis zu einer bestimmten Tiefe analysiert. Die Position wird durch die Blätter unseres Baumes geschätzt.
Als nächstes geben wir den minimalen oder maximalen Wert des Kindes an den übergeordneten Knoten zurück. Es hängt alles davon ab, welche Seite sich derzeit verrechnet. Mit anderen Worten, das Ergebnis wird auf jeder Ebene maximiert oder minimiert.
Hier ist b2-c3 der beste Zug für Weiß, da er sicherstellt, dass der Spieler mit einer Punktzahl von -50 die Position erreicht.
var minimax = function (depth, game, isMaximisingPlayer) { if (depth === 0) { return -evaluateBoard(game.board()); } var newGameMoves = game.ugly_moves(); if (isMaximisingPlayer) { var bestMove = -9999; for (var i = 0; i < newGameMoves.length; i++) { game.ugly_move(newGameMoves[i]); bestMove = Math.max(bestMove, minimax(depth - 1, game, !isMaximisingPlayer)); game.undo(); } return bestMove; } else { var bestMove = 9999; for (var i = 0; i < newGameMoves.length; i++) { game.ugly_move(newGameMoves[i]); bestMove = Math.min(bestMove, minimax(depth - 1, game, !isMaximisingPlayer)); game.undo(); } return bestMove; } };
Mit dem Minimax-Algorithmus hat unsere KI bereits begonnen, die grundlegenden Taktiken des Schachs zu verstehen.
Minimax mit einer Tiefe von 2 (Quellen und das Spiel
hier )
Es ist anzumerken, dass die Effizienz des Minimax-Algorithmus mit der Tiefe der Suche zunimmt. Der nächste Schritt ist dafür verantwortlich.
Stufe 4. Alpha Beta Clipping
Dies ist eine Methode zur Optimierung des Minimax-Algorithmus, mit der einige Zweige im Suchbaum ignoriert werden können. Auf diese Weise können Sie die Suchtiefe erhöhen und die gleiche Menge an Ressourcen verbrauchen.
Alpha-Beta-Clipping basiert auf einer Situation, in der wir die Bewertung eines bestimmten Zweigs beenden können, wenn festgestellt wird, dass ein neuer Schritt zu einer schlechteren Situation führt als die, die wir bei der Bewertung des vorherigen gesehen haben.
Die Optimierung wirkt sich nicht auf das Ergebnis von Minimax aus, aber alles beginnt schneller zu arbeiten.
Dieser Algorithmus ist viel effizienter, wenn Sie zuerst die Pfade überprüfen, die zu guten Bewegungen führen.
Das Bild zeigt Bewegungen, die bei Verwendung von Alpha-Beta-Clipping unnötig werden.
Wie Sie sehen können, wird Minimax mit Alpha-Beta-Clipping optimiert und ist sehr bedeutend.
Die Anzahl der Positionen, die Sie bei einer Suche mit einer Tiefe von 4 auswerten möchten, und die Startposition, die oben angezeigt wird. (Quelle und Spiel finden Sie
hier )
Schritt 5. Verbesserte Bewertungsfunktion
Die anfängliche Bewertungsfunktion ist recht einfach, da sie einfach die Punkte der Teile auf dem Brett zählt. Zur Optimierung können Sie die Position der Figuren berücksichtigen. Wenn Sie beispielsweise das Pferd in der Mitte des Bretts platzieren, wird es teurer - der Bereich der verfügbaren Züge für dieses Stück wird erweitert.
An dieser Stelle werden wir mit einer leicht modifizierten Version der quadratischen Tabellen arbeiten, die ursprünglich im
Schachprogrammier-Wiki beschrieben wurden .
Und jetzt spielt unser Algorithmus natürlich schon ziemlich gut im Vergleich zum durchschnittlichen Spieler.
Quellen und Spiel finden Sie
hier.Fazit
Der Vorteil des vorgeschlagenen Algorithmus besteht darin, dass er keine sehr dummen Fehler macht. Natürlich kann die Strategie hier kaum als perfekt bezeichnet werden, aber dennoch.
Die Implementierung unseres Algorithmus umfasst nur 200 Codezeilen, daher sind die Grundprinzipien recht einfach. Die endgültige Version des Programms kann <a href= target
github.com/lhartikk/simple-chess-ai'> auf GitHub angezeigt werden.
Dem Algorithmus können weitere Module hinzugefügt werden, darunter:
Weitere Informationen zu Schachalgorithmen finden Sie im
Schachprogrammier-Wiki .
Skillbox empfiehlt: