Projet d'un programme de jeu d'échecs

[Roland Chastain]

Merci pour ces explications. Cette fois (mis à part certaines connaissances qui me manquent) je crois que j'ai compris.

Autrement après une journée de recherches j'ai fini par trouver mon erreur : car c'était bien une vilaine erreur de ma part, à savoir une fonction qui s'appelait elle-même.

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
   Function Passage: Boolean;
    Var
      vx,vy,x,y: ShortInt;
      Obstacle: Boolean;
    Begin
      Passage:=Faux;
      Obstacle:=Faux;
      vx:=Signe(dx);
      vy:=Signe(dy);
      x:=x1;
      y:=y1;
      Repeat
 
        Inc(x,vx);
        Inc(y,vy);
        If (x=x2) And (y=y2) Then Passage:=Vrai;
        If (Passage=Faux) And (E[x,y]<>Vide) Then Obstacle:=Vrai;
 
      Until (Passage or Obstacle); { <--- Pas bon. }
    End;

C'était un essai involontaire de fonction récursive !

Voici la version corrigée, avec une variable en plus :

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
    Function Chemin: Boolean; { Changé le nom de la fonction. }
 
      Var
        x,y: TCoord;
        vx,vy: TCouleur;
        Obstacle: Boolean;
        Passage: Boolean;
 
      Begin
        Passage:=False;
        Obstacle:=False;
        vx:=Signe(x2-x1);
        vy:=Signe(y2-y1);
        x:=x1;
        y:=y1;
        Repeat
          Inc(x,vx);
          Inc(y,vy);
          If (x=x2) And (y=y2) Then
            Passage:=True
          Else
            If T[x,y]<>0 Then Obstacle:=True;
        Until Passage Or Obstacle;  { <--- Bon. Plus d'appel récursif. }
 
        Chemin:=Passage;
 
      End;

Joyeuses Pâques !

[Roland Chastain]

Bonjour !

J'ai réécrit la partie du programme qui calcule les coups possibles. J'ai essayé de tirer profit des conseils donnés par Alcatîz et par Paul TOTH concernant les paramètres. Voici l'en-tête de la fonction :

Code :

1
2
3
4
5
6
Procedure Possibles (Const T:TTablier;
                     Const C:TCouleur;
                     Const Prim:T4Bool;
                     Const Pass: TCarreau;
                     F: String;
                     Var N: Byte);

Cela donne un échiquier sur lequel je joue contre moi-même, vu qu'il n'y a pas d'évaluation. L'ordinateur vérifie que le coup saisi est sur la liste. Il détecte l'échec, le mat, les coups spéciaux.

[Paul TOTH]

voici deux petites remarques rapides

1) pour compiler le projet sous Delphi il suffit de faire ceci

Code :

1
2
3
4
5
6
7
8
 
{$IFDEF WIN32}
{$APPTYPE CONSOLE}
uses
  Crt; // http://sourceforge.net/projects/delphicrt/
{$ELSE}
Uses Crt, Dos;
{$ENDIF}

2) je pense que "fictif" correspond à ma remarque

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
// en paramètre : var T: TTablier;
// en variable : fictif: TPiece
...
              //fictif:=T;
              //fictif[x2,y2]:=fictif[x1,y1];
              //fictif[x1,y1]:=0;
              // sauver le coup
              fictif := T[x2,y2];
              T[x2,y2] := T[x1,y1];
              T[x1,y1] := 0;
 
              If Not EchecAuRoi({fictif} T,C) Then
              Begin
                cp:=Concat(NomCarreau(x1,y1),NomCarreau(x2,y2));
                Write(lst,cp);
                Inc(Ntemp);
              End;
              // restituer le coup
              T[x1,y1] := T[x2,y2];
              T[x2,y2] := fictif;

[/code]

[Roland Chastain]

Envoyé par Paul TOTH

1) pour compiler le projet sous Delphi il suffit de faire ceci

Je peux donc compiler mon code Turbo Pascal sous Delphi ? Bon à savoir !

Mais je n'ai pas encore vraiment pris en main Delphi, mis à part me servir de l'éditeur pour taper mon code.



J'ai téléchargé l'unité Delphi Crt, mais je n'ai réussi à compiler aucune des deux unités contenues dans le dossier. Dans les deux cas j'obtiens un message d'erreur :

[DCC Erreur] crt.pas(1222): E2010 Types incompatibles : 'AnsiChar' et 'Char'
[DCC Erreur] crt.pas(1244): E2010 Types incompatibles : 'AnsiChar' et 'Char'
[DCC Avertissement] crt.pas(1253): W1061 La réduction de la constante WideChar donnée (#$FFFF) en AnsiChar génère une perte d'information
[DCC Erreur fatale] Project1.dpr(6): F2063 Impossible de compiler l'unité utilisée 'Crt.pas'

C'est avec Delphi XE2. Peut-être il faudrait que j'essaie avec Delphi 6 ou 7, mais je ne veux pas perdre ma journée là-dessus. De toute façon, si je me lance dans un projet Delphi, je ne pense pas que j'utiliserai l'unité Crt. Sinon autant rester à Turbo Pascal, non ? J'ai fait un essai de compilation d'une application console, en ajoutant juste une instruction "write" au modèle. Résultat, un exécutable de ... 1047 ko ! Ça n'est pas très intéressant, un programme d'une tonne qui dit "bonjour"...

Envoyé par Paul TOTH

2) je pense que "fictif" correspond à ma remarque

J'ai bien compris l'idée de ne restaurer que les valeurs qui ont changé. C'est même comme ça que je faisais dans mes premiers programmes, mais j'y ai renoncé. S'il n'y avait que des mouvements ordinaires, cette solution irait très bien, mais le coup simulé peut être aussi : un pion se changeant en dame, un roque, une prise en passant. Il faut donc détecter ces coups spéciaux, et enregistrer les valeurs qui ont changé mais qui ne sont pas les mêmes dans chaque cas. C'est très faisable, mais c'est un peu casse-tête et ça complique le code. Ce sera peut-être plus rapide à l'exécution, mais je me pose la question, vu les tests qu'il faut ajouter.

[Paul TOTH]

Envoyé par Roland Chastain

Je peux donc compiler mon code Turbo Pascal sous Delphi ? Bon à savoir !

Mais je n'ai pas encore vraiment pris en main Delphi, mis à part me servir de l'éditeur pour taper mon code.



J'ai téléchargé l'unité Delphi Crt, mais je n'ai réussi à compiler aucune des deux unités contenues dans le dossier. Dans les deux cas j'obtiens un message d'erreur :



C'est avec Delphi XE2. Peut-être il faudrait que j'essaie avec Delphi 6 ou 7, mais je ne veux pas perdre ma journée là-dessus. De toute façon, si je me lance dans un projet Delphi, je ne pense pas que j'utiliserai l'unité Crt. Sinon autant rester à Turbo Pascal, non ? J'ai fait un essai de compilation d'une application console, en ajoutant juste une instruction "write" au modèle. Résultat, un exécutable de ... 1047 ko ! Ça n'est pas très intéressant, un programme d'une tonne qui dit "bonjour"...

c'est surtout que Windows 7 64bits ne sait pas executer des applications DOS

mais en effet j'ai utilisé Delphi 6 et non XE2 avec ces chaînes Unicode.

J'ai bien compris l'idée de ne restaurer que les valeurs qui ont changé. C'est même comme ça que je faisais dans mes premiers programmes, mais j'y ai renoncé. S'il n'y avait que des mouvements ordinaires, cette solution irait très bien, mais le coup simulé peut être aussi : un pion se changeant en dame, un roque, une prise en passant. Il faut donc détecter ces coups spéciaux, et enregistrer les valeurs qui ont changé mais qui ne sont pas les mêmes dans chaque cas. C'est très faisable, mais c'est un peu casse-tête et ça complique le code. Ce sera peut-être plus rapide à l'exécution, mais je me pose la question, vu les tests qu'il faut ajouter.

oui enfin le but est surtout d'économiser la pile

mais il y a une autre astuce possible:

Code :

1
2
3
4
5
6
7
8
9
10
11
 
procedure test;
var
  fictif: ^TTablier;
begin
  New(fictif);
  ...
  fictif^[x,y] := ...
  ...
  dispose(fictif);
end;

avec cela tu n'as qu'un pointeur dans la pile, le Tablier est alloué dans le tas (mémoire globale) qui est moins limitée que la pile.

[Roland Chastain]

Envoyé par Paul TOTH

en effet j'ai utilisé Delphi 6 et non XE2 avec ses chaînes Unicode

Je viens de faire l'essai : impeccable. Je vais pouvoir commencer à travailler sous Delphi.

Envoyé par Paul TOTH

oui enfin le but est surtout d'économiser la pile

C'est vrai, merci pour la précision.

Envoyé par Paul TOTH

mais il y a une autre astuce possible:

avec cela tu n'as qu'un pointeur dans la pile, le Tablier est alloué dans le tas (mémoire globale) qui est moins limitée que la pile.

C'est noté. Je vais regarder ça de près.

[Roland Chastain]

Bonjour !

Voici l'état actuel de mon projet. C'est un programme qui calcule toutes les variantes possibles sur un ensemble de quatre "demi-coups", soit deux "plis". Les variantes défilent à l'écran et sont enregistrées dans un fichier texte.

Pour la profondeur en question, cela donne un peu plus de 196 000 combinaisons. Sur ma machine, le programme prend une trentaine secondes pour s'exécuter.

N.B. Pour que le programme fonctionne, il faut modifier cette ligne qui se trouve tout au début :

Code :

1
2
3
Const
 
  CheminFichiers='C:\ATELIER\PASCAL\'; { ! }

[Roland Chastain]

Envoyé par Roland Chastain

J'ai fait un essai de compilation d'une application console, en ajoutant juste une instruction "write" au modèle. Résultat, un exécutable de ... 1047 ko ! Ça n'est pas très intéressant, un programme d'une tonne qui dit "bonjour"...

Je viens de comprendre mon erreur en lisant cette discussion.

En choisissant la configuration Release (au lieu de Debug) dans le gestionnaire de projet, la taille de l'exécutable passe à 134 ko.

EDIT
Et si on se passe de l'unité SysUtils, on obtient un exécutable de 28 ko.

[Roland Chastain]

Bonjour !

Je m'étais promis de finir un programme pour TP7. C'est chose faite.

Le code que je propose est une réécriture d'un programme que j'ai trouvé sur cette page parmi d'autres sources de jeux d'échecs en Pascal.

Maintenant je suis décidé à changer de compilateur, et j'ai choisi Free-Pascal pour continuer ce projet. Peut-être que j'ouvrirai une nouvelle discussion, si besoin est.

[Archimède]

Très intéressant le lien... merci

[M.Dlb]

Pourquoi ne pas avoir continué ton propre code ? Ca avait l'air prometteur !

[Roland Chastain]

Envoyé par wormful_sickfoot

Pourquoi ne pas avoir continué ton propre code ? Ca avait l'air prometteur !

Je ne voyais pas comment le finir. J'ai trouvé des solutions dans ce programme. J'y ai aussi trouvé des façons de procéder plus simples et plus économiques. Par exemple la représentation de l'échiquier :

Code :

tablier: array[-10..109] of shortint;

et des pièces :

Code :

cavalier: array[1..8] of shortint = (12, 21, 19, 8, -12, -21, -19, -8);

Moi j'avais fait comme ça :

Code :

tablier: array[0..7, 0..7] of shortint

et pour les mouvements des pièces, des équations :

Code :

if (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1) = 5 then

Cette façon me plaisait mais la première est bien meilleure : elle produit le même résultat avec peut-être cent fois moins d'opérations.

[Roland Chastain]

Donc j'ai repris mon programme depuis le début pour y apporter d'importantes modifications et, à cette occasion, je passe au compilateur Free-Pascal.

La première modification importante est le type utilisé pour représenter le tablier, à savoir un vecteur de 120 éléments. J'ai constaté que ce type était souvent utilisé dans les programmes d'échecs. Effectivement il est commode.

J'essaie de mieux organiser mon code, notamment en mettant à part tout ce qui concerne l'affichage, de façon à ce que le programme puisse être utilisé depuis une autre interface sans qu'on ait besoin de le modifier.

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
program Echecs; { Free-Pascal 2.6.0 }
 
const
  neant    = 0;
  pion     = 1;
  cavalier = 2;
  fou      = 3;
  tour     = 4;
  dame     = 5;
  roi      = 6;
  horsJeu  = 7;
  noir     =-1;
  blanc    = 1;
  e8c8     = 0;
  e8g8     = 1;
  e1c1     = 2;
  e1g1     = 3;
 
type
  tCouleur    = noir .. blanc;
  tPiece      = roi * noir .. horsJeu;
  tCarreau    = 11 - 21 .. 88 + 21;
  tDamier     = array [tCarreau] of tPiece;
  tPosition   = record
                  damier: tDamier;
                  trait: tCouleur;
                  roque: array [0 .. 3] of boolean;
                  enPassant: tCarreau;
                  demiCoups: word;
                  coups: word;
                end;
 
const
  initial: tDamier = (
  07,07,07,07,07,07,07,07,07,07,
  07,07,07,07,07,07,07,07,07,07,
  07,+4,+2,+3,+5,+6,+3,+2,+4,07,
  07,+1,+1,+1,+1,+1,+1,+1,+1,07,
  07,00,00,00,00,00,00,00,00,07,
  07,00,00,00,00,00,00,00,00,07,
  07,00,00,00,00,00,00,00,00,07,
  07,00,00,00,00,00,00,00,00,07,
  07,-1,-1,-1,-1,-1,-1,-1,-1,07,
  07,-4,-2,-3,-5,-6,-3,-2,-4,07,
  07,07,07,07,07,07,07,07,07,07,
  07,07,07,07,07,07,07,07,07,07);
 
type
  tNomCarreau = string[2];
 
var
  courante: tPosition;
 
procedure initialise(var p: tPosition);
begin
  p.damier := initial;
  p.trait := blanc;
  p.roque[e1c1] := true;
  p.roque[e1g1] := true;
  p.roque[e8c8] := true;
  p.roque[e8g8] := true;
  p.enPassant := 0;
  // 0, 31..38, 61..68
  p.demiCoups := 0;
  // remis … z‚ro en cas de prise ou de pion d‚plac‚
  p.coups := 1;
  // ‚changes de coups
end;
 
{$i affichageConsole.inc}
 
function nomCarreau(const c: tCarreau): tNomCarreau;
begin
  nomCarreau := chr(c mod 10 + 96) + chr(c div 10 + 48);
end;
 
{$i testNomCarreau.inc}
 
begin
  initialise(courante);
  affichageConsole(courante);
  testNomCarreau;
  readLn;
end.

[M.Dlb]

Petite remarque. L'utilisation de types "commodes" peut s'avérer être une solution pour la réalisation d'un programme, mais je pense que leur utilisation n'est pas toujours adéquate, en terme de lisibilité et de compréhension du code.

Relire des programmes qu'on a écrit des années après, en ayant utilisé ces commodités, peut être plus difficile avec des types "commodes" mais ne représentant pas la réalité. Chacun sa façon de penser, mais personnellement je suis pour utiliser des types qui représentent la réalité au plus près. Un damier est fait de 8 cases sur 8, alors pourquoi utiliser un vecteur qui va de -10 à 109. Ca n'engage que moi, mais ca me parait aberrant.

De plus, même si l'écriture est compliquée, le compilateur saura de toutes façons faire les bonnes optimisations lors de la compilation du code.

[droggo]

Loe,

+1 sur l'utilisation des types "commodes".

Ça se termine habituellement par un code incompréhensible, y compris pour l'auteur s'il doit y revenir plus tard (le "plus tard" correspondant à un délai variable, selon l'auteur et la taille du code)

[Roland Chastain]

Envoyé par wormful_sickfoot

Petite remarque. L'utilisation de types "commodes" peut s'avérer être une solution pour la réalisation d'un programme, mais je pense que leur utilisation n'est pas toujours adéquate, en terme de lisibilité et de compréhension du code.

Relire des programmes qu'on a écrit des années après, en ayant utilisé ces commodités, peut être plus difficile avec des types "commodes" mais ne représentant pas la réalité. Chacun sa façon de penser, mais personnellement je suis pour utiliser des types qui représentent la réalité au plus près. Un damier est fait de 8 cases sur 8, alors pourquoi utiliser un vecteur qui va de -10 à 109. Ca n'engage que moi, mais ca me parait aberrant.

De plus, même si l'écriture est compliquée, le compilateur saura de toutes façons faire les bonnes optimisations lors de la compilation du code.

Je te remercie d'avoir donné franchement ton avis. Je suis prêt à réexaminer la question.

Je suis plutôt d'accord avec ce que tu dis. Seulement j'ai observé une grande différence de vitesse entre mes précédents programmes et celui que j'ai adapté, et il m'a semblé que cette différence vient principalement du type utilisé pour la représentation de l'échiquier.

Entrons dans le détail.

Par convention, les cases de l'échiquier correspondent aux numéros d'index 11 à 18, 21 à 28, 31 à 38 etc.

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
const
  initial: tDamier = (
  07,07,07,07,07,07,07,07,07,07,  {-10.. -1}
  07,07,07,07,07,07,07,07,07,07,  {  0..  9}
  07,+4,+2,+3,+5,+6,+3,+2,+4,07,  { 10.. 19}
  07,+1,+1,+1,+1,+1,+1,+1,+1,07,  { 20.. 29}
  07,00,00,00,00,00,00,00,00,07,  { 30.. 39}
  07,00,00,00,00,00,00,00,00,07,  { 40.. 49}
  07,00,00,00,00,00,00,00,00,07,  { 50.. 59}
  07,00,00,00,00,00,00,00,00,07,  { 60.. 69}
  07,-1,-1,-1,-1,-1,-1,-1,-1,07,  { 70.. 79}
  07,-4,-2,-3,-5,-6,-3,-2,-4,07,  { 80.. 89}
  07,07,07,07,07,07,07,07,07,07,  { 90.. 99}
  07,07,07,07,07,07,07,07,07,07); {100..109}

On retrouve donc les coordonnées cartésiennes : le nombre de dizaines est la ligne, le nombre d'unités est la colonne. L'un et l'autre peuvent très facilement être obtenus au moyen de div 10 et mod 10.

Code :

1
2
3
4
5
6
function coordCarreau(const n: tCarreau): tCoordCarreau;
begin
  coordCarreau.x := n mod 10;
  coordCarreau.y := n div 10;
  // 11 = 'a1' = (1, 1)
end;

Cela étant dit, il est évident que ce système est économique, puisqu'une case sera représentée par un nombre au lieu de deux, un coup sera représenté par deux nombres au lieu de quatre.

Et puis il y a aussi la façon de générer les coups. Dans mes précédents programmes, j'examinais toutes les combinaisons de cases possibles pour ne retenir que les combinaisons vérifiant telle ou telle équation. Au lieu de cela, le programme dont je m'inspire utilise pour chaque pièce un ensemble de nombre relatifs représentant les mouvements possibles. Le plus grand de ces nombres, en valeur absolue, est 21 (qui est un mouvement du cavalier). C'est pourquoi l'index va de 11-21=-10 à 88+21=109. Du coup, au lieu de passer au crible toutes les combinaisons possibles, je vais directement aux bonnes cases. Si le coup tombe en dehors de l'échiquier, la variable prend simplement la valeur horsJeu.

C'est vrai que je pourrais utiliser ce système avec des coordonnées. C'est à étudier.

Le problème que tu soulèves (la représentation de la réalité) est très intéressant. Moi aussi je préfère la représentation la plus fidèle, mais je me suis aperçu qu'elle ne va pas toujours avec l'efficacité.

Un exemple encore à ce sujet. Aux échecs, comme chacun sait, on ne prend jamais le roi. Au début j'étais horrifié quand je voyais dans une routine tant de points attribués à la prise du roi.

Code :

1
2
3
4
5
6
  valeurPion = 2;
  valeurFou = 6;
  valeurCavalier = 7;
  valeurTour = 10;
  valeurRoi = 126;
  valeurDame =  19;

Mais entre-temps je me suis aperçu que c'était beaucoup plus simple de faire comme ça, que d'introduire dans l'évaluation la notion de mat. En effet, le mat signifie qu'au prochain coup le roi sera pris, même si cela n'est pas permis par les règles du jeu.

[droggo]

Zei,

Envoyé par Roland Chastain

En effet, le mat signifie qu'au prochain coup le roi sera pris, même si cela n'est pas permis par les règles du jeu.

Pas précisément.

Mat signifie que le roi est en prise et qu'il n'y a aucun moyen de l'en sortir, ce qui n'est pas tout à fait la même chose.

[Roland Chastain]

Envoyé par droggo

Mat signifie que le roi est en prise et qu'il n'y a aucun moyen de l'en sortir, ce qui n'est pas tout à fait la même chose.

Certes.

Cependant il est avantageux, pour la prévision et l'évaluation, de ne pas faire cette distinction et de considérer le roi comme une pièce ordinaire, qui a simplement plus de valeur que les autres. Cela simplifie beaucoup les choses, sans rien changer au résultat, si ce n'est que la prévision peut s'étendre plus loin puisqu'elle emploie moins d'opérations.

[droggo]

Joe,

J'avais bien compris le but, c'était juste pour rectifier l'expression.

[Roland Chastain]

Envoyé par droggo

Joe,

J'avais bien compris le but, c'était juste pour rectifier l'expression.

Elle le méritait en effet.

Voici la suite : une fonction qui détecte l'échec. D'après le test inclus dans le programme, elle paraît fonctionner correctement.

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
 
program Echecs;
 
// Free-Pascal 2.6
 
{$i const1.inc}
{$i type.inc}
{$i const2.inc}
{$i var.inc}
{$i initialise.inc}
{$i intToStr.inc}
{$i signe.inc}
{$i affichageConsole.inc}
{$i nomCarreau.inc}
{$i testNomCarreau.inc}
{$i coordCarreau.inc}
{$i testCoordCarreau.inc}
{$i geometrie.inc}
{$i echec.inc}
{$i testEchec.inc}
 
begin
  initialise(courante);
  affichageConsole(courante);
  testNomCarreau;
  testCoordCarreau;
  testEchec;
  readLn;
end.