Universit�t Bremen - Projekttag 2007

EXPLAYN Logo

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.

EXplayN Homepage