Duh!
You know something? Optimal simulation of storytelling is NP-hard for Grand Argument Stories.
Proof: A GAS can be encoded as an extended regex (a regular expression that includes backreferences to its own states previously in the processing). The GRAPH 3-COLORABILITY problem, which is known to be NP-hard, can be reduced to regex matching with backreferences. Thus, a GAS is equivalent to GRAPH 3-COLORABILITY in computational complexity: NP-hardness (at least).
Therefore, given some interactive storytelling system that refers to a GAS structure, finding compression algorithms that increase the system's storytelling efficiency - save some computational resources, particulary at runtime, by reusing objects - is possible, but none can be found that can compress the informational substrate, namely, the foundational Character Elements and their quad-wise interplay. Storytelling effectiveness - which I measure as "number of pleasant surprises per player per session" - can only ever be increased by human authors. Everything that's not reused - i.e., all "information" in the sense of (Algorithmic) Information Theory - needs to be thought-out and written before program execution, if the GAS structure is to be preserved during the interaction
Okay then. At least I know what's up.
Proof: A GAS can be encoded as an extended regex (a regular expression that includes backreferences to its own states previously in the processing). The GRAPH 3-COLORABILITY problem, which is known to be NP-hard, can be reduced to regex matching with backreferences. Thus, a GAS is equivalent to GRAPH 3-COLORABILITY in computational complexity: NP-hardness (at least).
Therefore, given some interactive storytelling system that refers to a GAS structure, finding compression algorithms that increase the system's storytelling efficiency - save some computational resources, particulary at runtime, by reusing objects - is possible, but none can be found that can compress the informational substrate, namely, the foundational Character Elements and their quad-wise interplay. Storytelling effectiveness - which I measure as "number of pleasant surprises per player per session" - can only ever be increased by human authors. Everything that's not reused - i.e., all "information" in the sense of (Algorithmic) Information Theory - needs to be thought-out and written before program execution, if the GAS structure is to be preserved during the interaction
Okay then. At least I know what's up.
scheuring - 13. Jun, 11:23
