Nim

Généralement, le jeu de Nim est un jeu à deux joueurs d'information parfaite dans lequel il y a un certain nombre de rangées ou de "tas" d'objets, et un coup légal consiste à enlever un nombre quelconque d'objets d'un seul tas. (Pour un jeu non trivial, il faut commencer avec au moins trois tas.) Dans le "jeu standard", le joueur qui ne peut pas faire de coup à son tour (parce qu'il ne reste plus d'objets) est le perdant. Une théorie très générale et approfondie de tels jeux est développée dans Winning Ways for Your Mathematical Plays de Berlekamp, Conway et Guy. Dans la version commerciale illustrée, les joueurs retirent à tour de rôle 1, 2, 3 ou 4 chevilles d'affilée. D'après l'image, les "rangées" peuvent s'étendre dans n'importe quelle direction, ce qui signifie que les "tas" se croisent. Ce n'est pas ce que la plupart des gens connaissent comme le Nim. De plus, selon la description originale, dans cette version, le perdant est le joueur qui doit retirer la dernière cheville. Il s'agit d'une variante appelée "jeu misère", plutôt que de la condition de victoire standard. De nombreux jeux combinatoires permettent le jeu misère comme variation. Le Nim est résolu, ce qui signifie que, à partir de n'importe quelle configuration initiale, on peut facilement déterminer si le joueur suivant ou le joueur précédent a une stratégie gagnante, et identifier un bon coup suivant dans le premier cas. Pour le Nim, cela peut être déterminé de manière surprenante facilement, quelle que soit la taille des tas, mais je ne vais pas vous révéler le secret. Comme la plupart de ceux qui s'intéressent au Nim connaissent la solution, il n'y a pas beaucoup de jeu ici. Mais le Nim joue un rôle central dans la théorie des jeux combinatoires, car tout jeu impartial fini à deux joueurs est en quelque sorte un Nim déguisé: toute position dans un tel jeu correspond à un tas de Nim unique, et on peut jouer le jeu déguisé à la perfection en faisant les coups qui correspondent aux coups gagnants dans le Nim. Sprouts est un exemple. Cela ne signifie cependant pas que Sprouts lui-même est résolu, car le "déguisement" n'est que partiellement révélé.