Phutball
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[1].
Les règles[modifier | modifier le code]
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[1]. 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[1], à 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[1].
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[1].
Le schéma de droite illustre un déplacement du ballon.
- Ohs déplace le ballon de K6-G9-G11-J11, ce qui fait trois sauts.
- Les hommes sur J7, H8, G10 et H11, sur lesquels le ballon est passé, sont ensuite retirés.
- Le déplacement de K6-G9-J9-G7 ne serait pas légal, car cela ferait sauter l'homme sur H8 deux fois. En application stricte de la règle, le premier saut K6-G9 a supprimé l'homme en H8, qui ne peut donc pas servir à une troisième étape.
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.
Stratégie[modifier | modifier le code]
- Des séquences de sauts soigneusement établies peuvent être « gâchées » en les prolongeant à des moments critiques.
- Un saut vers le bord gauche ou droit peut être bloqué en ne laissant aucun point vacant.
- Lors d'un saut, il est généralement mauvais de laisser un chemin de retour facilement utilisable à l'adversaire pour « annuler » sa progression.
Complexité de calcul[modifier | modifier le code]
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[2]. À 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[3].
É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[4].
Notes et références[modifier | modifier le code]
- R. Wayne Schmittberger, New Rules for Classic Games, John Wiley & Sons Inc, (ISBN 978-0471536215, lire en ligne), p. 112–14
- Demaine, Erik D., Demaine, Martin L. et Eppstein, David « Phutball endgames are hard » () (lire en ligne)
— « (ibid.) », dans More Games of No Chance, MSRI Publications 42, Cambridge Univ. Press, p. 351–360 - Sarkar, Sucharit « Phutball draws » () (lire en ligne)
— « (ibid.) », dans Games of No Chance 5, MSRI Publications 70, Cambridge Univ. Press, p. 439–446 - Dereniowski, « Phutball is PSPACE-hard », Theoretical Computer Science, vol. 411, nos 44–46, , p. 3971–3978 (DOI 10.1016/j.tcs.2010.08.019, arXiv 0804.1777)
Bibliographie[modifier | modifier le code]
- Grossman, J.P. et Nowakowski, Richard J. « One-Dimensional Phutball » () (lire en ligne)
— « (ibid.) », dans More Games of No Chance, MSRI Publications 42, Cambridge Univ. Press, p. 361–367
