4 Gewinnt Implementierungen
Tags: algorithmus, KI, OpenSource
Kategorie Software Engineering | Keine Kommentare »
Für ein kleines Projekt bin ich auf der Suche nach Implementierungen des Spiels „4 Gewinnt“. Erste Erkenntnis: Suche nach „4 gewinnt“ führt zu einem allseits bekannten HipHop Album :-)
Das Spiel heißt auf Englisch „Connect 4“ und damit gibt es dann auch ein paar sinnvolle Suchergebnisse. Der englische Wikipedia Artikel zu Connect 4 ist interessant, da dort die typischen Algorithmen zur Lösung erwähnt werden.
Benutzt man nicht eine Zugdatenbank, versucht man das Spiel mittels Minimax-Algorithmus zu lösen. Statt alle möglichen Zugkombinationen bis zum Spielende oder bis zur maximalen Suchtiefe durchzuprobieren, kann auch eine Alpha-Beta-Suche verwendet werden, um den Suchraum einzuschränken.
Im Netz habe ich eine Implementierung des Minimax Algorithmus gefunden. Bei einer Schwierigkeit von 3 (ich nehme an, dies ist die Suchtiefe), gewinne ich immer gegen das Programm. Bei Schwierigkeit 4 und höher rechnet mein PC zu lange. Das Programm ist in C und Französisch geschrieben :-)
Wenn ich der Selbstbeschreibung trauen darf, hat ein andere Autor die Alpha-Beta-Suche implementiert. Leider habe ich es nicht geschafft, sein Node.js Programm zum Laufen zu bekommen, aber zumindest die Implementierung sieht nachvollziehbar aus.
Bleibt also an dieser Stelle nur, selbst eine Variante der Alpha-Beta-Suche zu schreiben, natürlich im hippen Rust und nicht C :-)