… Et Scrabble prouvé PSPACE-Complet

Ayant été inventé aux États-Unis au milieu du 20e siècle, le Scrabble est maintenant disponible dans des dizaines de langues et se vend en nombre mesuré par centaines de millions. Cela en fait l'un des jeux les plus populaires au monde.

Cela a naturellement suscité l'intérêt des théoriciens des jeux. Étant donné que le Scrabble est un jeu si réussi, il devient naturel de déterminer la complexité de calcul pour trouver un jeu optimal, déclarent Michael Lampis du KTH Royal Institute of Technology en Suède et quelques amis.

La même question a été posée avec succès pour de nombreux jeux de société, tels que les échecs, Go et Othello, qui ont tendance à être complets avec PSPACE ou EXPTIME. Mais le Scrabble est plus délicat car les joueurs ne connaissent pas l'ordre dans lequel les tuiles seront tirées, ce qui signifie que le hasard joue un plus grand rôle.

La question à laquelle Lampis et ses collaborateurs tentent de répondre est la suivante : étant donné une position au Scrabble, à quel point est-il difficile de déterminer la meilleure stratégie de jeu ?

Ils soulignent qu'à n'importe quel tour, un joueur de Scrabble est confronté à deux tâches : décider quel mot former et décider où le placer sur le plateau. Ces tâches sont liées car les mots qui peuvent être formés dépendent de la position des lettres sur le tableau.

Mais laquelle de ces tâches rend le Scrabble difficile ? Ce que Lampis et ses collègues montrent, c'est que les deux sont durs et donnent des preuves de chacun pour étayer leur affirmation. C'est impressionnant car cela nous permet de « voir » pourquoi le Scrabble est difficile.

Nous établissons qu'au cours d'un jeu, les joueurs de Scrabble doivent effectuer non pas une, mais deux tâches informatiques difficiles, ce qui est probablement la raison pour laquelle le Scrabble est si amusant à jouer, écrivent-ils.

Cela ne veut pas dire que les théoriciens de la complexité computationnelle sont finis et saupoudrés de Scrabble. Leur prochaine tâche est de découvrir s'il existe un algorithme en temps polynomial pour déterminer le mouvement qui maximiserait le score obtenu dans ce tour.

Maintenant, ce serait pratique !

Réf : arxiv.org/abs/1201.5298 : Scrabble est PSPACE-Complet

cacher