StartTutorialsProgrammierungGrundpfeiler einer klassischen Schach-KI

Grundpfeiler einer klassischen Schach-KI

  • 9 Monaten her
  • 7Minuten

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.

Man fängt mit offensichtlichen Dingen an. Brett, Aufbau und Regeln.
Man fängt mit offensichtlichen Dingen an. Brett, Aufbau und Regeln.

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.

Gute und schlechte Züge, aber wie entscheidet das die KI?
Gute und schlechte Züge, aber wie entscheidet das die KI?

Sven Gramatke
Sven Gramatke//www.gravitationart.com/
Schreibt gelegentlich Artikel. Schwerpunkte sind Gamedesign, Programmierung (GML, PHP und JS), Retro und Berichte.
Abonnieren
Benachrichtige mich bei
guest

0 Comments
Inline Feedbacks
View all comments

NEWS

PDF

Artikel als PDF

0
Alle ByteGame-Artikel können nun bequem als PDF-Datei heruntergeladen werden. Diese Funktion wurde eingebaut, um vor allem längere Texte ausdrucken oder zumindest offline lesen zu...
Revision 2022

Revision 2022 – Eine Satellitenveranstaltung

0
Wer zu Ostern noch nichts vor hat, sollte über einen Besuch der Revision nachdenken. Diese Demoszene-Party startet am Karfreitag, den 15. April und endet...
news logo 696x400

Revorix Update 1.9

1
Revorix hat ein neues Update bekommen: Patch 1.9 Hauptfeature sind Ressourcen-Events mit der Möglichkeit wechselnde Ressourcen spenden zu können gegen noch zu enthüllende Überraschungen. Außerdem...
news logo 696x400

Godot 3.4.2 veröffentlicht

0
Kurz nach Version 3.4.1 wurde schon 3.4.2 der Spieleengine veröffentlicht. Grund für das schnelle Update war ein Fehler. Bein Rendering unter macOS konnte es...
news logo 696x400

CRYENGINE 5.7 Roadmap enthüllt

0
Nach langer Wartezeit wurde nun die Roadmap für die CRYENGINE 5.7 enthüllt. Crytek räumt dabei interne Schwierigkeiten ein. Intern sind wir bei der Entwicklung auf...
0
Would love your thoughts, please comment.x