Hackenbush

Le Hackenbush est un jeu mathématique développé par John Conway.

Règles du jeu

Le jeu du Green Hackenbush se joue à deux joueurs. Chacun à son tour, les joueurs enlèvent un bâton ou une boucle du jeu. Tous les éléments qui ne sont ainsi plus reliés au sol disparaissent également. Le joueur qui prend le dernier bâton gagne.

Principe des tiges de bambou

Afin de trouver une stratégie gagnante, nous prenons un dessin simple sous forme de tiges de bambou (fig. 2). Ces bambous de n segments peuvent être comparés à des colonnes de n pions (fig. 3 a). À partir de ce moment, nous pouvons appliquer la stratégie du jeu NIM.

La Somme NIM

Pour trouver une stratégie gagnante au jeu NIM, il faut additionner les pions de chaque colonne à l’aide de la somme NIM. Par exemple dans la figure 3, nous avons quatre piles. La première contient quatre pions, la deuxième cinq, la troisième trois et la quatrième trois.
Si nous additionnons : 4⊕5⊕3⊕3=1 (fig. 4)
Cette position est donc une position N (Next player wins). Pour faire un mouvement gagnant, il faut jouer dans une position P (Previous player wins), donc modifier la somme NIM de manière à ce qu’elle soit égale à zéro. Pour cela, nous pouvons par exemple enlever un pion de la dernière colonne, ce qui donnera : 4⊕5⊕3⊕2= 0 (fig. 3 b)
Ce même principe peut donc être appliqué aux tiges de bambou.

Principe de l’arbre

Après avoir revu le principe de la somme NIM dans le point précédent, nous pouvons compliquer un peu le cas des colonnes en utilisant des arbres.
Un arbre correspond à un bâton accroché au sol qui se sépare ensuite en plusieurs ramifications (fig 5). Le but est de simplifier un arbre en une colonne. En commençant par le haut, nous faisons la somme NIM de part et d’autre d’un nœud. Par exemple, prenons le sommet de l’arbre du côté droit sur la figure 5. la première simplification fonctionne comme une somme NIM de 3 ⨁ 2 ⨁ 1 = 0. Nous pouvons alors transformer l’arbre (fig. 6), et ainsi de suite jusqu’à obtenir une colonne de 5 bâtons (fig. 7). Ainsi, dès que les colonnes sont formées, nous retombons sur le principe des tiges de bambous expliqué au point précédent.

Astuce pour aller un petit peu plus vite dans la simplification de l’arbre : dans le cas où il faut additionner uniquement deux bâtons (correspond à un V), la somme NIM vaut 0. Le résultat sera pareil pour tous les nombres pairs. En revanche, si trois bâtons doivent être additionnés (ou d’autres nombres impairs), la somme NIM est de 1. En résumé, un nombre pair de bâtons liés directement à un nœud s’annule (fig. 8). Un nombre impair se simplifie en un seul bâton (fig. 9).

Principe de fusion

Le jeu final aura la forme d’une série de dessins quelconques, composés de bâtons assemblés les uns aux autres. Ils ne ressembleront donc plus forcément à des arbres, mais comporteront parfois des circuits fermés ou plusieurs attaches au sol (fig.10) . Notre but est d’arriver à simplifier ces dessins pour en faire des arbres, puis des colonnes, afin de pouvoir les résoudre à la manière du jeu NIM.
Nous allons donc voir comment développer ces circuits à l’aide de quelques règles.

1. Le sol ne correspond qu’à un seul noeud. Cela signifie que tous les noeuds posés sur le sol peuvent être assemblés (fig. 11 b).
2. Chaque bâton d’un circuit peut être représenté par une boucle (fig. 11 c).
3. Chaque boucle peut être représentée par un bâton (fig. 11 d).
4. Par la somme NIM de bâtons côte à côte, nous avons vu précédemment qu’un nombre pair est égal à zéro, et un nombre impair est égal à un. Notre forme de départ est donc égale à zéro. (fig. 11 e)

Variantes du jeu Hackenbush

Cet article décrit le jeu de Hackenbush, qu'on peut aussi appeler "green Hackenbush".
Il existe également deux autres versions de ce jeu:

1. Le "blue-red Hackenbush" dans lequel les bâtons sont de couleur bleue ou rouge. Chaque joueur se voit attribuer une couleur et n'a le droit d'enlever des bâtons que de sa couleur.
2. Le "blue-red-green Hackenbush" dans lequel les bâtons sont de couleur bleue, rouge ou verte. Chaque joueur se voit attribuer une couleur (soit bleu soi rouge) et la couleur verte n'est pas attribuée. Les joueur peuvent donc enlever des bâtons de leur couleur ou de couleur verte.

Vidéo

Voici une vidéo qui illustre un exemple du jeu du "green Hackenbush".

Sources

- Albert, Nowakowski, Wolfe: "Lessons in Play: An Introduction to Combinatorial Game Theory", CRC Press, 2007
- Berlekamp, Conway, Guy: "Winning Ways for Your Mathematical Plays, vols. I - IV", CRC Press, 2001
- Ferguson, Thomas S,: "Game theory, Class notes for Math 167", Fall 2000