Ca avance !

Beaucoup de changements depuis le dernier post ! En fait, je m'aperçois que j'ai pas envie de tout expliquer ici. Ce blog devient vraiment pour des connaisseurs, désolé...

Et avant de commencer, je conseille cet IDE:
Geany: http://www.geany.org/

Magic bitboards

En plus des rois et cavaliers, j'ai fait les déplacements des tours avec des magic bitboards.
Résultat: 4% de gain de perf. Tout ça pour ça ? (J'y ai passé du temps....)

Je gagne autant avec quelques améliorations de code Ruby (moins d'assignation de variables temporaires par exemple)

Les perfs justement...

40% de gagné (7m au lieu de 12) juste en enlevant l'éval de la mobilité, qui ne sert pas à grand chose finalement car le jeu (les déplacements joués) reste à peu près le même. Enorme !

45% de gain avec la nouvelle façon de vérifier les mises en échec pour générer les coups légaux! Enorme!

Au lieu de générer tous les coups, et voir si un coup prend le roi, je met une piece à la place du roi et je vois si elle ne prend pas la même pièce de couleur opposée. Ca s'appelle "la super méthode que j'ai trouvée sur cette page": http://www.sluijten.com/winglet/11movegen05.htm#isAttacked

Faster method: to test if a case is being attacked, we reverse the perspective: for example, in order to see if square b3 is attacked by a black knight, we place a (hypothetical) white knight on square b3 and see if this white knight can capture a black knight. If the answer is yes, then the black knight is also attacking the white knight's field.

Sinon, j'ai gagné énormément de temps avec les null move reduction et les LMR. Les LMR ne sont pas encore bien finis, mais c'est suffisant pour l'instant.

Quiescence finie !

J'ai enfin fini... Là par contre ça fait perdre des perfs... 8 minutes pour un coup qui prend 30 secondes d'habitude. Puis avec la fonction SEE (static exchange evaluation) je regagne 82% et je retombe à 54 secondes. Mais ça dépend énormément des positions.

L'avantage par rapport aux 30 secondes qui étaient limitées à 3 plis, c'est que je ne suis plus limité justement. Les captures s’enchaînent jusqu'à ce qu'il y en ai plus ou que la SEE soit négative (j'élague - ou "prune" - seulement les échanges perdants).

Mais au final je perds en performances... beaucoup... Il faudra que je fasse d'autres prunings. Je fais déjà du delta, il faut voir si ya pas autre chose à part l'ID (Iterative Deepening)

WAC strength suite

J'ai rajouté une fonction d'évaluation de la force du moteur (strength evaluation) avec une suite de tests qui s'appelle WAC.

C'est une liste de positions connues avec la désignation du meilleur coup possible. Si le moteur trouve le meilleur coup en moins de 10 secondes (par exemple), le moteur est bon. Pour l'instant, il met jusqu'à 6h pour 247 problèmes (sur 300 que contient la suite) pour finalement trouver que 19% des problèmes... Un peu nul mon moteur pour l'instant. N'empêche qu'il est dur à battre déjà :) Il s'arrêtte à depth=3 pour l'instant mais avec l'iterative deepening, il ira plus loin.

Les résultats ressemblent à ça:
Depth-first, depth: 1, quiescence depth = 3
On 300 problems, 268 (89%) were not found. Total time: 4m31
Depth-first, depth: 2, quiescence depth = 3
On 300 problems, 244 (81%) were not found. Total time: 1h11m47
Useless iterative, depth: 3, quiescence depth = 3
On 247 problems, 200 (81%) were not found. Total time: 6h25m31
Autre test avec depth = 3 mais sans les itérations si je me souviens bien:
On 73 problems, 50 (68%) were not found. Total time: 44m45

Avec les derniers changements (notamment la supression de la limite de la quiescence qui était juste là pour pas que je m'endorme devant un test) une recherche complète à 3 plis du premier problème prend 52 min... pour finir par ne pas trouver la solution.
Je vais mettre ce premier problème à la dernière place :)

Interative deepening

Et le plus important est à venir: l'iterative deepening avec le classement des coups afin d'arriver au final à faire du LMR (late move reduction). Tout ce jargon pour dire qu'il faut arriver à terme à ne pas calculer tous les coups, mais seulement les meilleurs présentis afin de gagner du temps et aller plus loin dans la profondeur.

Je voulais pas commencer avant de faire les tests de force, afin de voir l'amélioration du moteur. Puis j'ai finalement fini la quiescence. Bref.

Evidemment l'itérative deepening ne sert à rien si on ordonne pas les coups par leur score et si on ne reprend pas l'état de la recherche de l'itération précédente. Il faut tout faire d'un coup. Et c'est compliqué. Enfin... déjà à comprendre... avant de commencer à coder :)

Voilà, j'y bosse tous les jours pratiquement. Et demain c'est férié et je me retrouve coincé avec une entorse et une atèle... donc... devs en vue ! :)

Bitboards : ça y est, on y va

Petite page

J'ai fait cette page en anglais pour présenter MyTeacheR et résumer l'état des développements.

https://sites.google.com/site/faivrem/home/myteacher

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 !

Je joue (avec une interface graphique)

J'ai fait une interface xboard. C'est à dire que j'utilise xboard pour jouer contre mon moteur.

Le problème en codant un jeu c'est qu'on a envie d'y jouer ! Et en ce moment je passe plus de temps à jouer qu'à coder. Ce qui me motive à retourner coder c'est qu'il est encore suuupeeer lent, et quand j'en ai marre d'attendre, j'arrêtte de jouer et je me décide à améliorer les perfs :)

J'ai amélioré quelques fonctions très utilisées et consommatrices de temps. Je faisais Pert(3) en 20 secondes, ça se fait en 10s maintenant. Et j'en suis qu'au début des améliorations.

Petit rappel: la fonction Perft retourne le nombre d’enchaînement de déplacements possibles pour un niveau donné. Quand les blancs jouent il y a Pertf(1) = 20 déplacements possibles, puis les noirs répondent: Perft(2) = 400 (20x20 déplacements). Les blancs répondent et Perft(3) = 8902 (20x20x22). Pour générer ces 8902 déplacements j'ai besoin de 10 secondes. Pour 100 000 déplacements, Crafty met 1 seconde ..... Et encore, je simplifie les choses. Pour générer les premiers déplacements, c'est beaucoup plus rapide que pour générer les déplacements en milieu de partie. Bref....

Ensuite j'ai amélioré la fonction d'évaluation avec une "recherche tranquille" (quiescence search). C'est à dire que la recherche ne s’arrête pas s'il existe des captures possibles. Enfin... normalement elle ne devrait pas évaluer toutes les captures pour des raisons de temps de recherche.

Et ben... ça a vachement amélioré son jeu. Je ne fais plus le malin maintenant !

Je ne suis pas encore allé jusqu'à une fin de partie parce que c'est trop long... mais je vois bien que ça va être dur de le battre !

Ma "current TODO list":

- Iterative deepening and move ordering to be able to limit search time

- Finish Quiescence search (do not evaluate all the moves)

- Improve performance of legal move gen (moves generation really using bitboards, and maybe premove tables)

Il est vivant !

Et voilà le moment tant attendu où le moteur joue contre lui-même avec des mouvements pas trop cons. Le plus étonnant c'est qu'avec une fonction d'évaluation très simple et une recherche à 3 plis, ça suffit pour mimiquer un jeu pas trop déconnant. Arthur pourrait jouer comme ça (désolé mon fils, tu joueras contre lui quand j'aurai une interface graphique et on verra si tu es plus fort et si ton père raconte des bêtises)

Au niveau temps de recherche là ça pêche toujours. Le beta-cutoff permet de gagner vraiment pas mal de temps, mais je n'en suis qu'au début de la fonction de recherche. Bcp est encore à faire.

Ma TODO liste intermédiaire a augmenté.

- Pour l'instant je n'affiche que des plateaux en texte sur la console. Il est temps que je m'amuse contre lui. Il me faut juste un input texte ou une interface xboard. Et pour qu'Arthur joue, une interface graphique comme xboard c'est mieux.

- Ensuite pour améliorer le jeu et les performances, dans l'ordre:

1. remove beta cutoff (to be able to compare the added value)
2. Performance recording: maybe some branching factor (or nb of nodes visited) average based on a versioning to be able to compare versions.
3. add again beta cutoff
4. Quiescence search to improve play (that would increase the nb of nodes)
5. Iterative deepening (no changes for nb of nodes before ordering)
6. Move ordering (increase cutoffs, decrease nb of nodes visited)

Voilà, il est vivant ! Il marche ! A partir de maintenant, ce n'est que amélioration et expérimentations !

Perft et débugage

Le chargement d'une position à partir d'une chaine FEN est fait !
Ca veut dire que je peux tester des positions comme je veux et j'ai fini de faire les tests (que j'aurais dû faire avant) et corrigé les bugs que j'avais.

J'ai aussi fait la fonction Perft (générateur et compteur de positions à une profondeur donnée pour voir si ya pas de bugs).

Là ça fait mal...

22 secondes pour aller au niveau 3 de profondeur (ply == 3). 20 secondes en améliorant la fonction elle même, mais c'est pas le but, le but c'est d'améliorer le moteur. Un moteur moyen met 20ms (milli !) pour 3 plis :)

Bah je suis juste 10 000 fois plus lent, rien de grave :)
Et en plus j'ai des bugs.

Normalement les valeurs de Perf sont:

perft(1) = 20

perft(2) = 400

perft(3) = 8902

et pour perft(3) je trouve 8906 au lieu de 8902...

Il y a 12 mises en échec possible au niveau 3. Peut-être que ma fonction de générateur de mouvements a un bug au niveau des mouvements légaux, et qu'il autorise une autre pièce à bouger pendant que le roi est en échec ? Hum, ça en ferait trop....

Il faut que ma suite de tests soit plus étoffée !

Et il faut que j'améliore les perfs ! J'ai une petite idée d'où ça vient: la vérification des mouvements légaux. En la virant, je fais le niveau 3 en 0.85 s (au lieu de 20 s) et je fais le niveau 4 en 18 secondes (198 030 déplacements... au lieu de 197 281 si je n'avais pas de bugs). 0.85 s au lieu de 0.002 c'est toujours mieux (425 fois plus lent)

Bon, ben... vive la chasse aux bugs d'abord :)

TODO

Voici (en anglais puisque c'est dans un fichier source) l'avancement du moteur.

Fini:
- Set up TDD (RSpec)
- choose a board representation
- write functions to update chessboard representation
- write utility function to translate FEN position into your chessboard representation (if not, no easy TDD for move generator)
- write moves generator
- write a Perft function

En cours:
- write a search function with simple evaluation function
- xboard interface
- play !
- optimisation (Quiescence search, etc...)
- play !
- FICS interface
- play and watch it play !
- DB to store moves evaluations
- ... and play more !

Génération des déplacements fini !

Ca y est ! Première étape de franchie !

Les reines, les tours, et tout le reste se déplacent et peuvent prendre ! Les rois peuvent roquer et les pions peuvent avancer de deux cases et se faire prendre "en
passant". De plus, les déplacements sont vérifiés "légaux", c'est à dire qu'avant de bouger une pièce, il est vérifié que le roi n'est pas en échec, que ce soit le roi lui-même qui bouge ou une autre pièce ("pin").

C'est pas beau ça ?

J'ai pas encore de fonction de recherche (avec la fonction d'évaluation de la position) mais j'ai codé une simple fonction d'affichage des positions qui s’enchaînent au hasard. Et j'affiche ça en texte. C'est trop beau.

Bon, sauf que j'ai des bugs :)
Notamment dans la fonction prune_king_revealers ou unmake.
Lire la suite...

Sans fonction de chargement de position, pas de TDD possible

J'ai retardé de faire une fonction de chargement de position (à partir d'une notation FEN par exemple), mais finalement c'est super important: sans chargement de position initiale facile, pas de tests facilement faisables. Pas de bras, pas de chocolat. Pas de tests, pas de TDD. J'avoue, j'ai développé sans vraiment tester chaque fonction de déplacement en premier lieu, mais avec une simple fonction d'affichage des positions qui s’enchaînent. Donc avant de tomber sur la bonne position à tester... J'aurais pu au moins faire un lecteur de déplacements pour aller à la bonne position sans hasard. Prochain truc à faire donc, la fonction de chargement et les tests correspondants !

Motivé !

Quelle horreur quand au cours de mes lectures je suis tombé sur RubyKnight ! Un moteur en Ruby avec bitboards ! Là je me suis posé des questions. Mais que fais-je ? Quel est mon but ? Si mon but est faire un moteur en ruby avec bitboards, j'en ai un devant les yeux.

Puis quand j'ai vu qu'il ne calculait qu'un seul déplacement, que les déplacements n'étaient pas précalculés avec bitboards, je me suis dit tant mieux. Et en fait, j'ai développé ma motivation. Car le code que j'avais sous les yeux ne me parlait pas. Je suis retourné à mon code et il m'a regardé en retour et m'a dit: "je suis là ! C'est moi!" Mon bon petit code à moi, bien stylé.

Oh oui j'ai bien regardé le code de RubyKnight, ce qu'il faisait et comment il le faisait, mais je n'aime pas ses data structures et la façon toute simple (et sans aucun tests!) de commander cette armée.

Mon but est d'avoir du plaisir à coder, avec mon style et TDD, un moteur d'échecs qui sera amélioré au fil du temps et de le voir se battre avec des humains sur FICS tout en fournissant des fonctions qu'aucun autre programme ne le fait sur FICS. Comme son père MyTeacher.

La représentation du plateau est faite, la classe "Move" a vu le jour et je continue à faire du TDD sur cette classe, encore un peu, avant de tomber de sommeil.