Voici un extrait du programme d’informatique en MPII (sur lequel seront basées les épreuves des concours à partir de 2023) :

Jeux d’accessibilité à deux joueurs sur un graphe. Stratégie. Stratégie gagnante. Position gagnante.
Détermination des positions gagnantes par le calcul des attracteurs. Construction de stratégies gagnantes.
On considère des jeux à deux joueurs (J₁ et J₂) modélisés par des graphes bipartis (l’ensemble des états contrôlés par J₁ et l’ensemble des états contrôlés par J₂). Il y a trois types d’états finals :
les états gagnants pour J₁, les états gagnants pour J₂ et les états de match nul.
On ne considère que les stratégies sans mémoire.

En fait le même texte apparaît dans le programme d’informatique commune des autres CPGE. Les jeux à deux joueurs ont même déjà été présents dans trois sujets des concours ENS :

• ENS Cachan 2000 :

  

• ENS 2007 :

  

• ENS Cachan 2010 :

  

C’est de ces sujets qu’a été extrait le mot arène pour désigner le graphe sur lequel bouge le pion. Mais on voit que les exemples ci-dessus ne sont pas nécessairement bipartites. Une collection de graphes bipartites a donc été constituée préalablement à la semaine des maths :

Voici le graphe du jeu Hexapawn :

En enlevant les dessins d’échiquier, il devient ce jeu à un seul pion :

En fait on peut colorier plusieurs sommets en rouge ou en bleu, et même, l’arène idéale est précoloriée comme ici :

Le but du jeu, pour Rouge, est d’amener le pion sur un sommet rouge, et pour Bleu, d’amener le pion sur un sommet bleu.

Mais comme il s’agissait d’explorer, expérimenter et créer, le placement de jetons a été préféré, car alors le coloriage n’est pas définitif et il est possible de réutiliser les arènes pour les groupes d’élèves suivants.

Sur cette arène le pion n’est pas idéalement placé :

En effet il est sur un sommet rond et c’est donc à Bleu de le déplacer. Le faire aller vers le haut revient à le poser sur le jeton rouge et cela ferait gagner Rouge (donc perdre Bleu). Bleu a donc tout intérêt à faire aller le pion en bas, mais dans ce cas Rouge ne peut que le replacer au départ.

On peut se poser la question dans l’autre sens : où faut-il placer le pion pour assurer une certaine équité aux deux joueurs ?

On colorie en rouge le sommet gagnant pour Rouge et en bleu le sommet gagnant pour Bleu :

Aucun des deux sommets qui bordent le sommet rouge ne peut être considéré comme gagnant pour Rouge puisque Bleu peut décider, depuis un de ces sommets, de mettre le pion ailleurs que sur le sommet rouge. Par contre le sommet tout à gauche peut être colorié en bleu parce que, si le pion s’y trouve, Rouge ne peut que le diriger vers vers le jeton bleu, indépendamment de sa volonté (qui n’est pas de l’amener vers du bleu) :

Mais maintenant qu’on a un nouveau sommet gagnant pour Bleu, celui qui permet à Bleu d’y mener le pion, est aussi gagnant pour Bleu :

Si la position initiale du pion est coloriée en bleu, Bleu a une stratégie gagnante (mener le pion vers un sommet bleu), si la position initiale du pion est rouge, Rouge a une stratégie gagnante (mener le pion vers un sommet rouge). On peut donc préférer mettre au début le pion vers un sommet non colorié puisque ceux-ci ne donnent la préférence ni à Rouge ni à Bleu. Mais au risque d’avoir des parties de durée infinie...

Des élèves ont essayé une méthode statistique assez typique de la recherche scientifique. Elles ont placé le pion au hasard (ailleurs que sur les jetons rouge et bleu) puis joué, et noté qui a gagné :

En fait cela revient à regarder dans l’approche ci-dessus, la proportion de sommets rouges et bleus. Voici d’autres exemples avec d’autres jeux créés par des élèves de CM1, où l’on voit l’influence du choix des positions des jetons rouges et bleus, sur la « qualité » du jeu :

La même arène que précédemment mais avec un autre choix du placement des jetons :

Cette fois il n’y a pas de sommet blanc :

La même arène mais avec un autre placement des jetons :

Là par contre il y a majorité de sommets blancs :

C’est assez évident : le seul moyen pour le pion d’arriver au jeton bleu, c’est de passer par le jeton rouge : Bleu ne peut pas gagner sans passer par le jeton rouge et alors c’est trop tard puisque Rouge a déjà gagné. On verra plus bas des exemples de corrections proposées par des élèves pour chercher à éviter ce genre de situation (en gros, on établit des courts-circuits ce qui revient à modifier le graphe et non son coloriage).

Un jeu clairement à l’avantage de Rouge :

En effet :

Un jeu clairement à l’avantage de Bleu :

En effet :

Un jeu plus équilibré :

En effet

Un jeu que des élèves ont senti meilleur (d’instinct) :

Mon verdict sur ce jeu :

Pour le jeu Hexapawn cité au début de cet article, on colorie en rouge les sommets gagnants pour les noirs (pions blancs tous bloqués et c’est aux blancs de jouer) et en bleu les sommets gagnants pour les blancs (pions noirs bloqués) :

En coloriant selon les règles de coloriage ci-dessus, on découvre que le sommet où se trouve le pion initialement est rouge : cela signifie qu’à Hexapawn il y a une stratégie gagnante pour les noirs (qui commencent le jeu), elle consiste à jouer le pion du centre :

Pour les rares lecteurs qui, arrivés ici, persisteraient à s’intéresser plus à la classe préparatoire qu’au cours préparatoire (à la CPGE plus qu’au CP tout court), le programme de prépa évoque la notion de stratégie, et en particulieur de stratégie gagnante. Sur cet exemple

le coloriage des sommets en trois couleurs (gagnants pour Bleu, gagnants pour Rouge et de match nul) vu ci-avant permet d’élaborer une stratégie gagnante pour Bleu : mener le pion vers un sommet bleu chaque fois que c’est possible. On enlève alors les flèches qui ne vont pas vers un sommet bleu (sauf s’il n’y a pas d’alternative) :

Si on ne tient pas compte des coloriages, on a alors un moyen de savoir, pour chaque position possible du pion sur un sommet circulaire, où le mener :

On considère qu’on applique la stratégie aux sommets du graphe. Mathématiquement cela s’appelle donc une application (mathématiques).

Comme Bleu n’a aucun contrôle sur le mouvement du pion lorsque celui-ci est sur un sommet carré, on peut enlever les sommets carrés qui ne sont pas des destinations de l’application :

Le résultat est un concept fondamental en mathématiques : une fonction (mathématiques). Une stratégie est donc tout simplement une fonction...

Pour tenter d’améliorer un jeu à deux joueurs, rapidement, les élèves ont eu l’idée de modifier l’arène, ce qui laisse plus de latitude que seulement choisir l’emplacement des jetons.

Beaucoup de soin a été apporté à cette étape :

Pour dessiner les sommets de forme carrée, la règle a été mobilisée :

et pour les sommets circulaires, les ciseaux :

Des élèves ont même commencé un rendu figuratif (carrés en 3D et sommets gagnants en forme de bouche qui avale le pion) :

John Conway a lui aussi étudié les jeux à deux joueurs, mais avec un formalisme différent : ce ne sont pas les « couleurs » des sommets qui déterminent le joueur, mais celle des arcs (les arcs rouges sont pour Rouge et les arcs bleus sont pour Bleu). La théorie de Conway permet de construire le nombre en lui donnant un sens original puisque ludique. La voici résumée en 4 articles (ainsi que leurs sources), le dernier étant celui qui concerne les jeux à deux joueurs exposés ici :

nombres	jeu de Nim	infinitésimaux	kos

Voici des exemples de ko (go) représentés sous forme de graphes par Ivan Riou :

et le source en LaTeX :