Cours sur la récursivité
Date de publication : avril 2005 , Date de mise à jour : octobre 2009
IX. Les jeux de réflexion
IX-A. Le morpion à trois pions
IX-B. Le jeu d'Othello
IX. Les jeux de réflexion
IX-A. 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;
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;
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;
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;
|
IX-B. Le jeu d'Othello
Un jeu assez répandu est le jeu d'Othello. Nous allons nous intéresser ici à la manière de programmer ce jeu. Nous allons décrire et expliquer par des exemples la manière classique de programmer le jeu d'Othello, et nous allons ensuite l'appliquer pour réaliser le programme. Pour faciliter l'explication nous commencerons par un exemple de fin de partie.
L'avantage des fins de jeu est le suivant : la fonction d'évaluation d'un coup est très facile à réaliser, car elle consiste à faire le décompte des pions. Celui qui a le plus de pions après le dernier coup a gagné. Par contre, en début ou milieu de partie cette fonction est beaucoup plus difficile à réaliser, car il faut tenir compte du nombre de pions, de la valeur des cases (certaines cases ont une importance plus grande que d'autres, comme les coins), de la position des pions à un instant t... Il faudrait donc avoir l'avis d'un spécialiste de l'Othello.
Description des données et des procédures
Le plateau du jeu d'Othello sera un tableau à une dimension; ce tableau aura 100 cases et sera numéroté de 0 à 99. Ainsi, les cases du plateau seront 11, 12,...,18, 21,...,28,... jusqu'à 81,...,88. Le tableau de jeu s'appelle work, mais, pendant la réflexion, comme on va à plusieurs niveaux de profondeur, on est obligé de mémoriser plusieurs plateaux. Pour cela, on utilise le tableau tab_pense, qui peut contenir 19 niveaux de jeu (largement plus qu'il n'en faut; de plus, on peut changer quand on veut le nombre de plateaux qu'il contient).
On note les noirs par 0 et les blancs par 2. Les cases vides sont notées généralement avec un 8. Les cases vides qui sont autour d'un pion sont notées avec un 9. Ceci a été fait pour gagner du temps pendant le jeu. En effet, si on est en début de partie, on n'a que quatre pions. Comme la structure du tableau est linéaire, alors on avance linéairement dans le tableau jusqu'à ce qu'on trouve un 9. On sait alors qu'une case remplie avec un pion se trouve à proximité. Si on n'avait pas eu ce 9, alors, pour chacune des cases de l'échiquier on aurait été obligés de tester si on n'est pas en contact avec un pion.
Pour se déplacer dans les 8 directions, on utilise un tableau à 8 éléments appelé direction.
Pour essayer le programme, on a pris une situation de fin de partie un peu plus complexe que celle décrite dans les pages suivantes, afin de voir les performances du programme (coups, temps); le plateau représentant cette situation s'appelle work0. Sur cet othellier, on représente les pions du joueur par 2 et ceux de l'ordinateur par 0.On voit qu'il nous reste 11 coups à jouer. C'est pour cette raison qu'on a une variable profondeur, qui indique jusqu'à quel niveau l'ordinateur doit descendre pendant la réflexion.
Nous allons décrire maintenant les fonctions et les procédures afin de montrer à quoi servent les autres données.
Trouve_pos
Pour pouvoir jouer un coup, il faut d'abord trouver une case où placer son pion. La fonction qui trouve cette case s'appelle trouve_pos et elle a deux paramètres : niveau et joueur. Le paramètre niveau indique dans quel niveau (pendant la réflexion) il doit trouver un coup. Si, à ce niveau, on avait déjà joué un coup, il faut chercher un autre coup à partir de la position de ce pion déjà joué.
On mémorise donc la dernière place trouvée dans un tableau, appelé dans le programme position. L'algorithme de la procédure est le suivant : on cherche un 9 dans l'othellier, puis on regarde les huit directions et si, dans une de ces directions, le pion joint au 9 est un pion ennemi et quelques cases plus loin on a un pion ami, alors c'est qu'on peut jouer à la place occupée par le 9.
Une fois qu'on a trouvé une position, il faut pouvoir placer le pion dans la case et retourner les pions dans toutes les directions possibles; la procédure qui fait cela s'appelle joue_coup.
Etant donné que nous sommes en fin de partie, la meilleure manière d'évaluer un coup est de compter combien de pions il rapporte. Pour cela, on a écrit la fonction compte_les_pions, qui compte les pions pour une couleur indiquée, blanc ou noir (joueur ou ordinateur). Le paramètre est ici inutile car l'ordinateur a les noirs. Il suffirait donc de comparer les pions directement à 0; mais ceci a été laissé au cas ou le lecteur voudrait modifier le programme.
Nous allons voir maintenant la principale procédure du programme, arbre. C'est la procédure qui s'applique à tous les jeux de réflexion, aussi nous allons l'expliquer avec des exemples.
Supposons qu'on va à 3 niveaux de profondeur. A chaque niveau, on joue les coups possibles un par un et, pour chaque coup, on explore l'arbre qui en découle. A chaque niveau final, on évalue la situation de l'échiquier et on retourne la note. Si le niveau 2 était un niveau du joueur, alors la note attribuée à ce niveau sera la plus petite note trouvée,
car le but du joueur est que l'ordinateur obtienne la plus petite note possible. En revanche, au niveau 1, celui de l'ordinateur, l'ordinateur choisira le coup qui lui rapporte la plus grande note. Cette façon d'explorer un arbre et de retourner les notes, une fois les plus petites et une fois les plus grandes, s'appelle arbre min-max. Comme ici on explore un arbre en fin de partie, la fonction d'évaluation est faite par le compte des pions de l'ordinateur.
A chaque branche de l'arbre exploré on doit faire plusieurs étapes :
- faire les initialisations du niveau correspondant
- note attribuée au niveau
- le tableau "position" décrit ci-dessus
- le nombre de coups
|
Le nombre de coups sera utilisé au cas où aucun coup n'est possible au niveau actuel; dans ce cas, on doit "sauter" le niveau en cours et passer au niveau suivant en ayant pris soin d'incrémenter la profondeur; si, au niveau suivant, il n'y a pas de coup possible, alors c'est qu'on est arrivé à la fin de la partie et on évalue la situation.
repeter
- chercher un coup
- si trouvé, alors :
- jouer ce coup
- mémoriser le plateau de jeu
- descendre dans l'arbre si on n'est pas au niveau final, sinon
évaluer l'othellier
- si non trouvé, alors regarder si au niveau précédent on a pu jouer un
coup, auquel cas on continue à descendre dans l'arbre, sinon les
deux sont bloqués, donc niveau terminal, donc évaluation.
- faire l'élagage pour gagner du temps; l'élagage est expliqué par un arbre
dans les pages suivantes.
jusqu'à ce qu'il n'y ait plus de coups possibles.
|
La procédure arbre a deux paramètres, level (niveau, pour savoir à quel niveau de profondeur on est) et c (coefficient pour savoir qui doit jouer : soit le joueur, soit l'ordinateur; on appelle joue_coup avec le paramètre 1+c, qui vaut 0 ou 2; on n'a pas choisi des valeurs symétriques par rapport à 0 - comme dans le cas du le morpion -, car ici, on a un tableau de 100 bytes et non pas integer; or il faut gagner du temps pendant la réflexion, car il y a beaucoup de sauvegardes de plateaux).
Une fois le programme terminé, il ne nous restera plus qu'à écrire une fonction d'évaluation en cours de partie et de modifier la procédure arbre de façon à ce qu'elle n'appelle plus compte_les_pions, mais une autre fonction d'évaluation (malheureusement c'est ce qu'il y a de plus difficile à faire).
Nous allons étudier maintenant sur un exemple de fin de partie la programmation des jeux de réflexion. Nous allons voir la procédure alpha-beta (ou min-max) et aussi comment on doit faire un élagage (couper les branches d'un arbre), afin de gagner du temps pendant l'exploration d'un arbre (quelque soit le jeu de réflexion qu'on aura programmé). Nous allons illustrer ceci par un exemple concret (voir les images annexes).
La programmation de la réflexion d'un ordinateur se fait de la manière suivante : l'ordinateur simule un coup pour le joueur, ensuite un coup pour lui, ensuite pour le joueur et ainsi de suite jusqu'à ce qu'il atteigne la profondeur de jeu souhaitée. Une fois cette profondeur atteinte, il évalue le plateau et retourne la note trouvée. Pour les deux images qui illustrent notre étude (ou le dessin ci-dessus), la fonction d'évaluation est faite par le décompte des pions. On obtient successivement les notes 21, 30, 21, 26, 24, 31, 39, 32, 21, 25, 37, 21, 36, 28 et 29. Toutes ces notes seront retournées aux niveaux supérieurs.
Mais que va-t-il se passer si un noeud a plusieurs fils ? Quelle note va-t-il choisir ? Pour chaque noeud de l'arbre, si le noeud se trouve à un niveau correspondant au coup du joueur (les blancs jouent) alors c'est la note la plus grande qui est retournée parmi les fils de ce noeud. C'est pourquoi, au niveau 3, on se retrouve avec les notes suivantes: 30, 26, 31, 39, 21, 37, 36, 29. Par contre, pour les niveaux correspondants aux coups de l'ordinateur, c'est la note la plus petite qui est retournée, ce qui explique qu'au niveau 2 on se retrouve avec les notes 26, 21, 36, 29. Mais au niveau 1, on prend la note la plus grande, d'où le 36 en haut de l'arbre, qui nous provient du troisième coup. L'ordinateur doit donc jouer le troisième coup.
Cet algorithme s'appelle alpha-beta ou min-max, car, une fois sur deux, c'est la note maximale qui est retournée, et, une fois sur deux, la note minimale. Il est normal que parmi tous les coups qui s'offrent à lui, l'ordinateur cherche à minimiser la note de l'humain et à maximiser la sienne. On rappelle que c'est ce simple algorithme qui a battu Kasparov aux échecs (avec une puissance de calcul énorme, de l'ordre de 300 millions de coups à la seconde).
Mais, est-il bien utile d'explorer toutes les branches d'un arbre pendant le jeu ? N'y aurait-il pas un moyen de supprimer certaines branches de l'arbre, pour gagner du temps ? C'est ce que nous allons voir maintenant, avec l'opération d'élagage. Voici un dessin représentant un arbre, dont seulement le premier fils du noeud de niveau 2 a été visité en entier. On suppose que le noeud de niveau 2 a seulement 4 fils :
On explore d'abord le noeud A du niveau 3. On décide qu'à ce niveau l'ordinateur cherche à maximiser la note (il aurait très bien pu la minimiser). Le noeud A a trois fils, et le maximum est 30. Cette note est retournée au niveau précédent et comme c'est la première note à être retournée, alors elle devient la note témoin du niveau 2. On rappelle qu'au niveau 2, on cherche à minimiser les notes des fils. L'exploration du noeud A étant finie, l'ordinateur remonte au niveau 2, afin de parcourir les autres fils du niveau 2. Mais la note est retournée au niveau précédent (ceci est toujours valable : on retourne toujours la note au père du noeud en cours).
Il passe ensuite au noeud B. Le premier fils de B rapporte 26. Le deuxième fils rapporte 39. Cette note est supérieure à 30 (témoin du niveau précédent). Alors l'exploration du noeud B s'arrête, étant devenue inutile. En effet, le noeud B a une note supérieure à la note témoin de son père. Et comme son père cherche à minimiser les coups, il choisira le noeud A. Donc à partir de maintenant, quelque soit la note trouvée parmi les fils de B, on sait que son père choisira le noeud A, d'où l'inutilité de l'exploration. Cette opération d'abandon de l'exploration des noeuds fils s'appelle élagage, et elle nous fait gagner beaucoup de temps pendant la réflexion de l'ordinateur. Continuons l'exploration de l'arbre.
Au noeud C, l'exploration des fils continue tant qu'aucune note trouvée n'est supérieure à celle du père (qui jusqu'ici était de 30). Quand le noeud C a été complètement exploré, on constate que sa note est plus petite que celle de son père; elle est donc retournée et devient la nouvelle note témoin. On passe enfin au quatrième coup possible.
Le premier fils de D rapporte une note de 26. Comme cette note est supérieure à celle de son père, l'exploration de D est interrompue (élagage). En effet, l'ordinateur aurait pu trouver des notes supérieures à 26, mais de toutes façons, son père cherche à minimiser, et il aurait donc choisi le noeud C.
On peut donc résumer brièvement l'élagage :
1) on est sur un niveau qui maximise la note de ses fils.
- si la note de ce niveau est supérieure à celle de son père alors on arrête l'exploration et on retourne la note vers son père.
- tant qu'elle est inférieure, on continue l'exploration des fils.
- si on a terminé l'exploration, et si la note est inférieure à celle de son père, alors celle-ci est retournée et servira de témoin de comparaison avec les autres fils
2) on est sur un niveau qui minimise la note de ses fils
- si la note de ce niveau est inférieure à celle de son père alors on arrête l'exploration et on remonte la note vers son père.
- tant qu'elle est supérieure, on continue l'exploration des fils.
- si on a terminé l'exploration, et si la note est inférieure à celle de son père, alors celle-ci est retournée et servira de témoin de comparaison avec les autres fils
Voici le programme de fin de partie (on rappelle que l'ordinateur a les 0, représentés par la couleur noire, et que le joueur a les 2; il reste 11 cases à occuper donc la profondeur de l'arbre à explorer est de 11 ) :
const direction: array[1..8] of integer =
(-11, -10, -9, -1, 1, 9, 10, 11);
work0: array[0..99] of byte =
(8, 9, 9, 9, 9, 9, 9, 9, 8, 8,
8, 9, 0, 0, 0, 0, 0, 0, 9, 9,
9, 9, 9, 0, 0, 0, 0, 9, 2, 9,
9, 2, 2, 0, 0, 0, 2, 0, 2, 9,
9, 2, 2, 0, 2, 2, 2, 0, 2, 9,
9, 2, 2, 2, 2, 0, 0, 2, 2, 9,
9, 2, 2, 2, 2, 0, 0, 2, 2, 9,
9, 2, 9, 2, 0, 0, 0, 9, 9, 9,
9, 9, 9, 2, 2, 2, 2, 2, 9, 9,
9, 9, 9, 9, 9, 9, 9, 9, 9, 9);
COEF_ORDINATEUR = -1;
ORDINATEUR = 0;
COEF_JOUEUR = 1;
JOUEUR = 2;
type othellier = array[0..99] of byte;
utile = array[0..18] of integer;
n_othelliers = array[0..18] of othellier;
var work: othellier;
position: utile;
temoin: utile;
nb_coups: utile;
tab_pense: n_othelliers;
profondeur: integer;
function compte_les_pions(couleur: integer): integer;
var x, total_pions: integer;
begin
x := 10; total_pions := 0;
repeat
inc(x);
if work[x] = couleur then inc(total_pions);
until x = 88;
compte_les_pions := total_pions;
end;
function trouve_pos(niveau, joueur: integer): integer;
var a, xx, xv, opposant, delta: integer;
begin
xx := position[niveau];
trouve_pos := 0;
opposant := 2 - joueur;
repeat
repeat
inc(xx)
until (work[xx] = 9) or (xx > 88);
position[niveau] := xx;
if ((1 + xx) mod 10 > 1) and (xx < 89) then
for a := 1 to 8 do
begin
delta := direction[a];
if work[xx + delta] = opposant then
begin
xv := xx + delta;
while work[xv] = opposant do
inc(xv, delta);
if work[xv] = joueur then
begin
trouve_pos := xx;
exit
end;
end;
end;
until (xx > 88);
end;
procedure joue_coup(position_courante, joueur: integer);
var a, xx, opposant, delta: integer;
begin
opposant := 2 - joueur;
for a := 1 to 8 do
begin
delta := direction[a];
xx := position_courante + delta;
while work[xx] = opposant do
inc(xx, delta);
if work[xx] = joueur then
repeat
dec(xx, delta);
work[xx] := joueur;
until xx = position_courante;
end;
for a := 1 to 8 do
if work[position_courante + direction[a]] = 8 then
work[position_courante + direction[a]] := 9;
end;
procedure arbre(c, level: integer);
var x, next, last: integer;
begin
nb_coups[level] := 0;
position[level] := 10;
temoin[level] := c * 25000;
temoin[level + 1] := -temoin[level];
next := level + 1;
last := level - 1;
repeat
move(tab_pense[last], work, 100);
x := trouve_pos(level, 1 + c);
if x > 0 then
begin
inc(nb_coups[level]);
joue_coup(x, 1 + c);
move(work, tab_pense[level], 100);
if profondeur <> level
then arbre(-c, next)
else temoin[next] := compte_les_pions(ORDINATEUR);
end
else
if nb_coups[level] = 0 then
if nb_coups[last] = 0
then temoin[level] := compte_les_pions(ORDINATEUR)
else begin
move(work, tab_pense[level], 100);
inc(profondeur);
arbre(-c, next);
dec(profondeur);
end;
case c of
-1: begin
if temoin[level] < temoin[next] then temoin[level] := temoin[next];
if temoin[level] > temoin[last] then exit;
end;
1: begin
if temoin[level] > temoin[next] then temoin[level] := temoin[next];
if temoin[level] < temoin[last] then exit;
end;
end;
until position[level] > 88;
end;
procedure niveau_un;
var x, meilleur_coup, temoin1: integer;
begin
move(work, tab_pense[0], 100);
meilleur_coup := 0;
nb_coups[1] := 0;
temoin[1] := 0;
position[1] := 10;
profondeur := 11;
repeat
move(tab_pense[0], work, 100);
x := trouve_pos(1, ORDINATEUR);
if x > 0 then
begin
inc(nb_coups[1]);
if nb_coups[1] = 1 then meilleur_coup := x;
joue_coup(x, 2);
move(work, tab_pense[1], 100);
arbre(COEF_JOUEUR, 2);
temoin1 := temoin[1];
if temoin[1] < temoin[2] then temoin[1] := temoin[2];
if temoin[1] > temoin1 then meilleur_coup := position[1];
end;
until position[1] > 88;
form1.memo1.lines.add('Le meilleur coup pour les noirs est ' + inttostr(meilleur_coup));
form1.memo1.lines.add('Il rapporte ' + inttostr(temoin[1]) + ' pions noirs en fin de partie !');
end;
procedure tform1.affiche_jeu;
var x, y: integer;
begin
for x := 1 to 8 do
for y := 1 to 8 do
if work[x + 10 * y] = JOUEUR then
with image1.picture.bitmap.canvas do
begin
brush.color := clWhite;
ellipse((x - 1) * 30 + 5, (y - 1) * 30 + 5, (x - 1) * 30 + 25, (y - 1) * 30 + 25);
end
else
if work[x + 10 * y] = ORDINATEUR then
with image1.picture.bitmap.canvas do
begin
brush.color := clBlack;
ellipse((x - 1) * 30 + 5, (y - 1) * 30 + 5, (x - 1) * 30 + 25, (y - 1) * 30 + 25);
end;
end;
procedure TForm1.FormShow(Sender: TObject);
var i: integer;
begin
image1.picture.bitmap := tbitmap.create;
with image1.picture.bitmap do
begin
width := 240;
height := 240;
canvas.brush.style := bsSolid;
for i := 1 to 7 do
with image1.picture.bitmap.canvas do
begin
moveto(i * 30, 0); lineto(i * 30, 240);
moveto(0, i * 30); lineto(240, i * 30);
end;
end;
image1.autosize := true;
move(work0, work, 100); fillchar(temoin, sizeof(temoin), #0);
affiche_jeu;
end;
procedure TForm1.Button1Click(Sender: TObject);
begin
niveau_un;
end;
|
Copyright © 2005 Axel CHAMBILY et Pétrut CONSTANTINE.
Aucune reproduction, même partielle, ne peut être faite
de ce site ni de l'ensemble de son contenu : textes, documents, images, etc.
sans l'autorisation expresse de l'auteur. Sinon vous encourez selon la loi jusqu'à
trois ans de prison et jusqu'à 300 000 € de dommages et intérêts.
