Conception d'un jeu d'échecs en Pascal

Roland Chastain

Il y a bientôt deux ans, je me suis mis en tête d'écrire un programme de jeu d'échecs.

En cherchant des exemples à étudier, je suis tombé sur un programme court, rapide et d'un niveau de jeu correct(1), dont j'ai fait une adaptation.

J'ai renommé les variables et les fonctions, remplacé l'interface « texte » par une interface graphique, complété certains endroits du programme et enfin ajouté un petit livre d'ouvertures(2).

Maintenant je vais essayer de vous expliquer, non pas comment on fait un programme d'échecs, mais plutôt comment nous avons fait ce programme, Jürgen Schlottke et moi.

Commentez

- Titre : Conception d'un jeu d'échecs en Pascal

- Auteur : Roland Chastain

- Parution : 28 mai 2013

- Public visé :

- Licence : Les sources présentées sur cette page sont libres de droits et vous pouvez les utiliser à votre convenance. Par contre, la page de présentation constitue une œuvre intellectuelle protégée par les droits d'auteur. Copyright ® 2013 Roland Chastain. Aucune reproduction, même partielle, ne peut être faite de ce site et 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.

Sommaire

- Introduction

- Architecture du programme

- Représentation interne du jeu

- L'échiquier

- Les pièces

- III-C. Le mouvement des pièces

- III-D. Autres données

- Initialisation de la position et déplacement d'une pièce

- Génération des coups

- Évaluation des coups

- VI-A. Première étape

- VI-B. Deuxième étape

- VI-C. Étude d'un cas

- Livre d'ouvertures

- Interface graphique

- VIII-A. Utilisation d'une police True Type

- VIII-B. Programmation Win32 avec la bibliothèque OWL

- IX. Conclusion

- X. Remerciements

Introduction

« Ceux qui se mêlent de donner des préceptes se doivent estimer plus habiles que ceux auxquels ils les donnent, et s'ils manquent à la moindre chose, ils en sont blâmables. Mais ne proposant cet écrit que comme une histoire, ou, si vous l'aimez mieux, que comme une fable, en laquelle, parmi quelques exemples qu'on peut imiter, on en trouvera peut-être aussi plusieurs autres qu'on aura raison de ne pas suivre, j'espère qu'il sera utile à quelques-uns, sans être nuisible à personne, et que tous me sauront gré de ma franchise. »

René Descartes, Discours de la méthode pour bien conduire sa raison et chercher la vérité dans les sciences (1637).

« ESCHECS, ou ECHECS. Jeu de petites pièces de bois tourné, qui servent à jouer sur un tablier ou damier divisé en 64 carreaux, où l'adresse est tellement requise, que le hasard ne s'en mêle point, & on ne perd que par sa faute. Il y a de chaque côté huit pièces & huit pions, qui ont divers mouvemens et règles pour marcher. La commune opinion des Anciens est que ce fut Palamède qui inventa les échecs & l'échiquier pendant le siège de Troye. D'autres l'attribuent à un Diomède qui vivait sous Alexandre. Mais la vérité est que ce jeu est si ancien, qu'on n'en peut sçavoir l'auteur. »

Antoine Furetière, Dictionnaire universel, contenant généralement tous les mots françois tant vieux que modernes et les termes des sciences et des arts (1702).

Il y a bientôt deux ans, je me suis mis en tête de faire un jeu d'échecs pour ordinateur.

Je rêvais de refaire Fritz.

J'aimais bien aussiTarrasch, qui est une interface graphique à laquelle on associe un moteur.

Un jeu d'échecs est l'assemblage d'au moins deux programmes différents : l'un remplace l'échiquier et ses pièces ; l'autre a pour fonction de « jouer », c'est-à-dire de mouvoir les pièces, comme ferait un vrai joueur : aussi l'appelle-t-on un moteur.

La pièce maîtresse du jeu, c'est le moteur. L'interface graphique rend le programme plaisant à utiliser mais à la rigueur elle n'est pas indispensable. En tout cas il est important de bien faire la distinction entre le moteur et l'interface : ce sont deux ouvrages différents, auxquels on ne peut pas se consacrer en même temps.

Commençons par prendre une vue d'ensemble de notre jeu.

Architecture du programme

Le programme principal, celui qui en s'exécutant fait s'exécuter tous les autres, se trouve dans le fichier JEU. La fonction de ce programme est de permettre l'interaction entre le joueur et le moteur. Pour ce faire, le programme devra ouvrir une fenêtre, dessiner un échiquier (en fonction des informations communiquées par le moteur), enfin détecter et interpréter les clics de la souris.

Ce programme utilise l'unité ECHECS, qui contient le moteur.

program JEU;
{&PmType Pm}

uses
WINDOWS, OWINDOWS, STRINGS, ECHECS, LIVRE;

L'unité LIVRE renferme un petit programme qui a pour fonction de chercher dans le livre d'ouvertures. Les autres unités sont des unités de Virtual Pascal, qui vont servir à fabriquer une application Windows.

Voyons à présent ce qu'il y a dans la partie interface de l'unité ECHECS.

unit ECHECS;

interface

procedure Initialise;
function Valide(const coup: integer): boolean;
function Machine: integer;
function EtatJeu: integer;
var chaine: array[0..118] of char;
procedure ActualiseChaine;
var histoire: array[0..92] of char;

implementation

Voilà tout ce qui sera « visible » depuis le programme principal :

- une procédure qui initialise l'échiquier interne :

procedure Initialise;

- une fonction qui vérifie la légalité des coups de l'utilisateur, et les joue le cas échéant :

function Valide(const coup: integer): boolean;

- une autre qui calcule le coup de l'ordinateur, le joue s'il existe et, dans tous les cas, en informe le programme principal :

function Machine: integer;

- une autre qui fait connaître l'état du jeu(3) après chaque coup, afin que les notifications appropriées puissent être faites à l'utilisateur :

function EtatJeu: integer;

- enfin deux chaînes :

- la première qui est une représentation de l'échiquier, composée pour la police Chess Alpha(4) :

var chaine: array[0..118] of char;

- la seconde qui est la liste des coups joués, sous la forme « e2e4e7e5» :

var histoire: array[0..92] of char;

Et voici la partie initialization  de l'unité :

initialization
Initialise;
InitialiseChaine;
ActualiseChaine;
histoire[0] := #0;
end.

Ainsi l'exécution du programme principal entraînera automatiquement l'initialisation de l'échiquier interne et des autres variables globales que le programme principal utilise.

Représentation interne du jeu

Entrons maintenant dans le programme d'échecs proprement dit, c'est-à-dire dans la partie implementation de l'unité ECHECS.

L'échiquier

On y trouve d'abord des constantes, des types et des variables.

Pour représenter l'échiquier et ses pièces, nous allons utiliser un tableau. Quelles seront ses dimensions et que contiendra-t-il ? Avant de répondre à cette question, je dois vous dire un mot de la convention qui a été choisie au départ pour numéroter les cases de l'échiquier interne.

Partons de la désignation usuelle des cases. Comme on sait, les cases sont désignées par une lettre suivie d'un nombre. Ainsi le roi blanc commence-t-il la partie sur la case « e1 », « e » désignant la colonne et « 1 » la ligne.

En remplaçant le « e » par un 5, j'obtiens un nombre (51) dans lequel la chaîne initiale (« e1 ») se laisse encore facilement reconnaître. Ainsi les 64 cases de l'échiquier peuvent être représentées par des nombres allant de 11 à 88.

Il est donc possible de déclarer un tableau à une seule dimension. Il suffira de garder à l'esprit que le nombre des dizaines correspond à la colonne, et le nombre des unités à la ligne.

Pour déterminer le point d'arrivée d'une pièce à partir de son point de départ, il suffira de faire une addition ou une soustraction. Pour passer d'une colonne à la colonne voisine, on ajoutera ou on retirera 10 ; pour passer d'une ligne à la ligne voisine, on ajoutera ou on retirera 1.

Pour éviter de dépasser accidentellement les bornes du tableau, nous allons ajouter des cases supplémentaires, qui serviront de garde-fou.

Or il y a une pièce dont le pas est plus grand que celui des autres pièces, ou plutôt il y a une pièce qui saute au lieu de marcher. Ce « sauteur », comme l'appelle la langue allemande, vous l'avez reconnu : c'est le cavalier. Il saute une colonne et dans le même mouvement il change de ligne, ou inversement. Ses mouvements relatifs seront donc compris, suivant notre système, entre -21 et +21.

Nous avons donc trouvé la taille de notre tableau. Il aura une seule dimension, et ses cellules seront indexées de 11 - 21 = -10 à 88 + 21 = 109.

Les coups pourront être représentés par un seul nombre entier. Par exemple, le coup dont la notation usuelle est « e2e4 » sera représenté par le nombre 5254.

Les pièces

Ce tableau contiendra des nombres qui serviront à la fois à identifier les pièces et à leur attribuer une valeur relative. Le type échiquier est donc défini comme suit :

type
tEchiquier = array[-10..109] of integer;

Maintenant il s'agit de décider que tel nombre représentera telle pièce.

Pour commencer, la valeur 0 paraît tout indiquée pour représenter une case vide. Ensuite, convenons que les pièces blanches seront représentées par des nombres entiers naturels et les pièces noires par des nombres négatifs. De cette façon, nous pourrons facilement faire abstraction de la couleur des pièces, en considérant la valeur absolue des nombres ; ou inversement nous pourrons connaître la couleur d'une pièce indépendamment de sa nature, d'après le signe du nombre.

Ces nombres représenteront non seulement le type et la couleur des pièces mais aussi leur valeur relative.

const
P =   2; { Pion }
F =   6; { Fou }
C =   7; { Cavalier }
T =  10; { Tour }
D =  19; { Dame }
R = 126; { Roi }
H = 127; { Hors-jeu }

Les nombres utilisés vont donc de -126 à 127 : ce sont les limites du type shortInt, qui est le type utilisé dans le programme original. Quoique je l'aie remplacé par le type integer, je me suis bien gardé de modifier la valeur des constantes.

Bien que le roi, au jeu des échecs, ne puisse jamais être pris, on lui attribue une valeur comme à une pièce ordinaire : nous verrons plus loin pourquoi.

Les limites du type shortInt (-126 à 127) ont été savamment utilisées. De -126 à +126, les pièces, noires et blanches. Que ferons-nous de 127 ? Nous associerons cette valeur aux cases ne se trouvant pas sur l'échiquier. Quelle drôle d'idée, me direz-vous, et vous aurez peut-être raison.

Ces cases qui n'existent pas en théorie sont pourtant déclarées dans le programme. La valeur qui leur sera attribuée signifiera alors, non pas qu'il y a ceci ou cela sur la case, mais que la case n'existe pas. D'un point de vue logique, ce n'est pas très satisfaisant. Le bon sens voudrait plutôt qu'on s'assure de l'existence de la case avant de se demander par quelle pièce elle est occupée. En revanche, d'un point de vue mécanique, il est avantageux de vérifier ces deux choses dans une seule et même opération.

Voyons par exemple la génération des coups du cavalier.

C: // cavalier
for i := 1 to 8 do
begin
b := a + MC[i]; // il saute dans toutes les directions
if damier[b] * trait * -1 in [0..R] then
// cases existantes et vides ou occupées par l'adversaire
Enregistre(aPo, a, b);

Une seule expression suffit à vérifier que la case existe et qu'elle n'est pas occupée par une pièce de même couleur.

III-C - Le mouvement des pièces

Nous avons déjà vu comment obtenir la position relative d'une case de l'échiquier par rapport à une autre, à savoir en ajoutant ou en soustrayant des dizaines pour changer de colonne, des unités pour changer de ligne.

Les mouvements élémentaires de chaque pièce sont contenus dans des tableaux de constantes. J'ai écrit ci-dessous les valeurs de telle sorte qu'on puisse voir comment elles sont obtenues, à savoir par l'addition de deux nombres correspondant respectivement au déplacement horizontal et au déplacement vertical de la pièce.

{ Mouvement de pion }
MP: array[1..4]of integer = (+00+01, +00+02, -10+01, +10+01);
{ Mouvement de fou }
MF: array[1..4]of integer = (+10+01, -10-01, -10+01, +10-01);
{ Mouvement de tour }
MT: array[1..4]of integer = (+00-01, +00+01, -10+00, +10+00);
{ Mouvement de cavalier }
MC: array[1..8]of integer = (+10+02, +20+01, +20-01, +10-02, -10-02, -20-01, -20+01, -10+02);
{ Mouvement de roi }
MR: array[1..8]of integer = (+00-01, +00+01, -10+00, +10+00, +10+01, -10-01, +10-01, -10+01);

Les mouvements de la dame ne sont pas déclarés séparément, parce que ce sont les mêmes que ceux du roi, avec cette différence que le roi ne fait qu'un seul pas à la fois.

Notons également que les mouvements de pion que nous venons de déclarer sont ceux des pions blancs : pour obtenir les mouvements des pions noirs, il faudra inverser les valeurs.

Voilà comment l'échiquier et ses pièces seront représentés.

III-D - Autres données

Cependant nous avons encore besoin de déclarer d'autres variables.

Pour représenter une partie en cours, il ne suffit pas de connaître l'emplacement des pièces : il faut encore savoir qui doit jouer (« qui a le trait »), s'il y a un pion à prendre « en passant », si les rois ont encore le droit de « roquer »(5).

Si les règles du jeu ne vous sont pas bien présentes à l'esprit, voici de quoi réviser : Règles.

Nous utiliserons aussi des tableaux qui contiendront, pour chaque position, la liste des coups autorisés. Un coup sera un enregistrement de trois nombres entiers représentant le point de départ, le point d'arrivée et la valeur ou la note du coup.

type
tListe = array[1..100] of record
a, b, v: integer;
end;

Comme on voit, ces tableaux sont de longueur fixe. Nous utiliserons une variable supplémentaire (la variable compte) pour connaître le nombre d'éléments actuellement contenus dans le tableau.

Toutes ces données sont rassemblées dans un enregistrement.

tPosition = record
damier: array[-10..109]of integer;
passant: array[-1..1]of integer;
trait, balance, compte: integer;
coups: tListe;
end;

Le champ passant vaudra 0 si aucun pion ne peut être pris en passant ; autrement il aura pour valeur l'index de la case d'arrivée.

La variable trait vaudra 1 si les blancs ont le trait, -1 si ce sont les noirs.

La variable balance vaudra 0 au départ, ensuite on y ajoutera la valeur des pièces prises.

Enfin, la variable compte contiendra le nombre d'éléments du tableau coups de type tListe.

Initialisation de la position et déplacement d'une pièce

La procédure d'initialisation de la position ne présente aucune difficulté particulière. On remarquera seulement que le damier est parcouru tantôt au moyen d'un compteur, tantôt au moyen de deux compteurs, comme s'il avait deux dimensions.

procedure Initialise;
const
I: array[1..8, 1..8]of integer = (
(-T,-C,-F,-D,-R,-F,-C,-T),
(-P,-P,-P,-P,-P,-P,-P,-P),
( 0, 0, 0, 0, 0, 0, 0, 0),
( 0, 0, 0, 0, 0, 0, 0, 0),
( 0, 0, 0, 0, 0, 0, 0, 0),
( 0, 0, 0, 0, 0, 0, 0, 0),
(+P,+P,+P,+P,+P,+P,+P,+P),
(+T,+C,+F,+D,+R,+F,+C,+T));
var
x, y: integer;
begin
with initiale do
begin
{ On affecte à toutes les cases du damier la valeur hors-jeu. }
for x := -10 to 109 do
damier[x] := H;

{ Puis on affecte aux cases valides les valeurs du tableau de constantes. }
for x := 1 to 8 do
for y := 1 to 8 do
damier[10*x+y] := I[-y+9, x];

{ Enfin on initialise les autres variables. }
for x := E1G1 to E8C8 do
roque[x] := TRUE; { Le roque est autorisé partout. }

for x := -1 to 1 do
passant[x] := 0; { Aucun pion ne peut être pris en passant. }

balance := 0; { Il y a autant de pièces d'un côté que de l'autre. }

trait := 1; { Les blancs ont le trait. }
end;

courante := initiale; { La position initiale est conservée à part. }
demiCoups := 0;
end;

La suite demande une attention plus soutenue : il s'agit de la procédure qui déplace les pièces.

Les coups spéciaux, prise en passant et roque, vont nous compliquer la tâche : ils doivent être pris en compte, non seulement au moment où ils sont joués, mais aussi lorsque les conditions qui les autorisent ou les interdisent sont modifiées par un coup ordinaire. Il faut bien distinguer ces deux choses.

Par exemple, si un pion avance de deux pas, il peut être pris « en passant » au demi-coup suivant (et seulement au demi-coup suivant). Dans ce cas, on affectera à la variable passant l'index de la case sur laquelle le pion est passé : c'est sur cette case que le pion adverse viendra se placer. Dans le cas contraire (c'est-à-dire pour tous les autres coups), la variable prendra la valeur 0, pour signifier qu'aucune prise en passant n'est autorisée.

En ce qui concerne le roque, si la pièce déplacée est une tour ou un roi, nous modifierons en conséquence la valeur de la variable roque : si une tour se déplace, le roque n'est plus autorisé de ce côté-là ; si c'est le roi (qu'il s'agisse d'un roque ou d'un coup ordinaire), le roque est interdit des deux côtés.

Et si la tour est prise, que faisons-nous ? Nous ne faisons rien pour le moment, car l'existence de la tour sera vérifiée ailleurs, avec d'autres conditions que nous verrons le moment venu.

procedure Deplace(var aPo: tPosition; a, b: integer);
{ Les paramètres a et b représentent des cases de l'échiquier. }
begin
with aPo do
begin
if (damier[a] * trait = R) or (damier[a] * trait = T) then
{ Si la pièce qui se déplace est un roi ou une tour... }
case a of
11: roque[E1C1] := FALSE;
18: roque[E8C8] := FALSE;
51: begin
roque[E1G1] := FALSE;
roque[E1C1] := FALSE;
end;
58: begin
roque[E8G8] := FALSE;
roque[E8C8] := FALSE;
end;
81: roque[E1G1] := FALSE;
88: roque[E8G8] := FALSE;
end;

if ((b-a) * trait = 2) and (damier[a] * trait = P) then
{ Si la pièce avance de deux lignes et que c'est un pion... }
passant[trait] := a + MP[1] * trait
else
passant[trait] := 0;

if (b = passant[-trait]) and (damier[a] * trait = P) then
{ Si c'est une prise en passant... }
begin
passant[trait] := 0;
Deplace(aPo, a, (b div 10) * 10 + a mod 10);
trait := -trait;
a := (b div 10) * 10 + a mod 10;
end;

if(a in [51,58]) and (b in [71,31,78,38]) and (damier[a] * trait = R) then
{ Si c'est un roque... }
begin
damier[b] := damier[a];
damier[a] := N;
if b div 10 = 7 then
begin
a := 80 + a mod 10;
b := a - 20;
end else
begin
a := 10 + a mod 10;
b := a + 30;
end;
damier[b] := damier[a];
damier[a] := N;
end else
begin
{ Dans tous les autres cas que le roque... }
Dec(balance, damier[b]);
damier[b] := damier[a];
damier[a] := N;
if ((b mod 10 = 1) or (b mod 10 = 8)) and (damier[a] * trait = P) then
{ Si un pion est promu... }
begin
damier[b] := D * trait;
Inc(balance, (D - P) * trait);
end;
end;

trait := trait * -1;
end;
end;

Il y a encore un endroit de la procédure qui nécessite quelques mots d'explication : c'est la partie du code qui effectue la prise en passant.

Le mouvement s'effectue en deux fois. Un appel récursif déplace une première fois le pion, pour le placer sur la case occupée par le pion adverse. Auparavant la variable passant a été remise à zéro, pour éviter une boucle infinie.

passant[trait] := 0;
Deplace(aPo, a, (b div 10) * 10 + a mod 10);

Ensuite la valeur de la variable trait, qui a été automatiquement inversée par l'appel récursif à la procédure Deplace, est de nouveau inversée, de façon à ce que la même couleur conserve le trait ; la valeur de la variable a (qui représente la case de départ) est modifiée, et la procédure finit de s'exécuter : le pion fait un pas en avant.

trait := -trait;
a := (b div 10) * 10 + a mod 10;

Voici un exemple. Le pion noir vient d'avancer de deux pas. La variable passant vaut 76, c'est-à-dire que le mouvement du pion blanc est à destination de la case « g6 ».

Le pion blanc fait d'abord un pas de côté.

Puis il avance en « g6 ».

La partie du code qui effectue le roque est plus simple. On déplace d'abord le roi ; puis on modifie les valeurs de a et de b afin qu'elles correspondent au mouvement de la tour ; puis on déplace la tour.

{ Déplacement du roi }
damier[b] := damier[a];
damier[a] := N;

{ Calcul du point de départ et du point d'arrivée de la tour }
if b div 10 = 7 then
begin
{ Roque côté roi ou petit roque }
a := 80 + a mod 10;
b := a - 20;
end else
begin
{ Roque côté dame ou grand roque }
a := 10 + a mod 10;
b := a + 30;
end;

{ Déplacement de la tour }
damier[b] := damier[a];
damier[a] := N;

Génération des coups

Passons à la génération des coups. Il s'agit de remplir, pour une position donnée, la variable coups de type tListe. Cette variable est un tableau pouvant contenir jusqu'à 100 coups, nombre qui ne devrait jamais être atteint(6).

Pour commencer, nous avons une procédure qui sert à enregistrer un coup sur la liste.

procedure Enregistre(var aPo: tPosition; const a, b: integer);
begin
with aPo do
begin
Inc(compte);
coups[compte].a := a;
coups[compte].b := b;
end;
end;

Ensuite, la recherche des coups est faite en deux fois : une procédure pour les coups ordinaires et la prise en passant, une autre pour le roque. L'avantage de cette séparation est que nous pourrons négliger le roque pour économiser du temps au cours de la procédure récursive d'évaluation.

Voici la génération des coups de pion.

procedure GenereCoupsOrdinaires(var aPo: tPosition);
var
a, b, x, y, i, j: integer;
begin
with aPo do
begin
{ Compteur à zéro. }
compte := 0;
{ On parcourt les 64 cases. }
for x := 1 to 8 do
for y := 1 to 8 do
begin
a := 10 * x + y;
{ On s'arrête sur les pièces de la bonne couleur. }
if damier[a] <> 0 then
case damier[a] * trait of
P: { Pion }
begin
{ On commence par un simple pas en avant. }
b := a + MP[1] * trait;
if damier[b] = 0 then
begin
{ Si la case est vide, le coup est enregistré. }
Enregistre(aPo, a, b);
{ Si le pion n'a pas encore bougé, il a droit à un deuxième pas. }
if ((trait = 1) and (y = 2)) or ((trait = -1) and (y = 7)) then
begin
b := a + MP[2] * trait;
if damier[b] = 0 then
Enregistre(aPo, a, b);
end;
end;
{ Ensuite on passe aux mouvements en diagonale. }
for i := 3 to 4 do
begin
b := a + MP[i] * trait;
{ Pour que le coup soit valable, une pièce adverse doit être prise. }
if (damier[b] * trait * -1 in [P..R]) or (b = passant[trait * -1]) then
Enregistre(aPo, a, b);
end;
end;

Le principe est le même pour les autres pièces. Notons seulement que pour le fou, la tour et la dame, on utilise une boucle qui permet de générer les coups du plus court au plus long. On sort de la boucle si on rencontre une pièce adverse ou si on est sorti de l'échiquier (la pièce se trouvant sur une case ayant la valeur « hors-jeu »). Voici l'exemple de la tour.

T: { Tour }
for i := 1 to 4 do
begin
b := a;
repeat
Inc(b, MT[i]);
if damier[b] * trait * -1 in [0..R] then
Enregistre(aPo, a, b);
until damier[b] <> 0;
end;

Il est à noter que les coups ainsi générés ne sont pas des coups légaux, car on n'a pas vérifié si le roi n'était pas en échec après le coup. D'ailleurs, la détection de l'échec est basée sur cette procédure de génération des coups pseudolégaux.

La fonction Echec admet comme argument un enregistrement de type tPosition. On cherche si le roi de la couleur qui a le trait est en échec.

function Echec(const aPo: tPosition): boolean;
var
i: integer;
po: tPosition;
begin
result := FALSE;
po := aPo;
{ On inverse le trait, afin de générer les coups de l'adversaire. }
po.trait := po.trait * -1;
GenereCoupsOrdinaires(po);
{ On parcourt la liste des coups en cherchant si l'un de ces coups atteint le roi. }
for i := 1 to po.compte do
if po.damier[po.coups[i].b] = R * po.trait * -1 then
begin
result := TRUE;
Break;
end;
po.trait := po.trait * -1;
end;

A-t-on oublié le cas du roque qui met en échec l'adversaire ? Non, le cas est bien traité. Ce qu'on teste ici, c'est la prise du roi, qui ne peut se faire que par un mouvement ordinaire. Peu importe que la situation d'échec se présente à la suite d'un roque ou d'un autre coup.

Passons à la génération du roque, qui est une procédure assez complexe. Si vous arrivez à l'écrire du premier coup sans erreur, c'est que vous êtes très fort ! Voici la procédure qu'on a utilisée : elle est intégrée dans la procédure qui génère tous les coups.

procedure GenereTousLesCoups(var aPo: tPosition);

procedure GenereRoque(const aR, aT, pas: integer);
var
po: tPosition;
i, i1, i2: integer;
begin
with aPo do
begin
if damier[aT] * trait <> T then
Exit;
i := aR + pas;
repeat
if damier[i] <> 0 then
Exit;
Inc(i, pas);
until i = aT;
end;
if aR < aT then
begin
i1 := aR;
i2 := aT;
end else
begin
i1 := aT;
i2 := aR;
end;
po := aPo;
if not EmpechementRoque(po, i1, i2) then
Enregistre(aPo, aR, aR + 2 * pas);
end;

begin
GenereCoupsOrdinaires(aPo);
with aPo do
begin
if (damier[51] * trait = R) and (trait = +1) then
begin
if roque[E1G1] then GenereRoque(51, 81, +10);
if roque[E1C1] then GenereRoque(51, 11, -10);
end else
if (damier[58] * trait = R) and (trait = -1) then
begin
if roque[E8G8] then GenereRoque(58, 88, +10);
if roque[E8C8] then GenereRoque(58, 18, -10);
end;
end;
end;

On commence donc par vérifier que le roi de la bonne couleur est à sa place.

if (damier[51] * trait = R) and (trait = +1) then
begin

Ensuite on consulte la valeur de la variable roque, pour chacun des deux côtés. Si la valeur est TRUE (c'est-à-dire que ni la tour ni le roi n'ont bougé depuis le début de la partie), on appelle la procédure GenereRoque, avec comme arguments l'emplacement du roi, celui de la tour et la direction du mouvement du roi.

if roque[E1G1] then GenereRoque(51, 81, +10);

Cette procédure commence par vérifier que la tour est à sa place (car elle pourrait avoir été prise, sans avoir bougé).

if damier[aT] * trait <> T then
Exit;

On vérifie ensuite qu'aucune pièce ne se trouve entre le roi et la tour.

i := aR + pas;
repeat
if damier[i] <> 0 then
Exit;
Inc(i, pas);
until i = aT;

Enfin, si toutes les conditions qu'on vient de voir sont réunies, il reste à vérifier qu'aucune des cases du parcours n'est exposée à un coup de l'adversaire, ce qui inclut le cas où le roi serait en échec.

if not EmpechementRoque(po, i1, i2) then
Enregistre(aPo, aR, aR + 2 * pas);

La procédure EmpechementRoque est d'ailleurs calquée sur la procédure Echec : on génère les coups de l'adversaire et on cherche si l'un de ces coups n'atteint pas une case comprise entre la position initiale du roi et celle de la tour.

function EmpechementRoque(const aPo: tPosition; const b1, b2: integer): boolean;
var
i, b: integer;
po: tPosition;
begin
result := FALSE;
po := aPo;
po.trait := po.trait * -1;
GenereCoupsOrdinaires(po);
b := b1;
for i := 1 to po.compte do
while b <= b2 do
if po.coups[i].b = b then
begin
result := TRUE;
Break;
end else
Inc(b, 10);
po.trait := po.trait * -1;
end;

C'est tout ! Autant dire que si vous écrivez votre premier programme de jeu d'échecs, il serait peut-être sage de faire l'impasse sur le roque, qui occupe dans le programme une place disproportionnée par rapport à la fréquence de ce coup dans le jeu.

Évaluation des coups

Nous arrivons maintenant à la partie la plus intéressante et aussi la plus difficile du programme : la recherche du meilleur coup. Loin de moi la prétention de vous faire un cours sur le sujet ! Je vais seulement vous expliquer, dans la mesure où je l'ai compris, comment le programme de Jürgen Schlottke choisit ses coups. L'évaluation se fait en deux étapes que je vais vous présenter brièvement. Après cela, nous nous arrêterons sur l'étude d'un cas.

VI-A - Première étape

La première étape dans la procédure d'évaluation des coups consiste en la recherche du meilleur rapport entre le matériel du joueur et celui de l'adversaire.

On a vu que les pièces sont représentées par des nombres qui sont aussi une estimation de leur valeur. Il est à noter que dans la réalité, la valeur intrinsèque des pièces varie avec l'avancement de la partie ; cependant, nous n'en avons pas tenu compte ici.

const
P = 002; // Pion
F = 006; // Cavalier
C = 007; // Fou
T = 010; // Tour
D = 019; // Dame
R = 126; // Roi

Certains auteurs donnent au fou et au cavalier une valeur identique. À vous de voir !

On a vu également que la variable balance contenait la somme de la valeur des pièces présentes sur l'échiquier : somme supérieure à 0 si les blancs ont l'avantage, inférieure si ce sont les noirs (puisque les pièces noires sont représentées par des nombres négatifs).

Comme l'ordinateur doit pouvoir jouer aussi bien les blancs que les noirs, il nous faut une fonction qui inverse une fois sur deux la valeur de la variable balance, de telle sorte qu'une valeur supérieure à 0 signifie une différence matérielle favorable à l'ordinateur, quelle que soit la couleur qu'il joue.

function BalanceRelative(const aPo: tPosition; const aTr: integer): integer;
begin
result := aPo.balance * aTr;
end;

La première évaluation des coups est bâtie sur cette simple fonction. Pour chaque coup possible, on cherchera jusqu'à une certaine profondeur les positions résultant de ce coup et on suivra les évolutions de la balance.

La procédure de recherche du meilleur coup commence dans la boucle principale de la fonction Machine. Cette fonction est appelée lorsque c'est à l'ordinateur de jouer. Le résultat renvoyé par la fonction est le coup représenté par un nombre entier (ou 0 si l'ordinateur n'a aucun coup à jouer).

function Machine: integer;

À l'intérieur de la fonction Machine se trouve la fonction MeilleurCoup, laquelle reçoit comme argument le résultat de la fonction Max.

var
mc: integer; // meilleur coup

begin
mc := MeilleurCoup(Max(courante, courante.trait, 1, 32000));

Le principe de la fonction Max est d'attribuer une première note à chaque coup jouable, en fonction des valeurs minimales et maximales que pourra prendre la balance.

function Max(var aPo: tPosition; const aTr, aPr, alpha: integer): integer;
const
PROFMIN = 3;
PROFMAX = 5;
var
po: tPosition;
v, i, beta: integer;
arret: boolean;
begin
{ Générer tous les coups jouables. }
GenereTousLesCoups(aPo);
i := 0;
beta := -32000 * aPo.trait * aTr;
arret := FALSE;

{ Les jouer les uns après les autres, sur une copie locale de l'échiquier. }
while (i < aPo.compte) and not arret do
begin
Inc(i);
po := aPo;
Deplace(po, po.coups[i].a, po.coups[i].b);

{ Étudier toutes les combinaisons jusqu'à une certaine profondeur. Une fois
cette profondeur atteinte, on continue la recherche seulement s'il y a des
coups qui changent l'état de la balance. Si la profondeur maximale est atteinte,
on s'arrête. }
if ((aPr >= PROFMIN) and (aPo.damier[aPo.coups[i].b] = 0))
or (aPr = PROFMAX) then
v := BalanceRelative(po, aTr) // valeur définitive de v
else
v := Max(po, aTr, aPr+1, beta); // appel récursif de la fonction

{ On modifie en fonction de v la valeur des variables alpha et beta, qui représentent
les valeurs extrêmes de v. }
if aPo.trait = aTr then
begin
if v > beta then
beta := v;
if beta > alpha then
arret := TRUE;
end else
begin
if v < beta then
beta := v;
if beta < alpha then
arret := TRUE;
end;

aPo.coups[i].v := v;
end;
result := beta;
end;

Finalement la fonction Max renvoie le « meilleur minimum » trouvé : c'est-à-dire que si l'ordinateur joue ce coup, la balance ne pourra en aucun cas être inférieure à la valeur renvoyée, du moins sur le nombre de demi-coups examinés.

VI-B - Deuxième étape

C'est ce meilleur minimum qui est passé en argument à la fonction MeilleurCoup. Les coups de la liste ayant obtenu une note inférieure sont abandonnés ; les coups ayant obtenu la note maximale sont copiés dans une nouvelle liste, et le champ v de l'enregistrement est remis à zéro.

with courante do
begin
compte2 := 0;
for i := 1 to compte do
if coups[i].v = aMax then
begin
Inc(compte2);
coups2[compte2].a := coups[i].a;
coups2[compte2].b := coups[i].b;
coups2[compte2].v := 0;

Les coups de cette deuxième liste vont à présent être réévalués, d'après des critères de position.

On commence par attribuer une bonification au mouvement des pièces qui sont toujours sur leur emplacement initial ; la bonification est encore majorée si la pièce est un pion.

po := courante;
with po do
begin
if EtatInitial(po, coups2[i].a) then
begin
Inc(coups2[i].v, 5);
if damier[coups2[i].a] * trait = P then
Inc(coups2[i].v, 2);
end;

En revanche, on pénalise le mouvement du roi.

if damier[coups2[i].a] * trait = R then
Dec(coups2[i].v, 10);

On « encourage » les pièces à quitter les bords de l'échiquier ; on les « décourage » de s'y rendre.

if (coups2[i].a div 10 = 1) or (coups2[i].a div 10 = 8)
or (coups2[i].a mod 10 = 1) or (coups2[i].a mod 10 = 8) then
Inc(coups2[i].v, 2);
if (coups2[i].b div 10 = 1) or (coups2[i].b div 10 = 8)
or (coups2[i].b mod 10 = 1) or (coups2[i].b mod 10 = 8) then
Dec(coups2[i].v, 2);

Et ainsi de suite : si vous voulez en savoir davantage, je vous invite à aller regarder dans le programme.

Finalement la fonction renvoie l'index du dernier coup trouvé ayant obtenu la note maximale.

if coups2[i].v >= valMax then
begin
valMax := coups2[i].v;
result := i;
end;

VI-C - Étude d'un cas

Pour mieux saisir le fonctionnement des choses, je vous propose de considérer un exemple simple.

Voici la position que j'ai choisie. L'utilisateur a les blancs, l'ordinateur a les noirs. Les blancs ont le trait.

Je vais avancer de deux cases le pion qui est en e2. Il sera couvert par la tour mais le Noir devrait quand même prendre, le résultat de l'échange étant en sa faveur.

C'est ce qui arrive, et c'est le fou noir qui prend le pion.

Essayons maintenant de comprendre comment l'ordinateur a « choisi » ce coup. Pour cela j'ai inséré dans la fonction MeilleurCoup quelques lignes de code qui enregistrent dans un fichier les résultats obtenus.

Voici ces résultats.

aMax=2

c3e4 v(1)=aMax
c3e2 v(1)<aMax
c3d1 v(1)<aMax
c3b1 v(1)<aMax
c3a2 v(1)<aMax
c3a4 v(1)<aMax
c3b5 v(1)<aMax
d5e6 v(1)<aMax
d5f7 v(1)<aMax
d5g8 v(1)<aMax
d5c4 v(1)<aMax
d5b3 v(1)<aMax
d5a2 v(1)<aMax
d5c6 v(1)<aMax
d5b7 v(1)<aMax
d5a8 v(1)<aMax
d5e4 v(1)=aMax
e8e7 v(1)<aMax
e8d8 v(1)<aMax
e8f8 v(1)<aMax
e8d7 v(1)<aMax
e8f7 v(1)<aMax

c3e4 v(2)=31 valMax=31
d5e4 v(2)=34 valMax=34

Meilleur coup: d5e4

Comme on peut le voir, seuls deux coups ont été admis sur la deuxième liste, à savoir la prise du pion par le cavalier ou par la tour. Dans les deux cas, l'échange est à l'avantage du Noir. Mais pourquoi aMax vaut-il 2 ? Parce que c'est la valeur du pion, telle qu'elle a été établie au début du programme.

const
Pion = 2;

Or par la suite la balance ne peut jamais prendre une valeur inférieure : si le Blanc s'abstient de prendre la pièce (fou ou cavalier) qui vient de capturer le pion, la valeur de la balance reste à 2 ; si au contraire la tour prend le fou ou le cavalier, la différence matérielle en faveur du Noir augmente au coup suivant, par la prise de la tour.

Essayons maintenant de comprendre pourquoi c'est finalement le fou qui est déplacé.

Premièrement, l'échiquier ayant été initialisé dans cette position, les deux coups reçoivent un bonus de cinq points : c'est la prime au premier déplacement que nous avons déjà vue plus haut.

if EtatInitial(po, coups2[i].a) then
begin
Inc(coups2[i].v, 5);

Les deux coups reçoivent ensuite 20 points supplémentaires : c'est la prime à la mobilité en début de partie, dont bénéficient les pions, les cavaliers et les fous.

if (demiCoups < 32) and (damier[coups2[i].a] * trait in [P,C,F]) then
Inc(coups2[i].v, 20);

Jusqu'ici les deux coups ont la même note. Mais voici qu'on compte le nombre de deuxièmes coups possibles, comme si le Noir avait le droit de jouer deux coups à la suite.

{ On inverse le trait pour permettre à l'ordinateur un deuxième coup fictif. }
po.trait := po.trait * -1;
{ On génère les coups. }
GenereCoupsOrdinaires(po);
for j := 1 to po.compte do
begin
{ On ajoute un point pour chaque coup, sans distinction. }
Inc(coups2[i].v);
{ On ajoute un second point pour les coups qui atteignent une pièce adverse. }
if po.damier[po.coups[j].b] <> 0 then
Inc(coups2[i].v);
end;

Si c'est le cavalier qui se déplace, il barrera le chemin du fou vers les cases f3, g2, h1 ; alors que si c'est le fou qui se déplace, la mobilité du cavalier sera intacte. Voilà pourquoi le coup du fou obtient finalement 3 points supplémentaires.

Livre d'ouvertures

Quoiqu'un livre d'ouvertures ne soit pas indispensable, en général les programmes d'échecs en ont un, qui remplace avantageusement l'évaluation par algorithme pour les premiers coups de la partie.

J'ai donc ajouté un livre à mon programme. Il n'est pas fort épais : je l'ai fait moi-même avec un simple éditeur de texte. Pour choisir les coups, je me suis aidé des Pro Deo Utilities d'Ed Schröder.

Dans son état initial, le livre est un fichier contenant des lignes comme celle-ci :

e2e4e7e5g1f3b8c6f1b5a7a6b5a4g8f6e1g1b7b5a4b3c8b7f1e1f8c5

Les plus longues lignes ont 96 caractères, soit 24 demi-coups. Pour chercher un coup dans le livre, le programme ouvre le fichier, lit les lignes une à une jusqu'à en trouver une qui commence par la séquence de coups déjà jouée : il ne reste plus alors qu'à extraire les quatre caractères suivants.

J'aurais pu conserver mon fichier tel quel, mais ayant appris récemment à utiliser les tables de chaînes, j'ai voulu m'en servir dans ce projet. J'ai donc écrit un petit programme pour convertir le fichier LIVRE.TXT en un fichier LIVRE.RC contenant une table de chaînes.

Le début du fichier se présente maintenant comme ceci :

STRINGTABLE
{
1, "e2e4e7e5g1f3b8c6f1b5a7a6b5a4g8f6e1g1b7b5a4b3c8b7f1e1f8c5"

Après quoi j'ai utilisé Resource Workshop pour compiler ce dernier fichier et obtenir enfin un fichier LIVRE.RES, que je n'avais plus qu'à inclure dans mon programme.

Interface graphique

Il me reste à vous présenter l'interface graphique que j'ai réalisée pour ce programme. Elle est vraiment très simple : aussi serai-je bref.

VIII-A - Utilisation d'une police True Type

Pour le dessin des pièces, j'ai utilisé une police True Type, à savoir la police Chess Alpha(7). Pour que le programme fonctionne correctement, la police doit être installée sur votre ordinateur.

Cette police de caractères s'utilise comme n'importe quelle autre : la différence est qu'au lieu de contenir des lettres, elle contient des dessins de pièces et aussi d'autres éléments nécessaires à l'affichage d'un échiquier.

Par exemple, pour obtenir l'image du roi blanc sur une case blanche, il faut faire comme si l'on voulait écrire « k » ; pour le roi blanc sur une case noire, il faut écrire « K ». Si la police est sélectionnée, on verra à la place de ces lettres l'image souhaitée.

Après avoir pris connaissance des conventions utilisées par l'auteur de cette police, j'ai écrit une procédure qui, à partir de la position actuelle des pièces (contenue dans la variable damier), remplit un tableau de caractères avec les valeurs appropriées. Plus exactement, j'ai écrit deux procédures, l'une pour les caractères permanents de la chaîne (à savoir les bords de l'échiquier et les caractères de retour à la ligne), l'autre pour les caractères variables (qui dépendent de la position des pièces).

procedure InitialiseChaine;

function IIF(const aBool: boolean; const aChar1, aChar2: char): char;
begin
if aBool then result := aChar1 else result := aChar2;
end;

const
COORD = TRUE;
var
i: integer;
begin
for i := 0 to 117 do
chaine[i] := #32;
chaine[118] := #0;
for i := 1 to 9 do
begin
chaine[12*i-2] := #13;
chaine[12*i-1] := #10;
end;
chaine[000] := '1';
chaine[009] := '3';
chaine[108] := '6';
chaine[117] := '8';
for i := 1 to 8 do
begin
chaine[i+0000] := '2';
chaine[i+0108] := IIF(COORD, Chr(i+199), '7');
chaine[12*i+0] := IIF(COORD, Chr(200-i), '4');
chaine[12*i+9] := '5';
end;
end;

procedure ActualiseChaine;
var
x, y: integer;
begin
for x := 1 to 8 do
for y := 1 to 8 do
case courante.damier[10*x+y] of
-R: chaine[12 * (9-y) + x] := Chr(108 - 32 * Ord((x+y) mod 2=0));
-D: chaine[12 * (9-y) + x] := Chr(119 - 32 * Ord((x+y) mod 2=0));
-T: chaine[12 * (9-y) + x] := Chr(116 - 32 * Ord((x+y) mod 2=0));
-C: chaine[12 * (9-y) + x] := Chr(106 - 32 * Ord((x+y) mod 2=0));
-F: chaine[12 * (9-y) + x] := Chr(110 - 32 * Ord((x+y) mod 2=0));
-P: chaine[12 * (9-y) + x] := Chr(111 - 32 * Ord((x+y) mod 2=0));
0: chaine[12 * (9-y) + x] := Chr(032 + 11 * Ord((x+y) mod 2=0));
+P: chaine[12 * (9-y) + x] := Chr(112 - 32 * Ord((x+y) mod 2=0));
+F: chaine[12 * (9-y) + x] := Chr(098 - 32 * Ord((x+y) mod 2=0));
+C: chaine[12 * (9-y) + x] := Chr(104 - 32 * Ord((x+y) mod 2=0));
+T: chaine[12 * (9-y) + x] := Chr(114 - 32 * Ord((x+y) mod 2=0));
+D: chaine[12 * (9-y) + x] := Chr(113 - 32 * Ord((x+y) mod 2=0));
+R: chaine[12 * (9-y) + x] := Chr(107 - 32 * Ord((x+y) mod 2=0));
end;
end;

La variable chaine est déclarée dans la partie interface de l'unité.

var chaine: array[0..118] of char;

Elle sera passée en argument à la fonction DrawText dans le programme principal.

VIII-B - Programmation Win32 avec la bibliothèque OWL

Le programme principal, contenu dans le fichier JEU, a été écrit pour Virtual Pascal et la bibliothèque OWL. C'est une simple fenêtre, sans bordure ni titre. Elle ne contient que l'échiquier et un bouton pour fermer la fenêtre.

Si ce style de programmation vous intéresse, je vous renvoie à l'excellent tutoriel d'Alcatîz sur laprogrammation win32 en Virtual Pascal avec OWL. C'est là que j'ai trouvé la base de mon code. J'ai aussi fait quelques emprunts aux Lemmings de Paul TOTH.

Voici donc la déclaration des deux objets principaux, l'un dérivé du type tWindow (une fenêtre donc), l'autre du type tApplication (un programme).

type
pCssBrdWnd = ^tCssBrdWnd;
tCssBrdWnd = object(tWindow)
PinceauFond: hBrush;
R: tRect;
constructor Init(p: pWindowsObject; aName: pChar);
procedure SetUpWindow; virtual;
procedure GetWindowClass(var aWndClass: tWndClass); virtual;
procedure DrawCloseButton(aDC: hDC);
procedure Paint(PaintDC: hDC; var PaintInfo: tPaintStruct); virtual;
procedure WMLButtonDown(var msg: tMessage); virtual wm_First + wm_LButtonDown;
destructor Done; virtual;
end;

tCssPrg = object(tApplication)
procedure InitMainWindow; virtual;
end;

La boucle principale du programme est fort courte.

var
CP: tCssPrg;

begin
CP.Init('');
CP.Run;
CP.Done;
end.

Le déroulement du jeu est géré dans la méthode WMLButtonDown, c'est-à-dire que toute l'exécution du programme dépend des clics de la souris.

Je ne vous expliquerai pas dans le détail comment les choses fonctionnent : ce serait long et cela nous éloignerait du sujet de cet article. Disons simplement que le programme interprète les clics de la souris sur les cases de l'échiquier, et lorsque l'utilisateur a cliqué sur deux cases, la variable cmd (commande), qui peut valoir par exemple 5254 (« e2e4 »), est passée en argument à la fonction Valide de l'unité ECHECS. Si le coup est valide, il est d'abord joué dans l'échiquier interne, après quoi le programme principal s'occupe de faire les modifications correspondantes à l'écran.

IX - Conclusion

Voilà notre programme terminé. Il lui manque beaucoup de choses pour rivaliser avec les plus beaux jeux d'échecs : son interface est réduite au strict nécessaire, l'utilisateur n'ayant pas d'autre possibilité que de jouer ou de fermer le programme ; on ne peut pas attraper les pièces avec la souris, etc.

Du côté du moteur aussi, cela va sans dire, bien des améliorations pourraient être apportées : on pourrait toujours chercher le moyen de rendre l'automate plus fort, ne serait-ce qu'en augmentant la profondeur de recherche, qui dans l'état actuel du programme est limitée à cinq demi-coups.

const
PROFMIN = 3;
PROFMAX = 5;

Cependant l'amélioration d'un moteur de jeu d'échecs est une tâche infinie : on ne connaît pas le meilleur coup ; on ne sait pas non plus pourquoi le moteur joue ceci plutôt que cela, ou du moins il n'est pas facile de le savoir, à cause du grand nombre d'opérations impliquées dans la procédure.

L'ambition de cet article (comme celle du programme original) n'était que de présenter les fonctions essentielles d'un jeu d'échecs, et de montrer une façon d'écrire ces fonctions.

X - Remerciements

Je remercie Yves Lemaire, Jean-Luc Gofflot et Claude Leloup pour leur relecture.

(1)« Schachspiel : Demonstration der Schachprogrammierung unter Turbo-Pascal. » Jürgen Schlottke, 1993.

(2)On appelle « ouverture » les premiers coups de la partie. Les bons joueurs d'échecs connaissent par expérience les meilleurs enchaînements. Grâce au « livre » que nous allons lui fabriquer, notre automate aura lui aussi une espèce de science des ouvertures.

(3)Les valeurs renvoyées vont de 0 à 3 (en cours, échec, pat, échec et mat).

(4)« Chess Alpha, a True Type Font for chess diagrams and figurine notation. » Copyright Eric Bentzen, 1998. J'ai trouvé la police sur cette page : www.enpassant.dk

(5)On a volontairement négligé la règle des répétitions (qui veut que la partie soit déclarée nulle si la même position revient deux fois) et aussi celle des 50 coups (partie nulle après 50 demi-coups sans prise ni pion déplacé).

(6)À vrai dire, je n'en sais rien. Peut-être qu'avec plusieurs dames, par exemple, cette limite pourrait être dépassée. En travaillant sur mon programme, je ne me souviens pas d'avoir jamais vu une liste contenant plus de soixante coups. Les savants disent qu'il y en a en moyenne trente-cinq.

(7)« Chess Alpha, a True Type Font for chess diagrams and figurine notation. » Copyright Eric Bentzen, 1998.