Opération binaire sur une variable de type QWord

Bonjour !

Je voudrais apprendre la technique des damiers binaires (c'est comme ça que je traduirais bitboard).

Pour commencer j'ai voulu écrire un petit programme mettant en œuvre l'exemple présenté sur cette page.

Ça commence mal. Dès le début j'obtiens un résultat inattendu. :)

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

{$mode objfpc}   var damier: qword; i: integer;   begin damier := %0000000000000000000000000000000000000000000000001111111111111111;     for i := 0 to 63 do if (damier and (1 shl i)) > 0 then Write('1') else Write('0'); end.   // 1111111111111111000000000000000011111111111111110000000000000000

---

Qu'est-ce qui ne va pas dans mon code ? Pourquoi la chaîne affichée ne correspond-elle pas aux chiffres binaires de la valeur en question ?

D'autres liens intéressants pour la suite de la discussion :
https://www.chessprogramming.org/Bitboards
http://pages.cs.wisc.edu/~psilord/bl...ges/index.html

Dans un programme existant j'ai trouvé cette solution qui donne bien le résultat attendu, mais je me demande toujours pourquoi "ma" solution ne fonctionne pas.

Code:

---

1 2 3 4 5 6 7 8

for i := 0 to 63 do begin if damier and 1 > 0 then Write('1') else Write('0'); damier := damier shr 1; end;

---

Au fait, vous paraît-il plus judicieux d'utiliser un QWord ou un Int64 ? Ou est-ce que ça ne change rien ?

Salut salut,

juste sur ça, un petit cadeau (moi aussi j'en avais marre de chercher dans l'aide alors un jour j'ai pris le taureau par les cornes et hop !, copie d'écran de l'aide)

Citation:

---

Envoyé par Roland Chastain

Au fait, vous paraît-il plus judicieux d'utiliser un QWord ou un Int64 ? Ou est-ce que ça ne change rien ?

---

Ça doit surement changer quelque chose quand le bit tout à gauche est à 1 ou pas.

Pièce jointe 454906

Allez, que j'ai du graphisme qui m'attend, :mouarf:

Bonjour,

C'est la constante 1 qui joue des tours. Elle est integer par défaut donc 1 shl i renvoi un résultat 32 bits signé, ce résultat étant étendu ensuite à 64 bits par adjonction de 32 bits forts pour faire le AND.

Ceci fonctionne comme attendu :

Code:

---

1 2 3 4 5

for i := 0 to 63 do if (damier and (qword(1) shl i)) > 0 then Write('1') else Write('0');

---

Citation:

---

Envoyé par DomDA91

C'est la constante 1 qui joue des tours. Elle est integer par défaut

---

Oh lala, ça ne s'invente pas, des trucs pareils !

Bien joué -- comment tu sais ça, toi ? À force d'avoir pris des gamelles et des râteaux ? :mouarf:

@DomDA91

Oui, cela résout en effet le problème. Comme Jipété, je me suis demandé où vous étiez allé chercher cette solution. :ave:

Je laisse la discussion ouverte, car j'ai l'intention de continuer à creuser le sujet et j'aurai probablement encore besoin d'aide.

@Jipété

Merci pour ton soutien. ;)

Citation:

---

Envoyé par Jipété

Bien joué -- comment tu sais ça, toi ? À force d'avoir pris des gamelles et des râteaux ?

---

Citation:

---

Envoyé par Roland Chastain

Oui, cela résout en effet le problème. Comme Jipété, je me suis demandé où vous étiez allé chercher cette solution. :ave:

---

Non rien de miraculeux ! C'est le résultat

Code:

---

// 111111111111111100000000000000001111111111111111000000000000000

---

qui m'a interpellé. La répétition du même pattern au 32ème bit m'a fait penser à une particularité d'implémentation des instructions "machine" de décalage des processeurs Intel :

Lorsque le nombre de décalages est supérieur à la taille de la donnée (du registre), par exemple 64 décalages sur un registre 32 bits on pense logiquement que le résultat va donner une valeur tout à 0 et qu'il y aura seulement une perte de performance car à partir de 32ème décalage le registre est déjà tout à 0 et le restera jusqu'au 64ème décalage.

Les instructions de décalage des processeurs Intel de la série 8086 ne suivent pas cette logique. Elles optimisent le décalage en ignorant les bits forts excédentaires du nombre de décalage. Par exemple pour un registre 32 bits elles n'utilisent que les 5 bits faibles (6 si 64 bits). Il s'ensuit que si on programme par exemple un décalage de 40 bits sur un registre 32 bits il n'y aura en fait que 8 décalages effectifs (40 MOD 32).

Dans l'exemple du problème exposé dans cette discussion, la boucle 'For' effectue 64 itérations avec une valeur de nombre de décalages croissant de 0 à 63. Tout se passe bien de 0 à 31 mais à partir de 32, le processeur lui, s'il opère en 32 bits, recommence à 0 décalage ce qui donne le résultat constaté.

@DomDA91

Merci pour les explications supplémentaires.

Un petit pas en avant : une procédure qui affiche le damier.

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

{ http://www.fzibi.com/cchess/bitboards.htm }   {$mode objfpc}   procedure Affiche(const damier: QWord); var x, y: integer; begin WriteLn('+ abcdefgh +'#13#10);   for y := 7 downto 0 do begin Write(Succ(y), ' '); for x := 0 to 7 do if (damier and (qword(1) shl (8 * y + x))) > 0 then Write('1') else Write('0'); WriteLn(' ', Succ(y)); end;   WriteLn(#13#10'+ abcdefgh +'); end;   const PIECES_BLANCHES = %0000000000000000000000000000000000000000000000001111111111111111; CAVALIERS = %0100001000000000000000000000000000000000000000000000000001000010;   begin Affiche(PIECES_BLANCHES and CAVALIERS); end.

---

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12

+ abcdefgh + 8 00000000 8 7 00000000 7 6 00000000 6 5 00000000 5 4 00000000 4 3 00000000 3 2 00000000 2 1 01000010 1 + abcdefgh +

---

Une autre page intéressante, où l'on voit les différentes façons de construire le damier. Au cas où cela vous intéresse, je mets en pièce jointe l'application en question (le lien sur la page ne fonctionne plus).

Je crois que je vais opter finalement pour le type Int64, parce qu'avec le code suivant, je suis obligé de transtyper certaines constantes ; autrement j'ai une erreur de compilation :

Code:

---

1 2 3

const AA: array[0..63] of QWord = ( QWord(%1000000010000000100000001000000010000000100000001000000001111111),

---

Suite de mes investigations. Comment écrire un générateur de coups sur ce principe ?

Pour une certaine position de la tour par exemple, on peut, toujours avec 64 chiffres binaires, représenter les destinations possibles.

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

procedure TableMouvementTour(const a, b: integer); var x, y: integer; begin WriteLn('tour ', Chr(a + Ord('a')), Chr(b + Ord('1'))); for y := 7 downto 0 do begin for x := 0 to 7 do Write(Ord(((x <> a) or (y <> b)) and ((x = a) or (y = b)))); WriteLn; end; end;   begin TableMouvementTour(1, 1); end.   {   tour b2   01000000   01000000   01000000   01000000   01000000   01000000   10111111   01000000 }

---

Maintenant, je génère 64 tables (pour 64 positions de départ), et au lieu de les afficher en échiquier dans la console je les enregistre comme constantes dans un fichier.

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

procedure TableMouvementTour(const a, b: integer); var x, y: integer; begin Write('%'); for y := 7 downto 0 do for x := 0 to 7 do Write(Ord(((x <> a) or (y <> b)) and ((x = a) or (y = b)))); WriteLn(','); end;   var x, y: integer;   begin for y := 0 to 7 do for x := 0 to 7 do TableMouvementTour(x, y); end.

---

En incluant ce fichier dans un programme (après avoir enlevé la virgule en trop) je dispose de tous les mouvements de la tour pour les 64 cases de départ.

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

const MOUVEMENTS_TOUR: array[0..63] of Int64 = ({$I tour.inc});   procedure Affiche(const damier: Int64); var x, y: integer; begin WriteLn('+ abcdefgh +'#13#10);   for y := 7 downto 0 do begin Write(Succ(y), ' '); for x := 0 to 7 do Write(Ord((damier and (int64(1) shl (8 * y + x))) <> 0)); WriteLn(' ', Succ(y)); end;   WriteLn(#13#10'+ abcdefgh +'); end;   const A2 = 8;   begin Affiche( MOUVEMENTS_TOUR[A2] ); end.   {   + abcdefgh +     8 00000001 8   7 00000001 7   6 00000001 6   5 00000001 5   4 00000001 4   3 00000001 3   2 11111110 2   1 00000001 1     + abcdefgh + }

---

Et comme vous le voyez je me suis trompé quelque part mais l'idée est là. :ptdr:

Bref, c'est un peu casse-tête mais on entrevoit les possibilités redoutables du truc une fois au point. :)

Après j'avoue que je ne vois pas encore bien comment je vais gérer les obstructions par exemple. Si vous avez des idées je suis preneur.

J'ai résolu l'erreur précédente, et j'ai trouvé un moyen de vérifier si le chemin d'une case à l'autre est libre. C'est une table de 64 x 64 damiers binaires, qui contient pour chaque mouvement les cases à survoler.

Par exemple les cases à survoler pour aller de A1 en H8 :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

uses DamierBinaire, Tables;   begin Affiche(CChemin[A1, H8]); end.   {   + abcdefgh +     8 00000000 8   7 00000010 7   6 00000100 6   5 00001000 5   4 00010000 4   3 00100000 3   2 01000000 2   1 00000000 1     + abcdefgh + }

---

J'ai aussi fait une fonction qui permet d'initialiser une position (essentiellement un enregistrement de plusieurs damiers binaires) à partir d'une chaîne EPD.

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13

type TPosition = record PiecesBlanches, PiecesNoires, Pions, Tours, Cavaliers, Fous, Dames, Rois: TDamierBinaire; Trait: boolean; Roque, EnPassant: string; end;

---

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

uses DamierBinaire, Echecs;   {$assertions on}   const CChainePosition = 'rnbqkbnr/pppppppp/8/8/4P3/8/PPPP1PPP/RNBQKBNR b KQkq e3'; { Position après e2e4, au format EPD. }   var p: TPosition;   begin p := EncodePosition(CChainePosition); Affiche(p.PiecesBlanches and p.Pions); Assert(DecodePosition(p) = CChainePosition); end.   {   + abcdefgh +     8 00000000 8   7 00000000 7   6 00000000 6   5 00000000 5   4 00001000 4   3 00000000 3   2 11110111 2   1 00000000 1     + abcdefgh + }

---

Là il faut que je fasse une pause mais c'est vraiment à regret. :)

Je marque la discussion comme résolue.

Finalement mon damier binaire est devenu un moteur d'échecs UCI. Pour le moment, il joue le premier coup légal qu'il trouve. Avant d'aller plus loin je voudrais être satisfait du programme actuel et être sûr qu'il ne contienne pas d'erreur. Les commentaires sont bienvenus, notamment sur l'unité Damier (pour rester dans le sujet de la discussion).

Le roque est un vrai casse-tête quand on doit jongler entre la variante traditionnelle et les échecs 960, sans parler des différences de protocole d'une interface graphique à l'autre. Car Alouette joue aux échecs 960. 8-)

Bonjour,

Citation:

---

Envoyé par Roland Chastain

Le roque est un vrai casse-tête quand on doit jongler entre la variante traditionnelle et les échecs 960, sans parler des différences de protocole d'une interface graphique à l'autre. Car Alouette joue aux échecs 960. 8-)

---

Chose que je découvre ce jour.

As-tu lu ça ?

Je ne dirai rien de plus, je n'ai vraiment plus le temps de jouer...

Merci pour le lien Jipété. ;)