Jeu de Quilles - Strategie

Ce jeu, dérivé du jeu de Nim, consiste à abattre toutes les quilles.
Chaque joueur à tour de rôle abat une ou deux quilles voisines d'un même bloc. Ceci peut créer des nouveaux blocs.
Celui qui ne peut plus jouer à perdu (celui qui abat la/les dernière(s) quille(s) a donc gagné)

Si les blocs sont appariés, jouer la même chose que l'adversaire garantit le gain.
Ceci se généralise en considérant non pas le nombre de quilles d'un bloc, mais un nombre de Grundy associé.
La valeur d'une position est la somme Nim des nombres de Grundy de tous les blocs, c'est à dire le ou exclusif binaire (addition en base deux sans retenue).

Les nombres de Grundy se calculent de proche en proche.
Un bloc de 0 quilles vaut 0 : g(0) = 0, c'est la position finale gagnante.
Puis un bloc de n quilles se décompose en deux blocs de i + j quilles.
g(n) est le plus petit nombre qui n'est pas parmi les g(i)g(j) de toutes ces décompositions, où est la somme Nim.
Ceci permet d'affirmer que l'on peut décomposer un bloc de n en deux blocs dont la somme Nim est tout nombre <g(n)

Toute position de valeur 0 oblige le joueur à obtenir une position de valeur ≠0
Toute position de valeur ≠0 permet au joueur d'atteindre une position de valeur 0 (donc de gagner).

On obtient ainsi la stratégie gagnante :
Calculer la valeur g de la position comme somme Nim des nombres de Grundy de chaque bloc.
Si cette valeur est nulle, la position est perdante, jouer un coup au hasard.
Sinon, chercher un bloc dont la modification permet d'obtenir une valeur du jeu nulle.
Ce bloc est l'un de ceux dont g(n)g < g(n), puisqu'on peut toujours amener un bloc valant g(n) à toute valeur <g(n).
Le bloc g(n) étant alors remplacé par des blocs de valeur gg(n) et les autres blocs inchangés ayant comme valeur gg(n),
la valeur totale du jeu devient (gg(n)) (gg(n)) = 0
"" est ici la "différence Nim", mais "" est identique à "" et xx = 0!