Nim à pile unique

Tout comme la Tour de Hanoï, le jeu de Nim existe depuis très longtemps. Le principal responsable de sa popularité actuelle est sans doute le mathématicien Martin Gardner, qui, pendant plus de deux décennies, a tenu une chronique mensuelle dans Scientific American intitulée « Mathematical Games ». C'est en 1958 qu'il a écrit un article sur Nim : « Concernant le jeu de Nim et son analyse mathématique ».

Si vous ne connaissez pas Nim, vous découvrirez rapidement sa simplicité. Une pile de n pièces (ou allumettes, billes ou tout autre objet) est placée devant vous et votre adversaire. Après avoir déterminé qui commence, chaque joueur prend 1, 2, 3, ..., ou p pièces de la pile, un tour à la fois.

Le perdant est celui qui n'a plus qu'une seule pièce ou aucune pièce dans la pile.

Il existe de nombreuses variantes de Nim : certaines proposent plusieurs piles d'objets parmi lesquels choisir, d'autres déclarent vainqueur le joueur qui choisit le dernier objet.

Mais le programme  NIM.BAS ne joue qu'à une partie de Nim à pile unique, mais vous devez spécifier la taille initiale de la pile (jusqu'à 50 pièces) ainsi que le nombre maximal de pièces. De plus, vous devez indiquer qui doit prélever les pièces de la pile en premier : vous ou l'ordinateur.

Après avoir interrogé l'utilisateur sur les paramètres du jeu Nim, le plateau de jeu, avec les icônes des pièces de la pile, ainsi que celles prises par le joueur et l'ordinateur, s'affiche.

Les lignes 410 à 417 représentent l'« IA » de l'ordinateur (les guillemets sont ici indispensables) ; en utilisant l'opérateur MOD pour rechercher des multiples du nombre maximal de pièces qu'un joueur est autorisé à prendre, plus une pièce supplémentaire, l'ordinateur peut prédire, avec une assez bonne précision, le nombre de pièces à prélever de la pile.

Puisque le Nim à pile unique a été résolu mathématiquement pour chaque permutation possible, il existe plusieurs façons de programmer un adversaire informatique imbattable ; j'ai hésité à le faire dans NIM.BAS, car jouer contre l'ordinateur serait alors devenu un exercice futile.

Alors, que devriez-vous envisager pour améliorer NIM.BAS ?

Étendre le programme pour permettre des parties de Nim à piles multiples est une piste plus fructueuse et plus divertissante.

NIM.BAS

10 KEY OFF:SCREEN 9:COLOR 15,8:CLS
20 PRINT "--- GAME OF SINGLE-PILE NIM ---"
30 PRINT:INPUT"How many coins in the pile (has to be greater than 3 and less than 50)";N
40 IF N<4 OR N>50 THEN 30
50 INPUT"How many coins is the player allowed to take pen turn (must be at least 2)";P
60 IF P<2 OR P>=N THEN 50
70 PLAYER=0:COMPUTERS=0 'Keeps track of total coins taken by players
80 INPUT"Type 1 to go first, or 2 to have the computer go first";FIRST
90 IF FIRST<1 OR FIRST>2 THEN 80
100 'Set up game board
110 CLS
120 PRINT,,"--- GAME OF SINGLE-PILE NIM ---":PRINT
130 PRINT"Each player can take anywhere from 1 to ";P;" coins per turn."
140 PRINT"Player who has to take last coin LOSES the game."
150 PRINT"There are ";N;" coins in the pile:"
155 INCREMENT=630/N:CENTER=INCREMENT
160 FOR X=1 TO N
170 CIRCLE(CENTER,80),5:PAINT(CENTER,80),14,15
180 CENTER=CENTER+INCREMENT
190 NEXT X
200 LOCATE 8,1:PRINT"You have taken ";PLAYER;"coins so far:"
210 CENTER=8
220 FOR X=1 TO PLAYER
230 CIRCLE(CENTER,120),5:PAINT(CENTER,120),14,15
240 CENTER=CENTER+15
250 NEXT X
260 LOCATE 10,1:PRINT"The computer has taken";COMPUTER;" coins so far:"
270 CENTER=8
280 FOR X=1 TO COMPUTER
290 CIRCLE(CENTER,150),5:PAINT(CENTER,150),14,15
300 CENTER=CENTER+15
310 NEXT X
315 IF FIRST=2 THEN FIRST=0:GOTO 400
325 'Human player makes a move
326 IF N<=1 THEN LOCATE 17,20:PRINT"YOU JUST LOST THE GAME. SORRY.":END
330 LOCATE 15,1:INPUT"How many coins do you want to remove from the pile";PREMOVE
340 IF PREMOVE<1 OR PREMOVE>P OR PREMOVE>N THEN 330
350 N=N-PREMOVE
360 PLAYER=PLAYER+PREMOVE
400 'Computer makes a move
405 IF N<=1 THEN LOCATE 17,20:PRINT"YOU DUST WON THE GAME! CONGRATS!":END
410 IF ((N-P) MOD (P+1))=0 THEN CREMOVE=INT(1+(P-1)*RND(1)) ELSE CREMOVE=P
415 IF CREMOVE>N THEN CREMOVE=N-1
417 IF CREMOVE<0 THEN CREMOVE=1
420 LOCATE 17,1:PRINT"Press <ENTER> so the computer can remove the following number of coins: ";CREMOVE;
430 LINE INPUT A$
440 N=N-CREMOVE
450 COMPUTER=COMPUTER+CREMOVE
500 GOTO 100