A propos de jChecs
Conception
Divers |
Conception
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 :
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
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 :
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 :
Tableau à une dimension des cases
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 :
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
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 :
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
Cartes binaires des cases
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).
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...
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
English homepage | Dernière mise à jour le 24/10/2007 |