Suchoptimierung und Evaluation bei Zwei-Personen-Nullsummen-Spielen am Beispiel von Mühle

Allgemein

 

Das Spiel Mühle ist eines der ältesten und beliebtesten Brettspiele für zwei Personen. Aus spieletheoretischer Sicht handelt es sich um ein Zug-basiertes, deterministisches Null-Summen-Spiel.

Da das Mühlespiel bereits als Unentschieden bei perfektem Spiel beider Kontrahenten gelöst wurde, geriet es als informatisches Problem in den Hintergrund. Da allerdings eine für perfektes Spiel benötigte Datenbank sehr groß ist, wurde in dieser Arbeit ein Mühleprogramm entwickelt, das durch gute Evaluation der Spielsituation und effiziente Suche im Spielbaum auch ohne vollständige Datenbank ein hohes Spielniveau erreicht.

Die dem Programm zu Grunde liegenden Algorithmen, ihre möglichen Verbesserungen sowie deren Auswirkungen auf die praktische Spielstärke sind in der Ausarbeitung zusammengefasst.

Eine vereinfachte Version des Mühleprogramms ist direkt als Applet online spielbar, das vollständige Programm ist im Downloadbereich verfügbar.

Letzte Aktualisierung: 04.03.2005 - Bastian Späth