Arbre de jeux

Un arbre de jeu consiste à représenter sous forme d'un arbre toutes les positions que l'on peut atteindre à partir de celles du coup précédent. Selon le jeu, cet arbre devient gigantesque à partir de peu d'étages déjà. Aux échecs par exemple, les blancs ont le choix entre 20 coups (16 coups de pions et 4 coups de cavaliers) pour débuter la partie. Cela fait donc déjà 20 branches qui partent du sommet. Ensuite, les noirs ont aussi 20 coups à disposition. Cela fait déjà 400 positions possibles après 2 coups, puisque 20 branches partent des 20 positions précédentes!
Autant dire, que, sauf pour des jeux très simples, il est impossible de dessiner l'arbre de jeu complet. Aussi doit-on élaguer l'arbre pour éliminer les positions manifestement mauvaises pour le joueur. Nous verrons plus tard comment s'y prendre.
Voici ci-dessous un arbre partiel pour une fin de partie d'échecs, sur un échiquier 4x4.

Exercice

Vous voyez ci-contre de tablier du jeu Pong Hau K'i. Chaque joueur bouge à tour de rôle un des jetons de sa couleur sur la seule intersection disponible. Le but du jeu est de coincer l'adversaire.
Ce jeu est l'un des rares assez simples pour que l'on puisse dessiner l'arbre de jeu complet.

  1. Combien y a-t-il de positions possibles? Combien sont gagnantes?
  2. Dessiner l'arbre de ce jeu, en supposant que les noirs commencent. Que constatez-vous?
  3. Dessiner l'arbre de ce jeu, en supposant que les rouges commencent. Que constatez-vous?

Conseil: utilisez une feuille A3!
Remarque: dessinez un graphe plutôt qu'un arbre, c'est-à-dire que vous pouvez relier une position à une position déjà rencontrée dans votre arbre, et ainsi "remonter" dans l'arbre.

Didier Müller, 3.6.04