Das Zwei-Personen-Spiel Phutball

Phutball - ``Philosophen Fussball'' - ist ein Zwei-Personen-Spiel, welches von John H. Conway erfunden wurde. Das Spielfeld ist eine Matrix, welche meist 15 Felder breit und 19 Felder hoch ist, aber auch beliebige andere Ausmasse annehmen kann. Auf dem Feld befinden sich genau ein Ball sowie beliebig viele Spielsteine (``Männer''). Ziel des Spieles ist es, den Ball regelgemäss auf oder über eine Torlinie zu befördern. Diese Torlinie ist jeweils die erste beziehungsweise die letzte Zeile der Matrix.

Um dieses Ziel zu erreichen sind genau zwei Züge erlaubt: Man kann einen Spielstein auf ein freies Matrix-Feld setzen oder mit dem Ball adjazente Spielsteine überspringen. Nach einem Sprung werden die übersprungenen Steine entfernt und der Sprung kann fortgesetzt werden. Nachdem ein Spielzug ausgeführt wurde, zieht der Gegenspieler. Es wird keine Unterscheidung zwischen Spielsteinen der beiden Gegenspieler getroffen. Auch sind weitere Spielzüge wie zum Beispiel ``Passen'' nicht erlaubt.

Das Spiel Phutball gehört in die Klasse der schweren Spiele, das heisst, es ist nicht davon auszugehen, dass in absehbarer Zeit eine vollständige Theorie für das Spiel gefunden wird. Für viele Spiele ist bekannt, welche Komplexität das Problem, den Ausgang eines Spieles zu ermitteln, besitzt. Viele interessante Spiele liegen dabei in Komplexitätsklassen von PSPACE oder gar EXPTIME (Schach, Go). Ein ähnliches Resultat ist für Phutball nicht bekannt.

Demaine, Demaine und Eppstein gelang es aber zu zeigen, dass bereits das Ermitteln, ob in einer bestimmten Spielsituation ein Sieg-Sprung möglich ist, ein NP-vollständiges Problem ist. [4, Seiten 21ff]