Hacker News Reader

Comment by Retr0spectrum | Hacker News Reader

Is this technique scalable to more complex games?

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".

> "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.

> Tetris is an obvious example

And is unwinnable.

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...)

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.

Even 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

[2] Some papers: http://www.kmjn.org/publications/Mechanics_AIIDE08-abstract...., http://www.kmjn.org/publications/Playtesting_AIIDE09-abstrac..., http://www.kmjn.org/publications/Ludocore_CIG10-abstract.htm...

[3] https://potassco.org/

It 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.

You can even go with something like: Can the player cast >n spells. Or Is the players Average DPS > Boss's HP regen per second. Without having to care about the exact numbers.

> 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...

True. 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.

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.

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.

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.

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".

Part 2 of Zork featured exactly that scenario.

And you could render the room unreachable if you did things in the wrong sequence.

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

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

Reply on news.ycombinator.com