Efficacité des bitboards ?
Quel est le résultat d'expérience avec l'approche orientée pièce dite des bitboards ?
Le générateur de coups est-il significativement plus rapide qu'avec une approche orientée case telle que l'échiquier 0x88 ?
Avec le .NET Framework, le goulot d'étranglement est peut-être dans l'extraction du bit de poids faible LSB d'un bitboard 64-bit.
Voici PosLsb64(UInt64 bb) une version C# .NET adaptée de Crafty.
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
| static byte[] arrPosBit16 = new byte[65536];
static byte PosLsb64(UInt64 bb)
{
int iPosBit, indTab;
if (bb < 0x100000000)
{
if ((indTab = (ushort) bb) != 0) // Cast to ushort (16-bit) means AND with 0xFFFF
iPosBit = 0; // Keep indTab
else
indTab = (ushort) (bb >> (iPosBit = 16));
}
else
{
if (((indTab = (ushort) (bb >> 32))) != 0)
iPosBit = 32; // Keep indTab
else
indTab = (ushort) (bb >> (iPosBit = 48));
}
iPosBit += arrPosBit16[indTab];
return (byte) iPosBit;
} // end PosLsb64
static public void InitMaskArray()
{
int i, iMaskr;
arrPosBit16[0] = 64; // All bits in the bitboard are 0
for (i = 1; i < arrPosBit16.Length; i++)
{
iMaskr = 1;
for (byte j = 0; j < 16; j++)
{
if ((iMaskr & i) != 0)
{
arrPosBit16[i] = j;
break;
}
iMaskr = iMaskr << 1;
}
}
} // end InitMaskArray |
Contrairement à la version C de LastOne(bitboard bb) de Crafty, il est "difficile" d'insérer de l'assembleur x86 dans du code managé C# ou VB.NET afin d'optimiser l'extraction du LSB. S'il y a des pistes pour améliorer PosLsb64() dans un contexte .NET Framework, on aimerait bien savoir comment.
Il faut écarter également la solution d'une DLL C++ non managée pour extraire le LSB à cause du coût de conversion avec le monde managé du .NET Framework.
Avantages et inconvénients des bitboards
Citation:
Envoyé par
DonQuiche
L'unidimensionnel me semble meilleur (plus simple et plus rapide à manipuler).
Tout à fait d'accord :ccool:
Avec les bitboards, on ne cherche pas à optimiser la place mémoire bien au contraire. Car il faut plusieurs bitboards par type de pièces, par couleur, et d'énormes tables précalculées pour accélérer le traitement sans compter une liste impressionnante de constantes hexadécimales.
Si on fait tout cela, c'est que l'on espère un gain sur la vitesse du générateur de coups.
Citation:
Envoyé par
DonQuiche
les combinaisons logiques d'échiquiers ne sont pas nécessaires, etc... Je cherche désespérément le moindre avantage.
Les avantages des bitboards
Les bitboards sont compacts et encore plus efficace sur un ordinateur 64-bit où les registres du CPU ont exactement la taille d'un bitboard.
Ils permettent un traitement "en parallèle" en étant capable de gérer simultanément par exemple tous les pions. Ils sont performants si on arrive selon le langage et l'environnement de programmation à optimiser l'extraction du LSB que l'on remet à zéro pour rechercher le suivant.
Contrairement à l'approche orientée case, avec les bitboards il n'y a pas besoin de test aux limites de l'échiquier pour savoir si un index de n° de case sort de l'échiquier car on combine les bitboards non pas au niveau de la case mais au niveau de l'échiquier complet comportant un sous-ensemble donné de pièces au pluriel.
Les bitboards sont remarquables pour appréhender simultanément des surfaces, zones ou territoires sur l'échiquier c-a-d un ensemble de cases pas forcément restreint à une géométrie linéaire telle que la rangée, la colonne ou la diagonale plus ou moins obstruée par des pièces amies ou adverses.
Avec une vision orientée case 2D ou 1D, on est obligé de tester individuellement toute une série de cases dans une itération ou une expression logique conséquente. Les bitboards ont donc un avantage indéniable en matière de reconnaissance de forme c-a-d de positions typiques du jeu d'Echecs telle que le Fou en Fianchetto avec ses trois pions formant un triangle caractéristique.
Les inconvénients des bitboards
Les bitboards demandent une phase d'initialisation des tables plus ou moins précalculées. Mais ce n'est à faire qu'une fois.
Avec la capacité de représentation du bit réduite à sa plus simple expression 1 ou 0, il faut multiplier les bitboards. Cela veut dire maintenir la cohérence de tous ces bitboards quand une pièce bouge. Car cette même pièce est représentée dans différents bitboards.
Les bitboards eux-mêmes ne sont pas gourmands en mémoire mais les tables précalculées utilisées pour l'optimisation de la vitesse d'exécution par exemple de l'extraction du LSB peuvent demander beaucoup plus de mémoire qu'un échiquier 2D ou 0x88.
Les bitboards sont très difficiles à déboguer car très proche d'un niveau langage machine à l'opposé d'une approche orientée objet. Cela signifie que les opérations logiques (And, Or, Xor, Not, complément à deux, complément à 1, rotation, décalage à gauche, à droite) sur les bitboards peuvent apparaître complètement éloignées de la réalité physique du mouvement d'une pièce sur un échiquier tel que le parcours d'un Fou glissant sur une grande diagonale.
Si les opérations logiques entre bitboards sont extrêmement rapides, l'extraction de l'information des bitboards est de nature itérative donc coûteuse.
Conclusion
Tout n'est pas blanc ou noir comme sur un échiquier qu'il soit représenté par des cases acceptant des pièces ou par des pièces sur des cases. Il y a des avantages et des inconvénients dans chaque représentation de l'échiquier.
Le seul juge impartial en la matière c'est le nombre de position analysée par seconde et le ELO du moteur d'Echecs sauf considérations pédagogiques sur la maintenance et l'évolution du logiciel d'Echecs.
On peut très bien imaginer de mixer les approches c-a-d avoir un échiquier 0x88 selon une vision orientée case et des bitboards spécialisés pour les pions car ils sont nombreux au début de la partie d'Echecs.
