Y a-t-il une réduction des jeux de «porte et plaque de pression» qui n'explose pas la longueur de la solution?

Cet article prouve que dans un jeu avec des portes et des plaques de pression, il est difficile pour PSPACE de déterminer si l'avatar (du joueur) peut atteindre un emplacement donné. Cela est prouvé par une réduction de TQBF , et la longueur des solutions résultantes dépend exponentiellement du nombre de quantificateurs universels dans la formule.

Y a-t-il une réduction d'une machine NPSPACE à un tel jeu pour lequel la longueur des solutions du jeu est polynomialement liée à la longueur des chemins d'acceptation de la machine?

Vous pouvez peut-être facilement simuler un LBA; l'idée est la suivante:

• pour chaque cellule de la bande LBA, ajoutez un gadget de cellule qui ne peut être saisi que par le bas et sorti uniquement par le haut;$G_i$

• le gadget possède une porte d'entrée qui simule la position de la tête (un seul est ouvert à chaque pas);C $C_i$$C_i$

• alors il y a deux portes de bits et ; est ouvert si la cellule contient un zéro, est ouvert s'il y a une cellule;O i Z i O $Z_i$$O_i$$Z_i$$O_i$

• les deux portes de mors mènent à une structure de contrôle similaire qui est faite par plusieurs couloirs à sens unique ; un couloir correspond à un état du LBA, et la porte du ème couloir est ouverte si et seulement si l'état actuel du LBA est ; i q $q_i$$i$$q_i$

• selon la table de transition (éventuellement non déterministe) du LBA, une traversée du couloir (ouvert) modifie l'état actuel du LBA et la configuration des portes de bits, ferme la porte et ouvre ou .C i + 1 C i - $C_i$$C_{i+1}$$C_{i-1}$

Un gadget de cellule est esquissé dans la figure ci-dessous.

Des choix non déterministes peuvent être réalisés en divisant les couloirs des structures de contrôle en deux sous-couloirs ou plus, comme illustré dans la figure ci-dessous.

Remarque: si une plaque ne peut ouvrir / fermer qu'une seule porte, vous pouvez ajouter une structure auxiliaire avec des couloirs unidirectionnels (longs) qui (dés) activent les portes d'état distinctes de chaque cellule.

Un autre moyen rapide de prouver le Metatheorem 2c (dureté PSPACE lorsque les portes sont contrôlées par deux plaques) est d'utiliser le cadre logique de contrainte non déterministe ( RA Hearn et ED Demaine, Le modèle logique de calcul de contrainte non déterministe: réductions et applications ).

Dans ce cas, il suffit d'utiliser une série horizontale de paires de couloirs verticaux. L'état de chaque paire de couloirs représente la direction (vers l'intérieur / vers l'extérieur) d'une arête dans le graphique de contraintes d'origine. Il suffit de simuler le gadget AND et le gadget OR, comme illustré dans la figure ci-dessous.

ce type de recherche sur le lien entre les jeux vidéo et la complexité de calcul est assez intrigant mais il est également assez récent, généralement vieux de moins d'une décennie. Je soutiendrai ici qu'il y a parfois une subtilité qui manque parfois dans les analyses actuelles [je n'ai pas vu / remarqué cela souligné dans l'article cité ou dans d'autres articles jusqu'à présent] et qui empêche de répondre définitivement à la question posée.

pour prouver une relation avec un système de calcul, il faut être capable de mapper le système de calcul sur le jeu et vice versa. par exemple, dans l'article cité ci-dessus par Viglietta, il existe un concept selon lequel les plaques de pression et les portes (c'est-à-dire les portes de commande des plaques de pression) peuvent être "similaires" aux QBF. cette analogie est certainement viable car ils l'ont tracée. on peut utiliser un QBF pour résoudre un jeu avec des plaques de pression et des portes.

cependant, voici la subtilité. dans un jeu donné, les dispositions du jeu sont fondamentalement fixes. dans la conception de jeux vidéo, le concept de différentes mises en page est appelé "conception de mises en page" et n'est pas une "donnée" de tous les jeux. Par exemple, dans le jeu révolutionnaire Doom, les outils de conception de niveaux étaient open source, c'est-à-dire mis à la disposition des joueurs. en d'autres termes, la conception de niveaux arbitraires peut être considérée comme faisant partie du jeu. mais dans d'autres jeux considérés dans les journaux, les jeux vidéo tels que construits à l'origine ont des niveaux fixes. les documents n'en tiennent parfois pas explicitement compte.

par conséquent, il y a un argument solide à faire valoir que dans la plupart des jeux sans conception de niveaux ou dispositions aléatoires, les niveaux sont fixes, ce qui a un impact important sur la complexité réelle de la résolution du "jeu". c'est-à-dire, qu'est-ce que le "jeu" exactement? comprend-il des dispositions aléatoires et / ou une possibilité de conception de niveau? la conception de niveaux fait-elle partie de la cartographie informatique? ces questions sont passées sous silence dans les articles actuels.

Poussé à l'extrême opposé des articles, on pourrait dire que toutes les implémentations de jeux vidéo réels sont résolubles par les FSM car ils ont une mémoire finie !

pour qu'il y ait de vrais mappages de calcul, il faut essentiellement généraliser le jeu pour impliquer

• niveaux avec une taille arbitraire! afin que cela puisse être mappé sur des MT avec des bandes "d'entrée" de taille arbitraire / illimitée.
• conception de niveaux qui permet la création de ces niveaux.

un problème de mappage légèrement similaire se pose dans la recherche CA / Cellular Automata où il existe des idées sur l'utilisation de motifs périodiques infinis sur les CA comme "motifs de départ" pour prouver l'équivalence / l'exhaustivité de la MT.

Donc, en général, votre question n'est pas strictement définie tant que vous ne clarifiez pas mieux (c.-à-d . définissez de façon plus formelle / mathématique ) ce que vous entendez par "dans un jeu avec des portes et des plaques de pression" et d'une manière que même le papier ne définit pas apparemment strictement, en particulier écrit des idées sur la conception de niveaux, des niveaux de taille illimités, etc. mais avis que les « jeux » définis avec ces caractéristiques puis ont été abstraire loin des jeux vidéo réelle / réelle d'une manière très significative.

Donc, en bref, je pense que cette recherche est intéressante / utile, même si elle débute comme quelque peu informelle, et mérite des progrès supplémentaires, mais dans une certaine mesure, sa formalisation doit être rendue plus stricte, en particulier dans les définitions de base, si elle veut progresser davantage. il doit faire une distinction plus stricte / formelle / transparente entre les implémentations et les abstractions .