Mühle

Suchoptimierung und Evaluation

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

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.

Ausarbeitung

F. Lemmerich / B. Späth: Evaluation und effiziente Suche in einem 2-Personen-Nullsummen-Spiel am Beispiel von Mühle, Universität Würzburg, 2005. [PDF]

Kontakt

• Bastian Späth            bastian.spaeth@gmx.de
• Florian Lemmerich      flemmerich@gmx.de

Impressum

Diese Internetseite wurde im Rahmen einer Diplomarbeit am Lehrstuhl für Künstliche Intelligenz und Angewandte Informatik der Universität Würzburg erstellt. Verantwortlich für den Inhalt ist der Lehrstuhl.