chess_engine_using_python

Schach-Engine mit Python

Dieses Repository enthält die Implementierung einer Schach-Engine mit Minimax , Alpha-Beta-Pruning und dem Quieszenz-Suchalgorithmus . Für die Codierung wird ein Jupyter-Notebook in einem Docker-Container verwendet. Alle Jupyter-Notebooks sind auch in Form eines Docker-Images verfügbar.

Schauen Sie sich das Projektpapier an, um eine detaillierte Analyse zu sehen.

Externes Modul verwendet

• Python-Schach

So führen Sie es mit Docker aus

docker pull codewithnk/chess-engine-using-python:latest

docker run -p 8888:8888 -v $( pwd ) codewithnk/chess-engine-using-python:latest

Algorithmen der Schachmaschine

Minmax

Theorie

Der Kern des Schachspiels in Minmax. Minmax assoziiert normalerweise die schwarze Figur mit MAX und die weiße Figur mit MIN und bewertet immer aus der weißen Sicht.

Der Minmax-Algorithmus ist ein kontradiktorischer Suchalgorithmus in der Spieltheorie. Es nutzt den Spielbaum und umfasst MIN und MAX für zwei Spieler. Beide Spieler versuchen, die Aktion des anderen zunichte zu machen. Max versucht, das Ergebnis zu maximieren, während MIN versucht, das Ergebnis zu minimieren. Beide Spieler spielen abwechselnd, unter der Annahme, dass beide optimal spielen. Optimales Spiel bedeutet, dass beide Spieler gemäß der Regel spielen, dh MIN minimiert das Ergebnis und MAX maximiert das Ergebnis.

Der Minmax-Algorithmus verwendet den Depth-First-Search-Ansatz, um das Ergebnis zu finden. Darüber hinaus werden Backtracking und Rekursion eingesetzt. Der Algorithmus durchläuft den Knoten bis zum Endknoten und kehrt dann zurück, während er alle untergeordneten Werte vergleicht. Es wählt den Mindest- oder Höchstwert aus, je nachdem, wer an der Reihe ist. Anschließend wird der Wert an das übergeordnete Element zurückgegeben. Es verwendet eine statische Bewertungsfunktion, um den Wert an jedem Blattknoten zu bestimmen. Es nutzt den Vorteil des Nullsummenspiels.

Durchführung

Schach-Engine mit Minmax

Zeitkomplexität

Minmax verwendet Depth First Search (DFS) im Spielbaum, daher beträgt die zeitliche Komplexität des Minmax-Algorithmus O(b**m) , wobei b der Verzweigungsfaktor des Spielbaums und m die maximale Tiefe des Baums ist.

Weltraumkomplexität

Die räumliche Komplexität des Minmax-Algorithmus ähnelt auch der von DFS, nämlich O(bm) , wobei b der Verzweigungsfaktor des Spielbaums und m die maximale Tiefe des Baums ist.

Vollständigkeit

Der Minmax-Algorithmus ist abgeschlossen. Es wird auf jeden Fall eine Lösung, falls vorhanden, im endlichen Suchbaum finden.

Optimalität

Der Minmax-Algorithmus ist optimal, wenn beide Gegner optimal spielen.

---

Alpha-Beta-Beschneidung

Theorie

Der Minmax-Algorithmus kann durch Beschneiden einiger Zweige optimiert werden. Beschnittene Äste haben keinen Einfluss auf das Ergebnis. Es wird die Zeitkomplexität verbessern. Diese Minmax-Version ist als Minmax mit Alpha-Beta-Beschneidung bekannt. Er wird auch als Alpha-Beta-Algorithmus bezeichnet.
Beim Alpha-Beta-Beschneiden gibt es zwei Werte: Alpha und Beta. Im Folgenden finden Sie einige Punkte, die Sie bei Alpha und Beta beachten sollten:

Irgendwann etwas zu Alpha(α)

• Alpha ist der höchste Wert, der entlang des MAX-Pfades gefunden wird.
• Der Anfangswert von Alpha ist negativ unendlich, da der Alpha-Wert bei jeder Bewegung weiter ansteigt oder gleich bleibt. Wenn wir einen anderen Wert als negative Unendlichkeit wählen, kann das Szenario eintreten, dass alle Alpha-Werte kleiner als der gewählte Wert sind. Wir müssen also den niedrigstmöglichen Wert wählen, und das ist negative Unendlichkeit.
• Alpha wird nur vom MAX-Spieler aktualisiert.

Einige Punkte zu Beta(β)

• Beta ist der niedrigste Wert, der entlang des MIN-Pfades gefunden wird.
• Der Anfangswert von Beta ist positiv unendlich, da der Beta-Wert bei jeder Bewegung weiter abnimmt oder gleich bleibt. Wenn wir einen anderen Wert als die positive Unendlichkeit wählen, kann es zu einem Szenario kommen, in dem alle Beta-Werte größer als der gewählte Wert sind. Wir müssen also den maximal möglichen Wert wählen, und das ist positive Unendlichkeit.
• Der Beta-Wert wird nur vom MIN-Spieler aktualisiert.

Beim Backtracking wird nur der Knotenwert an den übergeordneten Knoten übergeben, nicht der Alpha- und Betawert.

Die Bedingung für das Alpha-Beta-Beschneiden:

 α >= β

Reihenfolge verschieben

Die Wirksamkeit des Alpha-Beta-Algorithmus hängt stark von der Reihenfolge der Durchquerung ab. Es spielt eine entscheidende Rolle bei der Zeit- und Raumkomplexität.

Schlechteste Bestellung

In einigen Fällen wird kein Knoten oder Unterbaum aus dem Game Tree entfernt. In diesem Fall findet der beste Zug im rechten Unterbaum des Spielbaums statt. Dies führt zu einer erhöhten Zeitkomplexität.

Ideale Bestellung

In diesem Fall wird die maximale Anzahl an Knoten und Unterbäumen beschnitten. Die besten Züge finden im linken Teilbaum statt. Dadurch wird die zeitliche und räumliche Komplexität verringert.

Durchführung

Schach-Engine mit Alpha-Beta-Pruning

Zeitkomplexität

Der Alpha-Beta-Algorithmus verwendet auch Depth First Search (DFS) im Game Tree.

• Im Fall der schlechtesten Reihenfolge: O(b^m)
• Bei idealer Ordnung: O(b^m/2)

Weltraumkomplexität

• Im Falle der schlechtesten Reihenfolge: O(bm)
• Bei idealer Ordnung: O(b(m/2))

Vollständigkeit

Der Alpha-Beta-Algorithmus ist abgeschlossen. Es wird auf jeden Fall eine Lösung, falls vorhanden, im endlichen Suchbaum finden.

Optimalität

Der Alpha-Beta-Algorithmus ist optimal, wenn beide Gegner optimal spielen.

---

Ruhesuche

Die Ruhesuche ist eine Modifikation zusätzlich zum Alpha-Beta-Pruning mit Min-Max. Ruhe bedeutet Stille. Bei dieser Suche werden nur ruhige Bewegungen ausgewertet. Mit anderen Worten: Ab einer bestimmten Tiefe werden nur noch Fangzüge zur Berechnung der nächsten Züge verwendet. Eine Ruhesuche kann den Horizonteffekt vermeiden.
Der Horizonteffekt tritt auf, wenn wir nur bis zu einer bestimmten Tiefe suchen. Es kann jedoch vorkommen, dass die Bewegung weniger Punkte bringt, wenn wir noch eine Ebene tiefer blicken. Um dies zu verhindern, verwendet eine Ruhesuche nur Fangzüge. Die Ruhesuche reduziert außerdem den Verzweigungsfaktor auf verschiedenen Ebenen, was zu einem schnellen Algorithmus führt.

Zeitkomplexität

Der Ruhesuchalgorithmus verwendet auch die Tiefensuche (DFS) im Game Tree.

• Im Fall der schlechtesten Reihenfolge: O(b^m)
• Bei idealer Ordnung: O(b^m/2)

Weltraumkomplexität

• Im Falle der schlechtesten Reihenfolge: O(bm)
• Bei idealer Ordnung: O(b(m/2))

Vollständigkeit

Der Ruhesuchalgorithmus ist abgeschlossen. Es wird auf jeden Fall eine Lösung, falls vorhanden, im endlichen Suchbaum finden.

Optimalität

Der Ruhesuchalgorithmus ist optimal, wenn beide Gegner optimal spielen.

---

Schlüssel zum Mitnehmen

• Die pro Zug erkundeten Knoten werden in Alpha Beta im Vergleich zu Minmax um das Zehnfache reduziert.
• Die Zeit, die benötigt wird, um den besten Zug zu finden, wird in Alpha Beta im Vergleich zu Minmax ebenfalls um das Zehnfache reduziert.
• Die Ruhesuche funktioniert in größerer Tiefe gut.
• Die Ruhesuche ist der schnellste von allen drei Algorithmen.
• Die Ruhesuche wertet weniger Knoten aus.
• Die Ruhesuche kann zu wiederholten Bewegungen führen, wenn sie nicht richtig gehandhabt wird.