Imaginons deux joueurs, Alice et Bob, qui s’affrontent autour d’une grille carrée à n lignes et n colonnes. Sur cette grille, chaque case est occupée par une ampoule électrique qui peut être soit éteinte, soit allumée.
Alice joue en premier. Son rôle est de choisir la configuration initiale de la grille, c’est-à-dire le nombre d’ampoules allumées et leur position. Bob a pour sa part accès à des interrupteurs situés au bout de chaque ligne et de chaque colonne (il y a donc 2n interrupteurs en tout), dont le basculement a pour effet d’intervertir les états des ampoules sur la ligne ou la colonne correspondante : les ampoules qui étaient allumées s’éteignent, et celles qui étaient éteintes s’allument. Bob peut manipuler tous ces interrupteurs dans l’ordre qu’il veut, aussi longtemps qu’il le souhaite.
L’objectif de Bob est de faire en sorte qu’à la fin de la partie il y ait aussi peu d’ampoules allumées que possible – autrement dit, il cherche à minimiser le nombre d’ampoules allumées dans la configuration finale. Alice, à l’inverse, cherche à faire en sorte qu’à la fin du jeu, il y ait un maximum d’ampoules allumées : elle cherche à maximiser le nombre minimal d’ampoules allumées que peut obtenir Bob après ...
Lire la suite