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 in progress (4)

3 octobre 2016

I’m done working on the 8-queens problem.  But while I was at it, I though I’d try something a little bit harder to solve.

30-queens(Click on image to enlarge)

Eight queens is fun. Ten queens is better.  But 30 queens is even better!


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