Este documento demuestra que en un juego con puertas y placas de presión, es difícil para PSPACE determinar si el avatar (del jugador) puede o no alcanzar una ubicación determinada. Esto se demuestra mediante una reducción de TQBF , y la longitud de las soluciones resultantes depende exponencialmente del número de cuantificadores universales en la fórmula.
¿Existe una reducción de una máquina NPSPACE a un juego para el que la longitud de las soluciones del juego está polinomialmente relacionada con la longitud de las rutas de aceptación de la máquina?
reductions
nondeterminism
pspace
Jeffε
fuente
fuente
Respuestas:
Quizás pueda simular fácilmente un LBA; La idea es la siguiente:
Un dispositivo celular se bosqueja en la figura a continuación.
Se pueden realizar elecciones no deterministas dividiendo los corredores en las estructuras de control en dos o más subcorredores como se muestra en la figura a continuación.
Nota: si una placa solo puede abrir / cerrar una sola puerta, entonces puede agregar una estructura auxiliar con corredores unidireccionales (largos) que (des) activen las puertas de estado distintas de cada celda.
fuente
Otra forma rápida de probar el Metatheorem 2c (dureza PSPACE cuando las puertas están controladas por dos placas) es usar el marco lógico de restricción no determinista ( RA Hearn y ED Demaine, el modelo lógico de restricción no computacional de cómputo: reducciones y aplicaciones ).
En este caso, es suficiente usar una serie horizontal de corredores-pares verticales. El estado de cada par de corredores representa la dirección (hacia adentro / hacia afuera) de un borde en el gráfico de restricción original. Es suficiente simular el gadget AND y el gadget OR, como se muestra en la figura a continuación.
fuente
Este tipo de investigación de relacionar los videojuegos con la complejidad computacional es bastante intrigante, pero también es bastante nuevo, generalmente tiene menos de una década. Argumentaré aquí que hay sutilezas que a veces se pasan por alto en los análisis actuales [no he visto / notado esto señalado en el documento citado u otros documentos hasta ahora] y eso impide responder definitivamente a la pregunta planteada.
Para probar una relación con un sistema computacional, uno debe ser capaz de mapear el sistema computacional en el juego y viceversa. Por ejemplo, en el artículo de Viglietta citado anteriormente, existe el concepto de que las placas de presión y las puertas (es decir, las puertas de control de las placas de presión) pueden ser "similares" a los QBF. Esta analogía es ciertamente viable ya que la han trazado. uno puede usar un QBF para resolver un juego con placas de presión y puertas.
Sin embargo, aquí está la sutileza. en un juego dado, los diseños del juego son básicamente fijos. En el diseño de videojuegos, el concepto de diferentes diseños se llama "diseño de diseño" y no es un "dado" de todos los juegos. Por ejemplo, en el innovador juego Doom, las herramientas de diseño de niveles fueron de código abierto, es decir, se pusieron a disposición de los jugadores para su uso. en otras palabras, el diseño de nivel arbitrario puede considerarse parte del juego. pero en otros juegos considerados en documentos, los videojuegos como se construyeron originalmente tienen niveles fijos. los documentos a veces no tienen esto explícitamente en cuenta.
por lo tanto, hay un fuerte argumento para argumentar que en la mayoría de los juegos sin diseño de niveles, o diseños aleatorios, los niveles son fijos, y esto tiene un gran impacto en la complejidad real de resolver el "juego". es decir, ¿qué es exactamente el "juego"? ¿incluye diseños aleatorios y / o posibilidad de diseño de nivel? ¿Es el diseño de nivel parte de la asignación computacional? estos temas se pasan por alto en algunos artículos actuales.
llevado al extremo opuesto de los documentos, se podría argumentar que todas las implementaciones de videojuegos reales son solucionables por FSM porque tienen memoria finita .
para que haya mapeos computacionales reales, básicamente uno debe generalizar el juego para involucrar
surge un problema de mapeo ligeramente similar en la investigación de CA / Autómatas Celulares donde hay ideas sobre el uso de patrones periódicos infinitos en las AC como "patrones iniciales" para probar la equivalencia / integridad de TM.
así que, en general, su pregunta no está estrictamente definida hasta que aclare mejor (es decir, defina más formal / matemáticamente ) lo que quiere decir con "en un juego con puertas y placas de presión" y de una manera que incluso el documento aparentemente no define estrictamente, especialmente Wrt a ideas sobre diseño de niveles, niveles de tamaño ilimitados, etc. pero aviso de que los "juegos" con estas características definidas a continuación, se han abstraído lejos de los juegos de vídeo real / real de una manera muy significativa.
en resumen, creo que esta es una investigación interesante / que vale la pena, aunque comienza como algo informal, y merece un mayor avance, pero hasta cierto punto su formalización debe hacerse más estrictamente especialmente en las definiciones básicas para avanzar más. debe hacer una distinción más estricta / formal / transparente entre las implementaciones y las abstracciones .
fuente