Bitboard
Cet article ne cite pas suffisamment ses sources ().
Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section « Notes et références ».
En pratique : Quelles sources sont attendues ? Comment ajouter mes sources ?Un bitboard est une structure de données spécialisée sous la forme d’un tableau de bits, utilisée dans les systèmes informatiques de jeux de plateau. Chaque bit d’un bitboard correspond à une case ou à une pièce du plateau, ce qui permet d’effectuer en parallèle des opérations bit-à-bit (AND, OR, XOR, etc.) pour mettre à jour ou interroger l’état du jeu, calculer des déplacements ou tester des positions.
Les bits d’un même bitboard sont liés entre eux par les règles du jeu : pris isolément ils indiquent une propriété locale (présence d’une pièce, case menacée, etc.), et pris dans leur ensemble ils forment une représentation compacte d’une position. D’autres bitboards — souvent utilisés comme masques — servent à transformer ou à interroger des positions de manière « vectorisée ». La technique s’applique à tout jeu dont l’état se résume à la présence ou à l’absence de pièces sur un ensemble fini de cases, et constitue une alternative très efficace à la représentation « mailbox » (tableau d’objets) traditionnelle, où chaque case ou pièce est stockée séparément.
Les bitboards sont performants lorsque le nombre de bits utilisés correspond à la taille d’un mot machine ou d’un double-mot (par exemple 64 bits sur processeurs modernes), car une seule instruction peut traiter simultanément l’ensemble des bits.
Parmi les jeux utilisant des bitboards, on peut citer les échecs, les dames, l’othello (reversi) ou certains jeux de lettres. La méthode a été employée dès les années 1950 dans des programmes de dames, et, depuis le milieu des années 1970, est devenue une référence pour la représentation de plateaux en intelligence artificielle ludique.
Description générale
Un bitboard est en fait un champ de bits (bit field) qui regroupe plusieurs variables booléennes connexes dans un seul mot machine. Chaque bit représente une case : si le bit vaut 1, la propriété associée à cette case est vraie (présence d’une pièce, case centrale, case attaquée, etc.).
Grâce aux opérations logiques sur mots entiers, on peut répondre à certaines questions en une seule instruction. Par exemple, pour savoir si un joueur d’échecs possède un pion dans les quatre cases centrales, on effectue un AND entre le bitboard des pions et celui des cases centrales ; si le résultat est nul, aucun pion n’occupe cette zone.
On peut multiplier les bitboards pour représenter différentes catégories de pièces, différents joueurs, ou encore des propriétés statiques (cases de coin, rangée initiale, etc.). Des bitboards temporaires servent parfois à stocker des résultats intermédiaires ou des masques locaux.
Problèmes d’implémentation
La mise en œuvre des bitboards exige généralement :
- de générer et stocker de vastes tables de masques et d’attaques précalculées (pour chaque case, chaque type de pièce, etc.) ;
- d’écrire du code « bit-twiddling » complexe pour mettre à jour incrémentalement ces tables lors d’un déplacement ;
- de veiller aux contraintes de taille et de performance du cache.
Utilisation du processeur
Avantages
- Les opérations logiques bit à bit (AND, OR, XOR, NOT) s’exécutent en un cycle sur la largeur native du processeur (32 ou 64 bits), pleinement pipelinées et souvent exécutées en parallèle sur plusieurs unités.
- Les séquences de code font moins appel aux branchements conditionnels, ce qui réduit les « flush » de pipeline en cas de prédiction erronée.
Inconvénients
- Le code source et binaire est plus volumineux, difficile à écrire et à déboguer.
- L’absence d’instructions matérielles pour compter le premier bit à 1 (« find-first-one ») ou le nombre de bits à 1 (« popcount ») sur certaines architectures anciennes ralentit fortement les implémentations logicielles.
Cache et mémoire
Avantages
- Bien que les tables précalculées occupent plus de mémoire que la simple liste de pièces, les nombreuses boucles et comparaisons sont remplacées par quelques opérations logiques, améliorant généralement la performance globale.
Inconvénients
- Sur appareils à cache limité (mobiles, systèmes embarqués, etc.), la taille importante du code et des tables peut provoquer des défauts de cache (cache-miss, thrashing), dégradant les performances.
Mise à jour incrémentale
Pour éviter de régénérer intégralement tous les bitboards dérivés (attaques, cases vulnérables, etc.) à chaque coup, on met à jour uniquement les masques affectés par le déplacement (source et destination). Cette approche requiert un code précis et finement optimisé, mais se révèle beaucoup plus rapide que la reconstruction complète.
Bitboards précalculés et tables de consultation
Certaines informations indépendantes de la configuration courante (par exemple la carte d’attaques d’un cavalier ou d’un roi depuis chaque case) sont calculées une fois pour toutes et stockées en table. On y accède ensuite par une simple lecture mémoire, ce qui rend quasi-instantanées des opérations qui, autrement, impliqueraient une énumération de mouvements légaux.
Bitboards aux échecs
Le plateau d’échecs, aux 64 cases, se prête naturellement à une représentation par un mot de 64 bits. La convention la plus répandue associe le bit 0 à la case a1, le bit 7 à h1, le bit 56 à a8 et le bit 63 à h8.
On maintient généralement plusieurs bitboards :
- un pour chaque type de pièce et chaque camp (pions blancs, tours noires, etc.) ;
- un pour tous les coups possibles d’un cavalier, d’un fou, d’une tour, etc., depuis chaque case ;
- des constantes (première rangée, diagonales, etc.).
Les attaques des pièces non glissantes (cavalier, roi) sont directement issues des tables pré-calculées. En revanche, les pièces glissantes (fou, tour, dame) nécessitent un calcul dynamique complexe, car leur portée dépend de l’occupation intermédiaire du plateau.
Représentation standard
Chaque bitboard correspond à une configuration précise (positions des pions blancs, cases des pièces noires, etc.). Par exemple, pour déterminer si une pièce est « en prise », on croise le bitboard des cases défendues avec celui des cases attaquées.
Représentations auxiliaires
Pour accélérer le calcul des attaques des pièces glissantes, plusieurs techniques « avancées » sont disponibles :
Bitboards tournés (rotated bitboards)
On fait pivoter la représentation d’occupation du plateau de 90 °, 45 ° ou –45 ° pour transformer les attaques sur colonnes/diagonales en attaques sur rangées, indexables par table. Chaque rotation implique un traitement en dizaines d’instructions, mais remplace de longues séquences de masques et décalages.
Hachage direct
On masque séparément la rangée, la colonne et les deux diagonales pour extraire 8 bits d’occupation, qui servent d’index dans des tables de hachage de taille modérée (quelques kilo-octets). On combine ensuite les résultats pour obtenir l’ensemble des cases attaquées.
Bitboards « magiques » (magic bitboards)
S’appuyant sur le principe du hachage parfait, on construit des « magics » (constantes multiplicatives et décalages) qui, appliqués à l’occupation masquée, donnent directement l’index de la table des attaques. Les tables peuvent rester volumineuses (plusieurs centaines de milliers d’entrées), avec un risque de surcharger le cache L1/L2, si bien que ce schéma n’est pas toujours plus rapide que les rotations ou le hachage direct.
Histoire
La méthode du bitboard est apparue dès le milieu des années 1950 dans le programme de dames d’Arthur Samuel. Pour les échecs, elle a été redécouverte à la fin des années 1960 par l’équipe Kaissa en URSS, puis au début des années 1970 par le programme Northwestern University Chess. L’essor des architectures 64 bits a accéléré son adoption.
Les bitboards tournés ont été imaginés dans les années 1990 par Robert Hyatt (Cray Blitz, Crafty). Les techniques de hachage et les bitboards magiques sont quant à elles apparues dans les années 2000, avec des gains variables selon les plates-formes et la taille du cache.
Autres jeux
- Connect Four : deux décalages et un AND par direction suffisent à tester l’alignement de quatre pions.
- Jeu de la vie de Conway : alternative possible aux tableaux classiques.
- Othello/Reversi : masques pour les lignes à renverser et décalages rapides.
Voir aussi
Bibliographie
- Atkin L. R. & Slate D. J., « Chess 4.5: the Northwestern University Chess Program », in P. W. Frey (éd.), *Chess Skill in Man and Machine*, Springer (1977).
- Heinz E. A., « How Dark Thought Plays Chess », *ICCA Journal* 20(3), 1997.
- Hyatt R., Rotated Bitboards: New Twist on an Old Idea, 1999.
- Tannous S., « Avoiding Rotated Bitboards with Direct Lookup », *ICGA Journal* 30(2), 2007.
- Sherwin M., Isenberg G., « Magic Bitboards Explained! », Winboard Forum, 2006.
Notes et références
- (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Bitboard » (voir la liste des auteurs).
- ↑ « Bitboards - Creating the Rustic chess engine », sur rustic-chess.org (consulté le )
