2
$\begingroup$

Given a fully deterministic single player resource management game with a pre-known finite number of turns and reasonably simple rules (eg, Farmville, if it were single player, deterministic, and ended after a certain number of turns), is it usually possible to write a computer program that can optimize the game in a reasonable amount of time? Details:

  • I'm trying to create such a game (sort of a M.U.L.E. clone, but not really). Players would compete individually to get the highest score under a given set of starting conditions. The game must be simple enough to be fun, but complex enough that someone can't write a computer program to rapidly optimize it. The game is semi-tedious (in its current form), so I encourage API/automated use.

  • Since the game is deterministic and finite, I realize that an optimization algorithm must exist. So my question really is: can someone always write an optimization algorithm that runs fast enough to be useful?

  • I realize the answer depends on the actual game I write, so I'm looking for one of these answers (roughly):

    • Give up. If you design a resource management game easy enough for people to understand, someone could easily design an algorithm to win it.

    • There's hope. Depending on how you design the game, it may or may not be possible to write a reasonable algorithm to optimize it. However, you have to be very careful.

    • Go for it. In general, there are no algorithms that can optimize most resource management games. Barring extreme conditions, any resource management game you design could not reasonably be optimized by a computer.

  • There are Farmville strategy guides online, but they focus on general strategy, not an explicit algorithm.

  • I realize this is a specific case of P != NP, and that's it theoretically possible to create simple questions that cannot be solved easily (eg, factor a product of two large primes) or even at all (eg, the halting problem), but I'm wondering if resource management games fall, in general, into the NP category.

  • For reference, the game will be a scaled down (and single player) version of:

https://github.com/barrycarter/bcapps/tree/master/YAMC

$\endgroup$

closed as unclear what you're asking by D.W., Juho, frafl, Luke Mathieson, vonbrand Jan 23 '14 at 18:45

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ In Farmville, you can by some linear programming determine what to plant, i.e. what will maximize your profit versus the time needed for growing. Then again there is the human factor (you know you can harvest in 4 hours, will you be there to do that?) Also, most people probably play the game for fun -- that means doing things that don't even aim to maximize rewards, but rather building things that look pretty, or whatever :-) You could consider giving the game multiple objectives as well (see Pareto optimality). $\endgroup$ – Juho Jan 3 '14 at 1:42
  • $\begingroup$ It is not clear what you are asking. If the question is "can you solve the game in polytime?" the answer is either "it depends on the game" or "not in general", but that question is too broad. If your question is "can you solve my specific game in polytime?", then you haven't provided enough details. We can't answer that question without a specification of the game. The question needs to be self-contained and contain all necessary information in the question itself (not in an external link). Sorry, but I don't know the rules of Farmville. (continued) $\endgroup$ – D.W. Jan 3 '14 at 8:03
  • $\begingroup$ (cont.) So, I recommend you edit the question to focus on just one of those two questions (be clear which you are asking; don't try to ask both), and if you're asking about a specific game, provide a full specification of that game. Be warned in advance: If your game is too complex, this question is not likely to be of use to anyone else and not a good fit for this site. $\endgroup$ – D.W. Jan 3 '14 at 8:04
2
$\begingroup$

In general, you cannot hope for a polytime solution to all such games. For many such games, the problem of playing them optimally is NP-hard.

For instance, Minesweeper (on a $n\times n$ grid) is NP-hard, and thus does not have a polytime algorithm to solve it (unless $P=NP$, which most consider unlikely). The same is true for Sudoku (on a $n^2 \times n^2$ grid) and Tetris. Optimal play for chess, checkers, Go, and Scrabble (on a $n \times n$ grid) is either EXPTIME-complete or PSPACE-complete (depending upon whether you put a bound on the number of moves that a player can make), so they too are very unlikely to have any polytime algorithm to play them optimally (unless the polytime hierarchy collapses or something equally surprising).

In fact, I've seen some folks suggest that there's a strong connection here: the best games tend to be ones where finding the optimal solution is asymptotically hard. If finding the optimal solution was too easy, the argument goes, the game wouldn't be fun for humans. Obviously, this is not a rigorous argument and it is easy to come up with counterexamples, but I think there might be something to it.

There's lots more written on this sort of topic. For a entry point and overview, see, e.g., the following:

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.