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 :-)

Dieser Beitrag wurde am 09.09.2020 um 22:09in der Kategorie Software Engineering veröffentlicht. Kommentare können per RSS 2.0 Feed abonniert werden. Sie können ein Kommentar schreiben oder einen Trackback von ihrer Seite hinterlassen.