Les jeux à deux joueurs

Comment un enfant peut créer son propre jeu
dimanche 10 avril 2022
par  Alain BUSSER

Lors de la semaine des mathématiques 2022, à l’école Michel-Debré du Chaudron, des élèves de CM1 ont appris ce qu’est un jeu à deux joueurs, et ont créé leur propre jeu !

L’activité semble abordable en cycle 2 (mais pas avant, il faut bien voir les flèches pour y jouer).

Licence Creative Commons
Ce(tte) œuvre est mise à disposition selon les termes de la Licence Creative Commons Attribution - Partage dans les Mêmes Conditions 2.0 France.

Attention le bloc suivant peut effrayer : il y est question du programme de CPGE sur les jeux à deux joueurs. Sa lecture n’est donc nullement indispensable pour qui veut simplement jouer ou créer des jeux.

classe préparatoire

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 (J1 et J2) modélisés par des graphes bipartis (l’ensemble des états contrôlés par J1 et l’ensemble des états contrôlés par J2). Il y a trois types d’états finals :
les états gagnants pour J1, les états gagnants pour J2 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 :

Dans cet article, à la classe préparatoire, on préférera le cours préparatoire (ainsi que l’ensemble des cycles 2 et 3).

Exemple

Voici le graphe du jeu Hexapawn :

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

Pour jouer à un jeu à deux joueurs, il faut un graphe

  • orienté (le pion ne doit pas remonter les flèches)
  • bipartite (toute flèche doit relier un sommet rond à un sommet carré ou vice-versa) :

On appelle arène ce genre de graphe, et les deux joueurs déplacent alternativement le pion (il n’y en a qu’un) sur l’arène.

L’un des joueurs (qu’on appellera Bleu mais est appelé Ève dans les sujets de concours) bouge le pion si le pion est sur un sommet de forme circulaire (cercle rime avec bleu...) et l’autre (qu’on appellera Rouge mais est nommé Adam dans les sujets de concours) bouge le pion si celui-ci est sur un sommet de forme carrée (mnémonique en anglais : car et red...).

Ci-dessus c’est donc à Bleu (ou Éve) de bouger le pion. Elle n’a pas d’autre choix que de le faire aller vers le bas, et ensuite Rouge (ou Adam) pourra ramener le pion au même endroit, aboutissant à une boucle sans fin évocatrice du ko (go)...

Mais au fait quand est-ce que le jeu s’arrête ? En plus de l’arène et du pion, il faut deux jetons, un rouge et un bleu, à placer quelque part sur le graphe avant de jouer :

Coloriage

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 :

image/svg+xml

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.

Le jeu s’arrête lorsque le pion est sur un jeton :

et la couleur du jeton indique le gagnant. Ici c’est Bleu qui a gagné parce que le pion est arrivé sur un jeton bleu. Ci-dessous Rouge a gagné :

En effet le pion est arrivé sur un jeton rouge.

Pour créer un jeu à deux joueurs, il faut donc

  • (créer) une arène
  • placer un jeton rouge et un jeton bleu sur deux des sommets de cette arène (ou colorier en bleu et rouge certains des sommets)
  • décider de la position de départ du pion.

Où placer le pion ?

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...

Où placer les jetons ?

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 :

Stratégie

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...

création d’arènes

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) :

Voici quelques exemples d’arènes conçues par des élèves de CM1 :

Un regard attentif révèle que certains d’entre eux sont hors programme (en CPGE mais pas en CP) car ils ne sont pas bipartites. Les autres ont été numérisés (chacune des images ci-dessous est cliquable et mène à un pdf à imprimer en A4 pour jouer) :

Construction du nombre par les jeux

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

Les kos du jeu de go

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

et le source en LaTeX :


Commentaires