Les mathématiciens ont essayé de prouver à quel point The Witness est difficile – avec des résultats surprenants
📱
“Chaque type d’indice a fini par offrir un problème intéressant à étudier.”
The Witness est un jeu curieux et pointilleux. D’une part, il est présenté comme un champion de la prétention. D’autre part, il est largement salué pour sa complexité mathématique. Les règles du témoin sont cartographiées par des symboles sur ses grilles d’échiquier, et bien qu’elles semblent assez simples, il se passe beaucoup plus qu’il n’y paraît – à tel point que certains étudient exactement ce qui rend les problèmes du témoin difficiles au niveau du doctorat.
Erik Demaine, professeur d’informatique au MIT, se concentre principalement sur la recherche et l’enseignement, et combine souvent les deux en chargeant les étudiants de résoudre des problèmes ouverts en groupe. Pour ce faire, Demaine utilise un style de recherche hautement collaboratif appelé supercollaboration.
Selon le site de Demaine – lié ci-dessus – la supercollaboration est une méthode de recherche innovante où les chercheurs résolvent des problèmes complexes sans se soucier de la paternité ou de l’ego. Il s’agit littéralement d’une super collaboration, dans la mesure où le travail d’équipe positif et efficace prime sur la contribution individuelle. Si vous êtes particulièrement intéressé, j’ai intégré une vidéo d’un cours enseigné à l’aide d’un modèle super collaboratif ci-dessous.
Demaine était l’un des principaux auteurs d’un article de 2018 intitulé Qui témoigne de The Witness ?, qui fournit un cas exemplaire de recherche supercollaborative tout en extrapolant simultanément ce qui fait de The Witness un jeu intéressant pour les doctorants en mathématiques et en informatique : principalement sa difficulté.
Pour ceux qui ne connaissent pas le terme “témoin” dans un contexte mathématique, c’est une valeur spécifique sous-jacente à une déclaration existentielle – fondamentalement, c’est une entité utilisée pour différencier quelque chose existant, quelque chose existant dans au moins un cas, et quelque chose existant étant donné certains conditions. Dans le cas de The Witness, le témoin minuscule a à voir avec la manière dont les énigmes sont réellement résolues – il s’agit de savoir quelle stratégie réussit et quel(s) chemin(s) à travers une grille représente cela.
Alors, qui est témoin du témoin ? En fin de compte, c’est remarquablement difficile à dire – et c’est pourquoi c’est si attrayant sur le plan académique.
L’équipe de Demaine étudie souvent les jeux afin de rechercher des algorithmes efficaces et d’analyser des problèmes informatiques insolubles comme moyen de tracer des solutions innovantes qui sont souvent dérivées du champ gauche.
“En général, nous voulions essayer de délimiter la frontière entre les aspects de calcul faciles et les aspects de calcul difficiles des énigmes de The Witness”, explique Demaine. “Certaines énigmes utilisent un type d’indice, tandis que d’autres utilisent un mélange de types d’indices. Nous voulions comprendre quels mélanges font des énigmes difficiles à résoudre pour les ordinateurs, et donc probablement [also] difficiles pour les humains, et qui sont en fait faciles à résoudre pour les ordinateurs – bien que cela ne signifie pas qu’ils sont nécessairement faciles pour les humains.”
“Ce dernier est rare en général lors de l’analyse des puzzles de cette manière, donc le cas des monominos était assez excitant”, ajoute-t-il.
L’épreuve de dureté est l’un des principaux objectifs de la recherche et de l’enseignement de Demaine. L’art de prouver la dureté est difficile : il s’agit de trouver une preuve de la difficulté d’un problème en le transformant ou en le réduisant en une forme problématique distincte. En cours de route, des algorithmes intéressants pouvant être appliqués ailleurs sont découverts – lutter contre les calculs difficiles engendre des solutions de simplification, ce qui signifie arriver à quelque chose qui est finalement plus facile à utiliser en compliquant davantage ce qui se cache sous le capot.
Adam Hesterberg est un autre chercheur crédité sur Qui assiste au témoin ? Alors qu’il était doctorant en mathématiques au MIT lorsqu’il a commencé à travailler avec Demaine, il étudie maintenant l’informatique au niveau post-doctoral. Pour lui, The Witness avait l’air “informatiquement intéressant”.
“Je n’avais pas joué à The Witness jusqu’à ce que nous décidions de travailler sur sa complexité informatique, bien que je fasse des énigmes logiques similaires”, me dit-il. “J’aime les jeux de société, que ce soit les jeux de gestion des ressources économiques à l’allemande comme Gaia Project ou n’importe quoi de Vlaada Chvátil, d’après qui j’ai nommé mon appartement. Notre groupe de recherche écrit occasionnellement des articles sur d’autres jeux.”
Le groupe de Demaine a commencé à travailler sur Qui assiste au Témoin ? en 2016, deux ans avant qu’il ne soit publié en tant qu’article FUN (de l’International Conference of Fun with Algorithms) en 2018. Il aboutira finalement à un article de journal complet co-écrit par 10 universitaires de trois départements du MIT, et un université en Allemagne.
Cependant, ils ne se concentrent pas uniquement sur The Witness: le groupe de Demaine se débat également avec des systèmes informatiques dans une variété d’autres jeux, appliquant généralement les mêmes preuves de dureté afin de prouver la difficulté et de découvrir des algorithmes alternatifs.
“La complexité informatique des jeux et des puzzles est un sujet qui me tient à cœur et que j’étudie depuis environ 2000”, explique Demaine. “Mon premier article portait sur Clickomania, que nous avons récemment revisité.”
Demaine souligne que ses articles sur Tetris étant NP-complet – ce qui signifie qu’il peut être résolu par une classe restrictive d’algorithmes de recherche par force brute – et Super Mario Bros. étant PSPACE-complet, ce qui est beaucoup plus complexe – comme certains de ses plus populaires réalisations dans le domaine à ce jour. Mais qu’est-ce qui distingue The Witness ? “Quand The Witness est sorti, cela semblait être un jeu naturel à aborder, offrant une variété de différents types de puzzles/indices”, explique Demaine. “Parce qu’une partie du jeu consiste à comprendre ce que signifient réellement les indices, nous avons d’abord averti le groupe que nous allions étudier The Witness et encouragé ceux qui voulaient éviter les spoilers à jouer au jeu et à comprendre les choses par eux-mêmes.
“Quelques semaines plus tard, nous nous sommes lancés dans l’analyse, et chaque type d’indice a fini par offrir un problème intéressant à étudier.”
Jeffrey Bosboom, qui est doctorant au MIT depuis 2011 et co-auteur de Qui assiste à The Witness ?, a rencontré The Witness pour la première fois lorsqu’il a été évoqué lors d’une des sessions hebdomadaires de supercollaboration de l’équipe. “Cela signifie que j’ai été gâté par la plupart des types de puzzles”, me dit-il. “Mais je n’ai pas l’impression qu’être gâté a réduit mon plaisir quand j’y ai joué ; les énigmes d’introduction dans chaque domaine sont de toute façon didactiques, et c’était toujours amusant de ressentir la transition d’une connaissance explicite (être capable de dire à quelqu’un la signification d’un symbole ) à la connaissance implicite (regarder un puzzle et reconnaître immédiatement quelle doit être la solution).”
L’une des choses les plus inhabituelles à propos des puzzles de The Witness est que certains sont Sigma_2-complete, note Demaine. Pour ceux qui ne savent pas trop ce que cela signifie – ce que j’étais certainement ! – Sigma_2-complétude fait référence à un point dans la hiérarchie polynomiale, qui présente une variété de différents niveaux de complexité de résolution de problèmes.
La NP-complétude implique de résoudre des problèmes en utilisant la force brute ; Sigma_2-completeness est un pas en avant par rapport à cela ; et l’exhaustivité PSPACE est encore plus complexe, en rapport avec le temps polynomial (le temps qu’il faut à un ordinateur pour résoudre un problème) et la complexité temporelle (la complexité de calcul du temps qu’il faut à un ordinateur pour exécuter un algorithme spécifique).
C’est un peu difficile à analyser, mais selon Demaine The Witness, les énigmes – du moins celles comportant des “anticorps”, sur lesquelles j’y reviendrai dans une minute – sont plantées fermement au milieu des trois, existant comme “un niveau au-dessus de l’exhaustivité NP habituelle, tout en étant bien en dessous de l’exhaustivité PSPACE commune aux puzzles qui nécessitent un nombre exponentiel de mouvements – comme les blocs coulissants ou l’heure de pointe”.
Rush Hour est le jeu de logique classique des embouteillages.
Les indices étiquetés comme “anticorps” dans le document, qui sont les règles logiques qui annulent l’effet d’autres indices dans la même région d’un puzzle donné, ont un qualificatif de “nécessité” inhérent qui nécessite une approche légèrement plus hypothétique de la résolution de problèmes. . Cela augmente la complexité de calcul et fournit un éventail intéressant de problèmes qui peuvent être transformés les uns dans les autres afin de proposer de nouveaux algorithmes efficaces (transformer un problème sous une autre forme est également une qualité de Sigma_2-complétude).
“Un autre cas inhabituellement intéressant était The Witness avec juste des indices monomino”, ajoute Demaine. Un monomino est un seul carré d’un polyomino, qui est une forme formée en cousant ensemble des carrés de taille égale. Le témoin comporte des grilles dans les deux formes.
“[It] se réduit à des hexagones à la frontière d’un puzzle, qui s’avèrent tous deux résolubles par un algorithme efficace », ajoute Demaine. La réduction est la transformation d’un problème en une autre variante plus complexe de lui-même, et est souvent utilisée dans l’étude de dureté, tandis que les « hexagones » désignent des arêtes ou des sommets qui doivent être visités pour satisfaire une solution. Comme le note Demaine, il s’agit d’une étape importante de la découverte et de la définition des algorithmes.
“Dans de telles énigmes, le but est effectivement de trouver un chemin visitant des sommets et/ou des arêtes spécifiés sur la frontière d’un graphe planaire, ce qui est une sorte de problème de chemin hamiltonien de sous-ensemble”, dit-il. “Notre algorithme pour résoudre ce problème présente un intérêt au-delà des énigmes.”
“Le chemin hamiltonien du sous-ensemble s’inscrit dans le domaine plus large des algorithmes de graphes (et non de l’analyse de casse-tête), il contribue donc à ce domaine plus large”, ajoute Demaine. “Au départ, nous essayions simplement de résoudre un puzzle amusant – les monominos dans The Witness – et nous avons rencontré un problème de graphe d’intérêt général, puis nous l’avons résolu parce que nous voulions résoudre le puzzle.
“Mais la contribution finit par être beaucoup plus large que” nous avons résolu un puzzle “- nous avons également proposé un algorithme de graphe qui pourrait aider à résoudre d’autres problèmes.”
“Mon puzzle préféré dans The Witness est le puzzle audio sans audio dans la chambre anéchoïque de la ville”, explique Bosboom. “C’est un puzzle facile, il suffit de vérifier que vous comprenez la correspondance entre les deux différents types de panneaux de puzzle audio, mais c’est le puzzle qui m’a donné le sentiment le plus prononcé de réfléchir avec les concepteurs du puzzle.
“En ce qui concerne ma carrière universitaire, The Witness est une source très riche de problèmes intéressants en matière de complexité informatique, qui est également populaire et intéressante pour de nombreuses autres personnes”, ajoute-t-il. “C’est un très bon – [but] pas parfait – jeu. Il n’y a rien de mystique là-dedans.”
Aux yeux de Demaine, la plupart des jeux sont suffisamment intéressants pour étudier les risques du point de vue de la complexité informatique. “Même les jeux avec de petites quantités de casse-tête peuvent être assez intéressants”, explique-t-il. “Par exemple, deux de nos co-auteurs sur The Witness ont écrit un autre article FUN 2018 sur la façon dont la coopération dans des jeux comme Team Fortress 2 ou Super Smash Bros. ou Mario Kart rend ces jeux très, très difficiles sur le plan informatique.”
“Il est difficile de formaliser ce que signifie pour un jeu d’être ‘fun'”, ajoute-t-il. “Mais je pense que l’une des raisons pour lesquelles les gens aiment jouer à des jeux est qu’ils sont difficiles, et cette recherche formalise ce que cela signifie pour un jeu d’être difficile, nous abordons donc un aspect fondamental du plaisir dans les jeux.”
Selon Demaine, certains chercheurs se plaignent que l’étude des jeux est récréative, sous-entendant que le domaine est une perte de temps.
“Mais je pense que la recherche en informatique récréative est une voie d’étude importante”, dit-il. “En particulier, cela motive les étudiants à faire de la recherche, et cela rend la recherche particulièrement amusante à faire.”
Découvrez d’avantage plus d’articles dans nos catégories Astuce, Consoles et Jeux.
Merci pour votre visite on espère que notre article Les mathématiciens ont essayé de prouver à quel point The Witness est difficile – avec des résultats surprenants
, pour nous aider, on vous invite à partager l’article sur Facebook, twitter et e-mail avec les hashtags ☑️ #Les #mathématiciens #ont #essayé #prouver #quel #point #Witness #est #difficile #avec #des #résultats #surprenants ☑️!