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