Get jChecs at SourceForge.net. Fast, secure and Free Open Source software downloads
Conception
Encodage d'une position
Représentation ASCII

Il est possible d’encoder les états complets du jeu sous forme ASCII, comme le démontre par exemple la notation FEN. La lisibilité et la relative légèreté de ce type d’encodage le rendent même particulièrement adapté aux échanges externes.

Un tel format est par contre inadapté dans une situation où les états doivent rapidement être dérivés les uns des autres et où les possibilités de mouvements doivent être recherchées. Un autre type d’encodage doit donc être utilisé en interne par les moteurs de jChecs.

Données génériques

Les informations à conserver pour stocker un état du jeu peuvent se répartir en deux grandes catégories : les positions des pièces et les données d'état annexes.

La recherche et la génération des mouvements s'intéressent essentiellement aux positions des pièces. L'encodage de cette information nécessite donc un soin particulier, et sera abordé par la suite.

Par contre, les données d'état annexes, telles que le joueur possédant le trait ou les droits au roque, n'interviennent que ponctuellement et leur encodage peut être générique sans compromettre les performances.

Une classe abstraite fournit donc une implémentation commune pour les informations suivantes :

  • le joueur possédant le trait,
  • le droit au petit roque des blancs,
  • le droit au petit roque des noirs,
  • le droit au grand roque des blancs,
  • le droit au grand roque des noirs,
  • l'éventuelle case cible d'une prise « en passant »,
  • le nombre de demi-coups joués depuis la dernière prise ou le dernier mouvement de pion,
  • le nombre de coups joués depuis le début de la partie.
Liste de couples pièce / position

Puisque que l'on a besoin de stocker les positions des pièces, pourquoi ne pas le faire directement, sous la forme d'une liste de couples pièce / position ? Cet encodage peut paraître intéressant puisqu'il semble correspondre strictement à la description du besoin.

L'espace consommé par cet encodage irait de n x 320 bits (n x 40 octets) , à raison de 32 pièces avec 4 bits pour le type de pièce (12 possibles) et 6 bits pour la position (64 possibles) à n x 20 bits (n x 3 octets) s'il ne reste que les deux rois. Soit une consommation moyenne relativement économique de n x 170 bits (n x 22 octets).

Mais, l'objectif principal d'un moteur d'échecs est de générer rapidement les listes de mouvements possibles or cet encodage se montre inadapté à une recherche efficace des positions relatives des pièces.

Matrice (tableau à deux dimensions) des cases
  a b c d e f g h  

L'espace de référence consommé par cet encodage serait de n x 256 bits (n x 32 octets), à raison de 4 bits pour le type de l'éventuelle pièce (12+1 possibles) de chacune des 64 cases.

8 (0;7) (1;7) (2;7) (3;7) (4;7) (5;7) (6;7) (7;7) 8
7 (0;6) (1;6) (2;6) (3;6) (4;6) (5;6) (6;6) (7;6) 7
6 (0;5) (1;5) (2;5) (3;5) (4;5) (5;5) (6;5) (7;5) 6
5 (0;4) (1;4) (2;4) (3;4) (4;4) (5;4) (6;4) (7;4) 5
4 (0;3) (1;3) (2;3) (3;3) (4;3) (5;3) (6;3) (7;3) 4
3 (0;2) (1;2) (2;2) (3;2) (4;2) (5;2) (6;2) (7;2) 3
2 (0;1) (1;1) (2;1) (3;1) (4;1) (5;1) (6;1) (7;1) 2
1 (0;0) (1;0) (2;0) (3;0) (4;0) (5;0) (6;0) (7;0) 1
  a b c d e f g h  

Un plateau d'échecs est assez naturellement vu comme une matrice de cases. C'est une approche équivalente au système file/rang adopté par les règles officielles, simple à coder et qui permet de calculer facilement les mouvements des pièces.

Avec cette représentation, les capacités de mouvements des pièces s'expriment avec des vecteurs :

  • (0;1), (0;-1), (1; 0) et (-1;0) pour les tours,
  • (1;1), (1;-1), (-1;-1) et (-1;1) pour les fous,
  • (2;1), (2;-1), (1;-2), (-1;-2), (-2;-1), (-2;1), (-1;2) et (1;2) pour les cavaliers,
  • etc...

Le principal est intérêt de cet encodage est de permettre d'obtenir rapidement une version stable d'un générateur de mouvements, pouvant être utilisé comme référence.

Par contre, cet encodage présente des inconvénients du point de vue des performances :

  • l'accès aux cellules d'une matrice est plus lent que pour un tableau à une dimension,
  • on doit fréquemment vérifier que les coordonnées de travail soient bien dans la matrice, d'où de nombreuses séries de tests du type (x >= 0) et (x <= 7) et (y >= 0) et (y <= 7),
  • la création et la copie d'une matrice, c'est-à-dire un tableau de tableaux, sont plus lentes en Java qu'avec un tableau équivalent à une seule dimension (Cf mesures de performances).
Tableau à une dimension des cases
  a b c d e f g h  

L'espace de référence consommé par cet encodage serait de n x 256 bits (n x 32 octets), à raison de 4 bits pour le type de l'éventuelle pièce (12+1 possibles) de chacune des 64 cases.

8 56 57 58 59 60 61 62 63 8
7 48 49 50 51 52 53 54 55 7
6 40 41 42 43 44 45 46 47 6
5 32 33 34 35 36 37 38 39 5
4 24 25 26 27 28 29 30 31 4
3 16 17 18 19 20 21 22 23 3
2 8 9 10 11 12 13 14 15 2
1 0 1 2 3 4 5 6 7 1
  a b c d e f g h  

Une matrice posant des problèmes de performance, elle peut aisément être remplacer par un tableau équivalent à une seule dimension.

Les coordonnées de la matrice se voient remplacées par des indices dans le tableau, et les vecteurs représentant les capacités de mouvements des pièces deviennent :

  • (8), (-8), (1) et (-1) pour les tours,
  • (9), (-7), (-9) et (7) pour les fous,
  • (10), (-6), (-15), (-17), (-10), (6), (15) et (17) pour les cavaliers,
  • etc...

Si cet encodage permet bien d'éviter la baisse de performance liée à l'utilisation d'une matrice, il ne supprime pas la nécessité des nombreux tests sur les coordonnées de travail. Au contraire, il a même tendance à rendre plus complexe la détection des débuts et fins de lignes du plateau lors des traitements.

Tableau borné à une dimension (« mailbox ») des cases
  a b c d e f g h  

L'espace de référence consommé par cet encodage serait soit de :

  • n x 480 bits (n x 60 octets), à raison de 4 bits pour le type de l'éventuelle pièce (12+1+1 possibles, indicateur de sortie de plateau compris) de chacune des 120 cellules, si la « mailbox » est duppliquée,
  • 1 x 840 bits (105 octets), à raison de 7 bits pour l'indicateur de case correspondante (64 + 1 possibilités, marqueur de sortie de plateau compris) de chacune des 120 cellules d'une « mailbox » commune + n x 256 bits (n x 32 octets de l'encodage à une dimension vue précédemment).
  -1 -1 -1 -1 -1 -1 -1 -1 -1 -1  
110 111 112 113 114 115 116 117 118 119
  -1 -1 -1 -1 -1 -1 -1 -1 -1 -1  
100 101 102 103 104 105 106 107 108 109
8 -1 56 57 58 59 60 61 62 63 -1 8
90 91 92 93 94 95 96 97 98 99
7 -1 48 49 50 51 52 53 54 55 -1 7
80 81 82 83 84 85 86 87 88 89
6 -1 40 41 42 43 44 45 46 47 -1 6
70 71 72 73 74 75 76 77 78 79
5 -1 32 33 34 35 36 37 38 39 -1 5
60 61 62 63 64 65 66 67 68 69
4 -1 24 25 26 27 28 29 30 31 -1 4
50 51 52 53 54 55 56 57 58 59
3 -1 16 17 18 19 20 21 22 23 -1 3
40 41 42 43 44 45 46 47 48 49
2 -1 8 9 10 11 12 13 14 15 -1 2
30 31 32 33 34 35 36 37 38 39
1 -1 0 1 2 3 4 5 6 7 -1 1
20 21 22 23 24 25 26 27 28 29
  -1 -1 -1 -1 -1 -1 -1 -1 -1 -1  
10 11 12 13 14 15 16 17 18 19
  -1 -1 -1 -1 -1 -1 -1 -1 -1 -1  
0 1 2 3 4 5 6 7 8 9
  a b c d e f g h  

La lourdeur de la détection des bords du plateau est un frein pour l'emploi direct d'un tableau à une dimension. Mais il est possible de contourner cette difficulté en bordant la représentation du plateau par un deuxième tableau englobant, souvent appelé « mailbox ».

Le contenu de chaque plateau est alors toujours stocké sous la forme simple, rapide à créer et copier, du tableau à une dimension vue précédemment.

Par contre, tous les mouvements doivent maintenant être calculés par rapport au tableau englobant de référence, dont chaque cellule contient soit l'indice de la cellule correspondante sur le plateau, soit un marqueur « hors plateau ». Les mouvements, par exemple, d'une tour en « h1 », donc dans la cellule n°7 du tableau encodant la disposition des pièces, sont à tester sur le tableau englobant de référence à partir de la cellule n°28.

Les vecteurs exprimant les capacités de mouvements des pièces doivent être adaptés au tableau englobant et deviennent :

  • (10), (-10), (1) et (-1) pour les tours,
  • (11), (-9), (-11) et (9) pour les fous,
  • (12), (-8), (-19), (-21), (-12), (8), (19) et (21) pour les cavaliers,
  • etc...

Le gain sur la détection des bords du plateau, qui se résume maintenant à un test (indiceCible <> 0), absorbe largement les pertes causée par les conversions d'indices entre les deux tableaux.

Cet encodage est globalement deux fois plus performant que la représentation sous forme de matrice, tout en restant simple à implémenter et à tester.

Tableau avec index masqué par x88
  a b c d e f g h
8 x70 x71 x72 x73 x74 x75 x76 x77 x78 x79 x7A x7B x7C x7D x7E x7F
7 x60 x61 x62 x63 x64 x65 x66 x67 x68 x69 x6A x6B x6C x6D x6E x6F
6 x50 x51 x52 x53 x54 x55 x56 x57 x58 x59 x5A x5B x5C x5D x5E x5F
5 x40 x41 x42 x43 x44 x45 x46 x47 x48 x49 x4A x4B x4C x4D x4E x4F
4 x30 x31 x32 x33 x34 x35 x36 x37 x38 x39 x3A x3B x3C x3D x3E x3F
3 x20 x21 x22 x23 x24 x25 x26 x27 x28 x29 x2A x2B x2C x2D x2E x2F
2 x10 x11 x12 x13 x14 x15 x16 x17 x18 x19 x1A x1B x1C x1D x1E x1F
1 x00 x01 x02 x03 x04 x05 x06 x07 x08 x09 x0A x0B x0C x0D x0E x0F
  a b c d e f g h

En construction
En construction...

Cartes binaires des cases
Correspondances entre les bits d'un entier long et les cases de l'échiquier...
63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 ... 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
h8 g8 f8 e8 d8 c8 b8 a8 h7 g7 f7 e7 d7 c7 b7 a7 h6 g6 f6 e6 d6 c6 b6 a6 ... h3 g3 f3 e3 d3 c3 b3 a3 h2 g2 f2 e2 d2 c2 b2 a2 h1 g1 f1 e1 d1 c1 b1 a1
Positions initiales des fous noirs... (= 0x2400000000000000)
0 0 1 0 0 1 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 0 0 0 0 0 0 0 0 0 0
Positions initiales des pions blancs... (= 0x000000000000FF00)
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 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0
... des tours blanches... (= 0x0000000000000081)
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 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1
... du roi noir... (= 0x1000000000000000)
0 0 0 1 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 0 0 0 0 0 0 0 0 0 0 0 0
... et ainsi de suite pour toutes les cartes nécessaires.

L'espace de référence consommé par cet encodage serait de n x 768 bits (n x 96 octets), à raison d'une carte binaire de 64 bits pour chacun des types de pièces (12 possibles).

En construction
En construction...

jChecs ne supporte pas encore cet encodage, mais une version future l'intégrera. C'est traditionnellement le plus efficace en assembleur ou en C, mais les premiers essais d'implémentation laissent planer des doutes sur sa réelle efficacité en Java...

Page précédente Notations standards Intelligence artificielle Page suivante