StartTutorialsProgrammierungGrundpfeiler einer klassischen Schach-KI

Grundpfeiler einer klassischen Schach-KI

  • 2 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//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

ByteGame News

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...
ByteGame News

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...
ByteGame News

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...
GameJam-Logo von ManaSoup-GameJam (irgendwas mit Pizza)

Tolle Projekte in der Manasoup-Gamejam

0
Die Manasoup-GameJam ist zu Ende und es gibt viele tolle, unglaubliche Spiele, die man kostenfrei runterladen und spielen kann. Herzlichen Glückwunsch an die Gewinner -...
ByteGame News

Update bei Revorix

0
Beim Scifi-Browsergame Revorix wird geschraubt. Das Entwicklerteam hat ein Update eingespielt, welches vor allem eines zeigt: das Revorix-Universum lebt! Zitat eines Spielers / Venad Rheingold...
0
Would love your thoughts, please comment.x
()
x