¶ Steckbrief
Der Name Phutball leitet sich von philosophers football ab.
- Spielart: Brettspiel für zwei Personen
- Erfinder: John H. Conway [1]
- Durchschnittliche Anzahl von Zügen pro Zug: 120 [2]
¶ Regeln
Lorem ipsum dolor sit amet, consetetur sadipscing elitr, sed diam nonumy eirmod tempor invidunt ut labore et dolore magna aliquyam erat, sed diam voluptua. At vero eos et accusam et justo duo dolores et ea rebum. Stet clita kasd gubergren, no sea takimata sanctus est Lorem ipsum dolor sit amet. Lorem ipsum dolor sit amet, consetetur sadipscing elitr, sed diam nonumy eirmod tempor invidunt ut labore et dolore magna aliquyam erat, sed diam voluptua. At vero eos et accusam et justo duo dolores et ea rebum. Stet clita kasd gubergren, no sea takimata sanctus est Lorem ipsum dolor sit amet. Lorem ipsum dolor sit amet, consetetur sadipscing elitr, sed diam nonumy eirmod tempor invidunt ut labore et dolore magna aliquyam erat, sed diam voluptua. At vero eos et accusam et justo duo dolores et ea rebum. Stet clita kasd gubergren, no sea takimata sanctus est Lorem ipsum dolor sit amet.
Duis autem vel eum iriure dolor in hendrerit in vulputate velit esse molestie consequat, vel illum dolore eu feugiat nulla facilisis at vero eros et accumsan et iusto odio dignissim qui blandit praesent luptatum zzril delenit augue duis dolore te feugait nulla facilisi. Lorem ipsum dolor sit amet, consectetuer adipiscing elit, sed diam nonummy nibh euismod tincidunt ut laoreet dolore magna aliquam erat volutpat.
¶ Komplexitätstheoretische Betrachtung
Die Speicherkomplexität des Spiels Phutball is PSPACE-hard [3].
Bezüglich der Laufzeitkomplexität konnten Erik Demaine et al. zeigen, dass schon die Frage, ob es in einer gegebenen Spielstellung einen Zug gibt, der direkt zum Sieg führt, NP-vollständig ist [4].
¶ Algorithmische Ansätze
Aufgrund der sehr hohen durchschnittlichen Anzahl von Zugmöglichkeiten pro Zug, sind einfache Suchalgorithmen wie die Alpha-Beta Suche bei Phutball nicht erfolgreich einzusetzen.
¶ Grundalgorithmen
Die folgenden Algorithmen liefern die Grundlage für den Gradual Proof Search Algorithmus [2:1], der einen guten Ansatz für das Spiel Phutball darstellt:
¶ Gradual Abstract Proof Search
...
¶ Anpassungen auf das konkrete Spiel
...
¶ Vermischtes
- Dies ist nicht Phutball: Philosophy football by Monty Python
¶ Implementationen
- Implementation als Browser Spiel von Ravi Charan auf http://philosophers.football, source code bei github
- Implementation von Alexander Taylor bei github
- Multiplayer online spielen bei IG Game Center
¶ Spielbeschreibungen
- Bei Board Game Geek: https://boardgamegeek.com/boardgame/25433/phutball
¶ Referenzen
Berlekamp ER, Conway JH, Guy RK. Winning ways for your mathematical plays, 2nd edition, volumes 1-4. AK Peters/CRC Press; 2004 Mar 30. (Vol. 1: ISBN 1-56881-130-6; vol. 2: ISBN 1-56881-142-X; vol. 3: ISBN 1-56881-143-8; vol. 4: ISBN 1-56881-144-6.); 1st edition 1982; Phutball is introduced in vol. 2 ↩︎
Cazenave T. Gradual abstract proof search. ICGA journal. 2002 Jan 1;25(1):3-15. url | pdf ↩︎ ↩︎
Dereniowski D. Phutball is PSPACE-hard. Theoretical computer science. 2010 Oct 25;411(44-46):3971-8. pdf ↩︎
Demaine ED, Demaine ML, Eppstein D. Phutball endgames are hard. More Games of No Chance. 2002 Nov 25;42:351. arXiv ↩︎