Universität Bremen - Projekttag 2007
Spiele sind schon immer eine beliebte Beschäftigung für groß und klein, und auch in der Mathematik und Informatik haben sich bereits viele Wissenschaftler Gedanken darüber macht, wie erfolgsversprechende Lösungsstrategien aussehen müssen. Durch die enorm gestiegene Leistung moderner Rechenanlagen ist es möglich, dass Rechner wie Deep Thought, Deep Blue und Deep Fritz beispielsweise beim Schachspiel einen sehr guten Spieler schlagen, weil sie viele Spielzüge im Voraus berechnen können. Im Bereich des computergestützten Schaltkreisentwurfs existieren Datenstrukturen und Algorithmen, die auf sehr großen Lösungsräumen arbeiten können. Da auch bei den ausgewählten Strategiespielen die Suchräume enorm groß sind, sollen die im Schaltkreisentwurf bewährten Methoden in diesem Kontext untersucht werden.
Ziel des Projektes ist es:Mehrere 1-, 2- und Mehr-Personen-Strategiespiele zu analysieren, und Strategien zum Gewinnen bzw. schnellen Lösen zu finden.
Dazu werden zunächst die zu betrachtenden Spiele in unterschiedliche Kategorien eingeteilt:
Bei Spielen, wie beispielsweise einem Jigsaw-Puzzle geht es darum, eine korrekte Puzzlelösung zu finden. Bei Spielen dieser Kategorie kann einerseits untersucht werden, wie eine schnelle Lösungsstrategie aussieht und andererseits, wie schwierig die betrachtete Probleminstanz ist.
Bei einer anderen Kategorie, den Mehr-Personen-Spielen, geht es ebenfalls darum, ob es eine optimale Strategie zum Gewinnen gibt und falls ja, wie sieht diese aus?
Bei Spielen wie den sogenannten NIM-Spielen, bei denen es um das abwechselnde Entfernen von Streichhölzern geht,
oder bei Legespielen wie Kalaha (wahrscheinlich das älteste Spiel der Welt!) gewinnt bei perfektem Spiel
nachweislich immer derjenige, der das Spiel begonnen hat. Für andere Spiele gilt dies bereits nicht mehr (z.B. TicTacToe).
Dagegen ist bei vielen komplexeren Spielen die Frage, ob eine solche Gewinnstrategie existiert, bislang noch
offen.