ANGE PROBLÈME DE L'

Certains problèmes de jeux possèdent des énoncés si simples que ce sont de véritables problèmes de mathématiques pures. C'est le cas du « problème de l'ange » qui appartient à une catégorie d'énigmes inventée par David Silverman et Richard Epstein à la fin des années 1940. Ce problème a été résolu en 2006-2007 simultanément par quatre chercheurs : Oddvar Kloster d'Oslo en Norvège, András Máthé de Melbourne en Australie, Brian Bowditch de Southampton en Grande-Bretagne et Peter Gacs de Boston aux États-Unis. Ils ont proposé des solutions différentes et indépendantes, mais arrivent tous à la même conclusion : un ange de force 2, s'il se comporte intelligemment, ne se fera jamais coincer par un démon. Qu'est-ce que cela signifie ?

Un ange de force 1 est un pion qui se déplace sur un échiquier infini à cases carrées et qui à chaque fois qu'il doit jouer se comporte comme un roi du jeu d'échecs : il peut donc passer de la case où il est posé à n'importe laquelle des 8 cases voisines. Un ange de force N est un pion qui à chaque fois qu'il joue opère N fois comme un ange de force 1. Un ange de force 2 peut donc atteindre en un coup n'importe laquelle des 24 cases les plus proches situées autour de lui : 8 cases juste autour de lui, et 16 autres entourant ces 8 cases.

Le démon, quant à lui, dispose à chaque coup du pouvoir de détruire une case autre que celle où se trouve l'ange. Son but est de bloquer l'ange sur une case cernée par des cases détruites. Le but de l'ange est d'échapper au démon. Le problème de l'ange est donc le problème le plus élémentaire de poursuite sur un tableau qu'on puisse imaginer.

On sait qu'un ange de force 1 perdra toujours face à un démon intelligent, car celui-ci, en construisant une sorte de grand fossé assez loin de la position initiale de l'ange, trouvera le temps d'encercler ce dernier avant qu'il ait pu s'échapper. La méthode de jeu du démon n'est pas très compliquée, mais il faut quand même être attentif pour la découvrir. Le lecteur, en jouant contre un adversaire humain, comprendra au bout de quelques parties comment jouer s'il est le démon, et pourquoi il ne peut pas s'en sortir s'il est l'ange de force 1.

Aussi étonnant que cela paraisse, le problème de l'ange de force 2 (et donc de l'ange de force N pour tout N plus grand que 2), était resté sans solution jusqu'à l'année dernière. On pensait qu'il était très difficile car le célèbre mathématicien John Conway y avait travaillé en vain produisant une série de beaux résultats partiels, mais pas la solution complète.

La réponse est que l'ange de force 2 peut s'échapper. Parmi les démonstrations proposées, la plus élégante est celle de Kloster qui non seulement a prouvé mathématiquement que la stratégie qu'il définit pour l'ange de force 2 réussit toujours, mais en a aussi donné une réalisation par programme permettant à qui le souhaite de jouer le rôle du démon, et donc de se faire battre par l'ange.

— Jean-Paul DELAHAYE