Le morpion à trois pions

Pour expliquer la programmation des jeux de réflexion, nous allons d'abord décrire la méthode, puis nous allons l'appliquer.

Nous allons commencer par des jeux très simples, ensuite nous attaquerons des jeux plus difficiles et plus complexes.

Le premier exemple étudié ici est le jeu du morpion qui se joue ici sur un échiquier de 3 sur 3. Le jeu se joue à deux. Chaque joueur pose une pièce sur l'échiquier puis laisse son adversaire poser sa pièce (d'habitude, les pions sont 'X' et 'O'); celui qui réussi à aligner 3 de ses pions en ligne, colonne ou diagonale, a gagné.

Lorsque deux hommes s'affrontent dans un jeu de réflexion, chacun essaie de prévoir le coup de l'adversaire, ou même plusieurs coups à l'avance. Nous allons appliquer la même méthode ici.

La méthode générale pour faire jouer un ordinateur comme un humain est la suivante :

- on décide jusqu'à quelle profondeur on prévoit les coups de l'adversaire

- on simule un coup de l'ordinateur par les étapes suivantes :

- on mémorise l'échiquier dans un tableau auxiliaire

- on parcourt l'échiquier jusqu'à trouver une case disponible où on pourrait poser un pion

- on pose le pion

- on simule un coup du joueur en faisant les mêmes étapes, ensuite on simule un coup de l'ordinateur et ainsi de suite jusqu'à ce qu'on ait atteint le niveau maximum de profondeur fixé au départ

- on évalue la position par une fonction d'évaluation (c'est ce qu'il y a de plus difficile à faire dans un jeu de réflexion)

- en fonction de la note renvoyée par la fonction d'évaluation on décide quel coup on va jouer

Nous allons étudier quelques cas simples pouvant apparaître pendant une partie du jeu de morpion, pour mieux comprendre comment appliquer la stratégie décrite ci-dessus.

On sait que dans un jeu de morpion à 3 pions on a trois possibilités : soit on gagne, soit on fait match nul, soit on perd.

Donc la fonction d'évaluation est très facile à faire pour ce jeu : si on a trois pions alignés on a gagné, si aucun des deux joueurs n'a trois pions alignés alors c'est un match nul, si l'adversaire a trois pions alignés alors on a perdu.

Ici on décide qu'on va descendre jusqu'au niveau 9, c'est à dire qu'on va simuler des coups jusqu'à ce que l'échiquier soit rempli, car cela ne demande pas trop de temps, vu sa taille.

C'est pour cette même raison que l'ordinateur va parcourir tous les coups possibles de l'échiquier et ne choisira que ceux qui le donnent gagnant à coup sûr et si cela est impossible, alors il choisira un coup qui lui rapporte le match nul.

Soit le cas suivant :

A B C A B C A B C

+-----+ +-----+ +-----+

1¦X¦ ¦ ¦ L'ordinateur 1¦X¦ ¦O¦ Le joueur 1¦X¦ ¦O¦ et on voit

+-+-+-¦ joue en C1; +-+-+-¦ joue en A3; +-+-+-¦ facilement

2¦ ¦O¦ ¦ 2¦ ¦O¦ ¦ 2¦ ¦O¦ ¦ qu'il gagne.

+-+-+-¦ +-+-+-¦ +-+-+-¦

3¦ ¦ ¦X¦ 3¦ ¦ ¦X¦ 3¦X¦ ¦X¦

+-----+ +-----+ +-----+

Ces deux coups ont été faits par simulations successives en mémoire; on n'a que deux coups car le premier échiquier représente la situation en cours.

Avant de jouer en C1, l'ordinateur a déjà exploré l'arbre qui résulte de B1;on est passé au coup C1 juste pour l'exemple, de même que pour A3. A partir du dernier échiquier, l'ordinateur va encore explorer quelques coups en profondeur, car nous, nous voyons que les X ont gagné, mais lui, il ne sait pas voir ! C'est pourquoi il faut encore simuler des coups jusqu'à ce que les X aient trois pions alignés.

Néanmoins, on sait que le coup A3 est excellent pour le joueur, et que l'ordinateur ne peut pas l'empêcher de gagner; ceci indique que le coup précédent simulé par l'ordinateur (à savoir C1) est mauvais. Il faut donc qu'il essaie un autre coup parmi les restants pour gagner, ou faire match nul dans le pire des cas.

Nous allons commencer par analyser le programme du morpion. On distingue 2 parties :

- une partie graphique (représentation de l'échiquier, possibilité de cliquer avec la souris afin de poser son pion sur l'échiquier...)

- une partie de simulation, où a lieu la mise en oeuvre de la réflexion, la simulation des coups par ordinateur, l'évaluation...

La première partie ne sera pas décrite ici, l'essentiel étant la réflexion.

Voyons la deuxième partie :

- la fonction d'évaluation d'abord, qui est très facile à faire dans ce cas : on représente en mémoire les X par 1 (JOUEUR dans le programme) et les O par -1 (ORDINATEUR dans le programme) ensuite on fait une fonction qui calcule la somme des lignes, des colonnes et des diagonales et si elle trouve à un moment une de ces sommes égale à 3 ou -3 alors c'est que soit le joueur, soit l'ordinateur, a aligné 3 pions. Cette fonction s'appelle note1 dans le programme.

- on a dans ce programme une deuxième fonction d'évaluation, qui fait appel à la première; cette fonction s'appelle note2. Elle est utilisée justement dans des cas spéciaux comme le suivant :

A B C

+-----+

1¦X¦ ¦X¦ C'est aux X de jouer; ils ont deux possibilités de

+-+-+-¦ gagner, donc ils sont gagnants quoiqu'il arrive; il est

2¦O¦O¦ ¦ donc inutile de descendre dans l'arbre de simulation des

+-+-+-¦ coups; la réflexion s'arrête ici, de cette manière on gagne

3¦O¦ ¦X¦ du temps, ce qui est très important dans un jeu de réflexion.

+-----+

- on a dans ce programme une fonction qui s'appelle coup obligatoire; elle est utilisée dans certains cas comme :

A B C

+-----+

1¦X¦O¦X¦ C'est aux X de jouer; ils ont cinq coups à disposition

+-+-+-¦ A2, C2, A3, B3, C3.

2¦ ¦O¦ ¦ Mais ici, il est inutile d'explorer tous les coups, car on

+-+-+-¦ voit qu'il n'y a qu'une case que les X doivent occuper obli-

3¦ ¦ ¦ ¦ gatoirement : B3, pour empêcher les O de gagner. Donc, grâce

+-----+ à cette fonction on gagne aussi du temps pendant la réflexion.

- nous avons enfin la procédure qui représente le coeur du programme, elle s'appelle "jeu"; cette procédure a plusieurs paramètres - nous verrons plus loin pourquoi et quelle est la signification de chacun de ceux-ci -.

Dans cette procédure nous allons simuler des coups, faire des évaluations et comparer la valeur des coups. Commençons par la simulation de coups : sachant que "t" est l'échiquier (tableau à deux dimensions) on simule un coup par l'instruction : "t[ligne,colonne]:=JOUEUR" ou par l'instruction : "t[ligne,colonne]:=ORDINATEUR"; ceci implique qu'il faudrait avoir deux procédures, une qui simule les coups du joueur et l'autre qui simule les coups de l'ordinateur; c'est pour cette raison qu'on a décidé d'initialiser les constantes : "JOUEUR = +1;ORDINATEUR = -1 ".Ainsi, on n'a plus qu'une seule procédure qui admet un paramètre "coef" initialisé une fois à "1" et une fois à "-1"; de cette façon l'instruction décrite ci-dessus "t[ligne,colonne]:=ORDINATEUR" devient l'instruction suivante : "t[ligne,colonne]:=JOUEUR*coef" avec coef=-1; car "JOUEUR*coef=-JOUEUR" et "-JOUEUR=ORDINATEUR".Il fallait donc choisir les valeurs de JOUEUR et ORDINATEUR symétriques par rapport à zéro. Pour annuler un coup, on fait simplement "t[ligne,colonne]:=PERSONNE", sachant que "PERSONNE=0" et qu'au début de la partie, tout l'échiquier est vide, rempli de 0 (donc "PERSONNE").

Etudions un peu la façon de noter et de renvoyer les notes. Supposons qu'on soit au niveau 6, par exemple. Supposons que c'est à l'ordinateur de jouer et qu'il joue un coup qui lui permet de gagner. Alors, il renvoie au niveau 5 une note égale à MAUVAIS pour indiquer au joueur que son coup était mauvais et qu'il doit en essayer un autre; donc il ne faut pas remonter au niveau 4 pour indiquer à l'ordinateur que le joueur perd et que le coup joué par l'ordinateur au niveau 4 est bon; pour cela, on utilise une variable dans le nom de la procédure "jeu"; cette variable s'appelle "remonte". Etant donné qu'on a une seule procédure pour renvoyer les notes "BON" et "MAUVAIS", on utilise le même système que ci-dessus : on initialise BON à une valeur positive et MAUVAIS à l'opposé de BON, de cette façon on a BON*coef=MAUVAIS avec coef=-1. n aurait pu choisir une autre valeur que 1 (ce choix est complètement arbitraire).

Le dernier paramètre de la procédure est "niveau" qui indique à quel niveau de profondeur on est dans la réflexion, qui est incrémenté à chaque appel récursifs de la procédure.

Voyons un peu maintenant les grandes lignes de cette procédure; nous allons faire cela à partir de situations réelles :

A B C

+-----+

1¦X¦O¦ ¦ C'est aux X de jouer; ils ont cinq coups à disposition

+-+-+-¦ C1, C2, A3, B3, C3.

2¦X¦O¦ ¦ Mais ici, il est inutile d'explorer tous les coups, car on

+-+-+-¦ voit que les X doivent jouer en A3 pour gagner; la première

3¦ ¦ ¦ ¦ chose qu'on fait est donc de voir si les X n'ont pas un coup

+-----+ obligatoire à jouer pour prendre l'avantage.

Si tel n'était pas le cas, alors il faut envisager un coup obligatoire pour bloquer l'adversaire.

Supposons qu'un de ces deux cas apparaît; on doit donc jouer un coup qui est obligatoire (soit pour gagner, soit pour bloquer) :

- s'il y en a un, alors on simule le coup en posant un X et :

- on vérifie si le JOUEUR a gagné (en faisant un appel à la fonction "note1";si c'est le cas, on annule le coup du joueur en posant un zéro sur l'échiquier et on renvoie au niveau précédent la note "MAUVAIS" pour indiquer à l'ordinateur que son coup était mauvais, étant donné qu'il a permis au joueur de gagner

- on vérifie si l'ORDINATEUR n'a pas 2 possibilités de gagner, auquel cas on sort de la procédure, car de toutes façons, on ne peut pas le bloquer, et dans ce cas, on renvoie la note "BON" pour indiquer à l'ordinateur que son coup était bon, étant donné qu'il lui a permis de gagner

- si aucun de ces 2 cas ne se présente, alors on appelle récursivement la procédure "jeu", pour continuer la simulation..

- s'il n'y en a aucun, alors on commence à explorer les cases une par une et simuler les coups :

- on pose un "X" ou "O" sur l'échiquier

- on évalue la situation de l'échiquier par un appel à "note1"

- la note a la valeur "BON" : dans ce cas on annule le coup et on renvoie au niveau précédent la valeur "MAUVAIS"

- la note a la valeur "MOYEN" : on fait un appel récursif pour savoir qui va gagner dans les coups suivants et suivant la valeur de la note reçue on sort de la procédure en cours ou on reste (si on reste alors c'est que le coup a engendré soit un match nul, soit une victoire pour l'adversaire. Il faut donc explorer les autres coups, pour essayer de gagner ou de faire match nul

- la note a la valeur "MAUVAIS" : on annule le coup et on continue d'explorer les coups restants.

Si on a exploré tous les coups et qu'ils engendrent tous une défaite, alors il faut renvoyer une note défavorable (ou favorable) au niveau du dessus.

const BON = +1;
 MOYEN = 0;
 MAUVAIs = -1;
 ORDINATEUR = -1;
 JOUEUR = +1;
 PERSONNE = 0;
 
var t: array[0..2, 0..2] of integer;
 meilleur_coup: integer;
 le_niveau: integer;
 
function note1(j: integer): integer;
var f: array[0..7] of integer;
 i: integer;
begin
 f[0] := t[0, 0] + t[0, 1] + t[0, 2]; f[1] := t[1, 0] + t[1, 1] + t[1, 2];
 f[2] := t[2, 0] + t[2, 1] + t[2, 2]; f[3] := t[0, 0] + t[1, 0] + t[2, 0];
 f[4] := t[0, 1] + t[1, 1] + t[2, 1]; f[5] := t[0, 2] + t[1, 2] + t[2, 2];
 f[6] := t[0, 0] + t[1, 1] + t[2, 2]; f[7] := t[0, 2] + t[1, 1] + t[2, 0];
 note1 := BON; j := 3 * j;
 for i := 0 to 7 do
 if f[i] = j then exit; //--- on quitte avec la valeur "bon"
 note1 := MOYEN;
end;
 
function note2(j, nb: integer): integer;
var x, y, note, nb_coups: integer;
begin
 note2 := BON;
 nb_coups := 0;
 for x := 0 to 2 do
 for y := 0 to 2 do
 if t[x, y] = PERSONNE then
 begin
 t[x, y] := j;
 note := note1(j);
 if note = BON then inc(nb_coups);
 t[x, y] := PERSONNE;
 if nb_coups = nb then exit; //--- on quitte avec la valeur "bon"
 end;
 note2 := MOYEN;
end;
 
function coup_obligatoire(j: integer): integer;
var x, y, note: integer;
begin
 coup_obligatoire := -1;
 for y := 0 to 2 do
 for x := 0 to 2 do
 if t[x, y] = PERSONNE then
  begin
 t[x, y] := j; note := note1(j); t[x, y] := PERSONNE;
 if note = BON then
 begin
 coup_obligatoire := y * 10 + x;
 exit;
 end;
 end;
end;
 
procedure jeu(coef, niveau: integer; var note, remonte: integer);
var x, y, z, nb: integer;
 la_note: integer;
 monte: integer;
 nb_poss, nb_notes: integer;
begin
 note := MOYEN;
 remonte := 0;
 if niveau = 9 then
 note := note1(JOUEUR * coef)
 else
 begin
 z := coup_obligatoire(JOUEUR * coef); nb := 1;
 if z = -1 then
 begin
 z := coup_obligatoire(ORDINATEUR * coef);
 inc(nb);
 end;
 if z >= 0 then
 begin
 y := z div 10;
 x := z mod 10;
 t[x, y] := JOUEUR * coef;
  if note1(JOUEUR * coef) = BON then
 begin t[x, y] := PERSONNE; note := MAUVAIS * coef; exit; end;
 if note2(ORDINATEUR * coef, nb) = BON then
 begin t[x, y] := PERSONNE; note := BON * coef; exit; end;
 jeu(-coef, niveau + 1, note, monte);
 t[x, y] := PERSONNE; remonte := 0;
 end
 else
 begin
 nb_poss := 0; nb_notes := 0;
 for y := 0 to 2 do
 for x := 0 to 2 do
 if t[x, y] = PERSONNE then
 begin
 t[x, y] := JOUEUR * coef; inc(nb_poss);
 case note1(JOUEUR * coef) of
 BON: begin
 t[x, y] := PERSONNE; note := MAUVAIS * coef;
 exit
 end;
 MOYEN: begin
  jeu(-coef, niveau + 1, la_note, monte);
 case coef of
 +1: begin
 if la_note > MOYEN then inc(nb_notes);
 if (la_note < MOYEN) and (monte < 1) then
 begin
 t[x, y] := PERSONNE; note := la_note;
 inc(remonte);
 exit;
 end;
 end;
 -1: begin
 if la_note < MOYEN then inc(nb_notes);
 if (la_note > MOYEN) and (monte < 1) then
 begin
 t[x, y] := PERSONNE; note := -la_note;
 inc(remonte);
  exit;
 end;
 end;
 end;
 end;
 end;
 t[x, y] := PERSONNE;
 end;
 if (nb_notes > 0) and (nb_notes = nb_poss) then
 note := coef * BON;
 end;
 end;
end;
 
procedure coup_ordinateur;
var x, y, coup: integer;
 la_note: integer;
 monte: integer;
begin
 coup := -1; inc(le_niveau);
 meilleur_coup := -1;
 for y := 0 to 2 do
 for x := 0 to 2 do
 if t[x, y] = PERSONNE then
 begin
 t[x, y] := ORDINATEUR;
 case note1(ORDINATEUR) of
 BON: begin
 t[x, y] := PERSONNE;
 meilleur_coup := y * 10 + x;
 exit;
 end;
 MOYEN: begin
 jeu(1, le_niveau, la_note, monte);
 t[x, y] := PERSONNE;
 case la_note of
 MAUVAIS: if meilleur_coup = -1 then meilleur_coup := y * 10 + x;
 MOYEN: meilleur_coup := y * 10 + x;
  BON: begin
 meilleur_coup := y * 10 + x;
 exit;
 end;
 end;
 end;
 end;
 t[x, y] := PERSONNE;
 end;
end;
 
 
procedure tform1.nouveau_jeu;
var x, y: integer;
begin
 le_niveau := 0;
 with image1.picture.bitmap.canvas do
 begin
 brush.style := bsSolid; brush.color := clWhite;
 rectangle(0, 0, 90, 90);
 rectangle(30, 0, 60, 90);
 brush.style := bsClear; //---- utilisé pour l'écriture des "x" et "o"
 rectangle(0, 30, 90, 60);
 for x := 0 to 2 do
 for y := 0 to 2 do
 t[x, y] := 0;
 end;
end;
 
procedure tform1.affiche_jeu;
var x, y: integer;
begin
 for x := 0 to 2 do
 for y := 0 to 2 do
 if t[x, y] = JOUEUR then image1.picture.bitmap.canvas.textout(x * 30 + 8, y * 30 + 8, 'X')
 else
 if t[x, y] = ORDINATEUR then image1.picture.bitmap.canvas.textout(x * 30 + 8, y * 30 + 8, 'O');
end;
 
procedure TForm1.Image1MouseMove(Sender: TObject; Shift: TShiftState; X,
 Y: Integer);
begin
 x := x div 30; if x > 2 then x := 2;
 y := y div 30; if y > 2 then y := 2;
 edit1.text := 'X=' + inttostr(1 + x) + '; Y=' + inttostr(1 + y);
end;
 
procedure TForm1.Image1MouseDown(Sender: TObject; Button: TMouseButton;
 Shift: TShiftState; X, Y: Integer);
begin
 if le_niveau > 8 then
 exit;
 button3.hide;
 x := x div 30; if x > 2 then x := 2;
 y := y div 30; if y > 2 then y := 2;
 if t[x, y] <> 0 then
 begin
  showMessage('Case déjà occupée !');
 exit;
 end;
 t[x, y] := JOUEUR;
 affiche_jeu;
 inc(le_niveau);
 if le_niveau < 9 then coup_ordinateur;
 y := meilleur_coup div 10;
 x := meilleur_coup mod 10;
 t[x, y] := ORDINATEUR;
 affiche_jeu;
 if note1(ORDINATEUR) = BON then
 begin
 showMessage('J''ai gagné !');
 le_niveau := 9;
 exit;
 end;
 if note1(JOUEUR) = BON then
 begin
 showMessage('Vous avez gagné !');
 le_niveau := 9;
 exit;
 end;
 if le_niveau = 9 then showMessage('Match nul !');
end;

Télécharger le code source Delphi