Catégories
Jeux Vidéo

Les mathématiciens ont essayé de prouver à quel point le témoin est difficile

"Chaque type d'indice a fini par offrir un problème intéressant à étudier."

The Witness est un jeu curieux et persévérant. D'une part, il est annoncé comme un champion de la prétention. De l'autre, 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 de choses que ce qui semble évident – à tel point que certains étudient ce qui rend exactement 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 est, littéralement, supercollaboratif, dans la mesure où le travail d'équipe positif et efficace prime sur les contributions individuelles. Si vous êtes particulièrement intéressé, j'ai intégré une vidéo d'une classe enseignée à l'aide d'un modèle supercollaboratif ci-dessous.

Pour voir ce contenu, veuillez activer le ciblage des cookies.

Demaine a été l'un des principaux auteurs d'un article de 2018 intitulé Qui est témoin du témoin?

Pour ceux qui ne connaissent pas le terme "témoin" dans un contexte mathématique, c'est une valeur spécifique insérée dans une déclaration existentielle – fondamentalement, c'est une entité utilisée pour différencier quelque chose d'existant, quelque chose d'existant dans au moins un cas, et quelque chose d'existant étant donné certains conditions. Dans le cas de The Witness, le témoin minuscule a à voir avec la façon dont les énigmes sont réellement résolues – il s'agit de savoir quelle stratégie est réussie, et quel chemin à travers une grille représente cela.

Alors, qui est témoin du témoin? En fin de compte, il est remarquablement difficile à dire – et c'est pourquoi c'est si académiquement attrayant.

1 "data-uri =" 2020 / articles / 2020-07-06-23-24 /itness_1.jpg "/></figure>
<p>L'équipe de Demaine étudie souvent les jeux afin de rechercher des algorithmes efficaces et d'analyser les problèmes intraitables en termes de calcul afin de retrouver des solutions innovantes souvent dérivées du champ gauche.</p>
<p>"En général, nous voulions essayer de délimiter la frontière entre les aspects faciles à calculer et difficiles à calculer des puzzles du Témoin", explique Demaine. "Certains puzzles utilisent un type d'indice, tandis que d'autres utilisent un mélange de types d'indices. Nous voulions comprendre quels mélanges rendent les puzzles difficiles à résoudre pour les ordinateurs, et donc probablement (aussi) difficiles pour les humains, et qui sont en fait faciles pour les ordinateurs. à résoudre – bien que cela ne signifie pas qu'ils sont nécessairement faciles pour les humains. "</p>
<p>"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.</p>
<p>L'essai 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 raison pour laquelle un problème est difficile en le transformant ou en le réduisant en une forme problématique distincte. En cours de route, des algorithmes intéressants qui peuvent être appliqués ailleurs sont découverts – aux prises avec les solutions de simplification difficiles à calculer, ce qui signifie arriver à quelque chose qui est finalement plus facile à utiliser en compliquant davantage ce qui est sous le capot.</p>
<p>Adam Hesterberg est un autre chercheur crédité sur Qui est le témoin du témoin? Bien qu'il fût 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 semblait "intéressant sur le plan informatique".</p>
<p>"Je n'avais pas joué The Witness jusqu'à ce que nous décidions de travailler sur sa complexité informatique, bien que je fasse des puzzles logiques similaires", me dit-il. "J'aime les jeux de société, que ce soit des jeux de gestion des ressources économiques à l'allemande comme Gaia Project ou n'importe quoi de Vlaada Chvátil, du nom duquel j'ai nommé mon appartement. Notre groupe de recherche rédige parfois des articles sur d'autres jeux."</p>
<figure class=

Pour voir ce contenu, veuillez activer le ciblage des cookies.

Le groupe de Demaine a commencé à travailler sur Qui est témoin du témoin? en 2016, deux ans avant sa publication en tant que document FUN (de la Conférence internationale du plaisir avec des algorithmes) en 2018. Il aboutira finalement à un article de revue 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 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 était sur Clickomania, que nous avons récemment revu."

Demaine souligne que ses articles sur Tetris sont NP-complets – 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? "Lorsque The Witness est sorti, cela semblait être un jeu naturel à aborder, offrant une variété de différents types de puzzles / indices en son sein", explique Demaine. "Parce qu'une partie du jeu consiste à comprendre ce que les indices signifient réellement, nous avons d'abord averti le groupe que nous allions étudier The Witness, et avons encouragé ceux qui voulaient éviter les spoilers à jouer au jeu et à comprendre les choses par eux-mêmes."

"Quelques semaines plus tard, nous sommes entrés dans l'analyse, et chaque type d'indice a fini par offrir un problème intéressant à étudier."

Jeffrey Bosboom, qui est un étudiant au doctorat au MIT depuis 2011 et co-auteur de Who témoins The Witness?, A rencontré The Witness pour la première fois lors de son apparition 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 ne me sens pas gâté réduit mon plaisir quand je l'ai joué; les puzzles d'introduction dans chaque domaine sont de toute façon didactiques, et c'était toujours amusant de sentir la transition de la 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 des puzzles The Witness est que Sigma_2-complet, note Demaine. Pour ceux qui ne savent pas trop ce que cela signifie – ce que j'étais certainement! – Sigma_2-exhausteness fait référence à un point de la hiérarchie polynomiale, qui présente différents niveaux de complexité de résolution de problèmes.

La complétude NP implique la résolution de problèmes en utilisant la force brute; Sigma_2-exhausteness est un pas en avant; et la complétude de PSPACE est encore plus complexe, ayant à voir avec le temps polynomial (le temps qu'il faut à un ordinateur pour résoudre un problème) et la complexité du temps (la complexité de calcul du temps qu'il faut à un ordinateur pour exécuter un algorithme spécifique).

2 "data-uri =" 2020 / articles / 2020-07-06-23-24 /itness_3.jpg "/></figure>
<p>C'est un peu difficile à analyser, mais selon Demaine, les énigmes du Témoin – au moins celles contenant des «anticorps», que j'aborderai dans une minute – sont plantées fermement au milieu des trois, existant en tant que «niveau par rapport à l'exhaustivité NP habituelle, tout en étant bien en deçà de l'intégralité PSPACE commune aux puzzles qui nécessitent de façon exponentielle de nombreux mouvements – comme des blocs coulissants ou des heures de pointe ".</p>
<figure class=4
Rush Hour est le jeu de logique classique des embouteillages.

Les indices étiquetés comme «anticorps» dans l'article, 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 une gamme intéressante de problèmes qui peuvent être transformés les uns pour les autres afin de proposer de nouveaux algorithmes efficaces (la transformation d'un problème sous une autre forme est également une qualité de Sigma_2-compléteness).

"Un autre cas inhabituellement intéressant était The Witness avec juste des indices monomino", ajoute Demaine. Un monomino est un carré unique d'un polyomino, qui est une forme formée en cousant des carrés de taille égale. Le témoin présente des grilles sous les deux formes.

"(Il) 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 la dureté, tandis que les «hexagones» se réfèrent à 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 d'algorithmes.

"Dans de telles énigmes, le but est effectivement de trouver un chemin qui visite des sommets et / ou des bords spécifiés à la frontière d'un graphe planaire, ce qui est une sorte de problème de chemin hamiltonien sous-ensemble", dit-il. "Notre algorithme pour résoudre ce problème présente un intérêt au-delà des simples énigmes."

"Le chemin hamiltonien du sous-ensemble s'inscrit dans le champ plus large des algorithmes de graphes (pas dans l'analyse des puzzles), il contribue donc à ce champ plus large", ajoute Demaine. "À l'origine, nous essayions simplement de résoudre un puzzle amusant – les monominos dans The Witness – et nous avons rencontré un problème graphique de grand intérêt, puis 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 casse-tête "- nous avons également trouvé un algorithme graphique qui pourrait aider à résoudre d'autres problèmes."

"Mon casse-tête préféré dans The Witness est le casse-tête audio sans audio dans la salle de 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 penser avec les concepteurs de puzzle.

"Pour ce qui est de 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 – (mais) pas parfait – jeu. Il n'y a rien de mystique."

3 "data-uri =" 2020 / articles / 2020-07-06-23-25 ​​/itness_7.jpg "/></figure>
<p>Aux yeux de Demaine, la plupart des jeux sont suffisamment intéressants pour étudier les dangers du point de vue de la complexité informatique. "Même les jeux avec des quantités mineures de puzzles peuvent être assez intéressants", explique-t-il. "Par exemple, deux de nos co-auteurs de 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 à calculer."</p>
<p>"Il est difficile de formaliser ce que cela signifie qu'un jeu soit" amusant "", ajoute-t-il. "Mais je pense que l'une des raisons pour lesquelles les gens aiment jouer à des jeux est parce qu'ils sont difficiles, et cette recherche formalise ce que cela signifie pour un jeu d'être difficile, donc nous obtenons un aspect fondamental du plaisir dans les jeux."</p>
<p>Selon Demaine, certains chercheurs se plaignent que l'étude des jeux est récréative, ce qui implique que le terrain est une perte de temps. </p>
<p>"Mais je pense que la recherche en informatique récréative est une voie d'étude importante", dit-il. «En particulier, cela stimule les étudiants à faire de la recherche, et cela rend la recherche particulièrement amusante.»</p>
</div>
<p><script>
				// For login with Facebook functionality
				function appendFacebookSDK() {
					window.fbAsyncInit = function () {
						FB.init({
							appId: '156247124404264',
							version: 'v2.7',
							channelUrl: '/channel.html',
							status: true,
							cookie: true,
							xfbml: true,
							oauth: true
						});
					};</p>
<p>					// Load the SDK Asynchronously
					(function (d) {
						var js, id = 'facebook-jssdk', ref = d.getElementsByTagName('script')(0);
						if (d.getElementById(id)) {
							return;
						}
						js = d.createElement('script');
						js.id = id;
						js.async = true;
						js.onload = function () {
							if (typeof runFacebookLogin == 'function') {
								runFacebookLogin();
							}
							if (typeof runFacebookRegistrationLogin == 'function') {
								runFacebookRegistrationLogin();
							}
						};</p>
<p>												js.src =

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *