« Apprendre, c’est transformer le doute en outil. »
« Chaque notion maîtrisée est une liberté gagnée. »
« On n’apprend jamais pour savoir, mais pour comprendre. »
« Le code n’est pas écrit, il est sculpté. »
« Un bug bien compris vaut mieux qu’un code ignoré. »
« Coder, c’est penser deux fois : pour la machine et pour soi. »
« Chaque ligne simplifie ou complique le monde. »
« L’organisation, c’est du temps rendu visible. »
« La clarté est une discipline avant d’être un état. »
Aperçu de l'implémentation dans Skrabby
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
Prenons maintenant un exemple concret afin de mieux comprendre le fonctionnement du moteur de recherche.
Avant de rechercher un coup, le moteur analyse le plateau afin de déterminer, pour chaque case vide, quelles lettres peuvent y être jouées. Ce précalcul produit ce que j'appelle les pivots. Une case isolée accepte naturellement n'importe quelle lettre, tandis qu'une case adjacente à des lettres déjà présentes doit respecter les mots croisés qui seront formés. Les pivots sont calculés indépendamment pour les recherches horizontales et verticales : lors d'une recherche horizontale, les contraintes verticales sont évaluées, et inversement.
À l'exception du premier coup, où la seule contrainte consiste à passer par la case centrale, toute recherche démarre à proximité d'une lettre déjà présente sur le plateau. C'est précisément dans cette situation que le GADDAG révèle tout son intérêt. Contrairement à un dictionnaire classique, il permet de construire un mot dans les deux directions à partir d'une lettre pivot déjà posée sur la grille.
Prenons le tirage AHULIT?. L'une des meilleures solutions consiste à jouer HUILANT en H4. Dans le GADDAG, cette solution est représentée par l'entrée ANT#LIUH. Le moteur construit d'abord la partie droite du mot (ANT), puis, après avoir rencontré le séparateur #, il repart dans l'autre sens afin d'ajouter le préfixe LIUH. Cette représentation bidirectionnelle évite de parcourir plusieurs fois le dictionnaire pour une même recherche.
Le schéma ci-dessous montre un autre exemple où le mot BRISÉES est déjà présent sur le plateau. Toutes les cases situées sous ce mot possèdent un ensemble de pivots qui limitent immédiatement les lettres autorisées. Ce filtrage est essentiel : il élimine dès le départ un très grand nombre de combinaisons impossibles, ce qui réduit considérablement le nombre de recherches à effectuer.
Une fois les pivots calculés, le moteur parcourt successivement toutes les cases adjacentes à une lettre existante, aussi bien horizontalement que verticalement. Dans notre exemple, la recherche débute en I4, première case libre située sous BRISÉES. À partir de la racine du GADDAG, le moteur essaie successivement chacune des lettres autorisées par les pivots. Pour cette première case, seules les lettres A, U, I ainsi que le joker sont envisageables. Chaque lettre utilisée est temporairement retirée du chevalet et le parcours se poursuit dans le dictionnaire.
La même opération est répétée sur la case suivante avec les lettres restantes. Les pivots recalculés pour cette position limitent à nouveau les possibilités, permettant d'écarter immédiatement toutes les branches incompatibles. Le joker constitue le seul cas particulier puisqu'il oblige à explorer chacune des lettres de l'alphabet.
À chaque fois que le parcours atteint une fin de mot valide dans le dictionnaire, une nouvelle solution est produite. Selon le mode de recherche choisi, le moteur peut conserver l'ensemble des solutions ou uniquement celles dont le score est supérieur aux précédentes.
À ce stade, le moteur n'a pourtant trouvé que UILANT, car la recherche a commencé en I4 alors que le mot complet débute en I3. C'est ici que le fonctionnement bidirectionnel du GADDAG prend tout son sens. Une fois la partie droite du mot construite, le séparateur # permet de repartir dans l'autre direction afin de compléter le mot avec le H restant sur le chevalet. La solution HUILANT est alors obtenue sans avoir à recommencer une seconde recherche.
Le même principe est ensuite appliqué à toutes les autres cases de la ligne. Les recherches deviennent toutefois plus simples, car la partie bidirectionnelle a déjà été explorée lors de la première position. Le moteur poursuit ainsi son exploration du plateau jusqu'à ce que toutes les positions potentielles aient été analysées.
Implémentation dans Skrabby
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 :
À 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. |