game-solver

Un moteur d’échecs cherche un bon coup dans un temps donné. Un solveur cherche autre chose : la valeur exacte de la position, sous l’hypothèse que personne ne se trompe plus. Ce sont deux métiers, et le second ne rend une réponse qu’après l’avoir démontrée.

Deux jeux tournent aujourd’hui : le morpion, qui tient dans une poignée de nœuds, et le Puissance 4, qui est la vraie cible. La méthode est un negamax alpha-bêta mémorisé, compilé en WebAssembly depuis de l’AssemblyScript et réparti dans un pool de workers, un par cœur, une colonne chacun, avec un repli en JavaScript si le WASM manque. Chaque coup possible reçoit alors son étiquette exacte : gagne, perd, ou nulle.

C’est là que la combinatoire se fait sentir. Analyser la position vide au Puissance 4 coûte une dizaine de minutes, ce qui est intenable dans une interface : l’analyse par coup ne démarre donc qu’au septième coup joué, et avant cela le solveur se contente d’une heuristique sûre, jouer au centre et ne jamais entrer dans une ligne perdante. Le budget est plafonné à huit millions de nœuds par worker.

La justesse ne se juge pas à l’œil sur ce genre de programme : les positions de test sont confrontées au solveur de référence de Pascal Pons, qui donne la valeur attestée. Un solveur qui se trompe en silence est plus gênant qu’un moteur médiocre, puisqu’il prétend démontrer.