Discussion :

[oliverell62]

J'ai pas de lien, non.

Il s'agissait d'échecs orthodoxes. J'aimerais bien en refaire un qui permette d'utiliser des jeux de règles différents, pour gérer les échecs féériques.

oki, tant pis, rien a voir avec ca alors ?

http://cheesechess.free.fr/

je pensais avoir trouver ...

Suite plus tard.

prends le temps qu'il faudra, je suis abonné :p
je vais surement commencer quelques trucs les tout prochains jours, j'ai deja la base ( j'utiliserai en dernier recours un generateur de coup autre que les bitboards en attendant tes lumieres )


ps : j ai beaucoup reflechis au bitboard, il ne me semble pas irrealiste de pouvoir en parti les utiliser pour evaluer une position ( position des pieces / structure de pions / colonne ouvertes .... )

[davcha]

Euh, rien à voir si ce n'est le nom lol...

Pour les bitboard, tu peux effectivement t'en servir pour la fonction d'évaluation.
Les bitboards te permettent de réaliser des opérations ensemblistes sur l'échiquier avec très peu de calcul.

[oliverell62]

en cherchant des infos sur le protocole uci et winboard je suis tombé dessus :

http://chengine.codeplex.com/SourceC.../57274#1490077

[oliverell62]

je suis désolé pour le double post ...

mais un petit détail me tracasse ...

on a 12 bitboard
=> pions
=> tours
=> cavalier
=> fou
=> roi
=> reine
=======> le tout fois 2( blanc et noir )

2 bitboard pour la vue d ensemble :
ensemble de pieces noires et blanches


comment utiliser efficacement le resultat des operations effectues sur le bitaboard ..
je m explique
=> on cherche les coups d un fou en a1
on obtient donc un bitboard avec des 1 sur la diag ( les 0 ailleurs ( en considerant qu il n y a pas de piece sur la trajectoire ))

comment exploité !!!!

a part ressortir la chaine binaire en string
et parcourir chaque caractère pour récupérer les "1" et les index correspondant ( pour connaitre les deplacements possible ... )

je vois rien d autre

ce qui me pose un petit pb c qu a la base la notion de bitboard a ete introduit pour diminuer les calculs ...
donc faire une boucle sur un string de 64 items ca me pose pb ( meme si ca marche ... )

quelque chose m a peut être échapper ???
y a t il moyen d eviter cette boucle en utilisant les bitboard ...?

[davcha]

C'est pas la même philosophie qu'avec une méthode plus classique utilisant des tableaux bidimentionnels.

Avec la méthode classique, tu vas calculer une liste de coups disponibles, puis les appliquer un à un, faire un parcours en profondeur, évaluer, remonter les résultats... Bref, ton min-max (ou n'importe quelle optimisation de cet algo).

Avec les bitboards, tu ne calcules pas de liste de coups, tu appliques directement les coups, jusqu'à ce qu'il n'y ait plus de coups à évaluer.

Autrement dit, pour ton fou, au lieu de calculer qu'en A1, il peut se déplacer en B2, C3, D4, etc... Puis faire ton minmax à partir de la liste.
Tu vas appliquer à partir de A1, une règle qui va décaler les bits de 9 bits (direction nord-est), et faire ton minmax au fur et à mesure.

[oliverell62]

bon ben je crois que j etais quelque peu hors sujet,

je voyais cela comme l application de "masque" donnant instantanément les case "joueable/utilisable" a exploiter ...

c'est plus un glissement de bit( ou piece) permettant l évaluation dynamique et en temps reel des forces en présences


petit edit :
a priori pas mal de méthode différente utilisant les bitboard,
=> ta methode avec le glissé
mais également
=> celle exposé au dessus avec la récupération des cases possible via la valeur binaires de l application des masques

en rapport certainement avec l expertise/test des différents développeurs

[davcha]

L'idée des bitboards, c'est avant tout de gérer en une seule fois les opérations ensemblistes faites sur l'échiquier.

Quand tu souhaites accéder individuellement aux cases, à leurs propriétés, là évidemment, tu perds un peu l'intérêt de ces bitboards.

[MattChess]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

[DonQuiche]

Bonjour, je me permets d'ajouter mon petit grain de sel.

Concernant le coup du tableau à une dimension ou deux dimensions, ça devrait être un détail d'implémentation. En effet, si on utilise C#, c'est pour faire de l'objet, sinon autant utiliser du C. La bonne question à se poser est donc : à quoi est-ce que je veux que ma classe "échiquier" ressemble ? Et là...
* Il faut des accesseurs bi-dimensionnels (x, y)
* Il faut des accesseurs uni-dimensionnels (i)
* Il faut peut-être un énumérateur des pièces actuellement présentes avec leurs positions (pièce, indice)

Après, "chess" elle-même peut reposer en interne sur un tableau unidimensionnel ou bidimensionnel, ce n'est qu'un détail sans grandes conséquences. L'unidimensionnel me semble meilleur (plus simple et plus rapide à manipuler).

Enfin, concernant la question du bitboard... Stop ! C'est de l'optimisation prématurée et pas forcément judicieuse (*) qui va alourdir et obscurcir le code. Mieux vaut faire les choses dans le bon sens : d'abord on écrit rapidement un noyau qui fonctionne et réussit les tests, en utilisant assez d'abstractions pour garder une souplesse en cas de problèmes. Puis on fait un bilan des performances en relevant les éventuels bottlenecks et on optimise alors ceux-ci et rien que ceux-ci. Et on reprend le développement du programme en ajoutant de nouvelles fonctionnalités.

(*) : l'échiquier prend une place ridicule (64-512 octets sans bitboard) et tient à l'aise dans le cache L1, les combinaisons logiques d'échiquiers ne sont pas nécessaires, etc... Je cherche désespérément le moindre avantage. En revanche chaque opération est ralentie et la taille du code est augmentée. Enfin, pour une vraie conception objet on pourrait préférer avoir un tableau de références vers des objets "pawn", "king", etc, plutôt qu'un tableau de bits.

[MattChess]

L'unidimensionnel me semble meilleur (plus simple et plus rapide à manipuler).

Tout à fait d'accord

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.

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.

[DonQuiche]

Bonjour à toi.

Bon, il semblait que j'étais à côté de la plaque après avoir lu tes explications et fouiné un peu. Cela dit, je reste assez craintif sur le fait de calquer ainsi les mécaniques développées pour du C/asm en C#. Les bitboards ont l'air de pouvoir être efficaces en C# mais...

EDIT : Ce que j'avais écrit ici était faux. Bien que la remarque de fond sur mes expériences douloureuses d'algos et structures de données performants en C mais médiocres en C# reste vraie, ça ne semble pas le être cas ici à première vue.

Au-delà de ça, je m'interroge sur la pertinence de faire ce genre de programmation en C#. Je suis un grand défenseur de C# et de la plateforme dotnet mais je sais aussi que, dans quelques cas, ce n'est pas le bon outil. Et utiliser C# si on ne compte pas faire d'objet et que l'on veut des performances aussi hautes que possible, ça ne me semble pas pertinent. Si on utilise C#, ça doit être pour en tirer partie, d'une façon ou d'une autre.

PS : Merci à toi pour ta patience et tes explications claires.