au Scrabble citoyens

Scrabblélipopette,

il fallait s'en douter. à force de faire des programmes pour jouer et/ou résoudre des problèmes d'Othello, Sudoku, compte et bon et mot le plus log, le Scrabble s'inscrit tout à fait dans cette continuité.
Mine de rien, il existe déjà pas mal d'adaptations de Scrabble pour ordinateurs, avec notamment des portages sur PlayStation et Android. Cela n'en fera qu'une de plus.

Et pourtant, le Scrabble, ce n'est pas Trivial ...

Un peu comme Othello, facile à jouer, difficile à maitriser.
Il faut :

• disposer d'un dictionnaire ( ok, celui déjà utilisé regroupe plus de 360.000 mots )
• avoir du temps ( ça tombe bien, tout comme pour les autres jeux, l'objectif est aussi de gagner du temps sur les parfois très longues et monotones parties. Il s'agit donc bien d'un investissement sur le futur)
• un ordinateur un peu puissant ( à quand les jeux sur Raspberry ? )
• savoir jouer avec les mots et marquer des points ( au propre comme au figuré ) et optimiser ses choix.

Le prototype : l'origine de tous les mots

L'objectif était de faire en 2 jours - bien remplis - un jeu capable de faire un minimum de choses essentielles, à savoir :

• gérer des lettres, le modèle est là : http://fr.wikipedia.org/wiki/Lettres_du_Scrabble#Fran.C3.A7ais
• créer des pions et les mélanger ( pour simplifier, les joker ne sont pas utilisés )
• gérer une partie avec un seul joueur
• avoir toujours 7 pions sur son chevalet, du moins jusqu'à la fin de partie
• remettre ses pions dans le chevalet si pas de mots trouvés
• pouvoir jouer 2 tours ( les cas 1 et cas 7 décrits ci-après )
• ne pas faire sauter le compteur ( surveiller sa mémoire vive )
• gérer les cases multiplicatrices des points et de mots
• maitre mot : faire à chaque tour le maximum de points possibles

Il reste encore pas mal de travail, notamment afficher le déroulement de la partie et la comptabilisation, jouer à plusieurs, étendre  tous les cas possibles et étudier des coups à jouer. Ce genre de choses.

La schématisation du problème

Sur une feuille A4, cela aurait pu ressembler à ceci :

Le scrabblier après 2 tours

Le sac contient les 100 pions lettrés mélangés 100 fois.
BAGNE fait (3*2+1+2+1+1)*2 = 22 points au 1° tour
TAXOLS fait (1+1+10+1+1+1)*2 = 30 points au 2° tour, soit 52 points sur les 2 premiers tours.

Gestion de la mémoire

avant la barre bleue, la création des dictionnaires ( dont anagrammes ) en mémoire à partir d'un simple fichier texte. Une dizaine de secondes pour préparer les données.
après la barre bleue, les 2 coups joués et la copie d'écran. Les deux coups du début sont ( quasiment ) instantanés.

Sur l'image un bug répértorié, l'ordinateur a placé "QUE" au milieu parce que le "mot compte double" de la case du milieu n'a pas été annulé après avoir été utilisé.

les 7 plaies des glyphes, je les prends aux mots

Le scrabble, ce n'est pas trivial, parce qu'il y a pas mal de façons de rajouter un mot à un autre. Voici listés les 7 types de base, passons-les en revue.

Imageons la scène

Comment poser les mots "DE" ( ou "DES" ) en relation avec "UN" ? Les 7 cas sont indiqués sur fond bleu.
Pour le fun, quelques exemples de placement avec le mot "TROIS".

Type 1

Il s'agit du cas le plus simple,trouver à placer le mot faisant le plus de points. Valable uniquement pour le 1° tour.

Type 2

à partir du chevalet, compléter un mot existant ( par exemple UN + DES = DUNES ).

Type 3

Le nouveau mot est un mot à part entière et ne modifie pas le mot existant, parallèle à celui-ci, joint par une lettre formant un troisième nouveau mot de 2 lettres.

Type 4

Les cas général de la rencontre du 3° type. Avec recouvrements multiples.

Type 5

pendant du type 3, mais en orthogonalité

Type 6

Le contraire du type  5. Le mot précédent ne change pas, mais le nouveau mot n'existe pas sans lui.

Type 7

Les mots croisés, le 2° mot traversant le 1°

Type 8

le contraire du type 7, mais je n'en parlerai pas pour ne pas créer un 8° cas à traiter.

Généralisation du problème

Si le type 3 est un cas particulier du type 4, il faut bien voir que l'on a 2 fonctionnements radicalement différents, dont le 2° est bien plus difficile à gérer.

cas général 1

Le cas le plus simple, on cherche à poser sur le chevalet un mot complet ( cas 1, 2, 3 , 4 et 5 - et 8 - ). nous pouvons utiliser le dictionnaire de mots pour

cas général 2

des pions sont à placer pour créer un mot existant. Dans le pire des cas, le nouveau mot peut s'appuyer sur plusieurs mots posés séparés ( cas 6 et 7, et l'exemple complexe AVANT + AVANT + ESUIE = 2 * AVANT + ENSUITE )