Phutball (short for Philosopher's Football) is a two-player

abstract strategy Abstract strategy games admit a number of definitions which distinguish these from strategy games in general, mostly involving no or minimal narrative theme, outcomes determined only by player choice (with no randomness), and perfect information. ...

board game Board games are tabletop games that typically use . These pieces are moved or placed on a pre-marked board (playing surface) and often include elements of table, card, role-playing, and miniatures games as well. Many board games feature a comp ...

described in

Elwyn Berlekamp Elwyn Ralph Berlekamp (September 6, 1940 – April 9, 2019) was a professor of mathematics and computer science at the University of California, Berkeley.Contributors, ''IEEE Transactions on Information Theory'' 42, #3 (May 1996), p. 1048. DO10.1 ...

John Horton Conway John Horton Conway (26 December 1937 – 11 April 2020) was an English mathematician active in the theory of finite groups, knot theory, number theory, combinatorial game theory and coding theory. He also made contributions to many branches ...

, and

Richard K. Guy Richard Kenneth Guy (30 September 1916 – 9 March 2020) was a British mathematician. He was a professor in the Department of Mathematics at the University of Calgary. He is known for his work in number theory, geometry, recreational mathemati ...

's '' Winning Ways for your Mathematical Plays''.

Rules

Phutball is played on the intersections of a 19×15 grid using one white stone and as many black stones as needed. 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, 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, 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. phutball 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 Checkers (American English), also known as draughts (; British English), is a group of strategy board games for two players which involve diagonal moves of uniform game pieces and mandatory captures by jumping over opponent pieces. Checkers ...

, multiple men in a row are jumped and removed as a group. The diagram on the right illustrates a jump. *Ohs moves the football from K6–G9–G11–J11. *The men on J7, H8, G10, and H11 are removed. *The jump from 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 In computational complexity theory, a problem is NP-complete when: # it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by tryi ...

. 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. 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 In computational complexity theory, PSPACE is the set of all decision problems that can be solved by a Turing machine using a polynomial amount of space. Formal definition If we denote by SPACE(''t''(''n'')), the set of all problems that can b ...

-hard.

Rules

Strategy

Computational complexity

References

Further reading