Pourquoi certains jeux ne sont-ils pas complets?

J'ai lu l'article de Wikipédia sur " Liste des problèmes NP-complets " et constaté que des jeux comme Super Mario, Pokemon, Tetris ou Bonbons Crush Saga sont sans fin. Comment puis-je imaginer la n-complétude d'un jeu? Les réponses n'ont pas besoin d'être trop précises. Je veux juste avoir un aperçu de ce que cela signifie que les jeux peuvent être complets.

Cela signifie simplement que vous pouvez créer des niveaux ou des énigmes dans ces jeux qui encodent des problèmes NP-Hard. Vous pouvez résoudre un problème de coloration de graphique, créer un niveau associé à Super Mario Bros. et ce niveau est configurable si et seulement si le graphique contient 3 couleurs.

Si vous voulez voir la manière spécifique dont les problèmes de NP-Complete sont traduits dans les jeux, je vous recommande le document "Les jeux Nintendo classiques sont difficiles (par ordinateur)" . C'est bien écrit et facile à suivre.

Une mise en garde importante à garder à l'esprit est que la dureté NP nécessite de généraliser les jeux de manière "évidente". Par exemple, Tetris a normalement un tableau de taille fixe mais la preuve de la dureté exige que le jeu autorise des tableaux arbitrairement grands. Un autre exemple est celui des ennemis hors écran dans Super Mario Bros: la preuve en est une variante du jeu dans laquelle les ennemis hors écran continuent à se déplacer comme s'ils étaient à l'écran, au lieu de cesser d'exister et d'être réinitialisés à leur position de départ lorsque Mario revient .

Honnêtement, je ne sais pas exactement quel type de modèle est utilisé par les auteurs de ces réclamations; Cependant, ce qui me semble raisonnable serait de parler de la décider de quelque chose à propos d'une situation de jeu.$\mathcal{NP}$

Prenons comme exemple Tetris, car c’est le seul de ceux que vous citez et que je comprends assez pour en parler. Tetris a une règle appelée "Perfect Clear", qui donne au joueur un gros bonus si une chute de pièce efface entièrement le tableau. On peut se demander si, étant donné une séquence ordonnée de pièces et un entier , il existe une séquence légale de déplacements pour les pièces qui permet d'obtenir au moins effacements parfaits. Les énoncés de problème tels que ceux qui sont suffisamment abstraits peuvent être modélisés avec les outils de la théorie de la complexité.k P $\{P_i\}$$k$$P$$k$

La longue histoire courte, " -complete" signifie une chose et une seule chose, des affirmations fantaisistes telles que "Super Mario is -complete" doivent être traduites en une déclaration formelle avant de sens.N $\mathcal{NP}$$\mathcal{NP}$

Voici une explication simpliste en agitant la main:

Ces jeux sont en NP car il est efficace de "gérer" le comportement d'un joueur au cours d'une partie et de vérifier s'il gagne ou perd (nous avons besoin que ce soit en temps polynomial dans la durée de la partie, mais c'est probablement linéaire ou -ish).$O(n \log(n))$

De tels jeux sont NP-difficiles car le comportement du joueur est très expressif. Bien qu’à un moment donné, un joueur ne puisse avoir qu’un nombre limité, voire fixe, d’actions, cela suffit pour créer un espace de comportements ou de stratégies exponentiels dans la durée de la partie; et bien que vous puissiez fournir une condition simple ou une formule logique sur la validité / le bénéfice / la correction des actions d'un joueur localement, globalement, vous obtenez un effet similaire à celui obtenu avec un grand circuit combinatoire ou une formule k-CNF.

Espérons que cela a un sens intuitif et sonne également assez de cloches de la théorie CS.

PS - Certains jeux sont beaucoup plus complexes (sur le plan informatique) que cela. Par exemple, les jeux de société Hex , Go et Reversi sont PSPACE-complete. C'est essentiellement parce que la formule que vous devez satisfaire pour une stratégie gagnante est une formule de quantificateur alternant plusieurs fois: Il existe un coup du joueur 1, tel que pour chaque coup du joueur 2, il existe un coup du joueur 1, etc. de telle sorte qu'avec tous ces mouvements ayant été joués, certains des mouvements du joueur 2 sont invalides ou nous avons une séquence valide que le joueur 1 a gagné. Avec les jeux NP, il s’agit généralement du comportement, de la stratégie et du choix des mouvements d’un joueur.

Pour les jeux à un seul joueur, vous pouvez toujours poser la question "Existe-t-il une stratégie gagnante pour le joueur", et cette question a souvent une réponse "OUI" qui peut être vérifiée en temps polynomial, et peut très bien être NP complète.

Pour les parties à deux joueurs, la réponse ne peut souvent pas être vérifiée en temps polynomial, car pour vérifier qu'un coup pour A est un coup gagnant, vous devez démontrer que pour chaque réponse de B, il y aurait de nouveau un coup gagnant pour A et bientôt.

Eh bien, c’est certainement dans NP, car une solution possible est juste un nombre fini d’entrées (dans chaque image, vous pouvez sélectionner l’un des k boutons, nous représentons chaque sélection de boutons pour chaque image avec une lettre) qui vous amène à l'écran de victoire. Nous savons que ce jeu a déjà été battu, donc nous savons qu’il existe une solution. Une MNT examine sa bande et devine comme par magie un certificat correct de longueur n. Ensuite, il simule Super Mario avec l'entrée et le vérifie. La vérification peut être faite en temps polynomial (temps linéaire en fait, si la solution est correcte, il faudra exactement n images pour gagner).

Pour montrer que NP est complet, nous pourrions y réduire 3-SAT en construisant un vérificateur 3-Sat avec le générateur de niveau (construit par exécution de code arbitraire https://www.youtube.com/watch?v=IOsvuEA2h4w ).

Nous avons donc une entrée 3-SAT CNF dans laquelle nous vérifions d’abord le bon formatage. S'il est mal formaté, nous le traduisons simplement en une entrée 'jump' (il n'est pas possible de battre Super Mario dans une image en effectuant un saut).

Nous appelons la longueur de l'entrée 3-CNF n.

S'il est correctement formaté, nous le traduisons en un certain nombre d'entrées, ce qui construit le vérificateur 3-CNF pour nous (toujours le même code de longueur k), traduit le 3-CNF en une chaîne d'entrées, qui construit le 3- CNF dans le vérificateur (en O (n)), et vérifie toutes les solutions possibles par force brute. Il ne fonctionne pas et ne fait rien si, après avoir passé en revue toutes les solutions, aucune solution n’est trouvée. Il redémarre le jeu et utilise une solution connue permettant à Super Mario de battre le jeu (le code à suivre est de longueur j). Notre transformation est donc en O (n), donc dans le temps polynomial.

Si le format CNF est mal formaté, nous ne gagnons pas (par définition, notre contribution n’est pas gagnante, si nous n’avons pas gagné une image après son exécution). Si la CNF n'est pas satisfiable, nous ne gagnons pas (vous ne pouvez pas gagner en ne tournant au ralenti qu'une image dans le générateur de niveau, nous nous en sommes assurés dans notre code). Si le CNF est satisfaisant, le vérificateur trouve une solution qui redémarre et gagne la partie. Ainsi, la réduction polynomiale de 3-Sat à Super Mario est terminée et nous avons prouvé que Super Mario est NP-complet.

(J'espère que je ne l'ai pas gâché quelque part. Nous rencontrons un problème de stockage, si le 3-CNF est trop long, mais le stockage limité est généralement ignoré dans ces contextes, je crois.)

J'ai réécrit cette réponse pour essayer d'adresser quelques commentaires sur une version précédente.

Je suppose que vous avez lu la définition de Wikipedia pour NP-complétude qui ne se concentre pas vraiment sur les jeux. Je vais juste clarifier un peu le sens exact de NP-complétude et de la théorie des jeux et expliquer l’essence d’un jeu NP-Complete.

Considérons une partie à 2 joueurs avec des mouvements alternatifs. Plus restrictivement, il s’agit essentiellement de jeux combinatoires . Fondamentalement, un jeu dans lequel vous avez un certain nombre de mouvements que vous pouvez effectuer et vous devez en choisir un. Vous aimeriez jouer "parfaitement", ce qui signifie que vous ne feriez jamais un "mauvais" coup. Donc, parmi les mouvements autorisés, vous souhaitez sélectionner le meilleur. (Bien sûr, votre adversaire a le même objectif ...)

Notez que le jeu parfait ne signifie pas que vous gagnerez toujours. Les règles du jeu peuvent être telles que le premier ou le deuxième joueur doit gagner. De plus, certains jeux comme Tic-Tac-Toe devraient se terminer par un match nul. Voici donc ce que "jeu parfait" signifie dans cette discussion:
(1) que vous ne serez jamais dans une position gagnante et que vous perdrez ensuite le jeu parce que vous avez fait un "mauvais" coup
(2) vous ne manquerez jamais une occasion d'obtenir dans la position gagnante si une telle opportunité se présente.

Dans l’état actuel du jeu, vous voudriez pouvoir utiliser un "algorithme efficace" pour calculer le meilleur coup. D'autre part, notons qu'un algorithme qui doit parcourir toute l'arborescence du jeu est un "algorithme inefficace".

Définissons maintenant «efficacité» un peu plus formellement. Je vais simplifier un peu mais l'essentiel est correct. Considérez le nombre de calculs, , qui doivent être effectués pour choisir le prochain mouvement, le premier moyen pour chaque mouvement ayant une possibilité (le facteur de branchement ) et le fait qu'il reste coups dans la partie. L'idée est également que chaque calcul prend le même temps pour que l'effort puisse être traduit en complexité temporelle , , au lieu de calculs bruts.B n $C$$B$$n$$T$

• Un "algorithme efficace" aura: où est un "petit entier," et ah sont de vrais nombres. Ainsi, l'algorithme efficace s'exécute en temps polynomial puisqu'il s'agit d'une expression polynomiale.
  $T \varpropto aB^a + bB^{\alpha-1} + cB^{\alpha-2} + ... + hB^0$
  $\alpha$
• Un "algorithme inefficace" aura: et cet algorithme s'exécute en temps exponentiel (c'est-à-dire en temps non polynominal). Le point ici est que lorsque devient plus grand, il en résulte une explosion combinatoire.
  $T \varpropto aB^n$
  $n$

Maintenant, l’important est qu’il est impossible d’avoir un algorithme efficace, le temps polynomial, qui joue parfaitement pour un jeu NP-complet. Pour jouer à la perfection, un problème NP-complet doit, par définition, être résolu par un algorithme inefficace fonctionnant en temps non polynomial.

Notez que le temps d'exécution concerne le nombre intrinsèque de calculs, pas le temps de réponse perçu par un humain. Pour un petit jeu comme Tic-Tac-Toe, l'ordinateur peut jouer tous les mouvements futurs possibles et toujours réagir rapidement tel que perçu par un humain.

Pour Nim, il est possible de créer un algorithme polynomial. À tout moment du jeu, l'algorithme peut calculer quel joueur a un coup gagnant et ce que ce coup devrait être.

Par contre, prenons le jeu de Qubic . (Vous essayez de faire une ligne de 4 dans une grille 3D. Il s'agit donc essentiellement d'un tic-tac-toe sur une grille 4x4x4.) Qubic est NP-complet, il n'y a donc pas d'algorithme polynomial pour calculer le prochain coup parfait. La seule façon de savoir si vous avez un coup gagnant est d'essayer tous les coups possibles des deux joueurs pour vérifier qu'un coup particulier est un gagnant, ou du moins pas un perdant.

En vérité, tout l’arbre de jeu de Qubic est suffisamment petit pour qu’il puisse être encodé dans un programme informatique qui fonctionne parfaitement. Ce que l’encodage signifie, c’est que tout l’arbre de jeu a été exploré et que tous les mouvements ont été calculés à l’avance. Ainsi, le programme peut essentiellement faire un appel rapide à la base de données en utilisant l'état actuel du conseil et obtenir le meilleur coup pour cet état sans avoir à effectuer la recherche arborescente à chaque fois qu'un déplacement doit être effectué. Ceci est vraiment un "triche" pour nos besoins ici.

Parlons maintenant des échecs pour discuter de la fonction d’évaluation en ignorant certaines des autres caractéristiques des programmes de jeu d’échecs. Les échecs sont encore un jeu non résolu . On ignore si le premier ou le deuxième joueur devrait gagner. Il n’est pas possible d’obtenir une position au sein du conseil et de prédire avec certitude qui va gagner. En fait, les échecs ont un tel arbre de jeu qu'il est impossible de parcourir tout cet arbre. Vous auriez besoin d'ordinateurs qui ne sont pas seulement 10 ou 100 fois plus rapides, mais des milliards de milliards de fois plus rapides que n'importe quel ordinateur actuel. (Il existe un espoir que l'informatique quantique puisse couper à travers ce nœud gordien.)

Pensez à la fonction d’évaluation des échecs comme donnant à chaque coup possible une probabilité d’être le meilleur coup. Ce que fait un programme d’échecs, c’est combiner regarder au-delà avec la fonction d’évaluation. Ainsi, le programme examine tous les mouvements possibles à venir jusqu'à atteindre un point où un "bon" score peut être attribué à la position du conseil. L’ordinateur évalue ainsi tous les chemins possibles dans l’arbre, puis choisit le chemin avec le meilleur score. Comme la recherche n’a jamais abouti à la fin du jeu pour tous les chemins en cours d’évaluation, tous les programmes d’échecs utilisent finalement une fonction d’évaluation imparfaite. (Si vous approchez de la fin du jeu, l'ordinateur pourra peut-être examiner tous les mouvements possibles.) Cela signifie qu'il sera peut-être possible de battre le programme même si le programme avait une position gagnante à un moment donné.