Jeu de N.I.M. (aussi appelé jeu des allumettes)

Le but de cet exercice est avant tout de manipuler le graphisme; c'est aussi de montrer montrer que l'on peut faire de petits programmes courts, simples... et amusants.

Le jeu

Il se joue à deux. Une configuration de jeu est un ensemble de lignes horizontales composées chacune d'un ensemble de cases. Un coup consiste à retirer un nombre arbitraire strictement positif de cases, mais dans une seule ligne à la fois. Celui qui ne peut plus jouer (parce que la configuration est vide) a perdu. La configuration initiale est arbitraire, mais pour simplifier nous pouvons utiliser la configuration suivante par défaut:
        jeu[0] = 1           X
        jeu[1] = 2           X X
        jeu[2] = 3           X X X
        jeu[3] = 5           X X X X X
        jeu[4] = 7           X X X X X X X 
Le but du programme est de faire gérer les configurations par l'ordinateur, puis de faire jouer l'ordinateur en mode automatique, enfin de le faire jouer au mieux, puisqu'il existe une stratégie gagnante.

Le programme

On s'efforcera de mettre au point le programme de façon progressive. En partant d'un programme élémentaire qui fonctionne, on peut ainsi maintient le programme dans un état cohérent tout en ajoutant de nouvelles fonctionalités.
  1. On commencera par écrire une fonction qui dessine une cellule de coordonnées abstraites (h, v) dans une couleur donnée. Son prototype est
            void dessine_cellule (Pattern c, int h, int v)
    
    Les coordonnées (h, v) sont entières (et petites). La fonction dessine_cellule devra donc tenir compte d'un facteur d'échelle. Le facteur d'échelle est une constante introduite à comme suit (par exemple):
            #define scale 20
    
    Elle peut se contenter des fonctions PenPat, PaintRect, FrameRect (voir annexe) et bien sûr SetRect

    Tester la fonction en dessinant une cellule.

  2. On écrira une fonction qui efface l'écran, par exemple avec EraseRect. Tester la fonction
  3. Corriger la fonction suivante pour qu'elle récupère un clique à la souris et retourne les coordonnées (h,v) en tenant compte de l'échelle.
            void selectionne (int* h, int* v)
            {
              Point p;
              GetClick (&p);
              *v = p.v;
              *h = p.h;
              return;
            }
    

    Tester en écrivant une fonctionne qui affiche les cases sélectionnées à la souris.

  4. On fait les déclarations suivantes:
    #define TAILLE_MAX 7
    #define CELL_MAX 13
    
    static int taille;
    static int jeu [TAILLE_MAX];
    
    Expliquer-les.
  5. Un état du jeu est défini par les variables taille et les valeurs de jeu. Écrire une procédure qui remplit la configuration par défaut.

    Écrire une procédure qui affiche une configuration quelconque.

    Tester

  6. Écrire une procédure qui teste si un clique est valide.
  7. Écrire une procédure qui teste si le jeu est vide (plus de case).
  8. Écrire une procédure qui grise les cases valides à droite d'une case donnée, et invalide les case grisés.

    (On pourra griser les cases en gis clair et gris foncé seleon le joueur, le joueur êtant défini par une variable globale).

  9. Ecire une procédure jouer_un_clique fait joueur l'utilsateur (en lui demandant un clique)
  10. Écrire une procédure jouer_au_hasard qui joue au hasard.
  11. Faire en sorte que le programme permette de jouer contre la machine en en la faisant jouer au hasard.

La stratégie gagnante

Pour certaines positions initiales, il existe une stratégie gagnante pour le jeu de Nim qui. Cela signifie que quelquesoit le coup adverse, on peut jouer à un son tour un coup qui ramène dans une position gagnante. En continuant jusqu'à la fn de la partie, on est assuré de gragner. L'intérêt est de trouver cette stratégie (des indications pourront vous être données), puis de l'implémenter par une procédure jouer_avec_intelligence qui sélectionne le coup gagnant lorsque le joueur se trouve dans une position gagnante. Bien sûr, cette procédure devra quand même jouer lorsque le joueur n'est pas dans une position gagnante, et si possible dissimuler sa stratégie... On pourra définir une procédure
jouer
qui prend un entier en argument indiquant le niveau de difficulté désiré, en fonction de ce niveau, elle pourra jouer au hasard, ou jouer avec intelligence, (on obtiendra un meilleur effet en prenant en compte la taille du jeu: plus le jeu est petit, plus on jouera avec intelligence).

Il ne vous reste plus qu'à impressionner vos camarades des autres groupes avec votre programme. Mais, attention aux bugs, qui n'apparaissent souvent que dans les démos.

Cliquez pour récupérer la solution nim.c (temporairement inaccessibles...). Évidemment, la procédure pour jouer avec intelligence est laissée à votre imagination.