Discussion :

[Roland Chastain]

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 :

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
{$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

[Roland Chastain]

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 :

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

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 ?

[Jipété]

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)

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.



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

[DomDA91]

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 :

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

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');

[Jipété]

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 ?

[Roland Chastain]

@DomDA91

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

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.

[DomDA91]

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

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

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

Code :

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

// 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é.

[Roland Chastain]

@DomDA91

Merci pour les explications supplémentaires.

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

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
{ 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 X :

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

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).

[Roland Chastain]

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 :

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

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

[Roland Chastain]

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 :

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
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 :

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
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 :

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
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à.

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.

[Roland Chastain]

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 :

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
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 :

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

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 :

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
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.

[Roland Chastain]

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.

[Jipété]

Bonjour,

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.

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...

[Roland Chastain]

Merci pour le lien Jipété.