Un jeu en LOGOPLUS:

 

            le jeu de Nim.  

    (quelques conseils pour les futurs candidats au jeu de fort Boyard)

 

Objectifs pédagogiques: Reconnaître un nombre pair ou impair. Appliquer la division   
                                       Euclidienne. Calculer le reste d'une division Euclidienne.

Sans doute avez-vous déjà regardé au moins une fois le jeu télévisé intitulé "Fort Boyard" qui est diffusé régulièrement chaque été depuis plusieurs années. Au cours de leurs épreuves, les candidats doivent passer dans la salle des maîtres du temps où de nombreux défis les attendent, dont celui de l'épreuve des bâtonnets. Chaque joueur doit retirer à son tour un, deux ou trois bâtonnets. Celui qui retire le dernier bâtonnet a perdu. Simple ? Pas si sûr que cela, et de nombreux candidats en ont fait les frais. Très ancien, ce jeu des bâtonnets est aussi connu sous le nom de "jeu de Nim" ( tiré du participe passé du verbe allemand nehmen (nim) qui signifie prendre) et le nombre de bâtonnets peut d'ailleurs varier. Il y a vingt bâtonnets dans le célèbre jeu télévisé et il était très tentant de programmer cette épreuve en LOGO et LOGOPLUS l'a bien réalisé. Voyez plutôt:

Comment donner du fil à retordre au joueur adverse ?

Les candidats malheureux à ce jeu évoquent souvent le hasard, ou le fait d'avoir commencé en premier. Hélas, le hasard n'a rien à faire dans la partie et le fait de commencer serait plutôt un avantage. Alors, que faut-il faire pour sinon gagner à ce jeu, au moins ne pas rendre la partie facile au maître du temps ?

Tout d'abord, la chose essentielle que beaucoup de joueurs oublient de faire: savoir compter !

1ère règle: compter le nombre de bâtonnets au début du jeu.

Si on a le trait et que le nombre de bâtonnets est pair, tirer un nombre impair de bâtonnets, ce qui aura pour effet de laisser un nombre impair de bâtonnets au joueur adverse au coup suivant (configuration n+1).

Si on a le trait et que le nombre de bâtonnets est impair, tirer en revanche un nombre pair de bâtonnets. L'adversaire aura de ce fait là encore un nombre impair de bâtonnets à réduire.

On l'a compris: il faut coûte que coûte laisser un ensemble ( ou configuration ) impair de bâtonnets à l'adversaire. Seule précaution à observer à la fin du jeu: ne pas aller trop vite pour ne pas laisser au  joueur adverse l'occasion de rétablir la parité de cet ensemble, ce qui aurait pour résultat de vous laisser un nombre impair de bâtonnets au tour suivant.

D'où la deuxième règle:

Si le joueur adverse retire deux bâtonnets, retirer également deux bâtonnets.

Si le joueur adverse retire un nombre impair de bâtonnets (1 ou 3), retirer également un nombre impair de bâtonnets.

Cette règle strictement observée au cours de la partie garantit la non-parité de la configuration des bâtonnets pour le joueur adverse. Elle se programme facilement grâce à l'opération modulo, qui consiste à calculer le RESTE d'une division Euclidienne. LOGOPLUS sait très bien le faire grâce à cette primitive.

Il reste finalement une troisième règle, de prudence, qui s'applique en fin de partie:

Troisième règle:

Eviter d'avoir en face de soi une configuration de 5 bâtonnets. Les deux précédentes règles doivent faciliter cet évitement mais on verra que le chiffre 5 est véritablement néfaste pour le joueur qui doit sélectionner des bâtonnets dans cette configuration (il a, sauf maladresse du joueur adverse, perdu la partie).

Voici donc l'exemple d'une partie qui applique ces trois règles:

Nombre initial de bâtonnets: 20. Le joueur n°1 a le trait.

                   nombre de bâtonnets retirés:               configuration restante:

joueur n°1                  3                                                20 - 3 = 17

joueur n°2                 2                                                17 -2= 15
     (le joueur n°2 essaie d'obtenir un nombre total impair de bâtonnets pour le joueur n°1.)

joueur n°1                2 (deuxième règle)                          15-2= 13

joueur n°2               1                                                    13-1=12

joueur n°1               3                                                    12-3= 9
     (le joueur n°1 essaie d'obtenir un nombre total impair de bâtonnets pour le joueur n°2.)
 
joueur n°2              3                                                    9-3=6
      (Attention: on approche de l'application de la troisième règle !) 

joueur n°1            1                                                       6-1= 5

        A ce stade du jeu, le joueur n°2 a de fortes "malchances" de perdre, car:

5-1=4 (joueur n°2 retire un bâtonnet) puis 4-3=1 (joueur n°1 retire 3 bâtonnets)
ou:
5-2=3 (joueur n°2 retire 2 bâtonnets) puis 3-2=1 (joueur n°1 retire 2 bâtonnets)
ou:
5-3=2 (joueur n°2 retire 3 bâtonnets) puis 2-1=1 (joueur n°1 retire un bâtonnet)    
        
Dans les trois cas, il reste un bâtonnet en face du joueur n°2, qui a donc perdu la partie.
La suite des nombres obtenus lors de cette partie est:
(17, 15, 13, 12, 9, 6, 5 et au choix: 4, 3, 1)
                                            ou:  3, 2, 1)
                                           ou:   2, 1, 1)

Remarquons que ce jeu, à l'instar de la conjecture de Syracuse,

construit une suite de nombres qui se termine toujours par 1.

Ces trois règles étant à présent données et qui permettent à un joueur humain qui les respecte scrupuleusement d'avoir des chances de gagner, il faut faire de telle manière que l'ordinateur puisse réagir correctement aux configurations (nombre total de bâtonnets ) laissées par le joueur humain.

L'algorithme proposé est simple et il a l'avantage de mettre en évidence une opération mathématique. Il en existe d'autres qui font appel à des techniques heuristiques et rien n'empêche aux plus téméraires de s'essayer à en trouver un.

Donc, puisque le but de l'ordinateur est également de gagner, il faut chercher à faire en sorte qu'il laisse au joueur humain une configuration impaire de bâtonnets dans laquelle il sélectionnera ses bâtonnets.

Intéressons nous d'abord de savoir si la configuration est paire ou impaire. Une division par 2 nous indiquerait le résultat mais puisque le nombre maximum de bâtonnets à retirer à chaque coup est au plus égal à 3, il est plus judicieux de diviser par 4. 

En effet:

1/4=0 reste 1 (configuration impaire)  remarque: 3 - 1 = 2 
                                                          (configuration paire laissée à l'adversaire)  
2/4=0 reste 2 (configuration paire)  remarque: 3 - 2 = 1
                                                         (configuration impaire laissée à l'adversaire)  
3/4=0 reste 3 (configuration impaire)  remarque: 3 - 3 = 0 (changé en 2)
                                                         (configuration paire laissée à l'adversaire)  
4/4=1 reste 0 (configuration paire)  remarque: 3 - 0 = 3
                                                         (configuration impaire laissée à l'adversaire)  

Exemple:

Si l'ordinateur se trouve en face d'une configuration de 12 bâtonnets, il calcule que:

12/4=3 reste 0 (configuration paire)

La configuration est paire et en choisissant un nombre impair de bâtonnets à retirer, il garde l'avantage, d'où la nécessité de soustraire ce reste à 3, avec un petit test supplémentaire si ce reste est nul.

Cela se traduit en LOGO par ces quelques lignes:

DONNE "coup 3- RESTE :nbâtons 4

/* L'ordinateur laisse au joueur adverse une configuration impaire au prochain coup.*/

TESTE :coup = :nbâtons
SIVRAI  DONNE "coup :coup -1
SIFAUX SI :coup = 0 DONNE "coup 1
DONNE "nbâtons :nbâtons - :coup

Les autres lignes du programme sont consacrées au graphisme et à éviter qu'un bâtonnet ne soit sélectionné plusieurs fois. L'utilisation des listes de coordonnées est ici indispensable.

Remarque: 

En changeant la ligne:
 
DONNE "coup 3- RESTE :nbâtons 4
par:
 
DONNE "coup RESTE :nbâtons 4

on favorise le joueur humain puisque l'ordinateur ne laissera plus de configurations impaires au coup suivant.

Voici maintenant un texte-programme en LOGO de ce jeu que vous pouvez télécharger en cliquant ici  et également un autre en cliquant ici  ou ici .

                                     

POUR localisebâtons
TRAIT 1 EFF FCFG MARRON EFFTXT CT TRAIT 1
DONNE "longueur ENTIER ((:nbâtons * 18) -6 )/2
DONNE "x -:longueur
FPOS :x (-25)
SEGMENT [117 (-190)] [197 (-190) ]
SEGMENT [197 (-190)] [197 (-220) ]
SEGMENT [197 (-220)] [117 (-220)]
SEGMENT [117 (-220)] [117 (-190)]
COLORIE [ 118 (-200) ] JAUNE
TAILLELETTRE 12
DESSINETEXTE [ 123 (-198) 0 ] [ suivant >> ]
TRAIT 12 FCC BLANCHE
REPETE :nbâtons [ DONNE "listex PH :listex :x AV 50 DONNE "x :x + 18 FPOS :x (-25) ]
sélectionnebâton 1 /* le joueur humain commence la partie. */
FIN
 
POUR sélectionnebâton :joueur
TESTE :joueur = 1
SIVRAI [ /* 1: humain */
               DONNE "nchoix 0 DONNE "arrêt FAUX
              TANTQUE (:nchoix < 3 ) ET ( :arrêt = FAUX ) [ /* 2 */
              TESTE SURECRAN?
              SIVRAI [ /* 3 */
                          TESTE CLIC?
                            SIVRAI [ /* 4 */
                                       TESTE (( SOURISY > (-25)) ET ( SOURISY < 25 ))
                                               SIVRAI [ /* 5 */
                                                   DONNE "rang 1 DONNE "trouvé FAUX
                             TANTQUE ( :rang <= CARD :listex ) ET ( :trouvé = FAUX ) [ /* 6 */
                                            TESTE NOMBRE? ITEM :listex :rang
                                                  SIVRAI [ /* 7 */
 TESTE (( SOURISX > (( ITEM :listex :rang ) -6 )) ET
          ( SOURISX < (( ITEM :listex :rang ) +6 )))
                                                       SIVRAI DONNE "trouvé VRAI
                                                       SIFAUX DONNE "rang :rang + 1
                                                           ] /* -7 *
                                     SIFAUX DONNE "rang :rang + 1
                                                                                                                                                                                                            ] /* -6 */
                                                                   SI ( :trouvé = VRAI ) [ /* 6 */
                                                                    DONNE "x ITEM :listex :rang
                                                                         DONNE "y -25
                                                                              REPETE 70 [ /* 7 */
                                       FCC MARRON SEGMENT [ :x :y ] [ :x (:y + 50 ) ]
                                                                        DONNE "y :y - 1
                                                FCC BLANCHE SEGMENT [ :x :y ] [ :x (:y + 50 ) ]
                                                                                             ] /* -7 */
                                                  TRANSFORME :rang TRANSFORME :rang
                                                            REMPLACE :listex "X :rang
                                                              DONNE "nchoix :nchoix + 1
                                                              DONNE "nbâtons :nbâtons - 1
                                   SI ((:nchoix > 3 ) OU (:nbâtons = 0 )) DONNE "arrêt VRAI
                                                                                          ] /* -6 */
                                                                              ] /* -5 */
                                                           SIFAUX [ /* 5 */
                                          TESTE (( SOURISY > (-190)) ET ( SOURISY < (-220)))
                                                                           SIVRAI [ /* 6 */
                                        SI (:nchoix > 0 ) ET
                                           (( SOURISY < (-190)) ET ( SOURISY > (-220 ))) ET
                                           (( SOURISX > 117 ) ET ( SOURISX < 197 )) 
                                                                            DONNE "arrêt VRAI
                                                                                        ] /* -6 */
                                                                             ] /* -5 */
                                                   SIFAUX [ /* 5 */
                                  SI (:nchoix > 0 ) ET
                                     (( SOURISY < (-190)) ET ( SOURISY > (-220 ))) ET
                                     (( SOURISX > 117 ) ET ( SOURISX < 197 )) 
                                                                           DONNE "arrêt VRAI
                                                                  SIVRAI DONNE "arrêt VRAI
                                                             ] /* -5 */
                                                                         ] /* -4 */
                           ] /* -3 */
                                             SI ( :nbâtons = 1 ) ECL [ Bravo, tu as gagné ! ]
                                                                                              ] /* -2 */
                                             DONNE "joueur 2
           ] /* -1 */
SIFAUX [ /* 1: ordinateur */
                  DONNE "coup 3 - RESTE :nbâtons 4 /* Elle est là " l'astuce " !... */
                         TESTE :nbâtons = :coup
                         SIVRAI DONNE "coup :coup - 1
                         SIFAUX SI :coup = 0 DONNE "coup 2
                           DONNE "nbâtons :nbâtons - :coup
                REPETE :coup [ /* 2 */
                                 DONNE "listechoix []
                                    REPETE CARD :listex
          SI NOMBRE? ( ITEM :listex BOUCLE ) DONNE "listechoix PH :listechoix BOUCLE
                                    TESTE NON VIDE? :listechoix
                                         SIVRAI [ /* 3 */
                                                          FIXEHASARD 1 CARD :listechoix
                                                          DONNE "pos HASARD 
                                            DONNE "x ITEM :listex ITEM :listechoix :pos
                                                          DONNE "pos ITEM :listechoix :pos
                                                          TRANSFORME :pos TRANSFORME :pos
                                                          REMPLACE :listex "X :pos
                                                          DONNE "y 25
                                                  REPETE 70 [ /* 4 */
                                 FCC MARRON SEGMENT [ :x :y ] [ :x (:y - 50 ) ]
                                                                  DONNE "y :y +1
                                 FCC BLANCHE SEGMENT [ :x :y ] [ :x (:y - 50 ) ]
                                                               ] /* -4 */
                                                      ] /* -3 */
                                      ] /* -2 */
                              TESTE ( :nbâtons = 1 )
                                 SIVRAI ECL [ L'ordinateur a gagné ! ]
                                 SIFAUX ECL [ A toi de jouer. ]
                             DONNE "joueur 1
              ] /* -1 */
                     SI (:nbâtons > 1 ) sélectionnebâton :joueur
FIN
 
DONNE "nbâtons 20 DONNE "listex []
localisebâtons

Haut de page >>

Retourner à la page d'accueil >>

Rückkehr >>