Perceptron et Pharo

13 avril 2017

Ceux qui s’intéressent aux classifieurs linéaires et à Pharo et/ou Smalltalk seront heureux d’apprendre qu’il existe maintenant une implémentation de perceptron en Pharo Smalltalk!!

Tous les détails sont ici.

That guy

3 avril 2017

We all know that guy. You know, that guy who sees performance improvements everywhere, all the time?

That programmer who squeezes everything into bitmaps because « it’s so much faster » ?  And when I say everything, I mean everything! Even if your class only has one flag!

That guy who caches everything in the application because « that’s the optimal way to do it« ?  Even if the data that is cached is just accessed only one time?

That guy who fits a date into an integer in the database because « it’s so much more compact » ?  There goes all your SQL and date functions!

That developer who always ends up re-implementing another sorting algorithm because he read a « great paper » on the subject and « it’s proven that it’s 0.2% faster than the default sort » available?  And after an insane debugging session, you finally realize he has overriden SortedCollection>>#sort: ?  And that his code just doesn’t work properly!

You know, that guy with a C/C++ background who spends countless hours optimizing everything not realizing he has to « make it work » first! You know, that guy who still doesn’t get that often times you only need to optimize very small parts of an application to make a real difference?

You know that guy with strange concepts such as « defensive programming » who tells you nobody ever caught a bug in his code in production? You know, that guy who came up with the « clever » catch-everything method #ifTrue:ifFalse:ifNil:onError:otherwise: ?

You know that guy who never works for more than 4 months at the same place because « they didn’t get it, they’re a bunch of morons » ?

You know, that guy who prefers to implement complex database queries with a #do: loop and a gazillion SELECT statement because « SELECT statements with a 1-row lookup are very optimized by the database server » instead of using JOINs. And then he blames the slow response time of his « highly optimized » data retrieval code on the incompetence of the DBAs maintaining the database?

You know, that guy who once told me « inheritance in Smalltalk is very bad because the deeper the class in the hierarchy, the slower the method lookup is going to be » so that’s why he always preferred « flattened hierarchies » (meaning promoting ALL instance variables into one root class) with 2-3 levels deep in the worst case? « Besides, my code is easier to understand and debug since everything is in one place« .

Well, I was going through some of the sh*ttiest code I’ve seen in a long time last night and I remembered that guy and his ideas about « highly optimized flattened hierarchies » and thought I’d measure his theory!  Here’s the script.

Basically, it creates a hierarchy of classes (10000 subclasses) and times message sends from the top class and the bottom class to measure the difference.

Well, that guy was right… There’s a 1 millisecond difference over 9 million message sends from the root class as compared to the 10000th class at the bottom of the hierarchy.

I wanted to tell that guy he was right but his email address at work is probably no longer valid…

CAVEAT: Make sure you do not have a category with the same name as the one in the script because the script removes the category at the end (and all classes in it!).  Also, be warned it takes a very very very long time to execute!

P.S. All the stories above are real. No f*cking kidding!  Those guys really existed : I’ve worked with them!

Paramétrer le garbage collector de Pharo

15 mars 2017

Un excellent article de Clément Béra sur les subtilitées, plus ou moins connues, des paramètres du garbage collector dans Pharo.  L’article est encore plus intéressant du fait qu’il aborde le sujet avec des cas concrets!

Google Fights

17 février 2017

Who’s more referenced by Google?  Here’s the answer to this Google fight between Squeak and PharoGoogleFight anything you want! Quick, funny, and not serious at all!



1001001 SOS

10 février 2017


I’ve been dealing a lot with bit operations lately.  And doing lots of benchmarking, like here. As I was looking for a bit count method in Pharo (it used to be there but it no longer exists in Pharo 5.0), I got curious about the many different versions of bit counting algorithms I could find on the internet.

What’s so special about bit operations you ask?  Not much.  Except when you have to do it really fast on 64bit integers!  Like in a chess program!  Millions of times per position. So instead of copying the #bitCount method that was in Squeak, I decided I’d have a look at what is available on the net…

So I decided to share what I found.  This could potentially be useful for people who have to deal with bit counting a lot. Especially if you deal with 14 bits or less!

Here’s a typical run of the different bit counting algorithms I have tested on Squeak 5.1 64bit.

Number of [myBitCount1 (128 bits)] per second: 0.061M
Number of [myBitCount1 (14 bits)] per second: 1.417M
Number of [myBitCount1 (16 bits)] per second: 1.271M
Number of [myBitCount1 (30 bits)] per second: 0.698M
Number of [myBitCount1 (32 bits)] per second: 0.651M
Number of [myBitCount1 (60 bits)] per second: 0.362M
Number of [myBitCount1 (64 bits)] per second: 0.131M
Number of [myBitCount1 (8 bits)] per second: 2.255M
Number of [myBitCount2 (128 bits)] per second: 0.286M
Number of [myBitCount2 (14 bits)] per second: 3.623M
Number of [myBitCount2 (16 bits)] per second: 3.630M
Number of [myBitCount2 (30 bits)] per second: 2.320M
Number of [myBitCount2 (32 bits)] per second: 2.336M
Number of [myBitCount2 (60 bits)] per second: 1.415M
Number of [myBitCount2 (64 bits)] per second: 1.208M
Number of [myBitCount2 (8 bits)] per second: 4.950M
Number of [myBitCount3 (128 bits)] per second: 0.498M
Number of [myBitCount3 (14 bits)] per second: 4.556M
Number of [myBitCount3 (16 bits)] per second: 4.673M
Number of [myBitCount3 (30 bits)] per second: 3.401M
Number of [myBitCount3 (32 bits)] per second: 3.401M
Number of [myBitCount3 (60 bits)] per second: 2.130M
Number of [myBitCount3 (64 bits)] per second: 1.674M
Number of [myBitCount3 (8 bits)] per second: 4.938M
Number of [myBitCount4 (128 bits)] per second: 0.041M
Number of [myBitCount4 (14 bits)] per second: 5.333M
Number of [myBitCount4 (16 bits)] per second: 4.819M
Number of [myBitCount4 (30 bits)] per second: 2.841M
Number of [myBitCount4 (32 bits)] per second: 2.674M
Number of [myBitCount4 (60 bits)] per second: 1.499M
Number of [myBitCount4 (64 bits)] per second: 0.270M
Number of [myBitCount4 (8 bits)] per second: 7.435M
Number of [myBitCount5 (128 bits)] per second: 0.377M
Number of [myBitCount5 (14 bits)] per second: 3.937M
Number of [myBitCount5 (16 bits)] per second: 3.035M
Number of [myBitCount5 (30 bits)] per second: 2.137M
Number of [myBitCount5 (32 bits)] per second: 2.035M
Number of [myBitCount5 (60 bits)] per second: 1.386M
Number of [myBitCount5 (64 bits)] per second: 1.188M
Number of [myBitCount5 (8 bits)] per second: 4.167M
Number of [myBitCount6 (128 bits)] per second: 0.381M
Number of [myBitCount6 (14 bits)] per second: 5.195M
Number of [myBitCount6 (16 bits)] per second: 3.552M
Number of [myBitCount6 (30 bits)] per second: 2.488M
Number of [myBitCount6 (32 bits)] per second: 2.364M
Number of [myBitCount6 (60 bits)] per second: 1.555M
Number of [myBitCount6 (64 bits)] per second: 1.284M
Number of [myBitCount6 (8 bits)] per second: 5.571M
Number of [myPopCount14bit (14 bits)] per second: 18.349M
Number of [myPopCount14bit (8 bits)] per second: 18.519M
Number of [myPopCount24bit (14 bits)] per second: 7.407M
Number of [myPopCount24bit (16 bits)] per second: 7.463M
Number of [myPopCount24bit (8 bits)] per second: 7.018M
Number of [myPopCount32bit (14 bits)] per second: 4.963M
Number of [myPopCount32bit (16 bits)] per second: 5.013M
Number of [myPopCount32bit (30 bits)] per second: 4.608M
Number of [myPopCount32bit (32 bits)] per second: 4.619M
Number of [myPopCount32bit (8 bits)] per second: 4.608M
Number of [myPopCount64a (14 bits)] per second: 2.778M
Number of [myPopCount64a (16 bits)] per second: 2.793M
Number of [myPopCount64a (30 bits)] per second: 2.751M
Number of [myPopCount64a (32 bits)] per second: 2.703M
Number of [myPopCount64a (60 bits)] per second: 2.809M
Number of [myPopCount64a (64 bits)] per second: 1.385M
Number of [myPopCount64a (8 bits)] per second: 2.755M
Number of [myPopCount64b (14 bits)] per second: 3.063M
Number of [myPopCount64b (16 bits)] per second: 3.096M
Number of [myPopCount64b (30 bits)] per second: 3.106M
Number of [myPopCount64b (32 bits)] per second: 3.053M
Number of [myPopCount64b (60 bits)] per second: 3.008M
Number of [myPopCount64b (64 bits)] per second: 1.444M
Number of [myPopCount64b (8 bits)] per second: 3.091M
Number of [myPopCount64c (14 bits)] per second: 1.625M
Number of [myPopCount64c (16 bits)] per second: 1.600M
Number of [myPopCount64c (30 bits)] per second: 1.542M
Number of [myPopCount64c (32 bits)] per second: 1.529M
Number of [myPopCount64c (60 bits)] per second: 1.566M
Number of [myPopCount64c (64 bits)] per second: 1.082M
Number of [myPopCount64c (8 bits)] per second: 3.945M

Now, since method #myBitCount2 is similar to the #bitCount method in Squeak, that means there is still place for improvement as far as a faster #bitCount is needed.  Now the question is : do we optimize it for the usual usage (SmallInteger), for 64bit integer or we use an algorithm that performs relatively well in most cases?  Obviously, since I will always be working with 64bit positive integers, I have the luxury to pick a method that precisely works best in my specific case!

All test code I have used can be found here.

Note: Rush fans have probably noticed the reference in the title…

Gnochon : le plan (2)

8 février 2017

Alice Kent Stoddard – The Chess Game


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.


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

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


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 : le plan

21 janvier 2017

Romuald Canas Chico, « L’échiquier »

Comme j’en parlais précédemment, je me suis finalement lancé dans la création d’un programme pouvant jouer aux échecs!  Après plus de vingt années passées à lire tout ce qu’il y avait sur le sujet en plus de dévorer chaque numéro de l’ICCA Journal, l’enthousiasme contagieux de quelques confrères développeurs a finalement eu raison de moi.  Par ailleurs, après avoir abandonné les tournois d’échecs il y a longtemps, j’ai depuis peu une nouvelle rage de jouer ou, à tout le moins, de faire quelque chose de relié aux échecs!

Évidemment, ce sera un programme écrit en Smalltalk!  J’utiliserai principalement Pharo tout en faisant en sorte que le programme soit aussi compatible avec Squeak.  En outre, ce sera également l’occasion de tester les performances de la VM Cog 64-bit Spur.

Qui plus est, j’ai décidé de bloguer sur le développement de ce programme en français!  Il faut dire que les articles, blogues, documents et ressources diverses en français sur la programmation d’un jeu d’échecs sont quasi-inexistantes sur le web.  Le seul papier digne de ce nom écrit dans la langue de Molière est celui de Jean-Christophe Weill, Programmes d’Échecs de Championnat: Architecture Logicielle Synthèse de Fonctions d’Évaluations, Parallélisme de Recherche.  Hormis cette thèse de doctorat, même dans le domaine de l’imprimé, les ouvrages sur le sujet sont rarissimes.  En fait, le seul que je connaisse est Échecs et C : Initiation à l’analyse et à la programmation du jeu d’échecs de Yann Takvorian.

Il n’est pas non plus exagéré de dire que les ressources en français sur Smalltalk sont, à peu de choses près, tout aussi rares sur le web.  Ça sera donc l’occasion rêvée de parler des divers outils disponibles dans Pharo, de performance et de développement en Smalltalk! De surcroît, c’est une occasion inespérée de conjuger deux de mes passions et de me forcer à apprendre à utiliser GitHub une fois pour toutes!


Moi-même, au Collège, en train de jouer des blitz à 17 ans

L’autre défi que je me suis donné est de ne pas consulter aucun code source de quelqu’autre programme d’échecs qui soit! Je lis sur le sujet depuis 20 ans alors j’ai une bonne idée d’où je m’en vais!  Mais l’humain étant ce qu’il est, le monde des programmeurs de jeu d’échecs est infesté d’abrutis qui copient intégralement le code source d’autres programmes, le traficotent un tantinet et qui s’approprient ensuite le travail des autres sans le moindre remord.  Le plagiat est malheureusement monnaie courante dans le domaine du chess engine programming.  Il n’est pas rare de voir de parfaits inconnus soudainement arriver avec la version 1.0 de leur programme et obtenir 2900 de cote ELO !  Je préfère avoir la fierté d’avoir tout codé par moi-même…

Mon but n’est pas de surpasser StockFish mais bien d’apprendre, d’expérimenter, de me casser la gueule et aussi de m’amuser en cours de route.  Si j’avais voulu à tout prix compétitionner avec les meilleurs programmes d’échecs, j’aurais choisi le langage C dès le départ et fait comme un bon nombre de « développeurs » en copiant le code d’un autre engin!  De plus, ma vision de ce que devrait être un programme de jeu d’échecs est assez différente de celles des autres.  Ma spécialisation en intelligence artificielle à l’université a fait en sorte que j’ai toujours été déçu des avancements dans le domaine des programmes de jeu d’échecs : la vitesse l’a toujours emporté sur l’intelligence.  J’ai donc l’intention d’éviter l’utilisation des tables de finales autant que possible.  J’espère aussi rendre mon programme un peu similaire à ma façon de jouer et lui insuffler quelques-unes de mes préférences échiquéennes, en commençant par son répertoire d’ouvertures (ésotérique il va sans dire!).


(cliquez pour agrandir)

Je ne suis pas encore tout à fait fixé sur la formule que j’utiliserai pour cette série d’articles mais une chose est claire, j’essaierai autant que possible de vous trouver des références en français où, à tout le moins, de vous fournir des explications en français.  J’envisage actuellement de présenter cette folle aventure sous forme de journal de bord et d’articles techniques qui s’alternent.  Évidemment, vos commentaires et questions seront les bienvenus!