Worldlex Wiki Les plateaux de jeu à bits s'appliquent à tout jeu de plateau dont l'état est représenté par la présence de pièces sur des cases discrètes, comme les échecs , les dames , Othello et les jeux de mots . Ce système a été utilisé pour la première fois dans les programmes de dames dans les années 1950 et, depuis le milieu des années 1970, il est devenu la norme de facto pour la représentation des plateaux de jeu dans les automates informatiques.
Les bitboards sont une représentation de plateau plus compacte que la représentation traditionnelle par boîtes aux lettres , où chaque pièce ou espace sur le plateau est un élément de tableau.
Les tableaux de bits sont souvent plus efficaces en termes de temps d'exécution . Lorsque les bits associés aux états liés sur le tableau de bits tiennent dans un seul mot ou un double mot de l'architecture du processeur, des opérateurs binaires simples comme ET et OU peuvent être utilisés pour manipuler le tableau. Ces opérations binaires parallèles sont beaucoup plus rapides pour définir et interroger les états du jeu, ainsi que pour déterminer les coups et les actions, que des opérations itératives sur un tableau de représentation par boîte aux lettres.
Les moteurs d'échecs modernes utilisent principalement des tableaux de bits magiques, qui emploient un hachage parfait pour faire correspondre le masque d'occupation d'une pièce directement à un tableau précalculé de modèles d'attaque en une seule opération de recherche.
booléennes dans un même mot machine. Chaque bit représente une case ; lorsqu’il est positif, une propriété de cette case est vraie.Les tableaux de bits permettent à l'ordinateur de répondre à des questions sur l'état du jeu en utilisant très peu d'opérations bit à bit. Par exemple, si un programme d'échecs veut savoir si le joueur blanc a des pions au centre de l'échiquier (les quatre cases centrales), il lui suffit de comparer le tableau de bits des pions du joueur avec celui du centre de l'échiquier à l'aide d'un ET binaire. S'il n'y a pas de pions au centre, le résultat sera composé uniquement de bits à zéro. Plusieurs tableaux de bits peuvent représenter différentes propriétés des cases de l'échiquier, et des tableaux de bits spéciaux ou temporaires (comme des variables temporaires) peuvent représenter des propriétés locales ou contenir des résultats intermédiaires.
L'efficacité des matrices de bits est renforcée par deux autres propriétés de leur implémentation. Premièrement, les matrices de bits sont rapides à mettre à jour de manière incrémentale ; par exemple, en inversant les bits des positions source et destination d'une matrice de bits pour la position d'une pièce lorsqu'elle est déplacée. Deuxièmement, les bitmaps représentant des propriétés statiques, comme toutes les cases attaquées par chaque type de pièce pour chaque position sur un échiquier, peuvent être pré-assemblées et stockées dans une table. Cela permet de répondre à une question comme « Quels sont les coups légaux d'un cavalier sur la case e4 ? » en une seule lecture de la mémoire.
Les implémentations de cartes à bits tirent parti des opérations logiques bit à bit (32 ou 64 bits) disponibles sur les architectures de processeurs modernes, telles que ET, OU, NON, etc., pour optimiser la rapidité des opérations. Leur efficacité peut toutefois être moindre sur les architectures de mini-ordinateurs et de microprocesseurs 8 et 16 bits plus anciennes.
Mise en œuvre
Étant donné que la mise en œuvre des bitboards nécessite une compression et un encodage corrects de tables massives et d'états de jeu complexes, les programmes de bitboard peuvent être fastidieux à écrire et à déboguer pour les développeurs de logiciels.
Utilisation du processeur
Avantages
Les représentations sur bitboard utilisent des opérations bit à bit parallèles, disponibles sur la quasi-totalité des processeurs , qui s'exécutent en un seul cycle et figurent généralement parmi les instructions les plus rapides (grâce à leur pipeline complet, leur mise en cache et d'autres optimisations spécifiques au processeur). Presque tous les processeurs disposent des opérations ET , OU , NON-OU et OU exclusif . De plus, les processeurs modernes possèdent des pipelines d'instructions qui mettent les instructions en file d'attente pour leur exécution. Un processeur doté de plusieurs unités d'exécution peut exécuter plusieurs instructions par cycle si plusieurs instructions sont disponibles dans le pipeline. Les séquences d'instructions classiques avec branchements peuvent vider le pipeline si un branchement est mal prédit. De nombreuses opérations sur bitboard nécessitent moins de conditions, ce qui améliore le pipeline et permet une utilisation efficace des multiples unités d'exécution sur de nombreux processeurs.
Les processeurs ont une largeur de bits , c'est-à-dire le nombre d'opérations bit à bit pouvant être effectuées en un cycle. Ainsi, sur un processeur 64 bits ou plus, 64 opérations bit à bit peuvent être réalisées en une seule instruction. Il est possible qu'ils prennent en charge des instructions de largeur supérieure ou inférieure. De nombreux processeurs 32 bits peuvent comporter des instructions 64 bits, mais celles-ci peuvent nécessiter plus d'un cycle ou présenter d'autres limitations par rapport à leurs instructions 32 bits.
Si la taille du bitboard dépasse la largeur du jeu d'instructions, plusieurs instructions seront nécessaires pour effectuer une opération sur toute sa largeur. Par conséquent, un programme utilisant des bitboards 64 bits s'exécutera plus rapidement sur un processeur 64 bits que sur un processeur 32 bits.
Inconvénients
Les représentations sur bitboard contiennent beaucoup plus de code, tant source que objet. Les longues séquences de manipulation de bits sont techniquement complexes à écrire et à déboguer. Ce problème peut augmenter les défauts de cache ou provoquer une saturation du cache.
Si le processeur ne dispose pas d'instructions matérielles pour « premier un » (ou « compter les zéros de tête ») et « compter les uns » (ou « compter les zéros »), l'implémentation sera considérablement handicapée, car ces opérations sont extrêmement inefficaces à coder sous forme de boucles ou d'autres constructions de haut niveau.
Utilisation du cache et de la mémoire
Avantages
Les structures de données de plateaux à bits nécessitent plus de mémoire que les plateaux à liste de pièces, mais sont plus efficaces à l'exécution car de nombreuses boucles et comparaisons sont réduites à une seule (ou un petit nombre) opération bit à bit. Par exemple, dans le jeu de la boîte aux lettres, déterminer si une pièce attaque la case vide nécessite de générer et de parcourir ses déplacements légaux , puis de comparer la case vide obtenue avec la case vide initiale . Avec les plateaux à bits, les déplacements légaux de la pièce sont stockés dans une carte de bits, et cette carte est combinée par un ET logique avec la carte de bits de la case vide . Un résultat non nul signifie que la pièce attaque la case vide .
Inconvénients
Pour certains jeux, l'écriture d'un moteur à bitboard nécessite une quantité importante de code source, notamment des tables de données plus volumineuses que l'implémentation compacte par boîte aux lettres/énumération. Ceci peut poser problème sur les appareils mobiles (comme les téléphones portables) dont le nombre de registres ou le cache d'instructions du processeur est limité. Sur les ordinateurs classiques, cela peut entraîner des défauts de cache entre le cache de niveau 1 et le cache de niveau 2. Il ne s'agit toutefois que d'un problème potentiel, et non d'un inconvénient majeur, car la plupart des machines disposent d'un cache d'instructions suffisant pour que cela ne pose pas de problème.
Mise à jour incrémentale
Certains types de représentations bitmap sont dérivés d'autres par un processus complexe de corrélation croisée, comme les cartes d'attaque aux échecs. Reconstituer toutes ces cartes à chaque changement d'état du jeu (par exemple, un coup) peut s'avérer extrêmement coûteux ; c'est pourquoi les bitmaps dérivés sont mis à jour de manière incrémentale, un processus qui exige un code complexe et précis. Cette méthode est beaucoup plus rapide à exécuter, car seules les bitmaps associées aux cases modifiées, et non l'ensemble des bitmaps de l'échiquier, ont besoin d'être modifiées. Sans mise à jour incrémentale, la représentation bitmap peut ne pas être plus efficace que l'ancienne représentation par boîtes aux lettres, où la mise à jour est intrinsèquement locale et incrémentale.
Bitmaps précalculés et consultation de tables
Certains types de bitmaps qui ne dépendent pas des configurations du plateau peuvent être précalculés et récupérés par consultation d'une table plutôt que d'être rassemblés après un mouvement ou un changement d'état du plateau, comme les cases attaquées par un cavalier ou un roi situées sur chacune des 64 cases d'un échiquier qui nécessiteraient autrement une énumération.
Aux échecs
La représentation la plus simple et évidente de la configuration des pièces sur un échiquier consiste en une liste (ou un tableau) de pièces triées de manière à faciliter la recherche (par exemple, de la plus petite à la plus grande valeur), chaque pièce étant associée à sa position sur l'échiquier. De même, le recensement des cases attaquées par chaque pièce nécessite l'énumération séquentielle de ces cases. Ce système est appelé adressage par boîte aux lettres . Des listes distinctes sont utilisées pour les pièces blanches et noires, et souvent aussi pour les pions blancs et noirs. Les associations sont mises à jour à chaque coup, ce qui requiert une recherche linéaire (voire deux si une pièce a été capturée) dans la liste des pièces. L'avantage de l'adressage par boîte aux lettres réside dans la simplicité du code ; son inconvénient est la lenteur des recherches linéaires. Les échiquiers à bits sont plus rapides, mais plus complexes.
Standard
Dans les représentations en bits, chaque bit d'un mot de 64 bits (ou d'un double mot sur les architectures 32 bits) est associé à une case de l'échiquier. Toute correspondance entre bits et cases est possible, mais par convention générale, les bits sont associés aux cases de gauche à droite et de bas en haut : le bit 0 représente la case a1, le bit 7 la case h1, le bit 56 la case a8 et le bit 63 la case h8.
De nombreuses configurations de l'échiquier sont souvent représentées par leurs propres tableaux de bits, incluant les emplacements des rois, de tous les pions blancs, de tous les pions noirs, ainsi que des tableaux de bits pour chaque type de pièce ou combinaison de pièces, comme toutes les pièces blanches. Deux tableaux de bits d'attaque sont également universels : un tableau de bits par case pour toutes les pièces attaquant cette case, et le tableau inverse pour toutes les cases attaquées par une pièce pour chaque case contenant une pièce. Les tableaux de bits peuvent aussi être constants, comme celui représentant la première rangée, qui aurait des bits à 1 aux positions 0 à 7. D'autres tableaux de bits locaux ou de transition, tels que « toutes les cases adjacentes au roi attaquées par les pièces adverses », peuvent être regroupés selon les besoins ou la commodité.
Un exemple d'utilisation des bitboards serait de déterminer si une pièce est prise : les bitboards pour « toutes les pièces amies gardant l'espace » et « toutes les pièces adverses attaquant l'espace » permettraient de faire correspondre les pièces pour déterminer facilement si une pièce cible sur l'espace est prise .
L'un des inconvénients des plateaux d'échecs classiques réside dans le calcul des vecteurs d'attaque des pièces mobiles (tour, fou, dame), car leur nombre d'emplacements d'attaque est indéfini et dépend des autres emplacements occupés. Cela nécessite plusieurs longues séquences de masques, de décalages et de compléments pour chaque pièce.
Représentations de bitboard auxiliaires
Des structures de données alternatives pour les tableaux de bits ont été conçues afin de réduire la taille du code et la complexité de calcul nécessaires à la génération des tableaux de bits pour les vecteurs d'attaque des pièces mobiles. L'utilisation de tableaux de bits auxiliaires pour les pièces mobiles n'affecte pas la représentation des cavaliers, rois, pions et autres configurations de l'échiquier sous forme de tableaux de bits.
Tableaux de bits pivotés
Les bitboards pivotés sont des structures de données complémentaires permettant de tabuler les vecteurs d'attaque par glissement de pièces : un bitboard pour les vecteurs d'attaque par file des tours, et un bitboard pour les vecteurs d'attaque diagonaux et anti-diagonaux des fous (les attaques par rang des tours peuvent être indexées à partir de bitboards standard). Grâce à ces bitboards, une simple consultation de table remplace de longues séquences d'opérations bit à bit.
Ces matrices de bits font pivoter la configuration d'occupation de l'échiquier de 90°, 45° et/ou 315°. Une matrice de bits standard possède un octet par rangée de l'échiquier. Grâce à cette matrice, il est facile de déterminer les attaques de tours sur une rangée, à l'aide d'un tableau indexé par la case occupée et les positions occupées dans la rangée (car les attaques de tours s'arrêtent à la première case occupée). En faisant pivoter la matrice de bits de 90°, les attaques de tours vers le haut et vers le bas d'une colonne peuvent être examinées de la même manière. Les matrices de bits pivotées de 45° et 315° (-45°) présentent des diagonales faciles à examiner, pour déterminer les attaques de fous. La dame peut être examinée en combinant les attaques de tours et de fous. La rotation d'une matrice de bits est cependant une transformation complexe qui peut nécessiter des dizaines d'instructions.
Hachage direct
Les vecteurs d'attaque des tours et des fous peuvent être masqués séparément et utilisés comme indices dans une table de hachage de vecteurs d'attaque précalculés en fonction de leur occupation : 8 bits pour les tours et de 2 à 8 bits pour les fous. Le vecteur d'attaque complet d'une pièce est obtenu par l' union des deux vecteurs unidirectionnels indexés dans la table de hachage. Le nombre d'entrées dans la table de hachage est modeste, de l'ordre de…
Tableaux de bord magiques
Les tables de hachage magiques sont une extrapolation du compromis temps-espace de la recherche directe par hachage des vecteurs d'attaque. Elles utilisent une transmutation du vecteur d'attaque complet comme index dans la table de hachage. Le terme « magique » est impropre et fait simplement référence à la génération et à l'utilisation d'une fonction de hachage parfaite, combinées à des techniques permettant de réduire la taille potentielle de la table de hachage à stocker en mémoire.
Les carrés extérieurs, ou les premier et huitième rangs ainsi que les fichiers 'a' et 'h', sont sans rapport avec l'occupation du vecteur d'attaque : la pièce attaque ces carrés ou non (en fonction des autres pièces bloquantes) indépendamment de l'occupation, ceux-ci peuvent donc être éliminés de la considération, ne laissant que 6x6 ou 36 carrés (~bits dans la fonction de hachage correspondante).
L'indice d'attaque
Comme pour d'autres systèmes nécessitant une fonction de hachage parfaite, un processus d'énumération exhaustif, en partie algorithmique et en partie empirique, est nécessaire pour générer cette fonction. Les tables de hachage « magic bitboards » sont également très actives, et leur taille (généralement inférieure à un million d'entrées) est considérable par rapport à la taille des caches de bas niveau des architectures de puces modernes, ce qui entraîne une saturation du cache. Dans de nombreuses applications, les tables de hachage « magic bitboards » n'offrent aucun gain de performance par rapport à des systèmes de hachage plus modestes ou à des tables de hachage pivotées.
Optimisation du jeu d'instructions BMI2
Sur les processeurs x86-64 modernes compatibles avec l'architecture BMI2 (Bit Manipulation Instruction Set 2), le calcul des attaques par glissement de pièces aux échecs peut être accéléré directement par le matériel, éliminant ainsi le besoin de hachage par multiplicateur magique. Cette approche utilise les instructions assembleur d'extraction de bits parallèle (parallel bit extract _pext_u64) et de dépôt de bits parallèle (parallel bit deposit _pdep_u64). L' PEXTinstruction utilise un masque de blocage précalculé pour extraire les bits d'occupation pertinents directement dans un index contigu étendu à zéro. Cet index est ensuite utilisé pour effectuer une recherche instantanée dans le tableau de la carte d'attaque, optimisant ainsi l'utilisation des registres du processeur et éliminant les défauts de cache potentiels associés aux tables de recherche magiques plus volumineuses.
Histoire
La méthode de représentation par bits d'un jeu de plateau est attribuée à Arthur Samuel , qui l'a utilisée au milieu des années 1950 dans son programme de dames. Pour le jeu d'échecs, plus complexe, la méthode a été attribuée à l' équipe Kaissa en Union soviétique à la fin des années 1960, et aux auteurs du programme « Chess » de l'Université Northwestern aux États-Unis au début des années 1970. La longueur de mot de 64 bits des supercalculateurs des années 1970, tels que les machines Amdahl et Cray, a facilité le développement des représentations par bits, qui permettaient de faire correspondre les 64 cases de l'échiquier à des bits d'un mot.
Les matrices de déplacement rotatives permettant de compiler les coups des pièces mobiles ont été inventées par le professeur Robert Hyatt , auteur des moteurs d'échecs Cray Blitz et Crafty, au milieu des années 1990, et partagées avec l'équipe de programmation de Dark Thought. Elles ont ensuite été implémentées dans Crafty et Dark Thought, mais la première description publiée ne date que de 1997.
Dix ans plus tard, des méthodes de recherche directe utilisant des rangs, des fichiers et des diagonales masqués pour indexer une table de vecteurs d'attaque en fonction de l'état d'occupation des bits sous le masque ont été introduites. L'un de ces schémas, utilisant une fonction de hachage parfaite pour éliminer les collisions de hachage, a été baptisé « tableaux de bits magiques ». Cependant, la taille importante et la fréquence d'accès élevée de ces tables entraînaient des problèmes d'occupation mémoire et de contention du cache, et elles n'étaient pas nécessairement plus efficaces que l'approche par tableaux de bits pivotés. En 2026, les programmes de jeux restent divisés, le schéma optimal dépendant de l'application.
Autres jeux
De nombreux autres jeux, outre les échecs, bénéficient des plateaux numériques.
- Dans le jeu Puissance 4 , ils permettent de tester très efficacement quatre disques consécutifs, en seulement deux opérations Maj + ET par direction.
- Dans le Jeu de la vie de Conway , ils constituent une alternative possible aux tableaux.
- Ils sont également utilisés dans Reversi (aussi connu sous le nom d'Othello).