Re: [Eliot-general] Algorithme Scrabble

[Olivier Teuliere]

Bonjour,

2010/12/29 Hibernatus <address@hidden>:
> Bonjour,
>
> Je cherche à entrer en contact avec l'un des auteurs de Eliot, car j'ai vu
> qu'ils étaient français, et j'ai moi-même écrit un petit programme servant à
> trouver les meilleurs coups.
> J'ai fait ça suite à un défi lancé par un collègue, en 2 jours, en C++ sous
> forme de DLL pour une application WinDev (framework pour Windows).
>
> Évidemment, je m'attendais à ce que d'autres l'aient fait avant moi, et je
> vous félicite d'ailleurs pour votre programme qui est si complet (le mien
> n'est qu'une expérience).
> J'aurais aimé discuter de l'algorithme de recherche des coups possibles, et
> voir si je n'ai pas oublié des cas tordus.
> Ce qui m'intrigue notamment c'est que vous faites référence à des white
> papers, alors que pour ma part je me suis contenté de suivre mon intuition
> en développant un simple arbre lexicographique (légèrement optimisé pour un
> petit alphabet, car je n'ai que 26 lettres) et les résultats me semblent
> satisfaisants :
> En lui donnant un tirage de 7 jokers et en plaçant quelques lettres sur le
> plateau, il me génère une liste d'un million de coups possibles en moins
> d'une seconde, réellement stockée avec les mots et les points de chaque
> coup. Des cas plus réalistes prennent quant à eux de 50µs à 20ms, avec de
> quelques dizaines à quelques milliers de coups générés.

Une recherche d'une seconde avec 7 jokers est une bonne performance,
surtout pour un programme codé en 2 jours :-)

Je pense que la même recherche serait beaucoup plus lente avec Eliot,
non pas parce que l'algorithme utilisé est mauvais (du moins je
l'espère :-)), mais parce qu'il fait plus de choses qu'un simple
stockage des mots. En particulier, le tri des résultats est
relativement coûteux, ainsi que la conversion des chaînes de
caractères internes en QString, utilisées pour l'affichage (c'est
d'ailleurs pour cela que l'affichage des résultats est limité à 1000
lignes).

Il est possible aussi que certaines parties du code puissent être
encore optimisées (je pense notamment à la classe Tile). Jusqu'à
présent le besoin ne s'en est pas vraiment fait sentir. mais si
j'implémente un jour des notions de tactique dans le mode "partie
libre", un coup de l'ordinateur pourra nécessiter des dizaines, voire
des centaines, de sous-recherches, et les optimisations prendront
alors tout leur sens...

Effectivement, l'algorithme utilisé par Eliot est celui décrit dans
l'article de Appel et Jacobson [1] (avec une petite optimisation
supplémentaire). Il est assez simple à comprendre, car relativement
intuitif, et vous avez probablement utilisé sans le savoir un
algorithme très similaire. L'algorithme d'Appel et Jacobson se base
aussi sur un dictionnaire arborescent [2], et contient quelques
astuces intéressantes (l'utilisation de "cross-checks", en
particulier), mais il est encore améliorable en termes de
performances, à l'aide d'un format de dictionnaire plus élaboré [3].
Ce dernier algorithme est environ 2 fois plus rapide, pour un
dictionnaire environ 5 fois plus gros. Il n'est pas (encore)
implémenté dans Eliot, et si cela vous intéresse je peux vous aider à
rentrer dans le code. Vous pouvez considérer cela comme un défi ;-)

Je suis aussi disponible pour discuter des détails d'implémentation
des différents algorithmes, que ce soit sur la mailing-list (en copie
de ce mail) ou en privé.

> Je pense qu'on peut facilement exploiter le multicore sur un tel algorithme,
> ne serait-ce qu'en distribuant les points de départ des recherches, ou en
> séparant horizontal et vertical. Avec OpenMP ça prendrait très peu ce lignes
> de code, et conserverait la portabilité.

Effectivement, ça devrait se paralléliser très bien.
En ce qui concerne Eliot, ce n'est pas dans mes priorités, car je n'ai
pas de multicore à disposition pour tester. Mais, encore une fois,
toute aide est la bienvenue, si vous voulez essayer ça :-)

> Je n'ai pas eu le temps de regarder votre code, je suis au travail quand je
> fais tout ça, mais je n'y manquerais pas, et je vous remercie pour votre
> excellent programme open source.

Merci à vous pour ce retour.

Cordialement,
-- 
Olivier
[1] http://www.nongnu.org/eliot/download/aj.pdf
[2] http://www.wutka.com/dawg.html
[3] http://www.ericsink.com/downloads/faster-scrabble-gordon.pdf