Jeu octal

Les jeux octaux, étudiés dans le cadre de la théorie des jeux combinatoires, sont une catégorie de jeux impartiaux, proches du jeu de Nim. Ils se jouent avec des tas d'objets où les coups autorisés consistent à retirer des objets d'un tas et éventuellement à séparer ce tas en deux. Les règles précises sont définies à l'aide d'un système numérique à 8 chiffres (les nombres de 0 à 7), d'où le nom de jeu octal.

Les jeux octaux font l'objet du chapitre 4 Taking and Breaking de la deuxième édition de Winning Ways for your Mathematical Plays.

Codage des règles

Un jeu octal se joue avec des tas d'objets. Les deux joueurs jouent à tour de rôle. Le joueur dont c'est le tour choisit un tas d'objets, retire un certain nombre d'objets de ce tas, et éventuellement sépare les objets restants en deux tas. Par ailleurs, le joueur dont c'est le tour doit laisser intacts les autres tas.

Le joueur qui ne peut plus jouer perd en version normale, et gagne en version misère.

Les règles d'un jeu octal précisent les actions possibles lorsqu'un joueur retire n objets d'un tas donné, et sont encodées par une suite de chiffres entre 0 et 7 :

d₀ . d₁ d₂ d₃ d₄ …

où chaque chiffre d_n indique en combien de tas le joueur doit scinder le tas dans lequel il a retiré n objets. Le chiffre d_n est la somme de :

• 1 si le joueur peut laisser 0 tas, 0 sinon;
• 2 si le joueur peut laisser 1 tas, 0 sinon;
• 4 si le joueur peut laisser 2 tas, 0 sinon

Par exemple, si d_n=0, les joueurs n'ont pas le droit de retirer n objets d'un tas. Si d_n=3, on retrouve la règle classique du jeu de Nim, à savoir que le joueur peut retirer n objets d'un tas de taille n (3=1+2) ou de taille strictement supérieure à n (3=1+2).

Le premier chiffre d'un jeu octal d₀ est particulier et encode les règles dans le cas où le joueur ne retire aucun objet du tas qu'il a choisi. Deux cas sont possibles : soit d₀=0, ce qui signifie que le joueur n'a pas le droit de ne retirer aucun objet d'un tas, soit d₀=4, ce qui signifie que le joueur peut ne retirer aucun objet, mais que dans ce cas, il doit séparer le tas en deux.

Si les chiffres non nuls dans la représentation des règles sont en nombre fini, on dit que le jeu octal est un jeu octal fini.

Exemples

Certains jeux octaux possèdent un nom et une histoire particulière.

• L'incontournable jeu de Nim correspond au jeu octal 0,333333... avec une infinité de 3, ce qui signifie que l'on peut retirer un nombre quelconque d'objets de n'importe quel tas.
• Le jeu octal 0,77 est appelé jeu de Kayles et 0,7777 double-Kayles.
• Le jeu octal 0,137 correspond aux échecs de Dawson, un jeu inventé par Thomas Dawson qui se joue avec des pions du jeu d'échecs.
• Le jeu octal 0,07 est appelé Kayles de Dawson (cf Winning Ways, p92) parce que sa notation ressemble à celle du jeu de Kayles, mais ses propriétés ressemblent aux échecs de Dawson.
• Le jeu octal 0,6, appelé jeu des officiers (cf Winning Ways, p95), est un exemple notable de jeu octal non résolu.

Suite des nimbers

D'après le théorème de Sprague-Grundy, un tas de n objets d'un jeu octal en version normale (celui qui ne peut plus jouer a perdu) est équivalent à un tas du jeu de Nim d'un certain nombre d'objets, appelé le nimber, et généralement noté G(n). La suite G(0), G(1), G(2), ... est appelée la suite des nimbers du jeu octal.

Les jeux octaux finis (ceux avec un nombre fini de chiffres non nuls) analysés jusqu'ici ont une suite des nimbers qui finit par devenir périodique au-delà d'un certain rang, mais on ne sait toujours pas si c'est bien le cas pour tous les jeux octaux finis. Cette question est listée par Richard Guy comme l'un des problèmes importants de la théorie des jeux combinatoires.

Records de calculs

L'analyse complète d'un jeu octal consiste à trouver la période et la pré-période de sa suite des nimbers. Il est montré dans Winning Ways for your Mathematical Plays que seul un nombre fini de termes de la suite des nimbers est nécessaire pour prouver qu'un jeu octal fini est périodique, ce qui a ouvert la voie aux calculs informatiques.

Les jeux octaux à 3 chiffres ont été les plus étudiés. Parmi les 512 jeux octaux à 3 chiffres possibles, 79 sont non-triviaux, et 14 d'entre eux ont été résolus :

• 0,156 par Jack Kenyon en 1967
• 0,356, 0,055, 0,644 et 0,165 par Richard Austin en 1976
• 0,16, 0,56, 0,127 et 0,376 par Anil Gangolli et Thane Plambeck en 1989
• 0,454, 0,104, 0,106, 0,054 et 0,354 par Achim Flammenkamp de 2000 à 2002

Il reste 63 de ces jeux dont la période - si elle existe - n'est toujours pas connue, malgré le calcul de millions de termes par Achim Flammenkamp.