Projet de création d’un solveur de fins de partie classique

Avertissement

Nous n’avons pas de logiciel d'analyse de fins de partie à offrir pour le moment.

Présentation vidéo du prototype DupliMot


Télécharger les fichiers gcg & liens de la présentation.

Vue d’ensemble de ce que nous avons obtenu

Notre solveur de fins de partie résout exactement et exhaustivement n’importe quelle fin de partie, peu importe si :

* Si les deux joueurs passent tour à tour alors on met fin à la partie et on soustrait la valeur du reliquat de chaque joueur de son cumul. Officiellement, le règlement stipule qu’on doit mettre fin à la partie après six passages consécutifs et non deux, mais cela revient au même ici.

Étant donné une grille et un tirage, notre solveur trouvera la valeur différentielle (c'est-à-dire le nombre de points à reprendre ou à laisser à l'adversaire) de chaque coup (excluant mots faux, pour des raisons évidentes) en supposant que les deux joueurs jouent de façon optimale à chaque tour. Pour chaque coup, la liste des séquences optimales menant à la valeur différentielle est donnée (certaines séquences peuvent être omises parce qu'elles sont équivalentes à d'autres à permutation de coups indépendants près).

Nous avons passé plusieurs heures à optimiser notre algorithme pour le rendre plus efficace. Par exemple, nous tirons profit du multithreading et nous sauvegardons des informations en cache pour éviter d’analyser les mêmes situations plusieurs fois. Avec un ordinateur portable de base possédant huit processeurs logiques 1,60 Ghz et 8,00 Go de RAM, les fins de partie simples sont résolues complètement en quelques secondes ou minutes. Les fins de partie plus complexes, typiquement celles avec des jokers et des lettres implaçables, peuvent prendre de nombreuses heures à être résolues complètement. Pour cette raison, nous avons développé trois modes, certains plus rapides que d’autres, qui peuvent être utilisés selon le type de solution recherché.

Notez que, pour chacun de ces modes, il est possible de spécifier une profondeur de recherche et un nombre de coups (du plus payant au moins payant) à considérer à chaque niveau. Selon les valeurs spécifiées, les réponses données par notre solveur pourraient être incertaines, mais ces deux paramètres restent utiles pour des fins de partie complexes où l’on veut une idée rapide de ce qui se passe. Enfin, similairement aux engins d’échecs, nous nous assurons d’afficher à l’écran les résultats partiels et de les mettre à jour au fur et à mesure que l’analyse progresse.

Mode écart : trouver les coups gagnants, perdants et ceux qui mènent à la partie nulle

Ce mode est de loin le plus rapide. Étant donné l’écart de points avec l’adversaire, il trouvera les coups qui permettent de gagner la partie, ceux qui perdent la partie et ceux qui mènent à la partie nulle. Ce mode est utile lorsqu’on n’est pas intéressé par l’écart final ; c’est le cas dans la plupart des finales de tournois.

Mode complet : trouver la valeur différentielle de chaque coup, en commençant par les coups qui marquent le plus de points

Ce mode-ci est le plus rapide lorsqu’on veut résoudre complètement une fin de partie. Il est utile lorsqu’on veut faire des statistiques, puisqu’il donne le classement des coups du meilleur au pire. Toutefois, la grande majorité du temps, les mauvais coups ne nous intéressent pas (sauf si on cherche à composer des problèmes où on doit aider l’adversaire à gagner, comme les échecs et mats aidés aux échecs)… Notre troisième et dernier mode a été conçu pour mettre les mauvais coups de côté et se concentrer sur les coups les plus prometteurs.

Mode meilleurs d’abord : trouver la valeur différentielle de chaque coup dans l’ordre du meilleur au pire

Dans ce mode, la recherche est concentrée sur les coups les plus prometteurs (du point de vue du différentiel). Notre algorithme trouvera les meilleurs coups classiques dans l’ordre, du meilleur au pire. Le mode meilleurs d’abord est bien plus rapide que le mode complet, si tout ce qui nous intéresse c’est les meilleurs coups dans la position. En effet, pour être sûr d’avoir trouvé le meilleur coup avec le mode complet, on doit attendre qu’il ait terminé d’analyser tous les coups.

Retour à la page d'accueil



Ortograf Inc. Ce site utilise des cookies informatiques, cliquez pour en savoir plus. Politique vie privée.
© Ortograf Inc. Mise à jour le 23 février 2021. Informations & Contacts.