Trouver les meilleures solutions au Scrabble peut sembler être un problème extrêmement complexe. Et en réalité… ça l’est. Pourtant, lorsqu’on décompose le problème en éléments simples, le fonctionnement général devient beaucoup plus facile à comprendre et même relativement simple à implémenter.

Au départ, tout repose sur quelques concepts de base très simples :

  • une grille composée de cases

  • des tuiles pouvant être placées sur ces cases

  • un chevalet contenant les lettres du joueur

  • et des règles qui déterminent où et comment les mots peuvent être posés

À partir de là, le moteur du Scrabble n’est finalement qu’un système qui explore des combinaisons possibles entre les lettres du chevalet et les contraintes imposées par la grille.

Chaque case possède un état : vide ou occupée. Chaque tuile connaît sa lettre et sa valeur. Chaque mot posé crée de nouvelles contraintes et de nouvelles opportunités. Petit à petit, toute la complexité du jeu émerge simplement de l’interaction entre ces éléments fondamentaux.

Bien sûr, créer un moteur performant capable de trouver les meilleurs coups en quelques millisecondes demande ensuite des optimisations avancées, des structures de données spécialisées et beaucoup d’algorithmes intelligents. Mais la bonne nouvelle, c’est que le cœur du problème reste étonnamment accessible.

Une fois les bases bien comprises, on réalise que derrière l’apparente complexité du Scrabble se cache surtout une succession de règles simples appliquées méthodiquement.

Nous reviendrons à l'implémentation concrètre dans Skrabby, plus tard.

Si vous ne connaissez pas le Dawg ou le GadDag pour comprendre la suite je vous invite à consulter les pages concernant la compilation et l'utilisation d'un dictionnaire compressé pour les jeux de lettres, ou tout autre outil de recherche de mots.

Exemple de recherche d'un coup

Scrabbles-Resolution.pngUtilisons maintenant un exemple concret illustré ci-dessous.

Avant d’entamer la recherche d’un coup, le moteur doit précalculer quelles lettres peuvent être utilisées comme pivots sur chaque case vide adjacente à une case déjà occupée. Toute case non adjacente à une autre lettre accepte naturellement n’importe quelle lettre.

Ces pivots diffèrent selon que l’on recherche des mots horizontalement ou verticalement. Pour une recherche horizontale, on vérifie les contraintes verticales, et inversement.

À l’exception du premier coup — où la seule contrainte est de passer par la case centrale — toutes les recherches se font à partir d’une lettre déjà présente sur la grille. C’est précisément là que le GADDAG révèle sa puissance grâce à son dictionnaire bidirectionnel.

Prenons le tirage AHULIT?. Une des meilleures ouvertures possibles est HUILANT en H4. Cette solution peut être trouvée en parcourant l’entrée GADDAG ANT#LIUH : on construit d’abord le mot vers la droite avec ANT, puis on repart vers la gauche après le pivot # pour préfixer avec LIUH.

Pour tous les coups suivants, chaque mot posé doit soit utiliser au moins une lettre déjà présente sur la grille, soit toucher une lettre existante.

Une règle essentielle du Scrabble est que tous les mots formés doivent être valides. Cette contrainte est également au cœur du moteur de recherche. Grâce au précalcul des pivots, il devient possible de filtrer immédiatement les combinaisons impossibles.

Ainsi, pour une recherche horizontale, le moteur précalcule pour chaque case les mots verticaux potentiellement formés. Pour une recherche verticale, il fait l’inverse. Cela permet d’éliminer très tôt une grande partie des solutions invalides et d’améliorer considérablement les performances.

Comme le montre le schéma, toutes les cases situées sous BRISEES admettent des pivots.

Une fois ce précalcul effectué, la recherche des solutions peut commencer. Le moteur parcourt toutes les cases adjacentes à une tuile déjà posée, dans les deux directions : horizontalement et verticalement.

Dans notre exemple, la solution recherchée est HUILANT, placée sous le mot BRISEES.

La recherche sur cette ligne débute donc en I4, première case vide adjacente à une lettre déjà jouée. Le moteur parcourt alors le dictionnaire depuis sa racine, appelée ici CurrentNode, en avançant case par case.

Pour cette première case, les pivots possibles sont A, U, I et le joker. Le moteur commence par essayer A, qu’il retire temporairement du tirage. CurrentNode est alors déplacé vers le nœud correspondant dans le dictionnaire.

Toutes les lettres incompatibles avec les pivots sont immédiatement ignorées.

La recherche continue ensuite sur la case suivante. Il reste alors ULITH? sur le chevalet. Les pivots autorisés deviennent E, U, I ainsi que le joker. Et ainsi de suite : le moteur avance tant qu’une solution valide reste possible.

Le joker constitue un cas particulier, puisqu’il oblige à tester toutes les lettres de l’alphabet.

À chaque fois que le parcours rencontre une fin de mot valide dans le dictionnaire, la solution est ajoutée à la liste des coups possibles. Si l’on ne recherche que les meilleurs coups, seules les solutions ayant un score supérieur sont conservées.

Évidemment, cela ne mène pas encore directement à HUILANT, puisque la recherche a commencé en I4 alors que le mot débute réellement en I3.

C’est ici que le GADDAG devient particulièrement intéressant.

Une fois UILANT trouvé de gauche à droite, le CurrentNode final contient un pivot permettant de repartir dans l’autre sens. Il ne reste alors plus qu’à préfixer le mot avec le H restant sur le chevalet.

La recherche s’arrête immédiatement après cette lettre, car RUILANT, par exemple, serait impossible : la lettre nécessaire n’est plus disponible dans le tirage.

Cette logique s’applique ensuite à toutes les autres cases de la ligne, de I5 à I10. La seule différence est qu’il n’est plus nécessaire d’effectuer une recherche bidirectionnelle : celle-ci a déjà été couverte lors de l’exploration initiale de la ligne.

Implémentation dans Skrabby

DiagramObjects.png

Voilà, en résumé, les classes de base permettant d’implémenter notre moteur de recherche. Dans Skrabby, ces classes ne contiennent volontairement aucune méthode : elles sont décorées par différentes extensions permettant diverses manipulations. La logique de recherche est, quant à elle, pilotée par différents contrôleurs. Ce sera le sujet des prochains articles.

Les points les plus importants sont :

  • L’utilisation d’une grille transposée pour la recherche verticale dans GridConfigurationContainer.

  • Le statut de chaque case permettant de savoir si elle est vide, occupée, ou temporairement utilisée par le tirage en cours de résolution.

  • Chaque lettre conserve une référence vers la case à laquelle elle est attachée.

GridConfigurationContainer

Cette classe contient l’état complet de la grille.

SizeH

Taille horizontale.

SizeV

Taille verticale.

Grid[]

Deux grilles contenant Squares de taille SizeH + 2 × SizeV + 2 :

  1. La représentation normale.

  2. Une représentation transposée où (X,Y) devient (Y,X).

À chaque coup, la grille est transposée afin de parcourir horizontalement et verticalement de manière uniforme, sans ajouter de logique spécifique selon le sens de recherche.

La grille est également étendue de cases vides sur chacun de ses côtés. Cela évite des vérifications récurrentes des limites : lorsqu’une case vide étendue est atteinte, le moteur sait immédiatement qu’il se trouve hors de la zone jouable.

Square

Cette classe contient la configuration de chaque case ainsi que son état d’occupation.

IsBorder

Indique que cette case appartient à la bordure vide étendue de la grille.

LetterMultiplier

Indique qu’un multiplicateur de lettre est présent sur cette case.

WordMultiplier

Indique qu’un multiplicateur de mot est présent sur cette case.

PivotLetters[]

Contient le nombre de lettres formant le pivot. Utilisé lors de l’évaluation du score d’un coup.

PivotsPoints[]

Contient les points associés aux mots formés par les pivots. Par exemple, si la grille contient JOUER, le pivot peut accepter A pour former AJOUER, avec un score associé de 12 points. Cela évite de recalculer constamment le score des pivots.

Pivots[]

Contient les lettres autorisées en pivot. Cette implémentation utilise un tableau de UINT 32 bits, où chaque bit représente une lettre valide.

Cela impose toutefois une limite : contrairement au GADDAG pouvant contenir jusqu’à 250 caractères différents, cette représentation nécessite un bitset plus large pour supporter davantage de caractères.

Status

Indique l’état actuel de la case : vide, occupée, ou temporairement utilisée par une lettre provenant du tirage courant.

CurrentLetter

Référence la lettre actuellement placée sur cette case.

Tile

Cette classe contient la configuration d’une tuile. Au départ, le sac contient autant de Tiles que défini dans la configuration des lettres.

IsEmpty

Indique que cette lettre n’est actuellement pas placée sur la grille.

IsJoker

Indique qu’il s’agit d’un joker.

IsJokerReplaced

À la fin d’un coup, le joker peut être remplacé par une lettre réelle si cela est possible. Ce booléen indique si ce remplacement a eu lieu.

IsPlayedJoker

Retourne true si IsJoker ou IsJokerReplaced est vrai.

Letter

Représente la lettre portée par cette tuile.

Parent

Si la lettre est placée sur la grille, Parent référence la case associée.

PivotPoints

Représente le nombre de points associés au pivot de cette lettre.

Points

Valeur en points de cette lettre.

Source

Représente le statut de la case associée à cette lettre.

PlayerRack

Cette classe contient simplement le tableau de Tiles constituant le tirage courant.

Tiles

Tableau de Tiles représentant le tirage du joueur.