Développement et environnements multi-langages

La présentation d’un projet plus qu’ambitieux (développé avec Squeak Smalltalk) avec en prime tous les détails!

Gnochon : c’est parti!

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 sur Pharo 5.0

2-Le premier adversaire

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. Les blancs jouent et matent en 13 coups!

1001001 SOS

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…

Bits and Pieces

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, primDigitBitXor,  primDigitBitShiftMagnitude 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

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!

Freewill in progress (5)

Not much new code was done since the last update.  But since I usually like to put my projects aside for a while just to have those « WTF-was-I-thinking » moments looking back at my own code, I took some time to scribble a skeleton of a FAQ and design a logo.

So coding of Freewill restarts today… with a fresh look at my code!

Save

Gnochon

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!

(click on image to enlarge)

Save

What’s new?

What’s new?

After a major data loss (I haven’t given up on getting back all my data, mostly code repositories and databases!), I had to start all my pet projects from scratch. Luckily, it’s easier second time around as they say! And, lucky me, I store all my personal stuff on the web! So here’s a list of what’s coming up on this blog.

Ruzzle

Even though I had a decent working version of the genetic algorithm program to find the best ruzzle grid (original posts in French here, here and here), I wasn’t satisfied with the code.  It slowly evolved from a bunch of code snippets into something I could somehow call a genetic algorithm.  Problem was that my solution was tailored for this specific problem only!  Since I lost all the Smalltalk code, I redid the whole thing from scratch : better design, simpler API, more flexible framework.  I can currently solve a TSP problem, the best ruzzle grid search and a diophantine equation.

I also plan to provide examples of the 8 queens problem, the knapsack problem, a quadratic equation problem, a resource-constrained problem and a simple bit-based example with the GA framework.  Besides, the are now more selection operators, more crossover operators, more termination detectors (as well as support for sets of termination criteria!), cleaner code and the list goes on!  So I’ll soon publish a GA framework for Pharo.

As most of you know, the Rush fan in me had to pick a project name in some way related to my favorite band!  So the framework will be called Freewill, for the lyrics in the song :

Each of us
A cell of awareness
Imperfect and incomplete
Genetic blends
With uncertain ends
On a fortune hunt that’s far too fleet

Bingo

A stupid quest I’ll address after the first version of my GA framework is published.  It all started with a simple question related to the game of bingo (don’t ask!) : can we estimate the number of bingo cards sold in an event based on how many numbers it takes for each card configuration to have a winner?  So it’s just a matter of generating millions of draws and cards à la Monte Carlo and averaging how many numbers it takes for every configuration.  Why am I doing that?  Just because I’m curious!

Glorp

There’s been a lot of action on the Pharo side and Glorp.  I plan on having a serious look at the latest Glorp/Pharo combo and even participate to the development!

Sudoku

I’ll translate my articles (in French here, here and here) on the SQL sudoku solver in English and test the whole thing on the latest MySQL server.  Besides, db4free has upgraded to a new MySQL server version!

NeoCSV

I had done a port of NeoCSV to Dolphin right before losing all my code data.  Wasn’t hard to port so I’ll redo it as soon as I reinstall Dolphin!

Smalltalk

It’s time to reinstall VisualAge, VisualWorks, Squeak, ObjectStudio and Dolphin and see what’s new in each environment!  From what I saw, there’s a lot of new and interesting stuff on the web side.  Add to that the fact that most social media platforms have had significant changes in their respective APIs recently, so there’s a lot to learn there!

 

That’s a wrap folks!

GitHub

Git

Le temps aura finalement eu raison de moi!

Il y a longtemps, j’avais abandonné avec peine CVS (avec WinCVS) pour passer à SVN (avec TortoiseSVN).  Après des années de loyaux services, il semble bien que comme toute la planète utilise Git et plus particulièrement GitHub, je n’avais d’autre choix que de me convertir!

De plus, comme tout le développement de Squeak, Pharo et Dolphin (ainsi que plusieurs contributions/projets pour ces divers environnements) est maintenant sur GitHub, avais-je le choix?

La première chose qui saute aux yeux pour un développeur Smalltalk, c’est la facilité avec laquelle il est facile de gérer les artefacts d’un projet.  Alors qu’il est souvent impossible de gérer le code Smalltalk en même temps que toutes les ressources « extérieures » d’un projet (scripts SQL, icônes, images, fichiers de configuration, etc) dans les outils de contrôle de version intégrés aux divers environnement Smalltalk, rien n’est plus facile avec GitHub!

En plus, GitHub ce n’est pas que pour gérer du code!  Que ce soit pour de la documentation ou l’écriture d’un roman, aucune différence!

Pour un excellent tutoriel sur Git, je recommande fortement celui de TutorialsPoint (en anglais) ou celui de ProGit en français. Après vos premiers pas, cette cheat sheet vous sera utile.

Pendant que j’y pense, je suis ici!

WinMerge

Tandis qu’on parle de gérer le changements, je ne peux me séparer du logiciel de comparaison de fichiers WinMerge. Si vous avez souvent à comparer différentes versions de fichiers, c’est de loin l’outil qu’il vous faut!

 

 

Logique floue

FuzzySqueak, un sympathique outil de logique floue.