Dans les parties de duplicate, il y a généralement un solver qui donne la ou les meilleures solutions, c'est-à-dire celles qui font le nombre de points maximum (c'est l'humain qui détermine la meilleure au sens où ça ouvre le jeu parmi toutes les possibilités). Et pour implémenter un solver de Scrabble, il faut des structures de données et des algorithmes un peu complexe mais très intéressant : par exemple un GADDAG. L'avantage, c'est qu'on peut générer toute la structure à l'avance pour un dictionnaire donné et la réutiliser à chaque fois. Mais le temps de génération peut être long pour des gros dictionnaires (de l'ordre de quelques secondes pour /usr/share/dict/french). C'est de la belle algorithmique, et le papier de Gordon est assez bien foutu avec des algorithmes clairs et explicites (ça change de ce qu'on peut lire de nos jours).
[^] # Re: Parties en duplicate
Posté par rewind (Mastodon) . En réponse à la dépêche Trivabble continue à évoluer. Évalué à 9.
Dans les parties de duplicate, il y a généralement un solver qui donne la ou les meilleures solutions, c'est-à-dire celles qui font le nombre de points maximum (c'est l'humain qui détermine la meilleure au sens où ça ouvre le jeu parmi toutes les possibilités). Et pour implémenter un solver de Scrabble, il faut des structures de données et des algorithmes un peu complexe mais très intéressant : par exemple un GADDAG. L'avantage, c'est qu'on peut générer toute la structure à l'avance pour un dictionnaire donné et la réutiliser à chaque fois. Mais le temps de génération peut être long pour des gros dictionnaires (de l'ordre de quelques secondes pour
/usr/share/dict/french). C'est de la belle algorithmique, et le papier de Gordon est assez bien foutu avec des algorithmes clairs et explicites (ça change de ce qu'on peut lire de nos jours).