3 Dames Algorithmique et Programmation

3.1 Objectif Projets 2012/2013

Il s’agit d’écrire un programme jouant aux Dames selon les règles. Le programme doit être le meilleur
possible. Vous utiliserez pour cela l’algorithme α − β de recherche du meilleur coup à jouer (Cf. document
joint).

3.2 Règles du jeu

Les règles sont disponibles sur le site de la Fédération Française de Jeu de Dames (http://www.ffjd.
fr/Web/index.php?page=reglesdujeu). On prendra garde de ne pas oublier les règles sur la prise obli-
gatoire de pions (pour ceux qui ne la connaissent pas se référer au site).

F IG . 6 – Une partie de Dames.

3.3 Résultats demandés

Vous devrez parvenir à écrire un programme qui joue le mieux possible aux Dames en respectant les règles,
est capable de jouer avec les noirs ou les blancs, dialogue avec l’utilisateur, sait quand la partie est terminée et
désigne le vainqueur.
Pour cela, le travail peut être séparé en plusieurs composantes :

3.3.1 Interface graphique

Vous devrez concevoir une interface graphique qui au minimum doit :
– afficher le damier et les pions,
– permettre d’entrer à la souris les coups joués par l’adversaire de l’ordinateur,
– afficher diverses informations (indiquer que l’ordinateur « passe » s’il ne peut jouer, indiquer que la
partie est terminée et désigner le vainqueur, afficher éventuellement le nombre de pions pour chacun
des camps en cours de partie...)
Il sera important dès le début de bien réfléchir aux structures de données utilisées pour représenter une
situation du jeu de Dames, et un coup de jeu.

3.3.2 Règles du jeu

L’interface de jeu permet à deux joueurs de s’affronter :
– créer la situation initiale du jeu (20 pions de chaque couleur placés sur les 4 premières rangées de chaque
côté),
– vérifier que les coups proposés par les joueurs sont valides à la fois pour un pion et pour une dame,
– vérifier que les coups joués correspondent bien au coup de prise maximale à chaque fois,

1
 – réaliser la fonction de transition qui fait passer d’une situation du jeu à une autre en respectant les règles
(déplacer le pion, et supprimer les pions adversent qui ont éventuellement été pris).

3.3.3 Stratégie de l’ordinateur

Comme un certain nombre de jeux, les Dames présentent les caractéristiques suivantes :
– deux adversaires jouent à tour de rôle
– la situation globale du jeu est connue de chacun des joueurs
– la chance n’intervient pas.
Dans un tel cas, l’ordinateur pourrait de manière théorique calculer la totalité de l’arbres des situations de
jeu possibles, de manière à adopter la meilleure stratégie possible.
Evidemment, la taille de cet arbre est sans commune mesure avec les possibilités de calcul d’un ordinateur,
et donc il n’est pas possible de faire jouer l’ordinateur selon cette meilleure stratégie possible (heureusement
d’ailleurs, sinon le jeu ne présenterait pas beaucoup d’intérêt !). Remarquez que pour le jeu du morpion, on
peut par contre dessiner cet arbre à la main, et qu’il existe une stratégie optimale qui permet à tous les coups
de faire au moins match nul.
En pratique, l’ordinateur regarde toutes les possibilités un petit nombre de coups à l’avance, n (il « parcourt
l’arbre du jeu jusqu’à la profondeur n »). Il décidera de jouer le coup qui amène le jeu dans la branche de l’arbre
qui lui semble la plus favorable. Pour ce faire, il a besoin d’évaluer les situation du jeu n coups plus loin, en leur
donnant une note selon que ces situations sont plus ou moins avantageuses pour lui ou pour son adversaire.
La programmation de la stratégie de l’ordinateur consistera donc en :
– l’algorithme Minimax qui réalise le parcours dans l’arbre du jeu, et son amélioration, l’algorithme α − β
– une fonction d’évaluation du jeu

3.4 Algorithmes Minimax et α − β

3.4.1 Justification
Les algorithmes de recherche de type Minimax (voir § 4.4.2), dont α − β (voir § 4.4.3) est une amélioration,
s’appliquent à une catégorie de jeux à deux joueurs, qui présentent les caractéristiques suivantes :
– les deux adversaires jouent à tour de rôle,
– la situation globale du jeu est connue de chacun des joueurs,
– la chance n’intervient pas,
– ils sont dits « à somme nulle » : les gains d’un joueur représentent exactement les pertes de l’autre joueur.
Pour ces jeux, on peut définir une notion d’arbre de jeux par
– S l’ensemble de toutes les situations possibles du jeu,
– succ : S −→ Reg(S) l’application qui à une situation s associent l’ensemble des situations s0 telles qu’il
existe un coup régulier faisant passer de s à s0 .
On suppose qu’il existe une fonction h : S −→ Z qui donne la valeur d’une situation du jeu (voir § 4.4.4).
Cette fonction, appliquée à chacune des situations accessibles légalement à partir de la situation courante per-
met de décider si un coup est meilleur qu’un autre. Toutefois, il peut être intéressant d’examiner les situations
de jeu plus profondément pour tenir compte des réponses possibles de l’adversaire. On appelle P cette pro-
fondeur de recherche. Plus P est grand, plus l’arbre de recherche est grand et donc long à explorer et meilleur
(en principe) est le coup joué.
L’exploration complète d’un arbre de jeu n’est généralement pas possible car ce serait trop long. C’est
pourquoi on se limite à une profondeur P assez faible.

3.4.2 L’algorithme Minimax

Dans l’approche Minimax, les joueurs sont appelés respectivement Max et Min. Max choisit parmi tous les
coups réguliers le coup qui a la valeur maximale tandis que Min choisit celui qui minimise le gain de Max.
Dans un arbre Minimax, la racine (profondeur 0) représente la situation du jeu actuelle. L’évaluation avec la
fonction h se fait à la profondeur P . L’algorithme Minimax (Cf. Fig. 7) remonte la meilleure valeur jusqu’à la
racine ce qui détermine le meilleur coup à jouer.
La figure 8 montre un arbre Minimax de profondeur 2.
Pour éviter d’avoir à faire des min et des max, on emploie une procédure Negamax (Cf. Fig. 9) qui ne
fait que des max. Pour cela, il suffit de considérer que le joueur Min prend la valeur maximale des valeurs
opposées des situations filles.

3.4.3 Amélioration du Minimax : α − β

L’algorithme Minimax effectue une exploration complète de l’arbre de recherche jusqu’à un niveau donné.
Il peut arriver qu’une exploration partielle de l’arbre suffise. Pour cela, il faut éviter d’examiner des sous-arbres
qui ne conduiront pas à des situations dont la valeur contribuera au calcul du gain à la racine de l’arbre.

2
Minimax (s : situation)
m, t : entier ;
Si s est une feuille
Alors renvoyer h(s) ;
Si s est de type Max Alors
m ← −∞ ;
Pout tout s0 : situation ∈ succ(s) Faire
t ← Minimax(s0 ) ;
Si t > m Alors m ← t ;
Fin Pour tout
renvoyer m ;
Si s est de type Min Alors
m ← +∞ ;
Pout tout s0 : situation ∈ succ(s) Faire
t ← Minimax(s0 ) ;
Si t < m Alors m ← t ;
Fin Pour tout
renvoyer m ;
Fin Minimax

F IG . 7 – Procédure Minimax

Profondeur

0 5

Max

1 5 1 2

Min

2 7 5 10 4 1 3 11 2 6

F IG . 8 – Arbre Minimax de profondeur 2

L’arbre de recherche est exploré en profondeur d’abord par l’algorithme, l’ordre de visite des nœuds est
donc totalement fixé. Sur la figure 10 les branches de gauche sont parcourus en premier.
Dans les exemples de la figure 10 certains nœuds ont une valeur définitive alors que les autres (étiquetés
avec un nom de variable) n’en ont pas encore reçue. D’après la définition de l’algorithme Minimax la valeur
de la situation racine de l’arbre (a) est obtenue par

u = max{5, v}, où v = min{4, . . .}.

Il est clair que u = 5 indépendamment de la valeur de v. Il en résulte que l’exploration des branches
filles du nœud étiqueté par v peut être arrêtée. On dit qu’on a réalisé une coupure superficielle. En appliquant
récursivement le même raisonnement à l’arbre (b), on en déduit que la valeur de u peut être obtenue sans
connaître la valeur finale de y. De même que précédemment, l’exploration des branches filles du nœud étiqueté
par y n’est pas nécessaire : on parle alors de coupure profonde.
Plus généralement, lorsque dans le parcours de l’arbre de jeu par Minimax il y a modification de la valeur
courante d’un nœud, si cette valeur franchit un certain seuil, il devient inutile d’explorer la descendance encore
inexplorée de ce nœud.
On distingue deux seuils, appelés pour des raisons historiques, α (pour les nœuds Min) et β (pour les
nœuds Max) :

3
Negamax (s : situation)
m, t : entier ;
Si s est une feuille
Alors renvoyer h(s) ;
m ← −∞ ;
Pout tout s0 : situation ∈ succ(s) Faire
t ← −Negamax(s0 ) ;
Si t > m Alors m ← t ;
Fin Pour tout
renvoyer m ;
Fin Negamax

F IG . 9 – Procédure Negamax

– le seuil α, pour un nœud Min s, est égal à la plus grande valeur (déjà déterminée) de tous les nœuds Max
ancêtres de s. Si la valeur de s devient inférieure ou égale à α, l’exploration de sa descendance peut être
arrêtée ;
– le seuil β, pour un nœud Max s, est égal à la plus petite valeur (déjà déterminée) de tous les nœuds Min
ancêtres de s. Si la valeur de s devient supérieure ou égale à β, l’exploration de sa descendance peut être
arrêtée.
On donne figure 11 l’énoncé de l’algorithme α − β, qui maintient ces deux seuils pendant le parcours de
l’arbre. Au départ, la procédure Alphabeta est appelée avec un intervalle (α, β) égal à ] − ∞, +∞[.

3.4.4 Fonction d’évaluation

D’une façon générale, on donne à la fonction d’évaluation la forme suivante :
pmat cmat + pmob cmob + ppos cpos
qui prend en compte trois critères : le matériel (cmat ), la mobilité(cmob ) et la position (cpos ). Chaque critère
est accompagné d’une pondération qui indique l’importance accordée à ce critère et qui peut être variable au
cours d’une partie.
Remarque : Pour estimer la valeur globale d’une situation, on doit faire intervenir la différence entre
l’évaluation de la situation pour un camp et l’évaluation de la situation pour l’autre camp.

3.5 Indications
3.5.1 Fonction d’évaluation
Pour le jeu de Dames, deux critères principaux d’évaluation :
– d’une part, éliminer le plus possible de pions adverses,
– d’autre part, pouvoir transformer ses pions en dames (qui présentent plus de possibilités qu’un simple
pion).

3.5.2 Stratégie
Dans les programmes classiques de jeux de dames, on distingue plusieurs phases de jeu.
– L’ouverture (resp. la fermeture), qui représente environ les douze premiers (resp. derniers) coups. On se
sert habituellement de parties déjà existantes pour savoir quel va être le meilleur coup à jouer.
– Le milieu de partie, où l’objectif va être de prendre le plus de pions possible ainsi que de créer le plus
grand nombre de dames possible (on se sert ici de l’algorithme alpha-beta).
Dans notre cas, on utilisera l’algorithme alpha-beta dans tous les cas de figures (sauf si vous connaissez
certaines tactiques de jeux pour les Dames). La fonction d’évaluation se limitera donc à une somme de deux
termes : le potentiel de pions pris et le nombre de dames créées. Ces deux termes correspondent à la partie
matérielle de la fonction d’évaluation mais sont amplement suffisants pour les dames.

3.5.3 Jeu
Pour éviter que l’ordinateur joue exactement les mêmes coups sur une même partie, on peut ajouter un peu
d’aléatoire dans les choix qu’il fait.
Au terme du projet, on pourra faire s’affronter en duels les algorithmes des différents binômes (avec un
temps de jeu limité !).
Que le meilleur gagne !

4
(a) (b)
u u

5 v 5 v

4 x

F IG . 10 – Coupure superficielle (a) et profonde (b)

Alphabeta (s : situation, α : entier, β : entier)

m, t : entier ;
Si s est une feuille
Alors renvoyer h(s) ;
Si s est de type Max Alors
m ← α;
Pout tout s0 : situation ∈ succ(s) Faire
t ← Alphabeta(s0 , m, β) ;
Si t > m Alors m ← t ;
Si m ≥ β Alors renvoyer m ;
Fin Pour tout
renvoyer m ;
Si s est de type Min Alors
m←β;
Pout tout s0 : situation ∈ succ(s) Faire
t ← Alphabeta(s0 , α, m) ;
Si t < m Alors m ← t ;
Si m ≤ α Alors renvoyer m ;
Fin Pour tout
renvoyer m ;
Fin Alphabeta