Petite page
J'ai fait cette page en anglais pour présenter MyTeacheR et résumer l'état des développements.
Bitboards précalculés
Après pas mal de recherche de bugs (et il en reste) j'ai commencé à générer les déplacements avec des bitboards précalculés (définition plus loin).
Depuis le début je représente les positions avec des bitboards, mais je ne les utilise pas pour générer les déplacements. Je génère les déplacements à la volé ("sur la mouche" comme disent les anglais) et sans faire appel à la puissance des bitboards.
Définition: un bitboard, c'est juste un nombre.
27, c'est un bitboard. Sous sa forme binaire, il pourrait représenter les positions des pions blancs par exemple. 27 en binaire c'est 11011, ça voudrait dire que sur la première case il y aurait un pion blanc, sur la deuxième aussi, pas sur la troisième, etc.... On peut aussi représenter les déplacements. Et on peut aussi faire des calculs de déplacements génériques avant même que le programme se lance vraiment pour gagner du temps ensuite. D'où le terme bitboards précalculés.
Et ben on dirait pas, mais représenter le plateau ("board") avec des 0 et 1 ("bit") permet de générer les déplacements très rapidement car les calculs se font sur de simples nombres et non pas sur des structures compliquées de données. Les bitboards sont nos amis. Il existe un nombre important de techniques basées sur les bitboards. Certaines sont mêmes magiques ! Peut-être que je ferai un post quand j'en arriverai à coder avec des "magic bitboards" ! Mais j'en suis pas encore là. Pour l'instant, MyTeacheR reste 10 000 fois plus lent que n'importe quel autre moteur et joue mal, c'est à dire mieux que moi mais avec des bugs :) En vous passant les détails, je m'attends à voir de grosses améliorations de performances en utilisant les bitboards pour la génération des déplacements. On verra quand j'aurai fini :)
Performances
Sinon je m'amuse toujours à faire des tests de perfs.
r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - 0 1
C'est une position connue, utilisée pour les tests de performance justement.
Il aura fallu 1h 50m et 21s à MyTeacher pour aller au niveau 3 (blancs jouent, puis noirs, puis blancs).... Et encore... avec une quiescence elle aussi limitée à 3 plis. (J'expliquerai peut-être la quiescence dans un autre post). ROCE a mis 0.01s à aller au niveau 3... 662100 fois plus rapide.... J'ai du boulot :)
La suite
Il faut d'abord que je trouve les bugs de Perft(4) avant de continuer à recoder le générateur de déplacement. Pour cela je vais coder une fonction "divide", pour ceux qui connaissent (pas envie d'expliquer tout ce que je fais non plus), et me baser sur les résulats de ROCE pour faire des comparaisons et trouver l'origine des bugs.
Puis je recoderai les déplacements avec les bitboards précalculés. Puis je referai des tests de performance. Je trouverai que mon moteur n'est plus que 123000 fois plus lent et je continuerai à itérer :)
Puis l'iterative deepening pour pouvoir controller le temps de jeu (sans ça on est obligé d'attendre que le moteur finisse d'aller à la fin d'une profondeur donnée sans pouvoir l’arrêter).
Entre temps évidement, je jouerai contre lui :)
Quand les performances seront acceptables et le temps de jeu contrôlable, alors là viendra un grand moment. Les hashtables pour enregistrer les positions connues mais surtout... une interface avec FICS !
A bientôt !
1 comment:
Intéressant ;)
Post a Comment