Editing Phutball (section)

== 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>