Allen gewidmet, die jetzt die gefeierte TV-Serie "The Queen's Gambit" sehen. Weitere Schachbegriffe in unserer neuen Übersetzung.
In diesem Artikel werden wir versuchen zu verstehen, wie Schach-Engines funktionieren, indem wir die Sunfish- Schach-Engine nach Go portieren. Sunfish zeichnet sich durch seine Einfachheit und geringe Größe aus, kann aber dennoch ein anständiges Schachspiel spielen. Go hingegen ist als einfache und lesbare Programmiersprache bekannt, daher hoffe ich, dass sie zusammen ein großartiges Paar bilden.
Um eine Schach-Engine zu erstellen, müssen Sie zunächst drei wichtige Punkte festlegen:
- Wie wird das Schachbrett dargestellt (Zellen, Figuren, erlaubte Züge)?
- Wie bewerten Sie das Board (wer gewinnt eher)?
- Wie finde ich den optimalen Zug?
Die Codefragmente in diesem Beitrag sind vereinfacht und enthalten nur die wichtigsten Teile. Den vollständigen Motorcode finden Sie unter github.com/zserge/carnatus (Carnatus ist der lateinische Name für Wolfsbarsch, Sebastes carnatus-Arten).
Zellen und Formen
Es ist wichtig, eine bequeme Darstellung der Karte zu finden, die nicht viel Platz beansprucht, da Tausende von Kartenvarianten bei der Suche nach der optimalen Bewegung im Speicher gespeichert werden.
Normalerweise ist eine Tafel eine Sammlung von Zellen. Wir werden das Standard-8x8-Board mit Polstern versehen, damit ungültige Teilbewegungen in diesen Bereich fallen. Auf diese Weise können wir die Überprüfung von Grenzen vermeiden und den Code erheblich vereinfachen.
Wir werden ein lineares Array verwenden. Die größte Entfernung, die eine Schachfigur zurücklegen kann, ist die eines 2-Quadrat-Ritters. Natürlich können sich andere gleitende Teile über große Entfernungen bewegen, aber solche Bewegungen werden nacheinander ausgewertet, wenn jedes Quadrat gekreuzt wird. Dies bedeutet, dass die Brettgrenzen erkannt werden, bevor ein Teil darüber hinausgehen kann.
Daher benötigen wir einen zweizelligen Raum entlang der Kanten der Platine. Wir könnten eine 12x12-Karte erstellen, aber da wir sie als Linienarray darstellen, benötigen wir eine 12x10-Karte, da das am weitesten rechts stehende Einrückungsquadrat in der vorherigen Zeile als das am weitesten links stehende Einrückungsquadrat in der nächsten Zeile verwendet werden kann (× = Einzug):
×××××××××× ×××××××××× ×........× ×........× ×........× ×........× ×........× ×........× ×........× ×........× ×××××××××× ××××××××××
In unserer Notation würde "a1" wie 9 × 10 + 1 = 91 und "a8" wie "2 × 10 + 1" = 21 aussehen.
Jede Zelle in der Brettanordnung würde eine Schachfigur, ein leeres Quadrat oder eine Einrückungszone darstellen. hätte numerische Konstanten für diese Werte verwenden können, aber um das Debuggen zu vereinfachen, verwenden wir lesbare Zeichen. Groß- und Kleinbuchstaben kennzeichnen Formen, Leerzeichen kennzeichnen Einrückungszonen und Punkte kennzeichnen leere Zellen:
| | RNBQKBNR | PPPPPPPP | ........ | ........ | ........ | <- ........ | ........ | ........ | pppppppp | rnbkqbnr | | |
Dekodierung von Abkürzungen
R — rook —
N — knight —
B — bishop —
Q — queen —
K — king —
N — knight —
B — bishop —
Q — queen —
K — king —
Schließlich können wir mit dem Schreiben von Code beginnen:
type Piece byte
func (p Piece) Value() int { ... }
func (p Piece) Ours() bool { ... }
func (p Piece) Flip() Piece { ... }
type Board [120]piece
func (b Board) Flip() Board { ... }
type Square int
func (s Square) Flip() Square { ... }
Formen haben einen bestimmten Wert. Diese Werte werden benötigt, um Positionen auf dem Brett zu bewerten und zu verstehen, wer gewinnt. Normalerweise ist ein Bauer = 100, ein Ritter = 280, ein Bischof = 320, ein Turm = 479, eine Königin = 929 und ein König so wertvoll, dass er 8 Königinnen (in Königinnen verwandelte Bauern) in Verbindung mit Paaren von Rittern, Bischöfen und Türmen schlägt. Wenn wir all diesen Reichtum haben, aber den König verlieren, zeigt das Zählen immer noch, dass wir verlieren werden.
Jeder Typ hat eine Flip () -Methode, die nach dem Umdrehen des Bretts den gleichen Wert zurückgibt, bevor sich der Gegner bewegt. Bei Formen wird die Groß- und Kleinschreibung des Formsymbols geändert. Auf den Feldern gibt er 119 Felder zurück (vom anderen Ende des Bretts aus gezählt). Was die Tafel betrifft, kopiert er alle Teile von den Quadraten in umgekehrter Reihenfolge und ändert ihre Groß- und Kleinschreibung.
Hubgenerator
Wir haben also bereits die Bausteine für die Engine und können jetzt über Spielpositionen nachdenken. Position ist ein Brett mit Steinen und zusätzlichen Zuständen im Spiel, wie z. B. einem Durchgangsfeld, einem Wanderfeld und Burgenmöglichkeiten. Wenn wir das Spiel vereinfachen wollten, könnten wir den Bretttyp wiederverwenden, aber wir werden einen separaten Positionstyp für Züge und Brettbewertung erstellen.
Was ist ein Umzug? Dies ist eine Kombination aus zwei Zellen - der Zelle, in der sich das Teil vor dem Verschieben befand, und der Zelle, in der sich das Teil bewegt hat. Die Position ist ein Schachbrett mit Punktzahl, Regeln für jeden Spieler und Durchgangs- / Wanderfeldern. Beide Typen haben auch eine Flip () -Methode für die Züge des Gegners.
type Move struct {
from Square
to Square
}
func (m Move) Flip() Move { ... }
type Position struct {
board Board //
score int // — ,
wc [2]bool //
bc [2]bool //
ep Square // ,
kp Square // ,
}
func (p Position) Flip() Position { ... }
Jetzt können wir die erste große Methode schreiben - den Generator für erlaubte Bewegungen. Wir kümmern uns nur um die weißen Teile, da wir zum Spielen von Schwarz das Brett umdrehen und wieder weiß bewegen.
Um alle gültigen Züge zu generieren, benötigen wir:
- Erstellen Sie für jedes Stück eine Liste aller einstufigen Bewegungen in jede Richtung.
- Machen Sie dasselbe für alle Zellen und ignorieren Sie nicht weiße Teile.
- Bestimmen Sie für jedes weiße Stück eine Bewegung in jede mögliche Richtung.
- Wenn die Länge der Bewegung eines Stücks nicht begrenzt ist (Turm, Bischof, Königin), bewegen Sie es weiter, bis auf dem Weg ein Hindernis auftritt: das Stück eines Gegners oder eine Einkerbung hinter der Kante des Bretts.
Dies ist ein vereinfachter Code, der die Erfassung und das Castling nicht berücksichtigt. Sie finden die vollständige Implementierung auf Github , es ist nicht viel anders.
Um die Richtungsarithmetik besser lesbar zu machen, verwenden wir die Richtungskonstanten N / E / S / W:
const N, E, S, W = -10, 1, 10, -1
var directions = map[Piece][]Square{
'P': {N, N + N, N + W, N + E},
'N': {N + N + E, E + N + E, E + S + E, S + S + E, S + S + W, W + S + W, W + N + W, N + N + W},
'B': {N + E, S + E, S + W, N + W},
'R': {N, E, S, W},
'Q': {N, E, S, W, N + E, S + E, S + W, N + W},
'K': {N, E, S, W, N + E, S + E, S + W, N + W},
}
func (pos Position) Moves() (moves []Move) {
for index, p := range pos.board {
if !p.ours() {
continue
}
i := Square(index)
for _, d := range directions[p] {
for j := i + d; ; j = j + d {
q := pos.board[j]
if q == ' ' || (q != '.' && q.ours()) {
break
}
if p == 'P' {
if (d == N || d == N+N) && q != '.' {
break
}
if d == N+N && (i < A1+N || pos.board[i+N] != '.') {
break
}
}
moves = append(moves, Move{from: i, to: j})
if p == 'P' || p == 'N' || p == 'K' || (q != ' ' && q != '.' && !q.ours()) {
break
}
}
}
}
return moves
}
Dies sind alle Regeln des Schachspiels, die wir berücksichtigen müssen, um gültige Züge zu machen. Der nächste Schritt besteht darin, einen Zug auf die Position anzuwenden, um eine neue Spielposition zu erstellen. Ohne Berücksichtigung der Erfassung unterwegs, der Bauernförderung und der Rochade würde die Methode folgendermaßen aussehen:
func (pos Position) Move(m Move) (np Position) {
np = pos
np.board[m.to] = pos.board[m.from]
np.board[m.from] = '.'
return np.Flip()
}
Er bewegt einfach das Stück, markiert die Zelle, auf der es zuvor leer war, und dreht das Brett um. Die vollständige Implementierung der Methode finden Sie auf Github . Sie behandelt alle speziellen Bauern- und Königsbewegungen korrekt.
In dieser Phase können Sie Schach "Mann gegen Mann" spielen, den Prozess kontrollieren und nur legale Schritte ausführen. Oder Sie können eine primitive Schach-Engine erstellen, die zufällige Züge ausführt, bis sie verliert.
Aber wie verstehen wir, dass wir verlieren?
Board Rating
Für jede Position auf dem Brett werden Punkte vergeben. Anfangs ist die Punktzahl Null, da beide Spieler zu gleichen Bedingungen starten. Nach Abschluss eines Zuges ändert sich die Punktzahl abhängig davon, welche Teile erbeutet wurden und wie sich die Position der Teile auf dem Brett geändert hat.
Im einfachsten Fall können wir die Steine auf dem Brett zählen und ihren Wert addieren (abzüglich der Steine des Gegners). Eine solche Berechnung zeigt, ob der König als Scheck und Schachmatt deklariert ist. Dies ist jedoch ein sehr schwaches Bewertungssystem.
Ein viel genauerer und überraschend einfacher Ansatz sind Form-zu-Quadrat-Verhältnis-Tabellen ( PST)- Stück-Quadrat-Tische). Für jede Figur wird eine Tabelle in der gleichen Größe wie ein Schachbrett erstellt, wobei jedem Quadrat ein entsprechender Wert zugewiesen wird. Diese Werte sind empirisch, daher habe ich sie nur der Sunfish-Engine entnommen.
Tatsächlich aktualisieren fortgeschrittenere Schach-Engines PSTs während des Spiels, weil sich der Wert der Figuren ändert (d. H. Bauern werden gegen Ende des Spiels wertvoller). Aber wir werden einen einfachen Motor haben.
Um die Position nach dem Umzug zu bewerten, benötigen wir:
- Bestimmen Sie die Bewertung der aktuellen Position,
- subtrahieren Sie den Wert des zu bewegenden Stücks,
- Fügen Sie einen neuen Zahlenwert gemäß der PTS-Tabelle hinzu.
- Fügen Sie gegebenenfalls den Wert des erfassten Teils hinzu.
Zusätzlich müssen wir in der PST-Tabelle den Wert des Turmes während der Rochade und den Wert des Bauern während der Beförderung oder Gefangennahme auf dem Pass anpassen. Aber hier werden wir dies nicht berücksichtigen:
var pst = map[Piece][120]int{
'P': { ... },
'N': { ... },
'B': { ... },
'R': { ... },
'Q': { ... },
'K': { .... },
}
func (pos Position) value(m Move) int {
i, j := m.from, m.to
p, q := Piece(pos.board[i]), Piece(pos.board[j])
// PST-
score := pst[p][j] - pst[p][i]
if q != '.' && q != ' ' && !q.ours() {
// PST-
score += pst[q.Flip()][j.Flip()]
}
return score
}
Jetzt können wir eine etwas fortschrittlichere Engine entwickeln, die den bestmöglichen Zug wählt, anstatt einen der gültigen.
Echte Schach-Engines analysieren jedoch eingehender und durchlaufen die Zweige möglicher Züge auf jeder Seite, um auf lange Sicht den bestmöglichen Zug zu finden.
Suchalgorithmus
Der gebräuchlichste Suchalgorithmus in Schachmaschinen ist einfacher - die Tiefensuche, die an der Wurzel beginnt und bis zu einer bestimmten Tiefengrenze reicht und alle möglichen Züge wiederholt, bevor sie zurückkehrt. Für jeden Strich wird der Positionswert unter Verwendung eines Minimax-Algorithmus (Minimax) c Alpha-Beta-Bereinigung ( Alpha-Beta-Bereinigung ) berechnet .
Minimax ist eine Regel, die verwendet wird, um mögliche Verluste im schlimmsten Fall zu minimieren: Der Spieler berücksichtigt alle besten Züge des Gegners und wählt einen solchen Zug, damit die beste Strategie des Gegners so viele Punkte wie möglich bringt.
Ein einfacher Minimax-Algorithmus wäre zu langsam für Schach und würde das Wiederholen zu vieler Züge erfordern, um einen guten zu finden.
Alpha-Beta-Bereinigung wird verwendet, um den Minimax-Algorithmus zu beschleunigen, indem Knoten entfernt werden, die nicht in Betracht gezogen werden sollten. Alpha-Beta-Clipping basiert auf der folgenden Logik: Stellen Sie sich vor, Sie spielen Schach und finden einen sehr guten Zug A. Sie schauen weiter auf das Brett und finden einen noch besseren Zug B. Aber dann analysieren Sie die Situation tiefer und verstehen das, wenn Sie möchten In Zug B erklärt der Feind Ihnen in wenigen Zügen Scheck und Schachmatt. Jetzt verwerfen Sie B und verschwenden keine Zeit damit, andere mögliche Kombinationen nach B zu analysieren.
Sowohl Minimax- als auch Alpha-Beta-Clipping sind wichtig, um die Funktionsweise der Schachengine zu verstehen. Die Sunfish-Engine verwendet einen verbesserten MDF (f) -Suchalgorithmus , der auch eine Variante des Minimax-Algorithmus in Kombination mit Clipping darstellt.
In unserer Engine erhöhen wir schrittweise die Suchtiefe und rufen den MDF (f) -Algorithmus auf, um die Unter- und Obergrenze des optimalen Ergebnisses zu ermitteln. Der MDF (f) -Algorithmus verwendet eine Alpha-Beta-Clipping-Iteration mit einem Transpositionscache.
Transpositionsgeld ist ein Cache, in dem wir uns für jede Position auf dem Brett die Tiefe, Anzahl und Bewegung merken, die uns zu dieser Position geführt haben. Wenn dann eine neue Position betrachtet wird, wird sie zuerst mit der Transpositionstabelle verglichen.
Ich werde den Code des Suchalgorithmus hier nicht veröffentlichen, da es sich nur um ein paar Zeilen rekursiver Suche handelt, aber Sie können immer den vollständigen Quellcode der Schachmaschine auf GitHub finden .
Was weiter?
Wenn Sie an einfachen Schach-Engines interessiert sind, empfehle ich dringend, mit Sunfish zu spielen. Sunfish basiert übrigens auf der Micromax- Engine und enthält eine großartige Dokumentation des Autors, die definitiv lesenswert ist.
Für unsere Engine in Go habe ich eine kleine Implementierung des UCI-Protokolls hinzugefügt, damit es mit der PyChess-Benutzeroberfläche verwendet werden kann. Höchstwahrscheinlich gibt es immer noch viele Fehler und viel Verbesserungspotential, aber es war ein interessanter Weg: von der Idee, eine Schachengine zu entwickeln, bis zu einem vorgefertigten, funktionierenden Computerschachprogramm.
Ja, er ist schwach, aber er spielt echte Schachspiele!
Ich hoffe, Ihnen hat dieser Artikel gefallen. Du kannst mir folgen bei Github , Twitter oder abonnieren über RSS .