Je disais récemment que les idées scientifiques ont tendance à
ressembler aux tamagotchis : on commence à les élever et rapidement
elles vous accaparent l'esprit en demandant sans arrêt votre
attention.
Je réfléchissais à la théorie
combinatoire[#] des jeux quand je
suis tombé sur l'idée du jeu suivant (qui a certainement déjà été
décrit et étudié, mais il est difficile de trouver sous quel nom), que
j'appellerai le jeu de nim épicé.
Tout d'abord je rappelle ce qu'est
le jeu de nim usuel :
il s'agit d'un jeu (impartial, à connaissance complète, à deux
joueurs) extrêmement simple, dans lequel l'état du jeu est donné par
un certain nombre de lignes de bâtonnets (ou
quelconques autres jetons : tas de pièces, rangées d'alumettes, ce que
vous voudrez ; il en existe aussi des avatars un petit peu moins
évidents où, par exemple, on avance des pions sur un échiquier sans
avoir le droit de les reculer). Seul compte le nombre de bâtonnets
présent sur chaque ligne (il n'y a pas d'ordre, pas de structure
supplémentaire). La règle du jeu est simplissime : les joueurs jouent
tour à tour et chacun, quand c'est son tour, peut et doit retirer des
bâtonnets situés sur une ligne — il doit en retirer au moins un
et peut en retirer autant qu'il veut, y compris vider (et donc
supprimer) la ligne, mais il ne peut en un tour retirer des bâtonnets
que d'une seule ligne (de son choix). Normalement, le joueur
qui ne peut plus jouer a perdu (i.e., celui qui retire le
dernier bâtonnet a gagné, puisque son adversaire est dans
l'impossibilité de jouer) : en fait, la version misère, où
celui qui retire le dernier bâtonnet perd, est peut-être plus commune
pour le jeu de nim, mais elle est en fait très
semblable[#2] et moins
intéressante mathématiquement.
Dans n'importe quel jeu de ce genre (i.e., un jeu impartial, à
connaissance complète, à deux joueurs, et qui termine toujours en
temps fini sur le gain d'un des joueurs avec par convention perte du
joueur qui ne peut plus jouer), l'un des deux joueurs a forcément une
stratégie gagnante. En fait, on peut définir deux sortes de positions
du jeu : les positions
dites nulles[#3]
— qui sont celles à partir desquelles le second joueur a une
stratégie gagnante —, et les autres (généralement les plus
nombreuses). La définition (récursive !) est qu'une position
nulle est une position qui ne conduit qu'à des positions non
nulles (y compris si elle ne conduit à rien du tout, car alors le
joueur qui vient de jouer à gagné) et, a contrario, une
position non nulle est une position qui conduit à au moins une
position nulle. La stratégie gagnante consiste à jouer, autant
que c'est possible, pour mettre le jeu dans une position nulle (auquel
cas le joueur adverse sera obligé de jouer pour aller dans une
position non nulle, donc on sera assuré de pouvoir jouer vers une
position nulle, et ainsi de suite : comme on peut toujours gagner, on
ne peut pas perdre). Connaître la stratégie gagnante revient donc à
identifier les positions nulles (pour pouvoir jouer vers elles).
Dans le cas du jeu de nim, elles ont une description
mathématiquement simple : sont nulles les positions telles que
le « ou
exclusif » du nombre de bâtonnets de chaque ligne (écrits en
binaire) soit nul. Par exemple, la position de départ habituelle,
(1,3,5,7) (ce qui signifie : un bâtonnet sur une ligne, trois sur une
autre, cinq sur une troisième, et sept sur la dernière ligne) est
nulle car 001⊕011⊕101⊕111=000
: cela
signifie qu'au jeu de nim usuel, à partir de cette position, le joueur
qui ne commence pas peut gagner le jeu à coup sûr (par exemple, si le
premier joueur retire deux bâtonnets de la dernière ligne,
c'est-à-dire joue vers (1,3,5,5), position non nulle, on répondra vers
(1,1,5,5), position nulle, et il est d'ailleurs clair qu'on a alors
une stratégie gagnante en reproduisant les coups d'une paire de lignes
(1,5) sur l'autre).
J'en viens donc au jeu de nim épicé : la différence avec le jeu nim
normal est qu'il existe deux sortes de lignes, des
lignes épicées et des lignes normales
(ou fades). La règle du jeu est la même (on peut retirer
autant de bâtonnets qu'on veut, mais d'une ligne seulement) avec la
seule différence que lorsqu'un joueur retire des bâtonnets d'une ligne
épicée, son adversaire ne peut pas en faire autant au coup
immédiatement après (il doit retirer des bâtonnets d'une ligne fade
— et s'il n'en reste aucun, il a perdu). Autrement dit, on ne
peut consommer deux coups de suite des bâtonnets épicés. Une position
du jeu est déterminée par le nombre de bâtonnets dans les lignes de
chaque sorte (je les écrirai en commençant par les
lignes fades) et par le fait que le coup immédiatement
précédet ait été épicé ou non.
Exemple : en commençant sur (1,2,11;4;4),
c'est-à-dire qu'il y a trois lignes fades avec 1, 2 et 11 bâtonnets,
et deux lignes épicées avec 4 bâtonnets chacune, le premier joueur
pourrait jouer vers (1,2,5;4;4), le second joueur répliquerait avec
(1,2,5;4,2)H (le H
, comme hot
signifiant qu'on vient de jouer épicé, donc que le coup suivant sera
forcément fade), le premier joueur tenterait maladroitement
(1,2,3;4,2), ce à quoi on rétorquera (1,2,3;2,2)H, et une
tentative désespérée vers (1,2,1;2,2) provoquera inévitablement la
réplique (1,2,1;2)H, et il n'y a plus de doute sur qui a
gagné.
La question à cent zorkmids est donc : quelles sont les
positions nulles du jeu de nim épicé ? Peut-on les décrire
de façon synthétique comme pour le jeu de nim usuel ?
Je n'ai que des réponses partielles à cette question. Je peux
facilement faire produire à mon ordinateur des tables gigantesques de
positions nulles, mais ensuite trouver la logique ressemble à un test
d'intelligence. Et si c'est un test d'intelligence, j'ai échoué :
j'ai trouvé beaucoup de motifs partiels, mais aucune decription
complète.
Il est clair que si le nombre total de bâtonnets épicés est
strictement supérieur au nombre total de bâtonnets fades (et que la
position n'est pas chaude, i.e., qu'on peut jouer épicé), alors la
position est non nulle : en effet, le premier joueur a la stratégie
gagnante consistant à manger les épices
, c'est-à-dire retirer
un quelconque bâtonnet épicé, auquel cas son adversaire devra en
retirer un fade, puis le premier joueur retire de nouveau un épicé, et
ainsi de suite jusqu'à épuisement des fades auquel moment le second
joueur perd. Dans « beaucoup » de cas, une position nulle s'obtient
en complétant une telle position jusqu'à ce que le nombre total de
bâtonnets fades égale le nombre total d'épicés : notamment, s'il y a
une seule ligne fade, il est facile de voir que la condition de
nullité est précisément que le nombre de bâtonnets de cette ligne soit
égal au nombre total de bâtonnets épicés ; il en va de même si les
épicés sont dans des lignes d'un seul bâtonnet chacune (i.e., de
nouveau, quelle que soit la répartition des fades, la condition de
nullité sera que les fades soient aussi nombreux que les épicés).
Mais parfois, il faut plus de fades : par exemple, s'il y a exactement
deux lignes de fades dont une avec un seul bâtonnet, la condition de
nullité est que le nombre total de fades soit deux de plus
que le nombre total d'épicés si toutes les lignes épicées ont un
nombre pair de bâtonnets (alors que c'est égalité s'il y a
une ligne épicée avec un nombre impair de bâtonnets) — je sais
le démontrer, mais je ne sais pas le généraliser correctement. Je ne
sais pas « expliquer » de façon satisfaisante le fait que (2,9;6,4) ou
(3,8;6,4) ou (1,2,8;6,4) (et pas (2,8;6,4) ou (2,n;6,4)
pour un quelconque autre n) soient des positions nulles.
C'est mystérieux : je cherche encore le motif, mais je
commence à douter de son existence…
Évidemment, le jeu de nim se prête à quantité d'autres variations
(on pourrait interdire de reprendre des bâtonnets de la ligne qui
vient d'être diminuée, ou bien seulement pour certaines lignes, ou
avoir plusieurs sortes d'épices, que sais-je encore…). Mais
celle-ci m'est venue à l'esprit dans le cours d'une réflexion plus
générale, alors maintenant elle m'obsède.
[#] Le
terme combinatoire
est là pour insister sur le fait qu'il ne
s'agit pas de la théorie des jeux
dans le sens où on
l'entend d'habitude (jeux à la von Neumann, équilibres de Nash,
tout ça) mais de jeux à information complète. Pour la bible sur le
sujet, voir le très
exotique Winning
Ways de Berlekamp, Conway et Guy. On peut dire que c'est
Conway
qui a inventé la théorie combinatoire des jeux partiaux, la
théorie combinatoire des jeux impartiaux — théorie
de Sprague-Grundy,
par exemple — est plus ancienne.
[#2] Pour jouer à la
version misère, si on connaît la stratégie optimale de la version
normale du nim décrite plus loin, il suffit de jouer comme pour la
version normale sauf lorsqu'on ne va laisser que des lignes avec (zéro
ou) un bâtonnet : à ce moment-là on en laisse un de moins (ou un de
plus).
[#3] Le choix du
mot nul
, pour les jeux où le second joueur a une stratégie
gagnante, pourra sembler bizarre. L'explication est que si on fait la
somme d'un tel jeu et d'un jeu G quelconque —
la somme
étant à comprendre au sens où chaque joueur peut jouer
dans une composante quelconque de la somme — alors la somme en
question a la même caractéristique que le jeu G. Ou
encore, les positions nulles sont celles dont la fonction de
Grundy est nulle.