Comment les robots fonctionnent-ils ?

Si vous vous posez parfois la question, voici en résumé la méthode qu’ils appliquent.

Cet article est aussi destiné à éclairer les joueurs qui, peut-être lassés après une série de défaites consécutives contre des « robots 3000 », lâchent par moment des commentaires désabusés et gratuits mettant  en doute la manière dont ils ont été programmés.

Interventions heureusement très rares et émanant presque toujours des mêmes personnes, mais qui blessent par leur ignorance du travail sous-jacent à la programmation de ces robots, et de sa complexité.

Robots doxiens vs robots scrabbleurs

Les robots de Dox ne sont pas très éloignés de leurs cousins utilisés par les programmes de Scrabble. Depuis très longtemps, ceux-ci sont devenus imabattables, même par des champions du monde, car ils sont capables de connaître presque instantanément tous les meilleurs coups à jouer pour une grille et un tirage donné.

Les robots doxiens eux aussi savent « calculer » tous les meilleurs coups de manière extrêmement rapide grâce à la puissance de calcul des ordinateurs actuels et à leur connaissance de tous les mots du dictionnaire.

Si les règles du jeu étaient plus simples (pas de vol de mot, pas de vidage) et réduites à celles d’un Diamino, avec ou sans les « cases multiplicatrices » du Scrabble, ils seraient quasiment imbattables et auraient peut-être franchi depuis longtemps la barrière des 4000 points. Sans aucun mérite, car les algorithmes permettant de solutionner les grilles de Scrabble ou autres jeux de lettres similaires existent depuis longtemps et sont parfaitement éprouvés.

Les règles particulières à Dox rendent la programmation des robots plus compliquée et incertaine, et c’est une chance pour nous joueurs humains, car ils commettent des maladresses dont nous pouvons profiter.

De plus, dans ce jeu, la notion de « coup optimal » est beaucoup plus problématique qu’au Scrabble, même dans sa version « classique ». Dans Fundox un coup est rarement optimal de manière indubitable. Il implique presque toujours une incertitude, un pari, souvent une prise de risque parfaitement assumée, ou même... du bluff. Ceci est vrai pour nous… mais aussi pour les robots, même avec leur énorme force de frappe lexicale et combinatoire.

Mis à part l’étape préliminaire qui consiste à collecter tous les coups possibles,  dont il existe plusieurs méthodes de programmation très bien connues, le reste du raisonnement que doit suivre le robot doxien n’est répertorié nulle part. Leur programmation repose donc largement sur des méthodes qu’il a fallu imaginer de toute pièce, transcrire en lignes de code, mettre à l’épreuve du jeu, affiner etc. Elles sont encore largement perfectibles et ont donné lieu à de très nombreuses mises à jour du jeu depuis leur première apparition.

Songez-y avant de ronchonner sur vos adversaires robotiques dans le lobby !

Comment « réfléchit » le robot doxien ?

Ce schéma représente de manière simplifiée la méthode employée par les robots :

Le robot procède en trois ou quatre étapes, selon que l’option « avec vidage » a ou non été sélectionnée :

1) Collecte de toutes les solutions possibles

C’est la tâche du « solveur ». Celui-ci fonctionne d’une manière similaire aux solveurs de Scrabble, avec certaines différences induites pas les spécificités de Dox (grille de 13 cases de côté, scores calculés différemment, pas de « joker »…).

Les données en entrée sont le contenu actuel de la grille et du chevalet (après tirage des nouvelles lettres) et la liste de tous les mots admis par le jeu (le « dictionnaire »). Le dictionnaire, qui inclut toutes les flexions de chaque mot ou verbe,  comprend environ 355 000 mots et le robot les connaît tous. Comme ses cousins les robots scrabbleurs, le robot doxien surclasse tous les champions du monde de Scrabble au niveau du vocabulaire.

Le dictionnaire est stocké sous la forme d’un arbre DAWG (« Directed Acyclic Word Graph »). Cette structure permet d’effectuer des recherches ultra-rapides et économes en mémoire vive.

A chaque solution trouvée, le programme associe le « gain » numérique que celle-ci peut apporter dans l’immédiat au robot. Le gain est calculé par cette formule :
 

En effet, il ne suffit pas de calculer les seuls points que la solution va ajouter au score du robot, mais il faut aussi prendre en compte les points que celle-ci vole à l’adversaire. Contrairement au Scrabble et à tous les autres jeux de lettres, dans Dox chaque coup fait à la fois avancer son propre  score et reculer celui de l’adversaire. S’il fallait le rapprocher d’un autre jeu à ce niveau, ce serait un peu au Tarot, sauf qu’ici la somme des points de tous les joueurs n’est pas nulle.

Voici comment a été établie la formule du gain :

SA = score initial du joueur A
SB = score initial du joueur B
Ecart initial entre A et B (E1) = SA - SB
LA = nouvelles lettres posées par le joueur A
LB = lettres volées au joueur B

Nouveau score du joueur A une fois le mot posé (NA) = SA + LA + LB
Nouveau score du joueur B (NB) = SB - LB
Nouvel écart entre A et B (E2)  =  NA - NB = SA + LA + LB - (SB - LB)
Donc E2 = SA + LA - SB + LB x 2

Le gain mesure l'évolution de l'écart entre A et B par rapport à l'écart initial :

Gain = E2 - E1 = SA + LA - SB + LB x 2 - (SA - SB)
Donc Gain = SA + LA - SB + LB x 2 - SA + SB = LA + LB x 2

L’avantage numérique apporté par un coup -le gain- est donc en fait un écart de points : de combien de points le coup que je vais jouer va-t-il augmenter (ou réduire, si je suis en retard) l’écart de score entre moi et mon adversaire ?

Une fois que le solveur a terminé sa tâche, le robot connaît absolument tous les coups qu’il est possible de jouer en fonction de la grille et du chevalet, et en particulier ceux qui rapportent le gain maximal. Le nombre de solutions possibles peut dépasser le millier dans certaines configurations de grille et de lettres présentes dans le chevalet.

2) Evaluation des solutions collectées

Après la collecte des solutions, le robot connait tous les meilleurs coups jouables dans l’immédiat (les « tops »). Cela ne suffit pas, car il faut éviter que l’adversaire rallonge le mot posé ou le maçonne trop facilement. Ici on s’écarte des robots de Scrabble car on ne joue pas en « duplicate », et les considérations d’ordre tactique sont bien plus nombreuses et complexes dans Dox que dans le Scrabble classique.

L’ « évaluateur » prend le relais du solveur en analysant une nouvelle fois toutes les solutions trouvées :

- Le mot est-il rallongeable ? Avec quelles lettres ? Et avec quelle probabilité que l’adversaire tire ces lettres ?

- Même question pour les rallonges « transversales » (les nouveaux mots formés indirectement, par maçonnage).

- La position du mot posé dans la grille est-elle intéressante ou non ? (cette analyse est très fruste pour l’instant chez les robots « non videurs », et un peu plus avancée chez les robots « videurs »)

Une fois ces analyses effectuées, le robot évalue le « score » de chaque solution. Le score synthétise numériquement l’intérêt de la solution.

Grosso modo il est calculé de cette manière :
 

La perte potentielle c’est, en gros, le gain maximal que l’adversaire pourrait à son tour obtenir à partir  de cette solution lors des tours suivants - pour le robot, il s’agit donc d’une perte - par exemple à l’aide d’une rallonge.

Ce n’est pas parce qu’on a posé un mot rallongeable que l’adversaire va forcément pouvoir poser la rallonge. Il faut encore qu’il tire les bonnes lettres.

Le robot essaie d’évaluer (« à la louche ») la probabilité que l’adversaire tire ces lettres. Celle-ci dépend de leur rareté (la rallonge « AF » est par exemple plus rare que la rallonge « ES ») et aussi de la proximité de la fin de la partie. S’il ne reste qu’environ 5 points pour que l’un des joueurs gagne la partie, cela veut dire qu’il n’a plus beaucoup de lettres à tirer et donc que le probabilité d’obtenir la rallonge est bien moins élevée qu’au début ou en milieu de partie.

Si l’adversaire a beaucoup d’avance sur le robot, celui-ci « lâche du mou » sur le calcul des probabilités de tirages favorables à l’adversaire. Au lieu d’évaluer la probabilité que celui-ci tire « ES » à une chance sur trois, par exemple, il va la sous-évaluer artificiellement à une chance sur cinq ou six. Ceci va se traduire par une prise de risque plus élevée de la part du robot, qui va moins hésiter à poser « volontairement » des mots rallongeables et/ou maçonnables.

Le robot va appuyer son choix du coup à jouer sur le « score ». de chaque solution. Celui-ci fait essentiellement la synthèse entre les points rapportés par la solution et le risque de perte potentielle qu’elle entraîne. La position du mot dans la grille n’est prise en compte que de manière marginale (surtout pour les robots non videurs).

Leur approche du jeu est donc pour l’instant plus « quantitative » et « probabiliste » que véritablement tactique, du moins sans le vidage. Voilà pourquoi ils sont à la fois redoutables au niveau du vocabulaire et des facultés de maçonnage, et assez friables dans d’autres aspects du jeu.Par exemple, ils n’hésiteront pas à poser de très longs mots sur les lignes ou colonnes périphériques de la grille, au risque de créer des « couloirs » aisément maçonnables.

A vous de profiter de ces faiblesses !

3) Analyse du vidage

Cette étape est évidemment spécifique aux robots « videurs ». Ceux-ci doivent prendre en compte l’existence des lignes et des colonnes de vidage.

Les robots videurs analysent en premier lieu la configuration de la grille et établissent une « matrice de vidage » qui leur indique les cases à éviter s’ils ne veulent pas que l’adversaire puisse vider. Si le robot a un avantage numérique important, il va au contraire essayer de privilégier ces cases de manière à mettre l’adversaire en difficulté. Celui-ci va devoir faire un choix : accepter le défi et vider la grille en se retrouvant pénalisé au niveau du score, ou alors essayer tant bien que mal de bloquer le vidage avec un coup qui lui rapportera peu de points.

De manière complémentaire, le robot videra la grille si cela lui apporte un avantage, ou essaiera de bloquer le vidage dans le cas contraire.

Comme pour  les robots non videurs, la force principale des robots videurs réside dans leur capacité d’analyse de toutes les solutions possibles et dans leur vocabulaire monstrueux, qui leur permet entre autres de connaître de manière imparable la totalité des mots qui permettent de vider la grille, en fonction des lettres présentes dans le chevalet.

Leur analyse du vidage est encore largement perfectible. En particulier, elle ne recourt pas encore aux probabilités. Quand le robot « ouvre » vers une ligne ou colonne de vidage, il ne cherche pas à évaluer la probabilité que l’adversaire puisse effectivement vider ou non.

Par exemple, si le mot ouvre sur le vidage à l’aide de la lettre Q et si celle-ci se trouve 4 cases après la case de vidage, la probabilité que l’adversaire s’appuie sur elle pour vider est nulle car il n’existe aucun mot de 5 lettres se terminant par un Q. Pour l’instant le robot ne le sait pas, donc soit il évitera de jouer cette solution en croyant faussement que c’est une ouverture, soit il la jouera volontairement pour « forcer » l’adversaire à vider, éventuellement en prenant des risques, alors que ça ne force l’adversaire à rien du tout.

Ce cas (probabilité nulle de vidage) serait simple à programmer mais dans la réalité les situations de ce type sont plus subtiles.

En outre, le robot videur essaie de jouer intelligemment le premier mot posé quand la grille est vierge, de manière à minimiser en particulier le risque que l’adversaire vide au coup suivant. Il recherche le meilleur mot non rallongeable dont la lettre posée en case centrale puisse le moins possible servir à vider en posant un scrabble. Dans le jeu français, les lettres à éviter en priorité sont dans l’ordre les lettres S, E, T, A et R. Là encore, leur choix du premier mot posé est encore perfectible.

Autre différence induite par l’option « vidage » : le robot cherche à la fois à éviter les lignes / colonnes périphériques si elles ne lui apportent aucun avantage, et aussi à privilégier les mots placés sur les lignes / colonnes impaires, classiquement considérées comme « fortes » dans ce style de jeu.

4) Décision

Une fois les données de départ passées à la moulinette du solveur et de l’évaluateur (plus les analyses complémentaires pour le vidage), le robot pose le mot qui a le score maximal. Dans le cas du jeu avec vidage il peut aussi décider de passer son tour.

 

[ 1 2 3 4 5 ]