Hey guys!

So I've been wondering . . . Did anyone try to incorporate a SAT solver into their games? Or another Non-Polynomial time algorithm solver? From my knowledge of the universe, many problems involve non-polynomial time algorithms, and it may be rather limiting in some cases to restrict games to only handling P problems. As an example, the n-clique problem could be solved to find individual groups of friends within a virtual friend-sim game, or the graph-colouring problem could be solved to colour the procedurally-generated map of a game where the stylistic art restrictions demand only a few colours. These aren't the best of examples, but NP problems often crop up, and when they do, it's nice to be able to solve them efficiently.

It may be bothersome to solve these problems by hand each time they arise, especially if they're NP-complete. Instead, it's often possible to reduce an NP problem to something like SAT, and use a dedicated solver. I haven't done this, but it seems like an interesting way to approach the problem! I do admit that many games would not benefit from such a thing, but it might be an interesting idea to think about.

On an interesting note, it seems that many games (Sudoku, Go, Skyrim, etc.) create NP mini-problems for players to solve, perhaps masked under layers of game storyline and randomness. Most notable in typical video games is the Knapsack problem: given limited inventory space and items of different weight and value, which combination of items results in the greatest profit? I skimmed through this paper (https://arxiv.org/abs/1203.1895) which shows that many games are essentially NP challenges to the player, which is interesting to consider.

I guess one other application I can think of an NP-solver in video games is the availability of challenges for the player that go beyond NP. NP consists of problems that are difficult to solve, but easy to verify. Perhaps some games could offer problems that are difficult to solve, and difficult to verify, requiring an NP solver just to verify the winning condition. The usefulness of this is questionable, but might create a unique gameplay mechanic that would have been impossible before.

I guess. It was more of a conversation thing ^^ I'm not too familiar with forum structure to be honest, sorry!

... but NP problems often crop up, and when they do, it's nice to be able to solve them efficiently.

NP problems are the more interesting problems to use in a game, I think. I mean, there is a reason why tic-tac-toe is not an AAA game :p

For very small instances of NP problems, it may be feasible to compute the answer. ie NP means it scales extremely badly, but in a game, you don't ever want to handle that size of a problem, as it becomes meaningless to a player. Lots of times however, the optimal answer is not interesting. Instead you run a simulation of the thing, and you get performance values. Games like simcity, or all the transport games, or in general, games where several different branches compete for the same resources, you make solving the NP problem a problem for the player, you just show results.