Features 29.05.2017 | 12:41von GM Pepe Cuenca

Wie denkt ein Schachprogramm?

1997 besiegte Deep Blue den Weltmeister Gary Kasparov mit 3,5:2,5 und beendete damit die menschliche Vorherrschaft beim Schach | Foto: www.ajedrezalataque.com

Heutzutage kommt es nur sehr selten vor, dass ein Schachspieler ohne seinen Computer mit einem Schachprogramm zu einem Turnier anreist oder seine heimischen Trainingssitzungen bestreitet. Und auch die Zeiten sind längst vorbei, in denen Großmeister mehrere Stunden oder gar Tage aufwandten, um eine komplizierte Stellung zu analysieren und den Dingen – leider oftmals ohne Erfolg – auf den Grund zu gehen. Mittlerweile braucht die „Maschine“ nur noch Sekunden, um uns verlässlicher als Weltmeister Magnus Carlsen zu sagen, welcher Zug in einer bestimmten Stellung der beste ist.

Aber wisst ihr auch nur ansatzweise, wie ein Schachprogramm funktioniert? Wie kann es sein, dass es in Sekundenschnelle zuverlässig eine unendliche Anzahl von Varianten berechnen kann? Ich selbst hatte nach 20 Jahren in der Schachszene immer noch keine Ahnung, wie diese Monster arbeiten. Irgendwann wurde ich aber neugierig und begann, zu dem Thema zu recherchieren. In diesem Artikel versuche ich zu erklären, wie ein Schachprogramm funktioniert und wie es denkt. Zu diesem Zweck muss ich einige mathematische Konzepte und Algorithmen vorstellen.

Aber keine Sorge, ich werde nicht zu sehr in die Tiefe gehen, sodass es jeder verstehen kann!

Fangen wir an:

Die Funktionsweise: Der Minimax-Algorithmus

Schach ist ein sogenanntes “Nullsummenspiel”, was nichts anderes bedeutet, als dass es sich um ein Spiel handelt, in dem ein Spieler gewinnt, wenn der andere verliert. Das hat zur Folge, dass die Gesamtzahl der Gewinne minus die Gesamtzahl der Verluste Null ergibt, und davon stammt der Begriff „Nullsumme“.

Beispiel: In der Diagrammstellung hat Weiß gerade auf c6 genommen und einen Springer gewonnen.

Weiße Gewinne: 1 Springer
Schwarze Verluste: 1 Springer
Gewinne – Verluste = 0 


Zur Ermittlung des Zwischenstandes eines Nullsummenspiels nach einer bestimmten Anzahl von Zügen kann man den Minimax-Algorithmus verwenden, der auf Basis einer Bewertungsfunktion den besten Zug anzeigt.

Minimax ist ein toller Begriff, aber wie funktioniert der Algorithmus?

In der einzügigen Suche, in der nur ein Zug im Voraus untersucht wird, schaut der am Zug befindliche Spieler (der Max-Spieler) einfach auf die Bewertung nach jedem möglichen Zug. Der Zug mit der besten Bewertung wird ausgeführt. In der zweizügigen Suche jedoch, bei der auch der Gegner (der Min-Spieler) zieht, wird es komplizierter. Er wählt nämlich ebenfalls den Zug mit der besten Bewertung.   

Kurz gesagt, geht es darum, den besten Zug unter der Voraussetzung zu finden, dass der Gegner den für uns schlechtesten Zug findet.

Schaut euch dazu das folgende Beispiel an:


Stellt euch vor, Weiß ist am Zug und muss sich zwischen den Zügen Tc7, Sc6 oder a4 entscheiden. Nach jedem Zug kann sich Schwarz zwischen drei Antworten entscheiden. Die Zahlen darunter zeigen die Bewertung der Stellung an (ein positiver Wert begünstigt Weiß, ein negativer Schwarz). Gemäß Minimax müssen wir den schlimmsten Fall annehmen und davon ausgehen, dass Schwarz den für uns schlechtesten Zug macht. Aus diesem Grund wird in der ersten Phase des Algorithmus der schlimmste Zug berechnet, der dann in allen Fällen das Minimum ist (-8, 0, 3). Schließlich wird das Maximum berechnet (3). Der Computer zieht als Konsequenz Sc6.

Wie ihr seht, braucht es aus Sicht des Programms zwei Unterprogramme – eins für den Min-Spieler und eins für den Max-Spieler. Sie können durch eine Version des Minimax-Algorithmus namens Negamax unterstützt werden, der auf folgendem mathematischem Verhältnis basiert (die positive Bewertung der einen Seite hebt sich mit der negativen Bewertung der anderen auf):

max (a,b) = - min (-a, -b)

Wer sich ein wenig über Minimax Gedanken macht, wird schnell merken, dass der Rechenaufwand so aussieht:

0 (b^d) 

Dabei ist b der sogenannte Verzweigungsgrad und d ist die Rechentiefe. b liegt im Mittelspiel bei etwa 35 (35 legale Züge für jede Seite) und d geht bis 100, da jede Partie etwa 50 Züge dauert. Das ergibt 35^100=2,5E154, was bedeutet, dass man viele Universen bräuchte, um zum Ende des Suchbaums jeder Schachpartie zu gelangen.

Wir brauchen für dieses Problem also eine Lösung. Ein sehr häufiges Verfahren ist die Verringerung der Suchtiefe. Bei einer bestimmten Tiefe wird das Verfahren einfach abgekürzt und eine statische Bewertung der Stellung wie im Diagramm unten vorgenommen. 


Stellungsbewertung

Wie bewerten Computer eine entstandene Stellung? Das ist ein wichtiger Punkt, da eine Suchtiefe von vielen Zügen nichts bringt, wenn die Bewertung am Ende falsch ist.

Diese Bewertungen werden von sogenannten Bewertungsfunktionen vorgenommen, die etwa so aussehen:

f(x)= w1*f1(x) + w2*f2(x)+ w3*f3(x)+ ... 

Eine Bewertungsfunktion ist in der Regel eine lineare Kombination der “Charakteristika” f(x) mit einer Gewichtung zur Bestimmung der Wichtigkeit aller Charakteristika. Die grundlegendste Bewertungs-funktion betrifft das Abzählen der Figuren auf dem Brett: 

        f1(x)= Anzahl weißer Damen - Anzahl schwarzer Damen          

f2(x)= Anzahl weißer Türme - Anzahl schwarzer Türme

f3(x)= Anzahl weißer Läufer - Anzahl schwarzer Läufer

f4(x)= Anzahl weißer Springer - Anzahl schwarzer Springer

f5(x)= Anzahl weißer Bauern - Anzahl schwarzer Bauern

und die Gewichtungen sind die Werte, die wir bereits kennen:   

w1=9

w2=5

w3=3

w4=3

w5=1

Da diese simple Bewertungsfunktion zu Fehlern führt, reicht sie dem Programm nicht aus. Schaut euch als Beispiel das folgende Diagramm an:


Weiß am Zug

Das Ergebnis der Bewertungsfunktion sähe so aus:

f(x)= 9*(1-0) + 5*(0-2) + 3*(1-1) + 3*(0-2) + 1*(1-4) = -10 

sprich Schwarz hätte entscheidenden Vorteil. Genau das Gegenteil ist aber wahr, denn nach Dh6 kann Schwarz aufgeben. Aus diesem Grund verwenden Schachprogramme ein umfangreicheres Bewertungssystem, in dem verschiedene Techniken angewandt werden:  

‌1. Bewertung anhand der Partiephase 

Es ist sinnvoll, die Gewichtung der Funktionen der konkreten Partiephase anzupassen. Im Mittelspiel etwa möchte man, dass der König sich weit weg vom Zentrum befindet. Dagegen ist er im Endspiel eine wichtige Figur und steht im Zentrum gut. Zur Beurteilung der Partiephase können Schachprogramme zum Beispiel die Anzahl der verbliebenen Figuren auf dem Brett heranziehen. 

2. Läuferpaar

Für das Läuferpaar kann ein Bonus vergeben werden (und einen zusätzlichen, wenn die Läufer viele Felder beherrschen).

3. Figuren und Felder

Es gibt einfache Methoden, um bestimmten Figuren auf bestimmten Feldern zusätzliche Werte zuzuschreiben. Zum Beispiel bekommt ein Bauer in der Eröffnung einen kleinen Bonus, wenn er ein Zentrumsfeld besetzt. 

4. Königssicherheit

Dies ist sehr wichtig. Man kann zum Beispiel die Anzahl der Bauern, die den König beschützen, heranziehen, oder einen Turm, der in der Nähe steht.

5. Flexibilität

Normal bevorzugt man Stellungen, in denen man mehrere Möglichkeiten hat, etwa mit offenen Diagonalen für die Läufer. Dies könnte man zum Beispiel bewerten, indem man in einer bestimmten Stellung die Anzahl der möglichen Züge als Flexibilitätsfaktor ansetzt.

6. Bauernstruktur

Doppelbauern haben genauso Schwächen wie isolierte Bauern im Endspiel, die leicht angegriffen werden können. 

7. Türme auf offenen Linien

Dies ist bekanntermaßen ein Plus, wie auch ein Turm auf der siebten Reihe. Man kann viele Faktoren berücksichtigen, aber diese sieben vermitteln eine Vorstellung von der umfangreicheren Bewertung. 

Der Horizonteffekt

Kommen wir nun zum Horizonteffekt, der durch die Begrenzung der Suchtiefe zustande kommt. Stellt euch vor, dass das Programm mit niedriger Suchtiefe arbeitet und einen gefangenen Turm erkennt. Dann kann es sein, dass das Programm eine Figur opfert, um den drohenden Verlust des Turmes „hinter den Horizont“ hinauszuzögern. Als Folge verliert es zwei Figuren, da der Turmverlust ohnehin nicht zu verhindern war.  


Zur Illustration des Horizonteffekts

Nehmen wir an, dass im vorliegenden Beispiel Weiß am Zug ist und das Programm Suchtiefe 2 hat. Der Turm auf a5 ist verloren, aber das Programm spielt Lxf7, um den Turmverlust innerhalb des Horizonts zu vermeiden. Das Resultat ist verheerend, da Weiß nach Txf7 beide Figuren verliert.

Die Lösung dieses Problems ist die sogenannte „Ruhesuche“ und besteht daraus, die Analysetiefe nicht einfach auf eine simple Zahl zu beschränken, sondern Varianten so lange zu analysieren, bis „Ruhe“ in die Stellung einkehrt. Was ist mit einer ruhigen Stellung gemeint? Eine zum Beispiel, in der nichts geschlagen werden kann.

Der Alpha-Beta-Suche

Die Alpha-Beta-Suche ist eine optimierte Variante des Minimax-Algorithmus, der 1955 von John McCarthy auf einer Konferenz vorgestellt wurde. Mit ihm werden die Möglichkeiten in einem Suchbaum erheblich reduziert und mit dem Verfahren der Verästelung und Begrenzung analysiert. Bei der Analyse verschiedener Antworten auf einen Zug reicht es dabei aus, wenn man eine Widerlegung findet. Vielleicht gibt es noch stärkere Widerlegungen, aber diese müssen nicht analysiert werden, da eine schon reicht, um den Zug zu verwerfen. Das klingt einfach, ist bei tiefer Analyse aber ziemlich komplex, daher sollten wir zum Verständnis wieder ein einfaches Beispiel heranziehen.

Stellt euch vor, Weiß ist am Zug und die Suchtiefe beträgt 2, sprich wir berücksichtigen alle Züge für Weiß und alle möglichen schwarzen Antworten darauf. Zunächst wählen wir einen Zug für Weiß aus, den wir als „Zug 1“ bezeichnen. Dann berücksichtigen wir alle schwarzen Antwortmöglichkeiten und stellen anhand unserer Analyse fest, dass die Stellung ausgeglichen ist, wenn Weiß sich für „Zug 1“ entscheidet.

Nach dieser ersten Analyse untersuchen wir einen weiteren Zug für Weiß – „Zug 2“. Stellt euch vor, dass der erste schwarze Gegenzug einen Läufer gewinnt! Wir können dann ohne weitere Untersuchung sagen, dass „Zug 2“ widerlegt ist. Vielleicht ist es sogar noch schlimmer, und Schwarz gewinnt die Dame oder kann mattsetzen, aber der Läuferverlust reicht schon aus, um „Zug 2“ zu verwerfen, und wir sparen viel Rechenzeit. Kurz gesagt, liefert die Analyse von „Zug 1“ eine Untergrenze, denn wir wissen, dass er uns eine ausgeglichene Stellung beschert, weshalb wir alle Züge verwerfen können, nach denen Weiß klar schlechter steht.

Natürlich ist bei einer Suchtiefe von 3 oder mehr die Komplexität deutlich größer, weil beide Spieler nun aus Möglichkeiten auswählen können, die den Suchbaum beeinflussen. Die Strategie ist dann, mit Ober- und Untergrenzen zu arbeiten, die als Alpha und Betas bezeichnet werden. Die Funktion der Untergrenze ist, Züge auszusortieren, die zu schlecht sind. Die Obergrenze wird eingeführt, da der andere Spieler eine zu gute Fortsetzung nicht zulassen und stattdessen aus der Fülle der Möglichkeiten eine andere wählen würde. Die Obergrenze des einen Spielers ist die Untergrenze des anderen.  

‌Reduzierung des Rechenaufwands:

Die Ersparnis durch diesen Algorithmus ist erheblich. Nehmen wir an, ein Minimax-Suchbaum hat x Knoten. Die Knoten der Alpha-Beta-Suche können die Quadratwurzel von x sein. Wie viele Knoten können wir einsparen? Nun, das hängt davon ab, wie gut aufgebaut der Suchbaum ist. Sucht ihr immer erst den besten Zug, könnt ihr viele Knoten eliminieren. Natürlich wisst ihr nicht immer, was der beste Zug ist, oder müsst gar nicht danach suchen

Umgekehrt werden keinerlei Knoten eingespart, wenn man die schlechtesten Züge vor den besseren analysiert. Aus diesem Grund ist eine gute Suchreihenfolge sehr wichtig und einer der Hauptbestandteile eines guten Schachprogramms. Levin schrieb bereits 1961: "Unter der Annahme, dass eine Konstante (b) sich bei jedem besuchten Knotenpunkt verändert - bei einer Rechentiefe von n - ist die maximale Anzahl der Nebenrechnungen in Alpha-Beta gleichzusetzen mit dem Minimax, b^n. Berücksichtigen wir immer den besten Zug zuerst, sieht das so aus: 

  b ^ aufrunden(n/2) + b ^ abrunden(n/2) -1

wobei aufrunden() und abrunden() arithmetische Funktionen sind, die aus einer berechneten Zahl die nächsthöhere oder nächsttiefere ganzzahlige Zahl machen. Die folgende Tabelle zeigt die minimale Anzahl von Nebenrechnungen unter der Annahme b = 40: 

            Tiefe                     schlechtester Fall               bester Fall

       0                                 1                             1

       1                                40                           40

       2                              1,600                        79

          3                              64,000                    1,639

          4                           2,560,000                  3,199

      ...                              ...                             ...

Schauen wir uns nun noch weitere Techniken an, mit denen der Rechenaufwand reduziert wird:

Null-Zug-Suche

Zur Erklärung dieser Technik verwenden wir eine Analogie aus dem Boxen. Wenn wir unserem Gegner einen „Extraschlag“ oder –zug geben und er kann uns nicht ausknocken, sieht es gut für uns aus, wenn wir am Zug sind. Diese Technik wird so angewandt: Bevor man in einer Stellung eine komplette Suche durchführt, führt man eine Suche mit niedrigerer Suchtiefe durch, in der der Gegner am Zug ist.

Homer Simpson ließ Drederick Tatum permanent zuschlagen, ging aber nicht K.O. Beim Schach solltet ihr das nicht versuchen! 

Ist das “Ergebnis” oder die Bewertung besser als ein bestimmter “Alpha-Wert”, muss man den Teilbaum nicht weiter untersuchen (da es suboptimale Züge gegeben haben muss, um an diesen Punkt zu gelangen, kann er ausgeschlossen werden). Das spart Zeit, da die Tiefe verringert wird. Sicher habt ihr erkannt, dass diese Technik nicht in Zugzwangstellungen funktioniert! Wir ihr wisst, verliert in solchen Stellungen jeder Zug und man wünschte sich, der Gegner wäre am Zug. Damit ist diese Technik in diesen Stellung nicht anwendbar.

Reduzierung der Suchtiefe bei Zügen, die wenig versprechen

Normal sind die Züge bei der Suche von besser nach schlechter sortiert. Es ist daher sinnvoll, die obersten Züge in der Liste mit maximaler Suchtiefe für jeden Knoten zu untersuchen und die untersten mit geringerer Suchtiefe. Auf diese Weise wird Rechenzeit gespart und der Verzweigungsgrad kann auf 2 reduziert werden.

Schauen wir uns zum Abschluss noch an, wie ein Schachbrett in all diesen Algorithmen „dargestellt“ wird.

Darstellung des Schachbretts: Bitboards

Das erste Problem, auf das die Entwickler von Schachprogrammen stießen, war die Frage, wie man das Schachbrett und die Figuren so einfach und ökonomisch wie möglich darstellen konnte. Zu Beginn war die Kapazität für die Hardware sehr begrenzt, daher war eine effiziente Darstellung sehr wichtig.

Bitboards waren ein großer Fortschritt in der Darstellung des Bretts, der Figuren und der Züge. Mit ihnen wurde das Brett im Programm „figurenbezogen“ dargestellt. Sie bestehen aus 64 Elementen, mit einem Bit pro Feld.

Neben der Darstellung des Bretts mit der Position der Figuren sind einige weitere Informationen nötig, um eine konkrete Schachstellung zu vervollständigen, wie die Frage, wer am Zug ist, ob die Rochade noch möglich ist, oder ob en passant geschlagen werden kann. In diesem Artikel nennen wir nur die Strukturen, mit denen die Figuren und das Brett dargestellt werden.

Eine „figurenbezogene“ Darstellung ist eine Liste, eine Abfolge oder Zusammenstellung aller Figuren, die noch auf dem Brett stehen, sowie zusätzliche Informationen, welche Felder sie besetzen. 

12 Bitboards reichen aus, um sämtliche Schachstellungen darstellen zu können | Quelle: chessprogramming wiki

Das war unsere kleine Reise in die Welt der Schachcomputer! Mit den folgenden Links könnt ihr noch tiefer in dieses Thema eintauchen.

Weitere Links:


GM Pepe Cuenca

Pepe Cuenca ist ein spanischer Schachgroßmeister. Er studierte an der Universität von Granada Bauingenieurwesen, hat einen Mastertitel in Mathematischer Modellierung und promovierte an der Universität Hamburg in Angewandter Mathematik.




Sortieren nach Datum (absteigend) Datum (absteigend) Datum (aufsteigend) meiste Likes Benachrichtigung bei neuen Kommentaren

Kommentare 4

Guest
Guest 7862635254
 
chess24 beitreten
  • Kostenlos, Schnell & Einfach

  • Sei der Erste, der kommentiert!

Registrieren
oder

registriere dich und leg los!

Ich bin älter als 16 Jahre.

Mit einem Klick auf 'Registrieren' stimmst du unseren Nutzungsbedingungen zu und bestätigst, dass du unsere Datenschutzrichtlinie und den Abschnitt über die Verwendung von Cookies gelesen hast.

Lost your password? We'll send you a link to reset it!

Nach der Übermittlung deiner E-Mail-Adresse erhältst du von uns eine E-Mail mit einem Link zum Zurücksetzen des Passworts. Wenn du dann weiterhin nicht auf deinen Account zugreifen kannst, melde dich bitte beim Kundendienst.

Welche Funktionen möchtest Du aktivieren?

Wir respektieren Deine Privatsphäre und Datenschutzbestimmungen. Einige Komponenten erfordern das Speichern von personenbezogen Daten in Cookies oder dem lokalen Speicher.

Show Options

Hide Options