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.
-
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.
-
On écrira une fonction qui efface l'écran, par exemple avec EraseRect.
Tester la fonction
-
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.
-
On fait les déclarations suivantes:
#define TAILLE_MAX 7
#define CELL_MAX 13
static int taille;
static int jeu [TAILLE_MAX];
Expliquer-les.
-
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
-
Écrire une procédure qui teste si un clique est valide.
-
Écrire une procédure qui teste si le jeu est vide (plus de case).
-
É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).
-
Ecire une procédure jouer_un_clique
fait joueur l'utilsateur (en lui demandant un clique)
-
Écrire une procédure jouer_au_hasard qui joue au hasard.
-
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.