Phutball (abréviation de football philosophique) est un jeu de société de stratégie abstrait à deux joueurs décrit dans l'ouvrage de Elwyn Berlekamp, John Horton Conway, et Richard K. Guy, « Winning Ways for your Mathematical Plays.
Phutball (abréviation de football philosophique) est un jeu de société de stratégie abstrait à deux joueurs décrit dans l'ouvrage de Elwyn Berlekamp, John Horton Conway, et Richard K. Guy, « Winning Ways for your Mathematical Plays.
Le Phutball se joue aux intersections d'une grille 19×15 avec une pierre blanche (le ballon) et autant de pierres noires (les hommes) que nécessaire. Dans cet article, les deux joueurs sont nommés Ohs (O) et Eks (X). Pour la notation du jeu, les intersections du tableau sont étiquetés de A à P (en omettant I) de gauche à droite, et de 1 à 19 de bas en haut du point de vue de Ohs. Les rangées 0 et 20 représentent "hors du tableau" au-delà des rangées 1 et 19 respectivement.
Comme les planches de phutball spécialisées sont difficiles à trouver, le jeu se joue généralement sur une planche de Go 19×19, avec une pierre blanche représentant le football et des pierres noires représentant les hommes. Dans ce cas, les deux colonnes latérales sont neutralisées de part et d'autre.
L'objectif est de marquer des buts en utilisant les hommes (les pierres noires) pour déplacer le ballon (la pierre blanche) sur ou au-dessus de la ligne de but adverse (rangées 1 ou 19). Ohs essaie de déplacer le ballon de football jusqu'aux rangées 19 ou 20, et Eks jusqu'aux rangées 1 ou 0. Au début du jeu, le ballon est placé sur le point central, à moins qu'un joueur n'accorde un handicap à l'autre, auquel cas le ballon commence plus près du but d'un joueur.
Les joueurs jouent alternativement. Un coup consiste soit à ajouter un homme à n'importe quel point vacant du plateau, soit à déplacer la balle. Il n'y a pas de différence entre les hommes joués par Ohs et ceux joués par Eks.
Le ballon de football est déplacé en effectuant une série de sauts. Chaque saut est effectué au-dessus d'un alignement d'hommes adjacents, en ligne droite horizontalement, verticalement ou en diagonale, par-dessus un ou plusieurs hommes, jusqu'au premier point vacant ; les hommes au-dessus desquels le ballon a sauté sont alors retirés du plateau (avant d'effectuer un éventuel saut ultérieur). Ce processus se répète aussi longtemps qu'il reste des hommes au-dessus desquels il est possible de sauter et tant que le joueur le désire. Le saut est facultatif : il n'est pas obligatoire de sauter. Contrairement aux dames, des séries d'hommes adjacents alignés sont sautés et supprimés en groupe.
Le schéma de droite illustre un déplacement du ballon.
Si le ballon termine le mouvement sur ou au-dessus de la ligne de but adverse, alors un but a été marqué. Si le ballon de football traverse une ligne de but, mais se retrouve ailleurs à la suite de sauts supplémentaires, le jeu continue.
Le jeu est suffisamment complexe pour que vérifier s'il y a une victoire pour l'un des joueurs (sur un plateau m×n) soit NP-complet. À partir de la position de départ, on ne sait pas si un joueur a une stratégie gagnante ou si les deux joueurs ont une stratégie de match nul, mais il existe d'autres configurations à partir desquelles les deux joueurs ont des stratégies permettant de faire nul.
Étant donné une position arbitraire sur le plateau, avec initialement une pierre blanche placée au centre, déterminer si le joueur actuel a une stratégie gagnante est de complexité PSPACE.
