In Teil 1 haben wir uns angesehen, wie man die Stellung auf dem Schachbrett als Klassen und Objekte darstellt, in Teil 2, wie man in einer gegebenen Stellung alle gültigen Züge generiert und in Teil 3, wie man eine Stellung bewertet und herausfindet, welche Seite im Vorteil ist. In diesem letzten Teil suchen wir nun die beste Folge von Zügen und setzen alles zusammen.
Der Minimax-Algorithmus
Schach kann man sich als Baumstruktur vorstellen. Die aktuelle Stellung bildet den Wurzelknoten, jeder gültige Zug führt zu einem Kindknoten und von diesen führen weitere Züge zu weiteren Knoten usw.
Bei einfachen Spielen wie Tic-Tac-Toe ist der Baum womöglich klein genug, dass wir ihn vollständig untersuchen können. Bei Schach übersteigt er aber die Fähigkeiten der besten Computer und wir müssen ihn bei einer bestimmten Tiefe abschneiden.
Knoten am Ende des Baums bewerten wir mit unserer Bewertungsmethode aus dem vorherigen Teil. Nehmen wir an, dass dabei positive Zahlen für einen weißen Vorteil stehen und negative für einen schwarzen. Wenn nun zuvor Weiß am Zug ist, wird Weiß den Zug wählen, der die größte Zahl liefert. Wir können die vorhergehende Stellung dann mit derselben Zahl bewerten. Schwarz hingegen würde die kleinste (bzw. die größte negative) Zahl wählen. Auf diese Art können wir Bewertungen im Baum nach oben weitergeben. Eine Seite minimiert das Ergebnis, die andere Seite maximiert es. Daher der Name Minimax-Algorithmus. Wir werden aber wieder unsere Vorzeichen-Magie einsetzen, so dass tatsächlich beide Seiten maximieren.
Wir können das als rekursive Funktion implementieren, ungefähr so:
def minimax(state, depth):
if depth == 0:
return state.evaluate(), None
moves = state.generate_moves()
if len(moves) == 0:
if state.check(state.player):
return -20000, None # checkmate
else:
return 0, None # stalemate
score = -float("inf")
for move in moves:
move_score = -minimax(move, depth - 1)[0]
if move_score > score:
score = move_score
top_move = move
return score, top_move
Ein paar Erläuterungen:
Die Funktion gibt zwei Werte zurück, die Bewertung der Stellung und den besten Nachfolgezug oder None, wenn wir keinen finden.
Zeilen 2 und 3: Wenn wir die Suchtiefe 0 erreicht haben, geben wir das Ergebnis der Bewertungsmethode aus Teil 3 zurück. Wenn ihr euch erinnert, haben wir bereits da die Vorzeichen-Magie angewendet, eine positive Zahl steht also für einen Vorteil der Seite am Zug.
Zeilen 5 bis 9: Wenn die Stellung keine Nachfolgezüge hat, muss sie Matt oder Patt sein. Ein Matt bewerten wir hier einfach mit 200 Bauern. Es könnte aber auch eine andere Zahl sein, hauptsache deutlich größer als jeder realistische Materialvorsprung.
Zeilen 11 bis 15: Ansonsten gehen wir alle Züge in einer Schleife durch und suchen den mit der höchsten Bewertung. In Zeile 12 rufen wir die Funktion rekursiv mit verminderter Suchtiefe auf. Beachte, dass hier ein negatives Vorzeichen steht, das ist natürlich wieder unsere Vorzeichen-Magie.
Alpha-Beta Pruning
Jetzt wird es etwas knifflig. Ich habe selbst eine Weile gebraucht, um es zu verstehen, und ich bin mir nicht sicher, ob ich es gut erklären kann. Hinterlasst ruhig einen Kommentar, wenn was unklar bleibt, vielleicht finden wir nachträglich eine bessere Erklärung. Ich versuche es einfach mal mit einem Beispiel.
Weiß ist am Zug und der erste von mehreren möglichen Zügen ergibt einen Vorteil von 50 Zentibauern für Weiß. Wir untersuchen nun den zweiten Zug und den ersten schwarzen Gegenzug und dieser liefert nur einen Vorteil von 25 Zentibauern für Weiß. Wir können jetzt schon sagen, dass das nicht Teil der besten Zugfolge sein kann. Warum?
- Selbst wenn die anderen schwarzen Züge ein besseres Ergebnis für Weiß liefern, wird Schwarz diese nicht wählen.
- Weiß wird aber schon gar nicht zulassen, dass es so weit kommt, und lieber den Zug mit 50 Zentibauern wählen. (Oder einen noch besseren, falls wir später noch einen finden.)
Wir können uns also die Untersuchung der übrigen schwarzen Züge sparen und so Teile des Baums abschneiden. Das kann uns eine Menge Arbeit ersparen.
In Code setzen wir das mit zwei Hilfvariablen um: alpha ist das Minimum, das die Seite am Zug erreichen kann, beta das Maximum, das die andere Seite zulässt. So würde dann unsere verbesserte Minimax-Funktion aussehen:
def minimax(state, depth, alpha=-float("inf"), beta=float("inf")):
if depth == 0:
return state.evaluate(), None
moves = state.generate_moves()
if len(moves) == 0:
if state.check(state.player):
return -20000, None # checkmate
else:
return 0, None # stalemate
score = -float("inf")
for move in moves:
move_score = -minimax(move, depth - 1, -beta, -alpha)[0]
if move_score > score:
score = move_score
top_move = move
if score > alpha:
alpha = score
if alpha >= beta:
break
return score, top_move
Bei manchen Stellungen erreicht kein Zug alpha. Das sind die sogenannten Fail-low-Knoten. Sie bringen uns nicht viel, da wir alle Nachfolgezüge untersuchen müssen, um das festzustellen. Andere Stellungen dagegen überschreiten beta. Bei diesen Fail-high-Knoten können wir die Schleife vorzeitig abbrechen und diese Beta-Cutoffs können potentiell große Teile des Baums abschneiden.
Weitere Ideen
Ohne sie vorzuführen, möchte ich noch ein paar weitere Verbesserungsideen andeuten, die ihr in eurem eigenen Code vielleicht mal probieren möchtet.
Killerzüge: Das Alpha-Beta Pruning kann noch effektiver werden, wenn man immer den besten Zug zuerst untersucht. Dadurch wird das Alpha-Beta-Fenster schnell kleiner und es kommt zu mehr Beta-Cutoffs. Leider weiß man halt vorher nicht, was der beste Zug ist, aber man kann es vielleicht schätzen. Man sammelt dazu Daten, welche Züge besonders oft Cutoffs verursachen („Killerzüge“) und wenn sie anderswo wieder auftreten, sortiert man sie nach vorn. Man kann das z.B. mit der History-Heuristik umsetzen.
Iterative Deepening: Statt sofort bis zur gewünschten Suchtiefe zu suchen, sucht man erst einmal mit verminderter Tiefe. Das hört sich erst einmal nach unnötiger Mehrarbeit an, aber man kann dabei bereits Informationen über mögliche Killerzüge sammeln und so bei der vollen Suchtiefe wieder Arbeit einsparen.
Quiescence Search: Bei Suchtiefe 0 rufen wir nicht sofort die Bewertungsmethode auf, sondern suchen mit unbegrenzter Suchtiefe weiter, allerdings nur Schlagzüge. Das kann uns Vorteile für eine Seite bei einem Abtausch in dieser Stellung verraten.
Monte Carlo Tree Search: Eine spannende Alternative zum klassischen Minimax-Algorithmus, meine eigenen Experimente damit waren aber noch nicht ganz zufriedenstellend. Bei Reversi und Dame konnte ich damit ganz gute Resultate erzielen, bei Mühle und Schach waren die Ergebnisse eher durchwachsen. Aber vielleicht kommt dazu auch mal ein Blogpost.
Der Code
Python ist bekanntlich nicht die schnellste Sprache, vielleicht probiert ihr mal, den Code mit PyPy statt CPython auszuführen, um ihn etwas zu beschleunigen. Die Suchtiefe ist fest auf sechs Halbzüge eingestellt, ändert das gegebenenfalls in Zeile 748.
Die Eingabe der Züge erfolgt in einer vereinfachten Notation, die nur aus Start- und Zielfeld besteht, z.B. e2e4. Bei der Rochade wird nur der Königszug eingeben, z.B. e1g1 und bei der Bauernumwandlung die gewünschte Figurenart angehängt, z.B. e2e1Q.
Die Regeln sind größtenteils vollständig implementiert, nur bei einigen Remisregeln gibt es leichte Abweichungen. Remis nach dreifacher Stellungswiederholung oder 50-Züge-Regel ist automatisch und muss nicht beansprucht werden. Remis bei unmöglichem Schachmatt wird nur in einer Teilmenge solcher Stellungen erkannt, alle anderen sind irgendwann wegen anderer Regeln remis.
WHITE = 1
BLACK = -1
WK = 6 # white king
WQ = 5 # white queen
WB = 4 # white bishop
WN = 3 # white knight
WR = 2 # white rook
WP = 1 # white pawn
BK = -6 # black king
BQ = -5 # black queen
BB = -4 # black bishop
BN = -3 # black knight
BR = -2 # black rook
BP = -1 # black pawn
EM = 0 # empty
LV = -7 # lava
white_king_table = (
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, -30, -40, -40, -50, -50, -40, -40, -30, 0,
0, -30, -40, -40, -50, -50, -40, -40, -30, 0,
0, -30, -40, -40, -50, -50, -40, -40, -30, 0,
0, -30, -40, -40, -50, -50, -40, -40, -30, 0,
0, -20, -30, -30, -40, -40, -30, -30, -20, 0,
0, -10, -20, -20, -20, -20, -20, -20, -10, 0,
0, 20, 20, 0, 0, 0, 0, 20, 20, 0,
0, 20, 30, 10, 0, 0, 10, 30, 20, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0
)
white_king_endgame_table = (
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, -50, -40, -30, -20, -20, -30, -40, -50, 0,
0, -30, -20, -10, 0, 0, -10, -20, -30, 0,
0, -30, -10, 20, 30, 30, 20, -10, -30, 0,
0, -30, -10, 30, 40, 40, 30, -10, -30, 0,
0, -30, -10, 30, 40, 40, 30, -10, -30, 0,
0, -30, -10, 20, 30, 30, 20, -10, -30, 0,
0, -30, -30, 0, 0, 0, 0, -30, -30, 0,
0, -50, -30, -30, -30, -30, -30, -30, -50, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0
)
white_queen_table = (
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, -20, -10, -10, -5, -5, -10, -10, -20, 0,
0, -10, 0, 0, 0, 0, 0, 0, -10, 0,
0, -10, 0, 5, 5, 5, 5, 0, -10, 0,
0, -5, 0, 5, 5, 5, 5, 0, -5, 0,
0, 0, 0, 5, 5, 5, 5, 0, -5, 0,
0, -10, 5, 5, 5, 5, 5, 0, -10, 0,
0, -10, 0, 5, 0, 0, 0, 0, -10, 0,
0, -20, -10, -10, -5, -5, -10, -10, -20, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0
)
white_bishop_table = (
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, -20, -10, -10, -10, -10, -10, -10, -20, 0,
0, -10, 0, 0, 0, 0, 0, 0, -10, 0,
0, -10, 0, 5, 10, 10, 5, 0, -10, 0,
0, -10, 5, 5, 10, 10, 5, 5, -10, 0,
0, -10, 0, 10, 10, 10, 10, 0, -10, 0,
0, -10, 10, 10, 10, 10, 10, 10, -10, 0,
0, -10, 5, 0, 0, 0, 0, 5, -10, 0,
0, -20, -10, -10, -10, -10, -10, -10, -20, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0
)
white_knight_table = (
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, -50, -40, -30, -30, -30, -30, -40, -50, 0,
0, -40, -20, 0, 0, 0, 0, -20, -40, 0,
0, -30, 0, 10, 15, 15, 10, 0, -30, 0,
0, -30, 5, 15, 20, 20, 15, 5, -30, 0,
0, -30, 0, 15, 20, 20, 15, 0, -30, 0,
0, -30, 5, 10, 15, 15, 10, 5, -30, 0,
0, -40, -20, 0, 5, 5, 0, -20, -40, 0,
0, -50, -40, -30, -30, -30, -30, -40, -50, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0
)
white_rook_table = (
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 5, 10, 10, 10, 10, 10, 10, 5, 0,
0, -5, 0, 0, 0, 0, 0, 0, -5, 0,
0, -5, 0, 0, 0, 0, 0, 0, -5, 0,
0, -5, 0, 0, 0, 0, 0, 0, -5, 0,
0, -5, 0, 0, 0, 0, 0, 0, -5, 0,
0, -5, 0, 0, 0, 0, 0, 0, -5, 0,
0, 0, 0, 0, 5, 5, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0
)
white_pawn_table = (
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 50, 50, 50, 50, 50, 50, 50, 50, 0,
0, 10, 10, 20, 30, 30, 20, 10, 10, 0,
0, 5, 5, 10, 25, 25, 10, 5, 5, 0,
0, 0, 0, 0, 20, 20, 0, 0, 0, 0,
0, 5, -5, -10, 0, 0, -10, -5, 5, 0,
0, 5, 10, 10, -20, -20, 10, 10, 5, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0
)
black_king_table = (
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 20, 30, 10, 0, 0, 10, 30, 20, 0,
0, 20, 20, 0, 0, 0, 0, 20, 20, 0,
0, -10, -20, -20, -20, -20, -20, -20, -10, 0,
0, -20, -30, -30, -40, -40, -30, -30, -20, 0,
0, -30, -40, -40, -50, -50, -40, -40, -30, 0,
0, -30, -40, -40, -50, -50, -40, -40, -30, 0,
0, -30, -40, -40, -50, -50, -40, -40, -30, 0,
0, -30, -40, -40, -50, -50, -40, -40, -30, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0
)
black_king_endgame_table = (
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, -50, -30, -30, -30, -30, -30, -30, -50, 0,
0, -30, -30, 0, 0, 0, 0, -30, -30, 0,
0, -30, -10, 20, 30, 30, 20, -10, -30, 0,
0, -30, -10, 30, 40, 40, 30, -10, -30, 0,
0, -30, -10, 30, 40, 40, 30, -10, -30, 0,
0, -30, -10, 20, 30, 30, 20, -10, -30, 0,
0, -30, -20, -10, 0, 0, -10, -20, -30, 0,
0, -50, -40, -30, -20, -20, -30, -40, -50, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0
)
black_queen_table = (
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, -20, -10, -10, -5, -5, -10, -10, -20, 0,
0, -10, 0, 5, 0, 0, 0, 0, -10, 0,
0, -10, 5, 5, 5, 5, 5, 0, -10, 0,
0, 0, 0, 5, 5, 5, 5, 0, -5, 0,
0, -5, 0, 5, 5, 5, 5, 0, -5, 0,
0, -10, 0, 5, 5, 5, 5, 0, -10, 0,
0, -10, 0, 0, 0, 0, 0, 0, -10, 0,
0, -20, -10, -10, -5, -5, -10, -10, -20, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0
)
black_bishop_table = (
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, -20, -10, -10, -10, -10, -10, -10, -20, 0,
0, -10, 5, 0, 0, 0, 0, 5, -10, 0,
0, -10, 10, 10, 10, 10, 10, 10, -10, 0,
0, -10, 0, 10, 10, 10, 10, 0, -10, 0,
0, -10, 5, 5, 10, 10, 5, 5, -10, 0,
0, -10, 0, 5, 10, 10, 5, 0, -10, 0,
0, -10, 0, 0, 0, 0, 0, 0, -10, 0,
0, -20, -10, -10, -10, -10, -10, -10, -20, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0
)
black_knight_table = (
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, -50, -40, -30, -30, -30, -30, -40, -50, 0,
0, -40, -20, 0, 5, 5, 0, -20, -40, 0,
0, -30, 5, 10, 15, 15, 10, 5, -30, 0,
0, -30, 0, 15, 20, 20, 15, 0, -30, 0,
0, -30, 5, 15, 20, 20, 15, 5, -30, 0,
0, -30, 0, 10, 15, 15, 10, 0, -30, 0,
0, -40, -20, 0, 0, 0, 0, -20, -40, 0,
0, -50, -40, -30, -30, -30, -30, -40, -50, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0
)
black_rook_table = (
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 5, 5, 0, 0, 0, 0,
0, -5, 0, 0, 0, 0, 0, 0, -5, 0,
0, -5, 0, 0, 0, 0, 0, 0, -5, 0,
0, -5, 0, 0, 0, 0, 0, 0, -5, 0,
0, -5, 0, 0, 0, 0, 0, 0, -5, 0,
0, -5, 0, 0, 0, 0, 0, 0, -5, 0,
0, 5, 10, 10, 10, 10, 10, 10, 5, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0
)
black_pawn_table = (
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 5, 10, 10, -20, -20, 10, 10, 5, 0,
0, 5, -5, -10, 0, 0, -10, -5, 5, 0,
0, 0, 0, 0, 20, 20, 0, 0, 0, 0,
0, 5, 5, 10, 25, 25, 10, 5, 5, 0,
0, 10, 10, 20, 30, 30, 20, 10, 10, 0,
0, 50, 50, 50, 50, 50, 50, 50, 50, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0
)
class State:
def __init__(self, other=None):
if other is None:
self.board = [
LV, LV, LV, LV, LV, LV, LV, LV, LV, LV,
LV, LV, LV, LV, LV, LV, LV, LV, LV, LV,
LV, BR, BN, BB, BQ, BK, BB, BN, BR, LV,
LV, BP, BP, BP, BP, BP, BP, BP, BP, LV,
LV, EM, EM, EM, EM, EM, EM, EM, EM, LV,
LV, EM, EM, EM, EM, EM, EM, EM, EM, LV,
LV, EM, EM, EM, EM, EM, EM, EM, EM, LV,
LV, EM, EM, EM, EM, EM, EM, EM, EM, LV,
LV, WP, WP, WP, WP, WP, WP, WP, WP, LV,
LV, WR, WN, WB, WQ, WK, WB, WN, WR, LV,
LV, LV, LV, LV, LV, LV, LV, LV, LV, LV,
LV, LV, LV, LV, LV, LV, LV, LV, LV, LV
]
self.player = WHITE
self.castling = [True, True, True, True]
self.en_passant = None
self.halfmove_clock = 0
self.white_king = 95
self.black_king = 25
else:
self.board = list(other.board)
self.player = other.player
self.castling = list(other.castling)
self.en_passant = None
self.halfmove_clock = other.halfmove_clock
self.white_king = other.white_king
self.black_king = other.black_king
def __eq__(self, other):
for square in range(21, 99):
if self.board[square] != other.board[square]:
return False
if self.player != other.player:
return False
for i in range(4):
if self.castling[i] != other.castling[i]:
return False
if self.en_passant != other.en_passant:
return False
return True
def __str__(self):
string = ""
for square in range(21, 99):
if square % 10 == 1:
string += "%i " % (10 - square // 10)
piece = self.board[square]
if piece == WK:
string += "K "
elif piece == WQ:
string += "Q "
elif piece == WB:
string += "B "
elif piece == WN:
string += "N "
elif piece == WR:
string += "R "
elif piece == WP:
string += "P "
elif piece == BK:
string += "k "
elif piece == BQ:
string += "q "
elif piece == BB:
string += "b "
elif piece == BN:
string += "n "
elif piece == BR:
string += "r "
elif piece == BP:
string += "p "
elif piece == EM:
string += ". "
if square % 10 == 8:
string += "\n"
string += " a b c d e f g h \n"
return string
def capturable(self, square):
piece = self.player * self.board[square]
return piece >= BK and piece <= BP
def capturable_or_empty(self, square):
piece = self.player * self.board[square]
return piece >= BK and piece <= EM
def double_step(self, origin):
if self.player == WHITE:
return origin // 10 == 8
else:
return origin // 10 == 3
def insufficient_material(self):
one_knight = False
bishops_on_white = False
bishops_on_black = False
for square in range(21, 99):
piece = abs(self.board[square])
if piece in (WQ, WR, WP):
return False
elif piece == WB:
rank = square // 10
file = square % 10
if rank % 2 != file % 2:
bishops_on_white = True
else:
bishops_on_black = True
elif piece == WN:
if one_knight:
return False
one_knight = True
if one_knight and bishops_on_white:
return False
elif one_knight and bishops_on_black:
return False
elif bishops_on_white and bishops_on_black:
return False
else:
return True
def notation(self):
notation = " abcdefgh"[self.move[0] % 10]
notation += " 87654321"[self.move[0] // 10]
notation += " abcdefgh"[self.move[1] % 10]
notation += " 87654321"[self.move[1] // 10]
if len(self.move) == 3:
notation += " rnbq"[self.move[2]]
return notation
def promotion(self, target):
if self.player == WHITE:
return target // 10 == 2
else:
return target // 10 == 9
def make_move(self, origin, target):
# copy state
move = State(self)
# move piece
move.board[origin] = EM
move.board[target] = self.board[origin]
# switch player
move.player = -move.player
# update castling rights
if origin == 95 or origin == 98 or target == 98:
move.castling[0] = False
if origin == 95 or origin == 91 or target == 91:
move.castling[1] = False
if origin == 25 or origin == 28 or target == 28:
move.castling[2] = False
if origin == 25 or origin == 21 or target == 21:
move.castling[3] = False
# update halfmove clock
if self.board[target] != EM or self.board[origin] == self.player:
move.halfmove_clock = 0
else:
move.halfmove_clock += 1
# update king positions
if origin == move.white_king:
move.white_king = target
elif origin == move.black_king:
move.black_king = target
# add move information
move.move = [origin, target]
return move
def generate_moves(self):
moves = []
for origin in range(21, 99):
piece = self.player * self.board[origin]
if piece == WK:
self.generate_king_moves(origin, moves)
if piece == WQ:
self.generate_queen_moves(origin, moves)
if piece == WB:
self.generate_bishop_moves(origin, moves)
if piece == WN:
self.generate_knight_moves(origin, moves)
if piece == WR:
self.generate_rook_moves(origin, moves)
if piece == WP:
self.generate_pawn_moves(origin, moves)
legal_moves = []
for move in moves:
if move.legal():
legal_moves.append(move)
return legal_moves
def generate_king_moves(self, origin, moves):
for offset in (-11, -10, -9, -1, 1, 9, 10, 11):
target = origin + offset
if self.capturable_or_empty(target):
move = self.make_move(origin, target)
moves.append(move)
# castling
if self.player == WHITE:
if self.white_kingside_castling():
move = self.make_move(95, 97)
move.board[98] = EM
move.board[96] = WR
moves.append(move)
if self.white_queenside_castling():
move = self.make_move(95, 93)
move.board[91] = EM
move.board[94] = WR
moves.append(move)
else:
if self.black_kingside_castling():
move = self.make_move(25, 27)
move.board[28] = EM
move.board[26] = BR
moves.append(move)
if self.black_queenside_castling():
move = self.make_move(25, 23)
move.board[21] = EM
move.board[24] = BR
moves.append(move)
def generate_queen_moves(self, origin, moves):
for offset in (-11, -10, -9, -1, 1, 9, 10, 11):
target = origin + offset
while self.board[target] == EM:
move = self.make_move(origin, target)
moves.append(move)
target += offset
if self.capturable(target):
move = self.make_move(origin, target)
moves.append(move)
def generate_bishop_moves(self, origin, moves):
for offset in (-11, -9, 9, 11):
target = origin + offset
while self.board[target] == EM:
move = self.make_move(origin, target)
moves.append(move)
target += offset
if self.capturable(target):
move = self.make_move(origin, target)
moves.append(move)
def generate_knight_moves(self, origin, moves):
for offset in (-21, -19, -12, -8, 8, 12, 19, 21):
target = origin + offset
if self.capturable_or_empty(target):
move = self.make_move(origin, target)
moves.append(move)
def generate_rook_moves(self, origin, moves):
for offset in (-10, -1, 1, 10):
target = origin + offset
while self.board[target] == EM:
move = self.make_move(origin, target)
moves.append(move)
target += offset
if self.capturable(target):
move = self.make_move(origin, target)
moves.append(move)
def generate_pawn_moves(self, origin, moves):
# captures
for offset in (-11, -9):
target = origin + self.player * offset
if self.capturable(target):
# pawn promotion
if self.promotion(target):
for piece in (WQ, WB, WN, WR):
move = self.make_move(origin, target)
move.board[target] = self.player * piece
move.move.append(piece)
moves.append(move)
else:
move = self.make_move(origin, target)
moves.append(move)
# en passant captures
elif target == self.en_passant:
move = self.make_move(origin, target)
move.board[self.en_passant + self.player * 10] = EM
moves.append(move)
# non-captures
target = origin + self.player * -10
if self.board[target] == EM:
# pawn promotion
if self.promotion(target):
for piece in (WQ, WB, WN, WR):
move = self.make_move(origin, target)
move.board[target] = self.player * piece
move.move.append(piece)
moves.append(move)
else:
move = self.make_move(origin, target)
moves.append(move)
# double step
if self.double_step(origin):
en_passant = target
target += self.player * -10
if self.board[target] == EM:
move = self.make_move(origin, target)
move.en_passant = en_passant
moves.append(move)
def attacked(self, target, attacker):
if self.attacked_by_king(target, attacker):
return True
if self.attacked_by_queen(target, attacker):
return True
if self.attacked_by_bishop(target, attacker):
return True
if self.attacked_by_knight(target, attacker):
return True
if self.attacked_by_rook(target, attacker):
return True
if self.attacked_by_pawn(target, attacker):
return True
return False
def attacked_by_king(self, target, attacker):
for offset in (-11, -10, -9, -1, 1, 9, 10, 11):
origin = target - offset
if attacker * self.board[origin] == WK:
return True
return False
def attacked_by_queen(self, target, attacker):
for offset in (-11, -10, -9, -1, 1, 9, 10, 11):
origin = target - offset
while self.board[origin] == EM:
origin -= offset
if attacker * self.board[origin] == WQ:
return True
return False
def attacked_by_bishop(self, target, attacker):
for offset in (-11, -9, 9, 11):
origin = target - offset
while self.board[origin] == EM:
origin -= offset
if attacker * self.board[origin] == WB:
return True
return False
def attacked_by_knight(self, target, attacker):
for offset in (-21, -19, -12, -8, 8, 12, 19, 21):
origin = target - offset
if attacker * self.board[origin] == WN:
return True
return False
def attacked_by_rook(self, target, attacker):
for offset in (-10, -1, 1, 10):
origin = target - offset
while self.board[origin] == EM:
origin -= offset
if attacker * self.board[origin] == WR:
return True
return False
def attacked_by_pawn(self, target, attacker):
for offset in (-11, -9):
origin = target - attacker * offset
if attacker * self.board[origin] == WP:
return True
return False
def legal(self):
return not self.check(-self.player)
def check(self, defender):
if defender == WHITE:
return self.attacked(self.white_king, BLACK)
else:
return self.attacked(self.black_king, WHITE)
def white_kingside_castling(self):
return (self.castling[0] and self.board[96] == EM
and self.board[97] == EM and not self.attacked(95, BLACK)
and not self.attacked(96, BLACK))
def white_queenside_castling(self):
return (self.castling[1] and self.board[94] == EM
and self.board[93] == EM and self.board[92] == EM
and not self.attacked(95, BLACK) and not self.attacked(94, BLACK))
def black_kingside_castling(self):
return (self.castling[2] and self.board[26] == EM
and self.board[27] == EM and not self.attacked(25, WHITE)
and not self.attacked(26, WHITE))
def black_queenside_castling(self):
return (self.castling[3] and self.board[24] == EM
and self.board[23] == EM and self.board[22] == EM
and not self.attacked(25, WHITE) and not self.attacked(24, WHITE))
def endgame(self):
white_queens = 0
white_rooks = 0
white_minor_pieces = 0
black_queens = 0
black_rooks = 0
black_minor_pieces = 0
for square in range(21, 99):
piece = self.board[square]
if piece == WQ:
white_queens += 1
elif piece in (WB, WN):
white_minor_pieces += 1
elif piece == WR:
white_rooks += 1
elif piece == BK:
black_queens += 1
elif piece in (BB, BN):
black_minor_pieces += 1
elif piece == BR:
black_rooks += 1
white_endgame = (white_queens == 0 or white_queens == 1
and white_rooks == 0 and white_minor_pieces <= 1)
black_endgame = (black_queens == 0 or black_queens == 1
and black_rooks == 0 and black_minor_pieces <= 1)
return white_endgame and black_endgame
def evaluate(self):
score = 0
endgame = self.endgame()
for square in range(21, 99):
piece = self.board[square]
if piece == WK:
if endgame:
score += white_king_endgame_table[square]
else:
score += white_king_table[square]
elif piece == WQ:
score += 900 + white_queen_table[square]
elif piece == WB:
score += 330 + white_bishop_table[square]
elif piece == WN:
score += 320 + white_knight_table[square]
elif piece == WR:
score += 500 + white_rook_table[square]
elif piece == WP:
score += 100 + white_pawn_table[square]
elif piece == BK:
if endgame:
score -= black_king_endgame_table[square]
else:
score -= black_king_table[square]
elif piece == BQ:
score -= 900 + black_queen_table[square]
elif piece == BB:
score -= 330 + black_bishop_table[square]
elif piece == BN:
score -= 320 + black_knight_table[square]
elif piece == BR:
score -= 500 + black_rook_table[square]
elif piece == BP:
score -= 100 + black_pawn_table[square]
return self.player * score
def minimax(state, depth, alpha=-float("inf"), beta=float("inf")):
if depth == 0:
return state.evaluate(), None
moves = state.generate_moves()
if len(moves) == 0:
if state.check(state.player):
return -20000, None # checkmate
else:
return 0, None # stalemate
score = -float("inf")
for move in moves:
move_score = -minimax(move, depth - 1, -beta, -alpha)[0]
if move_score > score:
score = move_score
top_move = move
if score > alpha:
alpha = score
if alpha >= beta:
break
return score, top_move
def game_over(state, history):
# checkmate or stalemate
if len(state.generate_moves()) == 0:
return True
# insufficient material
if state.insufficient_material():
return True
# threefold repetition
repetitions = 1
for past_state in history:
if state == past_state:
repetitions += 1
if repetitions >= 3:
return True
# 50-move rule
if state.halfmove_clock >= 100:
return True
return False
def get_player_move(state):
moves = state.generate_moves()
while True:
notation = input("> ")
for move in moves:
if move.notation() == notation:
return move
state = State()
history = []
print(state)
while not game_over(state, history):
history.append(state)
if state.player == WHITE:
state = get_player_move(state)
else:
state = minimax(state, 6)[1]
print(state.notation())
print()
print(state)
Michis Blog 
Hinterlasse einen Kommentar