Gnochon : quelques ressources

17 février 2017

Les ressources en français était rarissimes, je vous présente donc une courte liste de sites anglophones qui traitent spécifiquement de la programmation de jeux d’échecs.

Chess Programming Wiki (CPW)

Computer Chess Club (CCC)

WinBoard Forum

OpenChess forums

Computer Chess Club Archives

AutoChess forums

Internation Computer Games Association (ICGA)

Blogue de Roland Chastain (en français)

Pour une liste plus complète (incluant des blogues ou des forums en d’atres langues que l’anglais), tout est ici.

 


The Chess Games Repository

16 février 2017

What do you need to build a solid opening book for a chess engine? And what do you need to study chess openings seriously?

Games.  Lots of games. Lots of games by strong players. So my long-dead project revives again!

The Chess Games Repository!


Gnochon : c’est parti!

13 février 2017
gnochon_coding

Gnochon sur Squeak 5.1 (32bit)

1-Mise à jour

Gnochon, c’est parti!  Déjà quelques leçons d’apprises!

1-Quand tu pars de rien, sans t’inspirer d’aucun code source des autres, c’est long et compliqué!  Tout est à faire et à penser.
2-Les pions vont causer 99% de tes problèmes.  Les pions sont tes ennemis!
3-La vie d’un développeur est plus compliquée quand tu désires supporter deux environnements, Squeak et Pharo.

gnochon_coding_pharo

Gnochon sur Pharo 5.0

2-Le premier adversaire

squeak_chess

Dès que Gnochon sera en mesure de jouer une partie complète, j’ai décidé que le premier programme qu’il affronterait serait Chess, disponible sur SqueakSource et qui tourne sur Squeak!  Le projet est situé ici.  Ce programme tourne à environ 50000 NPS (nodes per second) sur mon ordinateur.  Évidemment, pour le battre je devrai être plus rapide!

3-Lozza

Finalement, pour rester dans le thème des échecs, j’ai découvert Lozza, un jeu d’échecs en ligne. Une petite merveille simple et efficace d’un programmeur nommé Colin Jenkins. Il permet même d’analyser des positions à partir de chaînes FEN.  Et pour les curieux, la position sur l’échiquier est un problème de mat en 13!  Essayez-vous : c’est beaucoup plus facile que c’en a l’air!

lozza

Lozza. Les blancs jouent et matent en 13 coups!


Bits and Pieces

10 février 2017

Often times, we take stuff for granted.  But while preparing to embark on a crazy project (description in French here and Google translation in English here), I wanted to benchmark the bit manipulation operations in both Squeak and Pharo, for the 32bit and 64bit images (I am on Windows so the 64bit VM is not available for testing yet but it’ll come!).  So essentially, it was just a test to compare the VM-Image-Environment combo!

To make a long story short, I was interested in testing the speed of 64bit operations on positive integers for my chess program. I quickly found some cases where LargePositiveInteger operations were more than 7-12 times slower than the SmallInteger equivalences and I became curious since it seemed like a lot.  After more testing and discussions (both offline and online), someone suggested that some LargePositiveInteger operations could possibly be slow because they were not inlined in the JIT.  It was then recommended that I override those methods in LargePositiveInteger (with primitives 34 to 37), thus shortcutting the default and slow methods in Integer (corresponding named primitives, primDigitBitAnd, primDigitBitOr, primDigitBitXorprimDigitBitShiftMagnitude in LargeIntegers module).  I immediately got a 2-3x speedup for LargePositiveInteger but…

Things have obviously changed in the Squeak 64bit image since some original methods (in class Integer) like #bitAnd: and #bitOr: are way faster than the overrides (in class LargePositiveInteger )!  Is it special code in the VM that checks for 32bit vs 64bit (more precisely, 30bit vs 60bit integers)?  Is it in the LargeIntegers module?

Here are 2 typical runs for Squeak 5.1 32bit (by the way, Pharo 32bit image performs similarly) and Squeak 5.1 64bit images  :

Squeak 5.1 32bit

Number of #allMask: per second: 7.637M
Number of #anyMask: per second: 8.333M
Number of #bitAnd: per second: 17.877M
Number of #bitAnd2: per second: 42.105M
Method #bitAnd2: seems to work properly! Overide of #bitAnd: in LargeInteger works!
Number of #bitAt: per second: 12.075M
Number of #bitAt:put: per second: 6.287M
Number of #bitClear: per second: 6.737M
Number of #bitInvert per second: 5.536M
Number of #bitOr: per second: 15.764M
Number of #bitOr2: per second: 34.409M
Method #bitOr2: seems to work properly! Overide of #bitOr: in LargeInteger works!
Method #bitShift2: (left & right shifts) seems to work properly! Overide of #bitShift: in LargeInteger works!
Number of #bitXor: per second: 15.385M
Number of #bitXor2: per second: 34.043M
Method #bitXor2: seems to work properly! Overide of #bitXor: in LargeInteger works!
Number of #highBit per second: 12.451M
Number of #<< per second: 6.517M 
Number of #bitLeftShift2: per second: 8.399M 
Number of #lowBit per second: 10.702M 
Number of #noMask: per second: 7.064M 
Number of #>> per second: 7.323M
Number of #bitRightShift2: per second: 29.358M

Squeak 5.1 64bit

Number of #allMask: per second: 36.782M
Number of #anyMask: per second: 41.026M
Number of #bitAnd: per second: 139.130M
Number of #bitAnd2: per second: 57.143M
Method #bitAnd2: seems to work properly! Overide of #bitAnd: in LargeInteger works!
Number of #bitAt: per second: 23.358M
Number of #bitAt:put: per second: 8.649M
Number of #bitClear: per second: 38.554M
Number of #bitInvert per second: 29.630M
Number of #bitOr: per second: 139.130M
Number of #bitOr2: per second: 58.182M
Method #bitOr2: seems to work properly! Overide of #bitOr: in LargeInteger works!
Method #bitShift2: (left & right shifts) seems to work properly! Overide of #bitShift: in LargeInteger works!
Number of #bitXor: per second: 55.172M
Number of #bitXor2: per second: 74.419M
Method #bitXor2: seems to work properly! Overide of #bitXor: in LargeInteger works!
Number of #highBit per second: 7.921M
Number of #<< per second: 10.127M 
Number of #bitLeftShift2: per second: 12.800M 
Number of #lowBit per second: 6.823M 
Number of #noMask: per second: 39.024M 
Number of #>> per second: 23.188M
Number of #bitRightShift2: per second: 56.140M

So now, I’m left with 2 questions :

  1. Why exactly does the override work (in 32bit images)?
  2. What changed so that things are different in Squeak 5.1 64bit image (overrides partially work)?

If you’re curious/interested, the code I have used to test is here.

Leave me a comment (or email) if you have an explanation!

To be continued…


Gnochon : le plan (2)

8 février 2017
alice-kent-stoddard-the-chess-game

Alice Kent Stoddard – The Chess Game

1-L’objectif

Comme je l’ai expliqué prédemment, je me lance dans la création d’un programme d’échecs en Smalltalk. J’y pensais depuis longtemps et m’y voici, finalement.  Je tâcherai d’atteindre deux buts : faire un programme d’échecs qui atteindra au moins 2000 Elo et ne consulter aucun code source pour m’inspirer des algorithmes des autres.  Autre défi de taille, essayer de trouver du contenu en français pour vous aiguiller si vous avez besoin d’un coup de pouce supplémentaire!

2-Pourquoi Smalltalk?

Pourquoi Smalltalk, un langage interprété? Tout d’abord, parce que c’est de loin le langage de programmation que je connais le plus comme je l’utilise depuis plus de 22 ans.  Ensuite, parce l’environnement Smalltalk offre une facilité de débogage, une panoplie d’outils et une rapidité de dévelopement inégalés.  Par ailleurs, Smalltalk est pourvu d’une riche et mature librairie de code et d’une multitude de classes de base par défault. Finalement, j’ai aussi choisi Smalltalk parce que c’est un des meilleurs exemples de « write once, run anywhere« .  Pharo et Squeak sont disponibles sur mac (macOS, OS X), Windows (x32, x64) et GNU/Linux (x86 et ARM).

3-Les prérequis

Dans la mesure où vous seriez tentés de suivre ce blogue et cette aventure en essayant vous aussi de coder un programme d’échecs, il vous faudra quelques prérequis pour suivre mes développements.  Premièment, une connaissance de Smalltalk est grandement souhaitable (quoique la syntaxe du langage et le code sont si simples que vous devriez tous être en mesure de comprendre).

Ensuite, une connaissance minimale des règles du jeu d’échecs est nécessaire : cela inclut le déplacement des pièces, la prise en passant, le roque, la promotion du pion, la règle des cinquante coups, la règle de répétition de position, le mat, le pat, les cas de parties nulles (e.g. matériel insuffisant pour mater), la notation algébrique, etc.  Idéalement, vous seriez un joueur d’échecs vous-même quoique cela n’est pas absolument nécessaire comme l’a déjà prouvé Claude Jarry [1]!

Claude Jarry attendant la réponse de son programme d’échecs « L’Excentrique »

4-Les outils

Évidemment, vous aurez besoin de Squeak et/ou Pharo!

Je ne compte utiliser que des solutions open source pour ce projet alors ne craignez pas de dépenser un seul sou! Alors si vous désirez me suivre pas à pas, j’utiliserai Squeak au début puis je migrerai ensuite mon programme sur Pharo.

ampoule48x48

Comme Pharo a comme ancêtre Squeak, vous pourrez utiliser l’un des deux environnements sans distinction ni problème. S’il y a des différences rencontrées en cours de chemin, je me ferai un devoir de vous les souligner et de vous les expliquer!

Il vous faudra aussi un éditeur de texte convenable (je n’ai que de bons mots pour Notepad++).  Puis un logiciel de comparaison de fichier pourra aussi s’avérer très utile (je ne jure que par WinMerge). Ensuite, un logiciel de base de données de parties d’échecs (pour pouvoir construire une bibliothèque d’ouverture, lire et sauvegarder des parties et des positions, imprimer des diagrammes, etc comme SCID vs PC ou SCID) est un outil incontournable et vital pour ce projet. Finalement, un logiciel de compression de données et d’archivage comme 7-Zip (j’utilise principalement les formats zip, gz et 7z).

Dès que le programme sera en mesure de jouer une partie complète, il nous faudra un logiciel d’appariement (comme Arena ou CuteChess) pour automatiser les tests et le faire jouer contre d’autres programmes d’échecs : il nous faudra alors utiliser un des protocoles de communication disponibles  (Xboard ou UCI). Aussi, un autre incontournable, le programme d’extraction PGN-Extract pour les parties d’échecs en format PGN.

Finalement, si votre esprit s’égare parfois d’une idée à l’autre comme moi, la technique Pomodoro (et un minuteur Pomodoro approprié) sont plus que bénéfiques!

5-Les ressources

Pour apprendre à jouer aux échecs : l’article dans Wikipedia, les leçons d’échecs pour débutants en ligne, le WikiLivre Apprendre à jouer aux échecs.

Pour apprendre Squeak : le livre Squeak par l’exemple.

Pour apprendre Pharo : le livre Pharo par l’exemple.

Pour de l’aide en programmation (général) : developpez.net

Pour de l’aide en Squeak ou Pharo : sachez que les listes de diffusion (toutes en anglais) de Pharo et Squeak sont toujours très efficaces et rapides à répondre aux questions.  Qui plus est, un grand nombre d’utilisateurs de Squeak et Pharo sont situés en Europe et parlent français!  Évidemment nétiquette oblige, posez vos questions en anglais en premier lieu!

Pour toute autre aide pour ce projet : bien que les salons de discussions sur IRC (sur irc.freenode.net) soient habituellement en anglais, sachez que vous me trouverez toujours sur ##chessprogramming, #pharo ainsi que #squeak sous l’alias lamneth (et un peu partout sur IRC dans tous les salons reliés à Smalltalk de près ou de loin)!

6-Pourquoi le nom Gnochon?

En québécois, un gnochon désigne une personne idiote, stupide, imbécile.  C’est probablement ce dont aura l’air mon programme d’échecs au début!

7-Les étapes

Voici une liste assez complète de tout ce dont j’ai l’intention d’équiper mon programme.  J’ai divisé le projet en sept jalons afin de ne pas perde de vue l’objectif final ni de céder au découragement ou à l’éparpillement des efforts!

a) Avoir un programme qui génère tous les coups valides d’une position

Définir les classes de base : l’échiquier et les coups.
Définir le générateur de coups
Arriver à lire/écrire des fichiers EPD
Tester le générateur de coups avec perft
Définir un évaluateur de position de base (matériel seulement)
Définir un mécanisme de tri des coups (move ordering)

b) Avoir un programme capable de faire une recherche de plusieurs niveaux

Définir les tables de piece-square et bitmasks nécessaires/manquants
Définir la recherche alpha-beta (ou équivalent)
Définir le iterative deepening

c) Avoir un programme capable de jouer une partie complète

Définir un gestionnaire de temps de réflexion (pour respecter les cadences)
Gérer le protocole de communication utilisé (XBoard ou UCI, à décider)
Définir une fonction d’évaluation positionnelle
Arriver à lire/écrire des fichiers PGN

d) Raffiner l’élagage de l’arbre et accélérer la recherche

Implémenter le null move
Implémenter le concept de aspiration window
Implémenter le static exchange evaluator
Arriver à lire une bibliothèque d’ouverture (opening book)

e) Permettre au programme de chercher à une plus grande profondeur

Implémenter le futility pruning
Implémenter le late move reduction
Implémenter la quiescence search
Implémenter une table de killer move

f) Accélérer l’évaluation et permettre un meilleur jeu en finales

Ajouter le support pour les tables de fin de partie (tablebases)
Implémenter une table de transposition avec le Zobrist hashing
Implémenter une table de hachage pour la structure de pions
Implémenter le late move reduction

g) Mieux gérer les débuts et les fins de partie

Implémenter un évaluateur de fin de partie
Générer ma propre bibliothèque d’ouvertures avec les parties du CGR
Ajouter des algorithmes de gestion de fin de partie pour certaines finales

8-Et après?

Il y aura toujours d’autres fonctionalités et algorithmes qu’on pourra ajouter à n’importe quel programme d’échecs.  Que ce soit le contempt factor, le desperate move, la recherche en parallèle, le pondering, etc.  Tellement de trucs ont été essayés, tellement de papiers ont été écrits sur le sujet, tellement d’algorithmes et de structures de données ont été expressément développées dans le cadre des jeux d’échecs par ordinateur que c’est une inépuisable spirale qui bouffera tous vos temps libres si vous n’y faites pas attention!

L’important est d’y aller lentement, pas à pas.  Et surtout de tester.  De retester.  De tester encore. Et d’encore tester! À chaque étape, à chaque changement!

Parce que comme Ken Thompson l’a déjà dit, écrire un programme d’échecs a été une des choses les plus difficiles qu’il a faite.

ken-joe

Ken Thompson (à droite) et Joe Condon

Quand on sait que le gars a inventé des fontes d’échecs, qu’il a inventé le langage B et participé à l’élaboration du langage C, qu’il a développé Unix, qu’il a développé le système d’exploitation Plan 9, qu’il a généré les toutes premières tables de finales de parties d’échecs, qu’il a écrit Belle (programme d’échecs champion en 1978, 1980, 1981, 1982 et 1986), qu’il a co-inventé le langage Go, qu’il a élaboré les expressions régulières, implémenté les éditeurs de texte QED et Ed, qu’il a participé à la définition du standard du codage UTF-8, bien on se dit que si Ken Thompson a trouvé qu’écrire un programme d’échecs c’était difficle, c’est que ça doit l’être!

kenthompsonchessfonts

Les fontes d’échecs inventées par Ken Thompson

Note: pour une liste encore plus longue de tous les accomplissements de Ken Thompson, la page wikipedia en anglais en encore plus complète.  La liste des choses que ce génie de l’informatique a réalisé est tout simplement hallucinante!

 

 


Gnochon

14 octobre 2016

Thanks to Twipply, ZirconiumX and JoshS (regulars of ##chessprogramming on IRC), I finally decided to go ahead with my chess engine named Gnochon!  At first, development will be slow as I am still working on Freewill and plan on finishing it before mid-November.

In case you asked, Gnochon is a French slang word in Quebec meaning someone *really* stupid!

gnochon(click on image to enlarge)

Save


OpenRefine : quelques ressources en français

21 septembre 2016

Vous le savez, je ne taris pas d’éloges à l’égard d’OpenRefine.  Le malheur, c’est que ce puissant outil a peu de vitrine dans la communauté informatique francophone.  Qu’à celà ne tienne, voici une courte liste de ressources en français sur le web!