4 ms·
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 comp
by JoshTriplett 10y 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 10y 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 10y ago> Tetris is an obvious example And is unwinnable.
- drdrey 10y agoI 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 10y agoThis 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.
- mjn 10y agoEven embedded exponential problems can be fine, since existing solvers in the SAT/SMT/ASP/etc. family working on finite domains like these can usually heuristically solve them in reasonable time. I did some work on formally modeling game mechanics in answer-set programming [1] for a prototyping system a few years ago [2], and in my case model size rather than complexity was almost always the bottleneck. And the biggest model-size culprit was just numerical stuff. If you have a game with a lot of numerical state variables (e.g. health of units), you get big explosions in the size of the state space, which even when the queries are trivial, end up taking the solver longer just to construct the space than solving complex problems in smaller state spaces does. By contrast very discrete-type games (that don't involve a lot of numerical status meters) worked great, even if they have a complex logical structure and you have complex questions to ask about their possibility space. However if you do have a numerically heavy game, SMT solvers can handle that too (the "modulo" part of satisfiability modulo theories can factor out things like the "theory of integers"). In my case I used ASP, specifically the Potassco suite [3], because imo the modeling language is friendlier, especially for incremental modeling, and I was more interested in investigating expressivity than scaling at the time. [1] https://en.wikipedia.org/wiki/Answer_set_programming https://en.wikipedia.org/wiki/Answer_set_programming [2] Some papers: http://www.kmjn.org/publications/Mechanics_AIIDE08-abstract.html http://www.kmjn.org/publications/Mechanics_AIIDE08-abstract...., http://www.kmjn.org/publications/Playtesting_AIIDE09-abstract.html http://www.kmjn.org/publications/Playtesting_AIIDE09-abstrac..., http://www.kmjn.org/publications/Ludocore_CIG10-abstract.html http://www.kmjn.org/publications/Ludocore_CIG10-abstract.htm... [3] https://potassco.org/ https://potassco.org/
- forgotpwtomain 10y agoIt occurs to me that there should be some kind of strategy that allows for simplified computation of numerical state variables though? Since in a lot of cases the value being within a certain range is more important than it's exact amount (e.g. HP > max damage of a single blow, or of MP is >= spell cost). Intuitively I'd probably want to try some kind probability-density function to represent numerical stats.
- Sunset 10y ago
- forgotpwtomain 10y ago> So, I'd venture as far as "this should scale to adventure games that humans enjoy playing". I'm really not sure about this one. Consider for example a savefile in an Angband-variant and whether a character can leave the dungeon alive (that's easy to define formally '@' on tile '>' with at 1 free turn seq and hp > 0), but I imagine the backtracking is going to be a very expensive computation...
- JoshTriplett 10y agoTrue. I should clarify that I meant "point-and-click adventure" or "text adventure". I don't think this method would work at all for a roguelike.