Avant de jouer, l'IA doit trouver son coup au milieu d'une botte de foin de cent cinquante mille mots, puis cesser sa recherche.
Donnez à une personne un porte-mots WordChess et l'instruction « joue un bon mot », et elle réduira le problème sans même s'en rendre compte. L'ordinateur ne bénéficie d'aucune telle intuition. Sur un 25×25 plateau, en ayant accès à la réserve complète de cent lettres, 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 encore, un placement n'est légal que si chaque nouvelle lettre qu'il introduit complète également un mot réel là où elle croise ce qui est 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, en silicium ou autrement, ne peut énumérer et classer intégralement.
C'est la raison pour laquelle les moteurs de jeux de mots sérieux, Quackle, l'implémentation de référence en open source, entre autres, ne forcent jamais le dictionnaire par la force brute.4 La structure GADDAG de Steven Gordon de 1994, et le DAWG avant cela, laissez un programme faire croître des mots à partir des tuiles déjà présentes sur le plateau et vérifiez les croisements au fur et à mesure, afin que les branches illégales meurent tôt plutôt que d'être notées puis écartées.1 La tâche n'est pas de « lister tous les mots ». Elle consiste à « générer uniquement les coups qui pourraient éventuellement être légaux, et le faire rapidement. »
Même un générateur économe renvoie plus de coups candidats qu'il n'est possible d'en évaluer en profondeur, si bien que le deuxième problème est le temps. Le programme de Scrabble le plus puissant jamais construit, celui de Brian Sheppard, Maven, a fait face à exactement cela et y a répondu en deux étapes: une heuristique rapide trie les coups bruts dans un ordre approximatif de qualité, et seule une liste restreinte des plus prometteurs est étudiée attentivement en simulant la partie de nombreuses fois vers l'avant pour voir quel candidat performe réellement le mieux.2 Sheppard a emprunté le nom de cette idée à d'autres jeux, ce que le backgammon appelle un rollout et le Go un playout, il l'a appelé simulation.
WordChess fonctionne dans le même esprit, sous une contrainte plus stricte : un budget de temps de recherche fixe par coup. Lorsque le budget est épuisé, l'IA s'engage sur le meilleur mot qu'elle a trouvé jusqu'alors. Ce n'est pas un compromis dont les ingénieurs regrettent ; c'est l'ensemble de la conception. Un joueur qui réfléchit indéfiniment n'est pas un adversaire meilleur, seulement plus lent. L'horloge force la machine à faire ce que les humains font instinctivement, se contenter d'un coup clairement bon plutôt que prouvablement optimal.
Le dictionnaire n'est pas l'esprit de l'adversaire. L'horloge, si.
La façon paresseuse de rendre une IA de jeu plus facile est de la rendre stupide au hasard, de la faire trébucher sur un coup qu'elle voyait clairement. Les joueurs le remarquent, et ils en sont mécontents. Le concepteur Sid Meier est souvent cité pour avoir supprimé des Civilization fonctionnalités permettant à l'ordinateur de négocier mieux que les joueurs, car l'effet, selon un compte rendu sur la conception des adversaires IA , « laisserait les joueurs avec le sentiment qu'ils ne pouvaient pas gagner parce que l'ordinateur trichait. »3 Une difficulté qui se lit comme une déloyauté empoisonne le jeu, c'est pourquoi la littérature de recherche sur l'ajustement dynamique de la difficulté se préoccupe de régler ce que l'IA est capable de faire plutôt que ce qu'elle est autorisée à voir.5
WordChess ajuste ses quatre niveaux le long d'axes qu'un humain reconnaîtrait, jamais en fournissant à l'IA des informations cachées. Chaque niveau diffère par la durée pendant laquelle il peut chercher, la profondeur dans le dictionnaire rare que sa vocabulaire atteint, et les bandes de longueur de mots qu'il privilégie. Un facile adversaire joue des mots faibles mais plausibles, réels, sensés, courts, pas du n'importe quoi. A grand-maître dispose de tout le lexique obscur et du temps pour l'exploiter. Le joueur perd face à quelque chose qui ressemble à un vocabulaire plus riche et à une lecture plus fine, car c'est exactement ce que c'est.
| Niveau | Portée du vocabulaire | Budget de recherche | Tendance de longueur des mots |
|---|---|---|---|
| Facile | Courants uniquement | Plus courts | Court |
| Normal | Courants + intermédiaires | Court | Mixte |
| Difficile | Large | Long | Plus long |
| Grand maître | Rare complet | Le plus long | Sans limite |
Une calculatrice donne toujours la même réponse ; un adversaire vous surprend. WordChess ajoute une étape aléatoire délibérée, anti-copie, à la sélection, de sorte que les coups quasi égaux ne sont pas toujours résolus de la même manière et que l'IA ne se contente pas de refléter votre dernier coup. Combinée aux plafonds de vocabulaire par niveau, l'effet est la variété, le sentiment que quelqu'un est assis de l'autre côté du plateau en faisant des choix, certains desquels vous auriez pu faire aussi.
C'est là que réside l'art discret de la chose. Un adversaire crédible a besoin de retenue autant que de force : la volonté de jouer un mot simplement bon, de laisser des points sur la table, d'ê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 chercher dans la meule. Le plus subtil était d'apprendre quand cesser de chercher, quoi savoir et combien se retenir.