Algorithme de résolution d'une grille de scrabble

Version imprimable

09/07/2006, 12h10
Muetdhiver

Algorithme de résolution d'une grille de scrabble

Bonjour, je cherche désespéremment un algorithme pour la résolution d'une grille d'un jeu de scrabble duplicate (c'est a dire trouver la meilleur solution pour un coup N avec le tirage T donné étant donné la disposition de la grille - les mots deja placés - à ce coup N). Ce n'est pas un algo pour une formule de jeu à deux joueurs, mais bien pour du duplicate que je cherche.

J'ai deja lu l'article suivant :
The World's Fastest Scrabble Program.
Andrew W. Appel and Guy J. Jacobson,
Comm. ACM 31(5):572-578,585, May 1988.
http://www.nongnu.org/eliot/download/aj.pdf

qui se base sur l'implémantation d'un dictionnaire sous forme de graphe acyclique (DAWG) mais j'aimerais utiliser un algo qui se base sur un dictionnaire dans une base de données, ou tout autre algorithme serait bon à essayer.

Merci d'avance pour votre aide.
Alexandre.
09/07/2006, 12h44
Jedai

A mon avis tu seras plus rapide en passant le dictionnaire sous forme de DAWG puis en utilisant l'algorithme qu'en utilisant directement ton dictionnaire... A ceci plusieurs raisons : cet algorithme avec l'usage du Dawg évite un nombre énorme d'essai, au jour d'aujourd'hui la construction du DAWG est extrèmement rapide (j'avais réussi à faire ça en 1 seconde en OCaml pour un vrai dictionnaire (dans un fichier texte)), et il ne prend quasiment pas de place, de plus on peut le stocker sous forme sérializée pour accélérer encore la procédure.

Sinon je te signale que ton article ne décrit pas le meilleur algorithme à ce jour car Steven Gordon l'a encore amélioré ! Tu trouveras la description de son algorithme là : http://perso.ens-lyon.fr/damien.pous.../gordon_94.pdf .
(par contre là sa structure est un peu plus complexe à construire, j'avais réussi à faire ça en moins de 30 secondes en OCaml je crois (sur une machine peu puissante), mais tu peux le stocker dans un fichier et donc le retrouver instantanément)

--
Jedaï
13/07/2006, 19h23
Muetdhiver

Merci bcp pour ton aide, je vais me pencher la dessus alors avec l'algorithme amélioré de Steven Gordon !

A bientot et encore merci, bye.
Alexandre.
27/07/2006, 13h34
Muetdhiver

Rebonjour.

J'ai etudié un peu l'algorithme de construction d'un Gaddag et me voici confronté a un nouveau probleme. Je me base pour cela sur deux sources : une explication :
http://cedar-solutions.com/JSPWiki/Wiki.jsp?page=GADDAG

Et un code source trouvé sur le net :
http://web.mit.edu/jasonkb/Public/le...makegaddag.cpp

Apres avoir mis en place cet algo : je me retrouve avec un graphe, comme prévu, et cela correspond tout a fait a l'explication du premier lien cité. Si je m'appuis sur l'exemple de GORDON (celui qui a fait l'article pour résoudre une grille de scrabble en 94), je prends un dico composé d'un seul mot : CARE.

Voici ma structure tracée :
http://stalex.free.fr/scrabble/Gadda...ion_Gaddag.jpg

Hors dans ce graphe je ne retrouve aucune correspondance avec l'article de Gordon au niveau du délimiteur (un losange sur le graphe page 222) et le premier hyperlien cité et aussi le code source (qui parlent pourtant d'un GADDAG et pas d'un DAWG !!).

Voici ma question : Dans la structure que j'obtiens (photo au dessus), comment je fais pour trouver la solution D de la figure 2 page 223 :

http://stalex.free.fr/scrabble/Gaddag/Care.jpg

Puisque dans l'article de Gordon, le graphe est organisé de facon a inverser le début du chemin avant le délimiteur. Donc pour <>CARE, si on inverse, on a ERAC<>, ce qui est exposé sur la figure précédente : on part du E pour arriver au C.

Avec la capture d'ecran de ma structure, je ne peux pas parcourir le graphe a l'envers. Le E est un état final ( [4] ) et ne pourra jamais revenir vers le R dans le sens ERAC !

Alors : Le code source trouvé sur le net et l'article http://cedar-solutions.com/JSPWiki/Wiki.jsp?page=GADDAG exposent-ils simplement une méthode de construction de DAWG ?
Ou je me plante dans la construction ?
Il n'y a pas d'histoire de délimiteur qui sert a inverser le début de la chaine (de facon a avoir ERAC) dans le code source que j'ai trouvé : est-ce normal ?

Ou simplement la methode de Gordon' 94 n'est-elle pas faisable (trop lourde ?) et les gens simplifient en n'inversant pas ? Auquel cas l'algo ne correspond plus ?

Est-ce possible d'utiliser l'algo de Gordon avec ma structure (en capture d'écran) epxosée ci-dessus ?

Merci pour votre aide.

A bientot.
Alexandre.
27/07/2006, 14h09
Jedai

Comme j'ai fait la méthode de Gordon, je peux te dire qu'elle est parfaitement faisable (comment pourrait-elle être trop lourde pour les ordinateurs actuels alors qu'elle était justement la plus rapide sur les ordinateurs de 94 !!).
L'article que tu cites a visiblement été écris par un petit rigolo ou plutôt par une personne qui utilise un outil assez faible !! Quand je lis que WordUtils mets dans les 8 minutes à compresser un Trie en un Dawg alors que mon programme pas vraiment optimisé en Ocaml compressait un Trie de taille équivalente en moins de 7 secondes... Je comprends qu'il ait un problème avec les gaddags !!
Un Gaddag construit selon la méthode de Gordon prenant plus de 2 Go ? Laisse moi rire : le mien fait 6 Mo.... et est construit en moins de 30 secondes, toujours en OCaml. Rappelons que l'algo de Gordon était censé construire une structure qui devait tenir intégralement en mémoire vive sur les ordis de l'époque (donc sur 32 Mo ou 64 maximum)...

(ta structure n'est pas un gaddag, mais il suffit de nourrir le constructeur à la main avec les mots du Gaddag pour que ça marche, cependant soit prévenu que ce programme ne compresse absolument pas son Gaddag (en fait il construit un Trie), donc il est très mauvais, d'ailleurs il ne fait même pas l'algorithme décrit par BobGibson)

--
Jedaï
28/07/2006, 09h04
Muetdhiver

Merci beaucoup Jedai pour ton aide précieuse.

J'ai encore quelques petites questions cette fois :

1) Qu'entends-tu par le fait de nourrir le constructeur a la main avec les mots du gaddag ?
J'utilise, comme tu as pu le voir, des noeuds (avec un lien de parenté) sotckés dans un vecteur. Tu parles de quel constructeur ?

2) Tu me dis que l'article a été écrit par un petit rigolo mais alors pourquoi parle-t-il de gaddag si ce n'est qu'un Trie ? Et pourquoi le code source trouvé ailleurs (qui n'a rien a voir) parle lui aussi de gaddag alors qu'il construit un Trie ? !! Ils sont tous de meche ?? !!

3) Tu me dis que mon truc est mauvais parce qu'il n'est pas compressé ? Effectivement BobGibson préconise de regrouper les noeuds identiques pour son Dawg. C'est parce qu'il faut regrouper les noeuds que tu me dis ca ?

Merci, a bientot.

Alexandre.
28/07/2006, 10h08
Jedai

1) Regarde ce fichier pour comprendre ce que je veux dire.

2) Le premier article que tu m'as donné a sans doute été écris par quelqu'un qui a été trahi par son outil : autrement dit son outils (WordUtils) ne lui construisait ni ses DAWG ni ses Gaddag en temps ou mémoire raisonnable... Aussi il a fini par construire à la main ses DAWG (Le Gaddag n'est qu'un DAWG au contenu particulier), choix respectable, mais qui n'a rien à voir avec une soi-disant insuffisance de l'algorithme ou de la structure de donnée proposée par Gordon.

Quant au code, il ne compresse rien (lis-le et tu t'apercevras que seuls les préfixes sont partagés, donc c'est un Trie, et pas un Dawg, de surcroit pas un Gaddag), en fait il s'agit sûrement d'une tentative d'implémentation mais le programmeur a dû s'arrêter avant d'implémenter la compression.

3) Un Dawg par définition est un graphe acyclique de mots, où les préfixes aussi bien que les suffixes sont partagés maximalement, dans le cas d'un Trie seuls les préfixes sont partagés, la compression est donc bien moindre. Dans le cas d'un Gaddag, la quantité de mots est telle qu'il est pratiquement obligatoire de compresser, donc d'utiliser un DAWG plutôt qu'un Trie. Le code que tu as trouvé ne construit que des Trie, dans makegaddag.cpp aussi bien que dans makedawg.cpp ...

--
Jedaï
28/07/2006, 13h11
Muetdhiver

1) Ohhhh !! Effectivement ! J'ai fait mon boulet ! J'avais completement zappé ce fichier, croyant qu'il s'appelait gaddagsize, d'ou un algo de calcul de la taille d'un gaddag, ce dont je me foutais eperdument ! (j'me suis dit que le mec devais avoir ses raisons !!). Merci merci !

2) et 3) Ok : donc ma mission : compresser les suffixes ?
Eclaire-moi : la figure 1 page 222 de Gordon est "un sous graphe d'un GADDAG non minimisé" : Il ne s'agit pas d'un Trie ?
Moi je dirais que si, si je le compare avec la figure 1 de Jacobson.

La figure 5 est un sous-graphe semi minimisé : C'est le GADDAG que tu as implémenté toi ?
Et la vraie question ! : est-ce que dans une de ses figures Gordon arrive a un moment ou a un autre a un Gaddag ? Parceque j'ai bien l'impression qu'il n'expose que des Trie..... dans un premier temps des Trie non compressés, puis des Trie compressés par le suffixe ensuite... le tout bien sur avec la notion du delimiteur (Trie avec delimiteur, comparé au Trie sans delimiteur et inversion de Jacobson). En gros si j'implemente la figure 5 de Gordon je vais dans le mur puisque j'ai un Trie et pas un graphe ?

Dans l'acceptation de l'article de Gordon, ma structure dont nous parlons tant, et sans prendre en compte le "gaddagize", ressemble a la figure 1 de Gordon ?

Merci d'avance pour tes eclaircissements.
Bye.
28/07/2006, 14h00
Jedai

Citation:

Envoyé par Muetdhiver

2) et 3) Ok : donc ma mission : compresser les suffixes ?
Eclaire-moi : la figure 1 page 222 de Gordon est "un sous graphe d'un GADDAG non minimisé" : Il ne s'agit pas d'un Trie ?
Moi je dirais que si, si je le compare avec la figure 1 de Jacobson.

Avant de s'attaquer à un sujet, peut-être serait-il utile de connaître un minimum les définitions des structures de données employées, surtout lorsqu'elles sont aussi courantes que les Trie.... Oui, la figure 1 est un Trie.

Citation:

Envoyé par Muetdhiver

La figure 5 est un sous-graphe semi minimisé : C'est le GADDAG que tu as implémenté toi ?

La figure 5 est une phase intermédiaire de la construction du Gaddag : grâce à l'algorithme qu'il expose par la suite Gordon peut compresser partiellement son Gaddag au fur et à mesure de la construction, mais il n'est pas complètement compressé (tous les suffixes identiques ne sont pas réunis), il faut encore lui appliquer la compression type "Trie vers Dawg", encore une fois il est très important que tu comprennes ce qu'est un Trie et comment on passe à un Dawg avant d'essayer de faire ton algorithme.
La compression partielle lors de la construction du Gaddag accélère grandement la phase de compression finale, c'est pourquoi je te conseille de ne pas utiliser une approche type gaddagize.cpp (qui construit un Trie au lieu de la forme semi-minimisée préconisée par Gordon), car la durée de la compression sera alors trop longue.

Citation:

Envoyé par Muetdhiver

Et la vraie question ! : est-ce que dans une de ses figures Gordon arrive a un moment ou a un autre a un Gaddag ? Parceque j'ai bien l'impression qu'il n'expose que des Trie..... dans un premier temps des Trie non compressés, puis des Trie compressés par le suffixe ensuite... le tout bien sur avec la notion du delimiteur (Trie avec delimiteur, comparé au Trie sans delimiteur et inversion de Jacobson).

Les Trie compressés par le suffixe sont des Dawg et pas des Trie (les Trie sont des ARBRES, donc ne peuvent pas ressembler aux figures suivantes de Gordon). Le GADDAG n'est autre qu'un DAWG dans lequel on stocke aussi les formes "début inversé-délimiteur-fin", il ne s'agit pas d'une structure de donnée particulière. D'une certaine façon la figure 1 est déjà un Gaddag, mais non compressé.

Citation:

Envoyé par Muetdhiver

En gros si j'implemente la figure 5 de Gordon je vais dans le mur puisque j'ai un Trie et pas un graphe ?

Et d'une les Trie sont des graphes, mais ils sont plus précisément des arbres (qui sont une catégorie de graphe : les graphes connexes non-orientés sans cycle). Et de deux, je n'ai personnellement jamais vu d'arbres dont les branches se rejoignaient après s'être séparés... Donc la figure 5 de Gordon n'est pas un arbre, donc pas un Trie, il s'agit d'un graphe connexe orienté sans cycle (DAG : Directed Acyclic Graph, tu notes que le "orienté" fait toute la différence avec les arbres puisque s'il n'était pas orienté ce graphe aurait des cycles).

Citation:

Envoyé par Muetdhiver

Dans l'acceptation de l'article de Gordon, ma structure dont nous parlons tant, et sans prendre en compte le "gaddagize", ressemble a la figure 1 de Gordon ?

Tout à fait, c'est un Trie absolument non-compressé.

--
Jedaï
28/07/2006, 19h20
Muetdhiver

Citation:

Avant de s'attaquer à un sujet, peut-être serait-il utile de connaître un minimum les définitions des structures de données employées, surtout lorsqu'elles sont aussi courantes que les Trie.... Oui, la figure 1 est un Trie.

Merci pour toute ton aide. Effectivement je ne savais meme pas que le "Trie" existait il y a deux jours... Je sais, j'ai des lacunes alors..... ;) Faut dire que c'est pas ma branche, pour rester dans les Tries....

Bon, merci pour ta patience, ton aide, ta gentillesse. Je crois qu'avec toutes tes billes je ne peux plus dénicher grand chose pour t'embeter.... ! A moi de voir maintenant... ;)

A plus et bonne continuation.
Bye.
Alexandre.