Jeu octal
From Wikipedia, the free encyclopedia
Les jeux octaux, étudiés dans le cadre de la théorie des jeux combinatoires[1], 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[1].
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 :
- d0 . d1 d2 d3 d4 …
où chaque chiffre dn indique en combien de tas le joueur doit scinder le tas dans lequel il a retiré n objets. Le chiffre dn 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 dn=0, les joueurs n'ont pas le droit de retirer n objets d'un tas. Si dn=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 d0 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 d0=0, ce qui signifie que le joueur n'a pas le droit de ne retirer aucun objet d'un tas, soit d0=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[1], 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[1], p95), est un exemple notable de jeu octal non résolu.
