Ruzzle : mise à jour (2)

7 décembre 2016

ruzzle-7-dec-2016

Ce soir, dans le cadre du petit défi (tous mes articles concernant le Ruzzle sont ici) que j’avais relevé il y a de ça belle lurette, j’ai dépassé le cap des 630 millions de grilles générées à l’aide de mon algorithme génétique Freewill sans avoir encore pu dépasser la marque de la meilleure grille de ruzzle (comportant 1634 mots) établie par Didier Müller.  J’ai trouvé plusieurs fois des transpositions des 2 meilleures grilles que lui-même avait trouvé mais je n’ai jamais pu faire mieux!

La recherche de cette meilleure grille va tout de même se poursuivre jusqu’à ce que j’aie terminé la première version de Freewill mais à moindre vitesse!  Il est temps que je me réapproprie quelques CPUs de mon ordinateur!


Freewill and Ruzzle

8 août 2016

Muller Record

(Click to enlarge)

Freewill already shows very good results!

My heart just stopped when I read the last results on the Transcript!  I had done it!  1634, my goal, had been achieved [1]!  I had broken Didier Müller’ record!  The maximum number of French words a ruzzle grid could contain was 1634!

The joy didn’t last long! I quickly realized that I had only equaled Müller’s record (see his results here), finding just another transposition of the 2 grids he had found.

But it’s promising!  The same iteration also found a grid with 1625 words in it, which is still better than Müller’s second best!  I’m currently setting up parallel workers to run 5 genetic algorithms at the same time. And this time, I’ll be looking for grids with more than 1634 words!

I want to break that record!

[1] Note: for those who are wondering what I am talking about, I explain that ruzzle quest here (in French).

Save

Save

Save

Save


Ruzzle : mise à jour

6 avril 2015

Je suis à peaufiner la 2ième partie (de 7) de la série débutée dans cet article.  Je devrais publier ce billet sur les méthodes de création durant la semaine.

Entre-temps, j’ai une version fonctionnelle de mon algorithme génétique : il ne me reste que 3 méthodes de sélection et 3 méthodes d’immigration à coder et à tester.  Ensuite, j’optimiserai certaines parties plutôt lentes du code! Pour l’intant, ça a l’air de ceci (cliquez sur l’image pour agrandir)…

Ruzzle dev


Ruzzle et algorithmes génétiques (1/7)

18 décembre 2014

ruzzle_board

J’ai toujours été fasciné par les jeux et les divertissements de lettres, que ce soit le Scrabble, le Boggle, les mots croisés et, plus récemment, le Ruzzle.

Si on exclut les cases lettre et mot compte double et triple, les règles du Ruzzle sont simples (extrait de Wikipedia) :

Il faut former le plus de mots possibles avec les seize lettres disponibles dans une grille de quatre par quatre. Les mots doivent être au moins de deux lettres, et trouvés en utilisant des lettres adjacentes les unes aux autres sans réutiliser deux fois la même case de la grille. Les formes conjuguées des verbes sont acceptées.

Je ne connaissais pas le Ruzzle avant de tomber sur cet article particulièrement intéressant, Ruzzle : à la recherche de la plus belle grille.  L’auteur, Didier Müller, y décrit les diverses méthodes (et ses résultats) ainsi que les programmes écrits en Python qu’il a employés afin de rechercher la grille comportant le maximum de mots.  Ça a piqué ma curiosité, en particulier les tentatives d’optimiser les grilles produites à l’aide d’un algorithme génétique.

J’ai donc décidé de tenter la même expérience : trouver la grille avec le plus de mots possible en utilisant un algorithme génétique.  J’opterai surtout pour la flexibilité au détriment de la performance pour essayer d’étudier une panoplie d’hypothèses et de tester certaines de mes idées.  Évidemment, j’ai comme objectif de battre le record de monsieur Müller !  Je vise, au moins, 1635 mots!

Pour me suivre dans cette longue aventure, vous aurez donc besoin de connaissances en programmation (j’utiliserai Pharo, un environnement de développement Smalltalk), de quelques connaissances en SQL (j’utiliserai probablement MySQL pour sauvegarder les résultats) et de peut-être quelques connaissances en R (pour les graphiques et l’analyse statistique).  Évidemment, je rendrai publics les scipts SQL et R, les chiffriers, le code Smalltalk ainsi que tous les fichiers utilisés à la fin de cette série de chroniques.

Le présent texte sert donc de présentation aux expériences d’optimisation que je décrirai dans les 6 prochains articles.

Voici donc, en vrac, quelques-unes des idées que je testerai :

Article 2 : Stratégies de création d’individus

a) Aléatoire : toutes les lettres ont la même probabilité d’être choisies lors de la création de la grille
b) Muller : utiliser la fréquence des lettres établie par Müller
c) St-Jean : utiliser la fréquence des lettres établie par moi-même (vous verrai en quoi je diffère de Müller)
d) Wikipédia : utiliser la fréquence des lettres décrite sur Wikipédia
e) Anglais : utiliser la fréquence des lettres en anglais
f) Digramme : utiliser la fréquence des digrammes du dictionnaire pour créer la grille
g) Trigramme : utiliser la fréquence des trigrammes du dictionnaire pour créer la grille
h) Quadrigramme : utiliser la fréquence des quadrigrammes du dictionnaire pour créer la grille
i) Voyelles et consonnes : utiliser la fréquence relative entre les consonnes et les voyelles en français
j) Mots de 16 lettres : utiliser des mots de 16 lettres pour créer les grilles
k) St-Jean inversé : utiliser l’inverse de la fréquence de c (les lettres les plus moches deviennent les plus probables)

Article 3 : Stratégies de croisement (crossover)

a) croisement multi-points 50-50
b) croisement multi-points à longueur variable
c) croisement multi-points à longueur fixe
d) croisement simple 50-50 à locus fixe
e) croisement simple 50-50 à locus variable
f) croisement simple à longueur variable
g) croisement simple à longueur fixe

Article 4 : Stratégies de mutation

a) Mutation aléatoire
b) Mutation de la lettre avec la plus petite fréquence de la grille
c) Mutation de la lettre avec la plus petite fréquence au centre de la grille
d) Mutation de la lettre avec la plus petite fréquence sur les bords de la grille
e) Mutation de la lettre la plus grande fréquence de la grille
f) Mutation de la lettre avec le plus d’occurences de la grille

Article 5 : Stratégies de sélection, de survie, d’immigration et d’épidémie

a) Sélection aléatoire pure
b) Sélection aléatoire basée sur la force (fitness) des individus
c) Sélection élitiste (seuls les n% meilleurs individus se reproduisent entre eux)
d) Sélection adaptative (les individus plus forts se reproduisent avec les plus faibles)
e) Survie des meilleurs individus (pour n générations au maximum)
f) Intégration de nouveaux individus « immigrants » dans la population
g) Épidémie : chaque individu avec un gène spécifique aléatoire est éliminé de la population

Article 6 : Paramètres de la population et de la simulation

a) Pourcentage de mutation fixe
b) Pourcentage de mutation variable
c) Taille de la population fixe
d) Taille de la population variable
d) Pourcentage de croisement fixe
f) Pourcentage de croisement variable
g) Pourcentage de survie fixe
h) Pourcentage de survie variable
i) Pourcentage d’immigration fixe
j) Pourcentage d’immigration variable

Article 7 : Conclusions, résultats et autres recherches

Si jamais il y avait un intérêt pour cette série d’article, je me propose de publier un document PDF détaillé que je pourrai (là encore, seulement s’il y a un intérêt!) aussi traduire en anglais.


Maman rage ou anagramme ?

24 novembre 2019

Un article intéressant sur le blogue de John D. Cook concernant la fréquence des anagrammes en anglais.  J’étais donc curieux faire le même exercice et de comparer avec les mots de la langue française!

Pour ce faire, vous aurez besoin du fichier texte de l’ODS 3 (Officiel du scrabble 3) disponible ici ainsi que de quelques requêtes SQL!

En premier lieu, créer une table pour importer tous les mots du dictionnaire.  Pourquoi je n’ai pas spécifié de clé primaire?  Parce que comme les accents ont été éliminés du dictionnaire (on se rappelle qu’il s’agit d’un dictionnaire de Scrabble, ce qui fait du sens!) alors il y aura des doublons lors de l’importation!

CREATE TABLE dictionnaire (
	mot VARCHAR(25) NOT NULL
)
COLLATE='utf8_general_ci'
ENGINE=InnoDB;

Maintenant, charger le fichier dans la table dictionnaire! Évidemment, vous modifierez la commande pour refléter l’emplacement du fichier sur votre ordi!

LOAD DATA LOW_PRIORITY LOCAL 
INFILE 'C:\\Data\\Tests\\dico_ruzzle.txt' 
INTO TABLE sandbox.dictionnaire 
FIELDS OPTIONALLY ENCLOSED BY '"' 
LINES TERMINATED BY '\r\n' (mot); 

Afin d’éliminer les doublons, nous allons créer un autre table avec une colonne supplémentaire, signature, qui est en fait une chaîne de caractère triée par valeur ASCII qui nous servira de signature (comme John D. Cook l’appelle).

CREATE TABLE anagrammes (
	mot VARCHAR(25) NOT NULL,
	signature VARCHAR(25) NULL DEFAULT NULL
)
COLLATE='utf8_general_ci'
ENGINE=InnoDB
ROW_FORMAT=DYNAMIC; 

Maintenant, ne reste qu’à insérer les mots uniques dans cette nouvelle table.

INSERT INTO anagrammes(mot, signature)
SELECT DISTINCT(mot), NULL
FROM dictionnaire; 

Pour calculer la signature, nous aurons besoin de cette fonction qui trie les lettres de chaque mot en ordre de valeur ASCII de chaque caractère. Cette procédure stockée est aussi disponible sur mon GitHub ici.

SET @OLD_SQL_MODE=@@SQL_MODE, SQL_MODE='STRICT_TRANS_TABLES';

DROP FUNCTION IF EXISTS ascii_sort;

DELIMITER //

CREATE FUNCTION ascii_sort (stringParam VARCHAR(255))
RETURNS VARCHAR(255)
DETERMINISTIC
NO SQL
SQL SECURITY DEFINER
COMMENT 'Sorts a string based on the ASCII value of each character (v1.00)'

/*****************************************************************************
*
* DESCRIPTION: Sorts the string <stringParam> based on the ASCII value of each character (v1.00)
*
* AUTHOR: Benoît St-Jean <bstjean@yahoo.com>
* URL: http://www.endormitoire.wordpress.com
* VERSION: 1.00
*
* USAGE: SELECT ascii_sort('hsizbap');
* RESULT: 'abhipsz'
*
* PARAMETERS: stringParam string that needs to be ascii sorted
*
* RETURN: VARCHAR(255)
*
* NOTES: https://en.wikipedia.org/wiki/Selection_sort
*
******************************************************************************/

BEGIN
DECLARE newString VARCHAR(255);
DECLARE n TINYINT UNSIGNED;
DECLARE i TINYINT UNSIGNED;
DECLARE j TINYINT UNSIGNED;
DECLARE min_idx TINYINT UNSIGNED;
DECLARE str_j CHAR(1);
DECLARE str_i CHAR(1);
DECLARE str_min_idx CHAR(1);
DECLARE temp CHAR(1);

SET newString = stringParam;
SET n = CHAR_LENGTH(stringParam);

SET i = 1;

WHILE i < n DO
SET min_idx = i;
SET j = i + 1;

/* Find the minimum element in the unsorted part of the string */
WHILE j <= n DO
SET str_j = MID(newString, j, 1);
SET str_min_idx = MID(newString, min_idx, 1);

IF ASCII(str_j) < ASCII(str_min_idx) THEN
SET min_idx = j;
END IF;

SET j = j + 1;
END WHILE;

/* Swap the element found with the first one in the unsorted remaining part of the string */
SET str_i = MID(newString, i, 1);
SET temp = MID(newString, min_idx, 1);

SET newString = INSERT(newString, min_idx, 1, str_i);
SET newString = INSERT(newString, i, 1, temp);


SET i = i + 1;
END WHILE;

RETURN newString;
END
//

DELIMITER ;

SET SQL_MODE=@OLD_SQL_MODE;

Maintenant, calculons la signature de chacun des mots!

 
UPDATE anagrammes
SET signature = ascii_sort(mot);

Règle de base : CHAQUE table devrait TOUJOURS avoir une clé primaire! Ne serait-ce que pour vérifier qu’il n’existe plus aucun doublon dans notre cas!

ALTER TABLE anagrammes
ADD PRIMARY KEY (mot); 

Comme on s’intéresse à la signature pour trouver les anagrammes, un index est nécessaire sur cette colonne!

 
CREATE INDEX signature_idx
ON anagrammes(signature); 

Nous y voici! Déterminons les classes de mots : ceux qui ont une signature unique (frequence = 1), ceux qui ont une anagramme (fréquence = 2), ceux qui ont 2 anagrammes (fréquence =3) et ainsi de suite…

 
SELECT t.frequence, COUNT(*) as total
FROM (
SELECT COUNT(*) as frequence
FROM anagrammes
GROUP BY signature) as t
GROUP BY t.frequence
ORDER BY t.frequence;

Quel est la signature (l’anagramme) la plus fréquente?

 
SELECT *
FROM (
SELECT COUNT(*) as frequence, signature
FROM anagrammes
GROUP BY signature) as t
WHERE frequence = 16;

Quels sont les mots qui ont en commun cette signature et qui sont des anagrammes?

 
SELECT *
FROM anagrammes
WHERE signature = 'aeinrst';

P.S. Vous l’aurez sans doute deviné, « maman rage » est une anagramme pour le mot « anagramme » lui-même!


Freewill in progress (3)

2 octobre 2016

freewill_oct_2

(Click on image to enlarge)

What’s new?

After a break from Freewill (I like to put projects aside for a while, it gives me another perspective on my own code!), I just came back to it yesterday.  I had a few WTF moments (it’s usually a good indication that your code is not clear!), renamed some methods with imprecise names, cleaned up some of Ruzzle’s crumbs that were sprinkled everywhere, refactored code here and there, looked at what Code Critics came up with and corrected some of the issues, ran a few tests and finally got fed up by performance issues.

I got rid of the SharedRandom number generator that was previously used in Freewill.  This resulted in a huge speedup! From what I measured, the Random class is 2.1 times faster than the SharedRandom one! This change alone brought a performance boost of 31-48% !  I also cached the cumulative weights for the Roulette Wheel selection policy which gave me a 14% speedup!  There are still a few things I want to optimize here and there and my estimates tell me I could get another 15-45% speedup.

What’s next?

I’ll start adding tests to cover all policies (creation, selection, crossover, mutation, termination) to make sure the next changes don’t break anything.  This will also give me reproduceable tests against which I’ll get more precise statistics to measure performance.  I will also start working on another example, most likely the 8 queens problem.

To Do List Until Next Update

  • 8 queens problem
  • Policies Tests
  • Speed up Roulette Wheel selection
  • Start to add class/method comments
  • Code 2-3 more termination policies
  • Think about Freewill’ community (Google group?  Mailing List? Repository? etc.)

Freewill in progress (2)

3 août 2016

Freewill Selection Policies(Click to enlarge)

What’s up?

As you can see, Freewill now supports 17 different selection policies.  At this point, all of them are coded but only half of them have been tested.

The 11 available termination policies are coded, half of them tested.

So far, only 2 mutation policies are available.  Both of them are coded and tested. I will probably need a few extras for TSP type of problems as well as numerically parametrized problems (e.g. De Jong functions with a domain for each variable).  I’ll probably add 3-4 other ones specific to the problem that started all this adventure!

Only one immigration policy (no immigration!) is available and it will stay that way for a long time.  I’ll wait until I am hyper confident that this framework is rock solid before introducing parallelism and exchange of individuals between « islands » (i.e. simulations).  This one is a faaaaaaar away!

Six crossover policies are available as of now .  This area will require some (minor I think at first glance) changes for the TSP type of problems : not quite decided on the approach I will take to solve this.  Since crossover is often very problem/chromosome specific, I’ll probably delay those change until the end, once I have all examples coded and ready to be tested to have a better idea of what is needed.  But I will definitely add a few (3-4) crossover policies tailored for the Ruzzle problem.

I have solved the discrepancy (see here and here) between my results and the TSPLIB ones regarding the tour length of the Burma14 problem.  Will probably add a lot bigger TSP problem to see how the framework can handle an extremely huge search space! Oh!  And I need to clean up all the crap I added/modified while looking for the problem of « distance difference » : 2 classes were butchered in the process!

I need to add a few « crash test dummy » classes to test all those different selection policies (and crossover) in a simpler and more efficient manner!  Or I should kick myself in the %*&#$!@ and code the « bits » example classes…

I will soon work on a customizable display of statistics.  All that’s needed is already there, it’s just a matter of gluing everything together!

Once I’m done with the 8 queens problems, I’ll attack the numerically parametrized problems.  Will probably have 2-3 examples (from De Jong functions) as well as the INSANE Griewank function.

The classes used for randomly choosing the next parent chromosomes as well as scaling/ranking can be optimized.  But since they just work great since day 1, I’ll keep that for the very end.  But I know they can be a lot faster than what they are right now.

I also plan on having a very basic export mechanism so I can dump all those ruzzle chromosomes in a MySQL database to be able to do some reporting and study the various policies and their effects.

I started adding comments to the classes, mostly to keep references, maintain a todo list per class and add some notes for myself to quickly remember why things work that way!

I’ll probably have an image by tomorrow that will run simulations for the ruzzle problem full-time. I wanna beat that record!

 

Save

Save

Save

Save


Freewill in action

19 juillet 2016

The very first image of Freewill (see here for details) in action, trying to solve a ruzzle problem as well as a TSP problem (Burma14) and a simple diophantine equation (Hermawanto)! Click on picture to enlarge!

First look at Freewill in action


What’s new?

19 juillet 2016

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!


Ça avance et ça arrive!

15 mars 2016

Ruzzle

J’ai recommencé à travailler sérieusement sur mon projet de Ruzzle après l’avoir laissé de côté pendant une très longue période…

Ça avance!

P.S. Oui, c’est bien Christina Hendricks en background