5 ms·

Is this technique scalable to more complex games?

devindotcom 9y ago
In a way it's necessary already for procedural generation, right? You can't have a level where the key to open a room is inside the room itself. So these nesting dependencies have to be carefully defined.
- rcthompson 9y ago
  Not necessarily. I believe a lot of games simply use a set of heuristics to check for unwinnable situations after generating a scenario. These are usually based on unwinnable states that play testers have encountered, so there is no guarantee that they are exhaustive, and most procedurally generated games have a small chance to produce an unwinnable scenario.
- jsnell 9y ago
  No, there's a difference between "this scenario is solvable with perfect play" and "it is impossible for the player to make moves that make the game unsolvable".
- logfromblammo 9y ago
  Part 2 of Zork featured exactly that scenario. And you could render the room unreachable if you did things in the wrong sequence.
CJefferson 9y ago
In the past I've looked at some models of games. Most human playable adventure games have a fairly small state space, unless you do something cute like embed chess in it :) The only tricky bit is you want to avoid modelling the exact pixel location of every object / player if at all possible, but need to make sure your simplifications don't end up hiding some unsolvable corners.
JoshTriplett 9y ago
Depends on what you mean by "more complex". This uses cbmc, a formal model checker that runs relatively fast, and that doesn't require writing excessively complex formalisms to ask "is this state reachable". The README mentions a variation on this approach that scales to larger games. Now, if you built a game isomorphic to a traveling salesman problem, or other exponential problem, then the model checker might have a problem with that. But so would a human; such a game would get extremely tedious. So, I'd venture as far as "this should scale to adventure games that humans enjoy playing".
- WorldMaker 9y ago
  > "this should scale to adventure games that humans enjoy playing" I'm not sure that premise holds. Admittedly it's a different genre, but a lot of puzzle games are in exponential/NP-Hard/NP-Complete spaces. Tetris is an obvious example as a simple reduction of the packing problem. Humans very much enjoy playing those. Even just restricting it to the genre of "adventure games", I'd be hesitant to say that there can't be games with very complex state spaces that humans enjoy playing. Maybe especially with "adventure games" where if the story and writing are interesting enough players will put up with a very wide variety of puzzles and exploration styles.
  - lmm 9y ago
    > Tetris is an obvious example And is unwinnable.
- drdrey 9y ago
  I don't think it's fair to associate "tediousness" with the computational complexity of the underlying problem. Some games are Turing complete (Factorio, Dwarf Fortress, Minecraft, Braid...)
  - JoshTriplett 9y ago
    This wouldn't work for open-ended sandboxes like Minecraft or Dwarf Fortress, and not just because you can build a Turing machine in those. I'm talking about adventure-style games that have a defined solution and way to "win", and the complexity of computing that solution. In that regard, games that require a full backtracking search and aren't amenable to shortcuts tend to become tedious. As an example, it's entirely possible to build an adventure game puzzle equivalent to an arbitrary SAT problem.
cowardlydragon 9y ago
I'd guess the complexity is dependent on the decision graph complexity: cyclic vs acyclic, entrance/exit points... If it gets to conditional / puzzle evaluation that starts to get Turing Complete, then it will hit the halting problem, which I believe is thought to be noncomputable for nontrivial graphs / code. https://en.wikipedia.org/wiki/Halting_problem https://en.wikipedia.org/wiki/Halting_problem
makapuf 9y ago
Yes but only if computed on fpga with open-source tooling. (thanks to Clifford for that also !) no this is not completely nonsensical...

In a way it's necessary already for procedural generation, right? You can't have a level where the key to open a room is inside the room itself. So these nesting dependencies have to be carefully defined.

rcthompson 9y ago
Not necessarily. I believe a lot of games simply use a set of heuristics to check for unwinnable situations after generating a scenario. These are usually based on unwinnable states that play testers have encountered, so there is no guarantee that they are exhaustive, and most procedurally generated games have a small chance to produce an unwinnable scenario.
jsnell 9y ago
No, there's a difference between "this scenario is solvable with perfect play" and "it is impossible for the player to make moves that make the game unsolvable".
logfromblammo 9y ago
Part 2 of Zork featured exactly that scenario. And you could render the room unreachable if you did things in the wrong sequence.

CJefferson 9y ago

In the past I've looked at some models of games. Most human playable adventure games have a fairly small state space, unless you do something cute like embed chess in it :) The only tricky bit is you want to avoid modelling the exact pixel location of every object / player if at all possible, but need to make sure your simplifications don't end up hiding some unsolvable corners.

JoshTriplett 9y ago

Depends on what you mean by "more complex". This uses cbmc, a formal model checker that runs relatively fast, and that doesn't require writing excessively complex formalisms to ask "is this state reachable". The README mentions a variation on this approach that scales to larger games. Now, if you built a game isomorphic to a traveling salesman problem, or other exponential problem, then the model checker might have a problem with that. But so would a human; such a game would get extremely tedious. So, I'd venture as far as "this should scale to adventure games that humans enjoy playing".

WorldMaker 9y ago
> "this should scale to adventure games that humans enjoy playing" I'm not sure that premise holds. Admittedly it's a different genre, but a lot of puzzle games are in exponential/NP-Hard/NP-Complete spaces. Tetris is an obvious example as a simple reduction of the packing problem. Humans very much enjoy playing those. Even just restricting it to the genre of "adventure games", I'd be hesitant to say that there can't be games with very complex state spaces that humans enjoy playing. Maybe especially with "adventure games" where if the story and writing are interesting enough players will put up with a very wide variety of puzzles and exploration styles.
- lmm 9y ago
  > Tetris is an obvious example And is unwinnable.
drdrey 9y ago
I don't think it's fair to associate "tediousness" with the computational complexity of the underlying problem. Some games are Turing complete (Factorio, Dwarf Fortress, Minecraft, Braid...)
- JoshTriplett 9y ago
  This wouldn't work for open-ended sandboxes like Minecraft or Dwarf Fortress, and not just because you can build a Turing machine in those. I'm talking about adventure-style games that have a defined solution and way to "win", and the complexity of computing that solution. In that regard, games that require a full backtracking search and aren't amenable to shortcuts tend to become tedious. As an example, it's entirely possible to build an adventure game puzzle equivalent to an arbitrary SAT problem.

cowardlydragon 9y ago

I'd guess the complexity is dependent on the decision graph complexity: cyclic vs acyclic, entrance/exit points... If it gets to conditional / puzzle evaluation that starts to get Turing Complete, then it will hit the halting problem, which I believe is thought to be noncomputable for nontrivial graphs / code. https://en.wikipedia.org/wiki/Halting_problem https://en.wikipedia.org/wiki/Halting_problem

makapuf 9y ago

Yes but only if computed on fpga with open-source tooling. (thanks to Clifford for that also !) no this is not completely nonsensical...