View source for Phutball

{{Short description|Two-person board game}}
{{redirect|Philosopher's Football|the Monty Python sketch|The Philosophers' Football Match}}
[[File:phutball opening.svg|thumb|A game of phutball after five men have been placed (the ball has yet to move)]]

'''Phutball''' (short for '''Philosopher's Football''') is a two-player [[Abstract strategy game|abstract strategy]] [[board game]] described in [[Elwyn Berlekamp]], [[John Horton Conway]], and [[Richard K. Guy]]'s ''[[Winning Ways for your Mathematical Plays]]''.<ref name=newrules>{{cite book
 |last=Schmittberger
 |first=R. Wayne
 |title=New Rules for Classic Games
 |publisher=John Wiley & Sons Inc
 |year=1992
 |pages=[https://archive.org/details/newrulesforclass00rway/page/112 112–14]
 |isbn=978-0471536215
 |url-access=registration
 |url=https://archive.org/details/newrulesforclass00rway/page/112
 }}</ref>

== Rules ==
Phutball is played on the intersections of a 19×15 grid using one white stone and as many black stones as needed.<ref name=newrules/>
In this article the two players are named Ohs (O) and Eks (X).
The board is labeled A through P (omitting I) from left to right and 1 to 19 from bottom to top from Ohs' perspective. 
Rows 0 and 20 represent "off the board" beyond rows 1 and 19 respectively.

As specialized phutball boards are hard to come by, the game is usually played on a 19×19 [[Go (board game)|Go]] board, with a white stone representing the football and black stones representing the men.

The objective is to score goals by using the men (the black stones) to move the football (the white stone) onto or over the opponent's goal line (rows 1 or 19). Ohs tries to move the football to rows 19 or 20 and Eks to rows 1 or 0. 
At the start of the game the football is placed on the central point,<ref name=newrules/> unless one player gives the other a handicap, in which case the ball starts nearer one player's goal.

Players alternate making moves. 
A move is either to add a man to any vacant point on the board or to move the ball. 
There is no difference between men played by Ohs and those played by Eks.<ref name=newrules/>

[[File:phutball jump.svg|thumb|A jump]]

The football is moved by a series of jumps over adjacent men. 
Each jump is to the first vacant point in a straight line horizontally, vertically, or diagonally over one or more men. 
The jumped men are then removed from the board (before any subsequent jump occurs). 
This process repeats for as long as there remain men available to be jumped and the player desires. Jumping is optional: there is no requirement to jump. 
In contrast to [[checkers]], multiple men in a row are jumped and removed as a group.<ref name=newrules/>

The diagram on the right illustrates a single move consisting of a series of jumps.  
*Ohs moves the football from K6–G9.
*The men on J7 and H8 are removed.
*Ohs moves the football from G9–G11.
*The man on G10 is removed.
*Ohs moves the football from G11–J11.
*The man on H11 is removed.
*Note that the move consisting of K6–G9–J9–G7 would not be legal, as that would jump the man on H8 twice.

If the football ends the move on or over the opponent's goal line then a goal has been scored. 
If the football passes through a goal line, but ends up elsewhere due to further jumps, the game continues.

== Strategy ==
*Carefully set-up sequences of jumps can be "spoiled" by extending them at critical moments.
*A jump to the left or right edge can be blocked by leaving no vacant points.
*When jumping, it is usually bad to leave an easily used return path for the opponent to "undo" one's progress.

== Computational complexity ==
The game is sufficiently complex that checking whether there is a win in one (on an m×n board) is [[NP-complete]].<ref>{{cite conference
  | author = Demaine, Erik D.
  | author-link = Erik Demaine
 |author2=Demaine, Martin L.
 |author2-link=Martin Demaine
 |author3=Eppstein, David
 |author3-link=David Eppstein
 | title = Phutball endgames are hard
  | book-title = More Games of No Chance
  | pages = 351–360
  | publisher = MSRI Publications 42, Cambridge Univ. Press
  | date = 2002
  | url = http://www.msri.org/publications/books/Book42/files/dephut.pdf}}</ref> From the starting position, it is not known whether any player has a winning strategy or both players have a drawing strategy, but there exist other configurations from which both players have drawing strategies.<ref>{{cite conference
  | author = Sarkar, Sucharit
  | author-link = Sucharit Sarkar
  | title = Phutball draws
  | book-title = Games of No Chance 5
  | pages = 439–446
  | publisher = MSRI Publications 70, Cambridge Univ. Press
  | date = 2019
  | url = https://www.cambridge.org/us/academic/subjects/mathematics/discrete-mathematics-information-theory-and-coding/games-no-chance-5
  | arxiv = 2504.06451}}</ref>
<!--How about including some sample games and a description of strategy?-->

Given an arbitrary board position, with initially a white stone placed in the center, determining whether the current player has a winning strategy is [[PSPACE]]-hard.<ref>{{cite journal|last1=Dereniowski|first1=Dariusz|title=Phutball is PSPACE-hard|journal=Theoretical Computer Science|date=2010|volume=411|issue=44–46|pages=3971–3978|doi=10.1016/j.tcs.2010.08.019|ref=pspace|arxiv=0804.1777|s2cid=14975402}}</ref>

==References==
{{Reflist}}

==Further reading==
* {{cite conference
  | author = Grossman, J.P.
  |author2=Nowakowski, Richard J.
  | title = One-Dimensional Phutball
  | book-title = More Games of No Chance
  | pages = 361–367
  | publisher = MSRI Publications 42, Cambridge Univ. Press
  | date = 2002
  | url = http://www.msri.org/publications/books/Book42/files/grossman.pdf}}

[[Category:Abstract strategy games]]
[[Category:Mathematical games]]
[[Category:John Horton Conway]]
[[Category:Games played on Go boards]]