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.