|
Philipp Hoffmann Mentor: Prof. Dr. Javier Esparza
Zur Zeit beschäftige ich mich mit Infinite Games. Dies sind Spiele, bei denen (bis zu) unendlich viele Züge über den Ausgang des Spiels entscheiden. Hier versucht man nun, für bestimmte Arten von Spielen wie zum Beispiel Parity Games Strategien zu finden oder zu beweisen, dass solche existieren und bestimmte Eigenschaften aufweisen. Parity Games sind Spiele, welche auf gerichteten Graphen gespielt werden, wobei jeder Knoten mit einer Farbe gefärbt ist - üblicherweise dargestellt durch eine von endlich vielen natürlichen Zahlen. Ein endliches Spiel gewinnt derjenige, der den letzten Zug machen kann (dieser endet dann in einer Sackgasse). Ein unendliches Spiel wird durch die Menge der unendlich oft besuchten Knoten bzw. die Menge der Farben dieser Knoten entschieden. Spieler 0 gewinnt typischerweise, wenn die kleinste der unendlich oft besuchten Farben einen geraden Wert hat (daher der Name Parity Game). Diese Spiele weisen die Besonderheit auf, dass nicht nur der Spielausgang bei perfektem Spiel vorherbestimmt ist, sondern die Strategie sogar memoryless - also nur aufgrund der aktuellen Position und ohne Kenntnis des bisherigen Spielverlaufs - festgelegt werden kann. Eine wichtige, noch offene Frage in diesem Gebiet ist die, ob man eine solche Strategie in polynomieller Zeit finden kann. |
|
TopMath
