Seit ein paar Monaten habe ich ein neues Hobby. Ich programmiere eine Schach-KI. Und wie das mit neuen, aufregenden Dingen so ist, erzählt man gerne darüber. Bei den Gesprächen, die eigentlich überwiegend Monologe sind, werden mir manchmal Fragen bezüglich der Denkweise einer solchen KI gestellt. Darauf möchte ich nun ein wenig eingehen. Wie funktioniert eine klassische Schach-KI?
Programmierer werfen zwei Begriffe in den Raum. „Alpha-Beta-Suche“ und „Minimax-Algorithmus“. Daraus besteht eine Schach-KI. Technisch gesehen ist das richtig, aber unvollständig. Diese beiden Mechanismen sorgen dafür, dass die KI Züge findet, ohne alle Möglichkeiten berechnen zu müssen. Ob gute Züge herauskommen, hängt von ganz anderen Dingen ab.
Denken
Ein Anfang muss her. Am besten startet man damit, dass die KI die Regeln kennt. Ein Brett von 64 Feldern lässt sich mit Arrays gut realisieren. Die einzelnen Figuren, Bewegungsmöglichkeiten, Schlagen, Zug zurück und dann kommen die Sonderregeln wie Rochade und der Bauer mit Doppelzug, Umwandlung und en passant. Wann ist Schach? Welche Regeln gelten hier? Matt, dreifache Stellungswiederholung, 50-Züge Regel.
Eine simple KI ist damit schon beendet. Jetzt braucht man nur noch eine kleine Funktion, die zufällig einen möglichen Zug auswählt. Ende der Geschichte.
Das Resultat ist aber furchtbar. Also weiter.
Suchen
Irgendeinen Zug zu machen ist somit nicht die Lösung. Wir brauchen eine Möglichkeit, alle durchführbaren Züge zu sammeln und zu bewerten. Hier spielen die beiden o. g. Algorithmen eine wichtige Rolle. Sie sucht sämtliche Züge, die nach den Regeln erdenklich sind. Dann werden diese bewertet. Ist ein Zug gut bzw. weniger schlecht als andere, geht die KI weiter in die Tiefe.
Bei Schach-KIs denkt man in Halbzügen. Bauer e2 auf e4 ist ein solcher. Wenn Schwarz e7-e5 zieht, ist es ein weiterer. Wie viele Halbzüge eine KI schafft, hängt von zahlreichen Faktoren ab. Prozessor, Speicher, Zugzeit, aber auch die Programmiersprache. Die meisten KIs mit einer Spielstärke von 2000 Elo schaffen im Blitzschach zwischen 7 und 14 Halbzüge. Meine KI liegt bei 9 bis 12, je nach Zeit. Die Weltspitze bei 20 bis 30. Das ist durch Optimierungen und Multithreading möglich.
Es ist aber nicht automatisch so, dass eine KI mit einer höheren Suchtiefe gegen eine mit geringerer gewinnt.
