Problème de l'ange

Un article de Wikipédia, l'encyclopédie libre.

Le problème de l'ange est un jeu mathématique conceptuel inventé par le mathématicien J. H. Conway.

Sur un plateau de jeu d'échecs de taille supposée infinie, un diable tente de piéger un ange. À chaque coup, le diable élimine l'une des cases du plateau, puis l'ange doit sauter à une case quelconque non éliminée, distante de N cases au maximum, N étant un entier positif fixé au préalable (dénommé « pouvoir » de l'ange). L'ange pouvant « voler », les cases intermédiaires entre sa case de départ et sa case d'arrivée peuvent avoir déjà été éliminées ou non. Seule la distance entre ces deux cases est limitée par le pouvoir de l'ange.

L'objectif du diable est de piéger l'ange sur une « île » située à une distance d'au moins N cases de toute autre case non éliminée du plateau, empêchant ainsi l'ange de se déplacer.

On peut penser a priori que l'ange est beaucoup plus puissant que le diable, car il peut se déplacer tous azimuts sur un plateau de taille infinie, tandis que le diable ne peut éliminer qu'une case à la fois. Toutefois, il faut noter que le diable est lui même très puissant puisqu'il peut éliminer des cases qui se trouvent à une grande distance de la position actuelle de l'ange et en quelque sorte « piéger le terrain » en prévision du passage de l'ange dans ces régions. Conway et ses collaborateurs avaient ainsi montré très vite qu'un ange de pouvoir 1 est piègeable en moins de 150 coups, et qu'un ange de pouvoir arbitraire, mais qui n'a jamais le droit de reculer (d'aller vers le Sud) de plus de 1000 cases, se fait finalement pièger.

La question principale que posait ce jeu a peut-être (il semble que les vérifications soient encore en cours) été finalement résolue en 2006 :

• l'ange peut-il échapper indéfiniment au diable, à condition que son pouvoir soit suffisant ?

La réponse serait positive, dès que ce pouvoir est supérieur ou égal à 2 : une stratégie gagnante (pour l'ange), due à O. Kloster est décrite ici (en anglais) : [1], et peut être testée à l'adresse suivante : [2]