Hackenbush

Hackenbush est un jeu à 2 joueurs inventé par le mathématicien John Horton Conway. Il peut être joué sur n'importe quelle configuration de segments de lignes colorées connectées les uns aux autres par leurs extrémités et à une ligne « sol ».

Une configuration de départ pour le jeu de Hackenbush

Gameplay

Le jeu débute avec les joueurs traçant une ligne « au sol » (généralement, mais pas nécessairement, une ligne horizontale en bas de la feuille ou dans une autre zone de jeu) et plusieurs segments de ligne de manière que chaque segment soit relié au sol, soit directement à un point d'extrémité, soit indirectement, via une chaîne d'autres segments reliés par des points d'extrémité. Un nombre quelconque de segments peut se rejoindre en un point, permettant ainsi l'existence de multiples chemins vers le sol.

À leur tour, les joueurs « coupent » (effacent) un segment de ligne de leur choix. Chaque segment de ligne n'étant plus relié au sol par aucun chemin « tombe » (c'est-à-dire est effacé). Conformément à la convention normale de jeu de la théorie des jeux combinatoires, le premier joueur qui ne peut plus effectuer de mouvement perd.

Les planches Hackenbush peuvent se composer d'un ensemble fini (dans le cas d'une « planche finie ») ou d'un ensemble infini (dans le cas d'une « planche infinie ») de segments de ligne. L'existence d'un nombre infini de segments de ligne ne contredit pas l'hypothèse de la théorie des jeux selon laquelle le jeu peut être terminé en un temps fini, pourvu qu'il n'y ait qu'un nombre fini de segments de ligne touchant directement le sol. Sur une planche infinie, en fonction de la disposition du plateau, le jeu peut se prolonger indéfiniment, à condition qu'il y ait une infinité de points touchant le sol.

Variantes

Une fille Hackenbush bleu-rouge, présentée dans le livre Winning Ways for your Mathematical Plays

Dans la version folklorique originale de Hackenbush, tout joueur est autorisé à couper n'importe quelle branche : comme il s'agit d'un jeu impartial, il est relativement simple de fournir une analyse complète en utilisant le théorème de Sprague-Grundy. Ainsi, les versions de Hackenbush qui suscitent l'intérêt dans la théorie des jeux combinatoires sont des jeux partisans plus complexes, Cela signifie que les options (mouvements) disponibles pour un joueur ne seraient pas nécessairement les mêmes que celles disponibles pour l'autre joueur s'il devait jouer à partir de la même position. Cette complexité est réalisée de deux manières:

• Hackenbush original : Tous les segments de ligne sont de la même couleur et peuvent être coupés par n'importe quel joueur. Cela signifie que les gains sont symétriques et que chaque joueur effectue les mêmes opérations en fonction de sa position sur le plateau (dans ce cas, en fonction de la structure du dessin).
• Hackenbush bleu-rouge : Chaque segment de ligne est coloré en rouge ou en bleu. Un joueur (généralement le premier, ou joueur de gauche) est autorisé à couper uniquement les segments de ligne bleue, tandis que l'autre joueur (généralement le deuxième, ou joueur de droite) est autorisé à couper uniquement les segments de ligne rouge.
• Hackenbush bleu-rouge-vert : Chaque segment de ligne est coloré en rouge, bleu ou vert. Les règles sont les mêmes que pour le Hackenbush Bleu-Rouge, avec la stipulation supplémentaire que les segments de ligne verte peuvent être coupés par l'un ou l'autre joueur.

Le Hackenbush bleu-rouge est simplement un cas particulier du Hackenbush bleu-rouge-vert, mais il mérite d'être mentionné séparément, car son analyse est souvent beaucoup plus simple. En effet, le Hackenbush bleu-rouge est un jeu dit « froid », ce qui signifie essentiellement qu'avoir le premier coup ne peut jamais être un avantage.

Analyse

Hackenbush a souvent été utilisé comme exemple de jeu pour illustrer les définitions et les concepts de la théorie des jeux combinatoire, notamment dans les livres On Numbers and Games et Winning Ways for Your Mathematical Plays écrits par certains des fondateurs de ce domaine. En particulier, Blue-Red Hackenbush peut être utilisé pour construire des nombres surréels : les plateaux finis de Blue-Red Hackenbush permettent de construire des fractions dyadiques, tandis que les valeurs des plateaux infinis de Blue-Red Hackenbush représentent des nombres réels, des nombres ordinaux et bien d'autres valeurs générales qui sont ni l'un ni l'autre. Quant au jeu Blue-Red-Green Hackenbush, il permet la construction de jeux supplémentaires dont les valeurs ne sont pas des nombres réels, comme l'étoile et tous les autres nimbers.

Une analyse plus approfondie du jeu peut être réalisée en utilisant la théorie des graphes en considérant le plateau comme un ensemble de sommets et d'arêtes, tout en examinant les chemins menant à chaque sommet situé au sol (qui devrait être considéré comme un sommet distinctif — il n'y a aucun inconvénient à identifier tous les points au sol ensemble — plutôt que comme une ligne sur le graphe)

Dans la version impartiale de Hackenbush (celle sans couleurs spécifiées par les joueurs), on peut envisager de l'aborder en utilisant des tas de nim, en subdivisant le jeu en plusieurs cas: vertical, convergent et divergent. En jouant exclusivement avec des empilements verticaux de segments de lignes, également appelés tiges de bambou, le jeu se réduit directement à Nim et peut être analysé de cette manière. Les segments divergents, ou arbres, ajoutent une complexité supplémentaire au jeu et nécessitent l'application du principe du colon, stipulant que lorsque des branches se rejoignent à un sommet, on peut remplacer ces branches par une tige non ramifiée d'une longueur équivalente à leur somme nim. Ce principe modifie la représentation du jeu pour se rapprocher de la version fondamentale des tiges de bambou. Le dernier ensemble de graphiques possible qui peut être créé est celui des graphiques convergents, également connus sous le nom de graphiques arbitrairement enracinés. En utilisant le principe de fusion, nous pouvons affirmer que tous les sommets d'un cycle peuvent être fusionnés sans altérer la valeur du graphique. Par conséquent, tout graphique convergent peut également être interprété comme un simple graphique en tige de bambou. En combinant ces trois types de graphiques, nous pouvons ajouter de la complexité au jeu sans jamais altérer la somme nim du jeu, permettant ainsi au jeu d'adopter les stratégies de Nim.

Preuve du principe du côlon

Le principe du colon indique que lorsque des branches convergent vers un sommet, on peut les remplacer par une tige non ramifiée d'une longueur égale à leur somme nim. Considérons un graphe fixe mais arbitraire, noté G, et choisissons un sommet arbitraire, noté x, dans G. Soient H ₁ et H ₂ des arbres (ou graphiques) arbitraires qui ont la même valeur Sprague-Grundy. Prenons les deux graphes G₁ = G_x : H₁ et G₂ = G_x : H₂, où G_x : H_i représente le graphe obtenu en attachant l'arbre H_i au sommet x du graphe G . Selon le principe du colon, les deux graphes G1 et G2 ont la même valeur Sprague-Grundy. Considérons la somme des deux jeux. L'affirmation selon laquelle G₁ et G₂ ont la même valeur Sprague-Grundy équivaut à dire que la somme des deux jeux a une valeur Sprague-Grundy de 0. En d'autres termes, nous devons démontrer que la somme G₁ + G₂ est une position P. Un joueur est assuré de gagner s'il est le deuxième joueur à jouer dans G₁ + G₂ . Si le premier joueur choisit de couper l'un des côtés de G dans l'un des jeux, alors le deuxième joueur coupe le même côté de G dans l'autre jeu. (Une telle paire de mouvements peut supprimer H₁ et H₂ des jeux, mais sinon H₁ et H₂ ne sont pas perturbés.) Si le premier joueur choisit de couper un côté dans H₁ ou H₂, alors les valeurs Sprague-Grundy de H₁ et H₂ ne sont plus égales, ce qui signifie qu'il existe un mouvement dans H₁ ou H₂ permettant de maintenir les valeurs Sprague-Grundy identiques. De cette manière, vous aurez toujours une réponse à chaque mouvement qu'il pourrait effectuer. Cela garantit que vous effectuerez le dernier mouvement et remporterez la partie.

Voir aussi

Bibliographie

• John H. Conway, On Numbers and Games, AK Peters, 2000, 2^e éd.

Liens externes

• Hackenstrings, et 0,999... contre 1
• Hackenbush sur les jeux de crayon et de papier