4 ms·

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 heuristic

by mjn 9y ago

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 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 9y ago
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.
- Sunset 9y ago
  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.

by mjn 9y ago

forgotpwtomain 9y ago

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.

Sunset 9y ago
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.