Avant de jouer, l'IA doit trouver son coup dans une botte de foin de cent cinquante mille mots, puis cesser de chercher.
Rédigé et édité en anglais. Cette version française a été produite par traduction automatique ; en cas de doute sur un point précis, l'original anglais fait foi. Lire l'original en anglais →
Donnez à quelqu'un un jeu complet de jetons de WordChess et la consigne « jouez un bon mot » : il restreint le problème sans même s'en apercevoir. L'ordinateur ne jouit d'aucune intuition de ce genre. Sur un plateau de 25×25, avec son propre jeu complet de cent jetons, il peut tenter presque n'importe lequel des 148 941 mots du dictionnaire, et chaque mot peut être posé à des milliers de coordonnées et d'orientations légales. Pire, un placement n'est légal que si chaque nouvelle lettre qu'il introduit complète elle aussi un mot réel là où elle croise ce qui se trouve déjà sur le plateau. Multipliez les mots par les placements par cette contrainte de croisement et vous obtenez un espace de recherche qu'aucun joueur, de silicium ou non, ne peut énumérer et classer en entier.
C'est la raison pour laquelle les moteurs sérieux de jeux de lettres, dont Quackle, l'implémentation de référence open source, n'attaquent jamais le dictionnaire par force brute. 4 La structure GADDAG conçue par Steven Gordon en 1994, et le DAWG avant elle, permettent à un programme de faire croître les mots vers l'extérieur à partir des jetons déjà posés sur le plateau et de vérifier les croisements au fur et à mesure, de sorte que les branches illégales meurent tôt au lieu d'être évaluées puis écartées. 1 La tâche n'est pas « énumérer tous les mots ». Elle est « ne générer que les coups susceptibles d'être légaux, et le faire vite ».
Même un générateur économe renvoie plus de coups candidats qu'on ne peut en évaluer en profondeur ; le second problème est donc le temps. Maven, le programme de Brian Sheppard, le premier à surpasser les meilleurs adversaires humains, a affronté exactement cela et y a répondu en deux temps : une heuristique rapide trie les coups bruts dans un ordre approximatif de qualité, et seule une liste restreinte des plus prometteurs est étudiée soigneusement, en simulant la partie vers l'avant de nombreuses fois pour voir quel candidat se comporte réellement le mieux. 2 D'autres jeux connaissent la même idée sous d'autres noms, le rollout du backgammon et le playout des programmes de go ; dans Maven, elle s'appelle simulation.
WordChess procède dans le même esprit, sous une contrainte plus stricte : un budget de temps de recherche fixe par coup. Quand le budget est épuisé, l'IA s'engage sur le meilleur mot qu'elle a trouvé jusque-là. Ce n'est pas un compromis que les ingénieurs regrettent ; c'est toute la conception. Un joueur qui réfléchit indéfiniment n'est pas un meilleur adversaire, seulement un adversaire plus lent. L'horloge oblige la machine à faire ce que les humains font d'instinct : se contenter d'un coup manifestement bon plutôt que démontrablement optimal.
Connaître le dictionnaire, c'est la partie facile. Savoir quand cesser d'y chercher, c'est la partie difficile.
La façon paresseuse de rendre une IA de jeu plus facile consiste à la rendre stupide au hasard, à lui faire rater un coup qu'elle avait manifestement vu. Les joueurs s'en aperçoivent, et ils le prennent mal. On cite souvent le concepteur Sid Meier pour avoir retiré de Civilization des fonctionnalités d'alliance, parce que l'ordinateur pouvait les exploiter presque aussi bien qu'un joueur ; l'effet, selon les mots de Meier cités par un exposé consacré à la conception des adversaires artificiels, aurait « laissé aux joueurs le sentiment qu'ils ne pouvaient pas gagner parce que l'ordinateur trichait ». 3 Une difficulté qui se lit comme une malhonnêteté empoisonne le jeu, et c'est pourquoi la littérature de recherche sur l'ajustement dynamique de la difficulté s'attache à régler ce dont l'IA est capable plutôt que ce qu'elle a le droit de voir. 5
WordChess règle ses quatre niveaux selon des axes qu'un humain reconnaîtrait, jamais en fournissant à l'IA des informations cachées. Les niveaux diffèrent par le temps de recherche accordé, par la profondeur à laquelle leur vocabulaire puise dans le dictionnaire rare, et par les tranches de longueur de mots qu'ils privilégient. Un adversaire facile joue des mots plausiblement faibles : réels, sensés, courts, pas du charabia. Un grand maître partage avec le niveau difficile tout le lexique obscur, et dispose du plus de temps pour l'exploiter. Le joueur perd face à quelque chose qui ressemble à un meilleur vocabulaire et à une lecture plus fine, parce que c'est exactement ce dont il s'agit.
| Niveau | Étendue du vocabulaire | Budget de recherche | Longueur de mots privilégiée |
|---|---|---|---|
| Facile | Courants seulement | Le plus court | Courts |
| Normal | Courants + intermédiaires + moitié des rares | Court | Mixte |
| Difficile | Complet | Long | Plus longs |
| Grand maître | Complet | Le plus long | Sans limite |
Une calculatrice renvoie toujours la même réponse ; un adversaire vous surprend. WordChess ajoute à la sélection une étape délibérément aléatoire, afin que des coups de valeur voisine ne soient pas toujours départagés de la même façon et que l'IA ne rejoue pas le même mot à chaque fois. Combiné aux plafonds de vocabulaire propres à chaque niveau, l'effet produit est la variété : le sentiment que quelqu'un est assis en face de vous et fait des choix, dont certains auraient pu être les vôtres.
C'est là l'art discret de la chose. Un adversaire crédible a besoin de retenue autant que de force : la disposition à jouer un mot simplement bon, à laisser des points sur la table, à être battable d'une manière qui semble méritée. Le problème d'ingénierie le plus difficile de la machine était de fouiller la botte de foin. Le plus subtil fut d'apprendre quand cesser de chercher, quoi savoir, et combien en retenir.