Re: [Eliot-dev] aide generation des coups possibles au scrabble

[eliot-dev]

Bonjour,

2008/7/18  <address@hidden>:
> j'ai lu le document de Appel et Jacobson ,mais la langue de shakespeare ne
> m'inspire pas trop sur ce coup.

J'ai bien peur que ce document ne reste la référence. Il décrit en
détail l'algorithme utilisé, illustré avec du pseudo-code. Si vous
avez du mal avec l'anglais, vous pourriez tenter une traduction
automatique via un site en ligne.

> ce que je souhaite de votre part , c'est de m'instruire sur, par où
> commencer et comment proceder  avec une (petite) explication de l'algorithme
> en pseudo-code de recherche des coups possibles avec le pion blanc(si
> possible en code, mais pas obligatoire, je pourrai coder moi-meme). J'ai lu
> les sources de Eiot toute la semaine mais je ne m'en suis pas sortis tout
> seul.

Expliquer tout l'algorithme serait un peu trop long, mais de façon
très schématique, l'idée est d'identifier les cases "pivots" (case
touchant une lettre déjà posée). Pour chaque case pivot, on essaie à
partir du tirage de faire tous les débuts de mots possibles se
terminant sur cette case, en se limitant aux mots qui ne débordent pas
sur la case pivot précédente (cela donne une limite vers la gauche).
C'est le rôle de la fonction LeftPart décrite dans le document d'Appel
& Jacobson. Puis pour chacun de ces préfixes, on essaie de compléter
vers la droite en un mot valide (ce qui est facile grâce à la
structure du DAWG). C'est la fonction ExtendRight du document. Pour
s'assurer que les éventuels mots formés dans l'autre sens sont
valides, les lettres autorisées sur chacune des cases sont
pré-calculées avant même de démarrer la recherche (vu que ça ne dépend
pas du tirage).
Cette explication sommaire suppose que le mot à placer est horizontal,
mais par symétrie les mots verticaux fonctionnent de la même manière.

Dans les sources d'Eliot, l'essentiel de la recherche se trouve dans
game/board_search.cpp.
Les fonctions LeftPart et ExtendRight correspondent à celles décrites
dans le document.

A noter, la méthode LeftPart est le gros point faible de l'algorithme
d'Appel et Jacobson, car la structure du DAWG ne s'y prête pas très
bien. Une amélioration (pas encore implémentée dans Eliot) consiste à
utiliser une autre structure de dictionnaire (le GADDAG), décrite en
détail dans un document écrit pas Gordon (désolé, je n'ai pas de lien
sous la main).

> Merci d'avance pour votre aide et pour votre comprehension.

Bon courage,
-- 
Olivier