Conception d'un jeu d'échecs en Pascal

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.

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.

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.

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.

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.

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;

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.

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.

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.