With the advent of BWAPI, many AI enthusiasts have been making amazing AIs that can compete against top players in Starcraft. This led me to wonder if RTS (Real-Time Strategy) games can ever be solved theoretically.

One of my colleague argues no, because RTS games are non-deterministic and stochastic. What does this mean exactly? For instance, in Starcraft you have a set of defined and limited moves (I.E: Units, buildings, economy) you can make in the game, so I don't see what can be so stochastic about the game.

enter image description here

  • 4
    $\begingroup$ The word you are looking for is "winning strategy", rather than "solution", I think. The game is not stochastic (maybe a little bit?). It is a game of several players, without perfect information. It is very unlikely that there is a winning strategy for it. Though I don't know if that can be proved or disproved. $\endgroup$ Jan 14 '13 at 14:56
  • 1
    $\begingroup$ The idea isn't new and you can find some papers on Google $\endgroup$
    – Vor
    Jan 14 '13 at 15:23
  • 2
    $\begingroup$ For any kind of proof, you need a formal model. Do you have one for Brood War? As it stands, the question is open-ended and asks for guesswork: how can anybody know whether any RTS game can be algorithmically won at any future point in time? (The concept of building "intelligent" bots for SC is exciting, though.) $\endgroup$
    – Raphael
    Jan 14 '13 at 19:15
  • $\begingroup$ What does this mean exactly? Maybe the best person to ask is your colleague? It is unclear what the sources of non-determinism are in Starcraft. Also, what do you mean by "solved theoretically"? $\endgroup$
    – mhum
    Jan 15 '13 at 0:28
  • $\begingroup$ @Raphael As Karolis pointed out, the meaning of "solved game" in this particular context refers to determining a particular winning strategy or a proof that such strategy does not exist. At least that's what I think but I'm all ears for other interpretations. $\endgroup$
    – l46kok
    Jan 15 '13 at 1:17

It looks like there are elements of (pseudo)randomness in StarCraft.

Of course, this does not seem like a major property and you can ask for solving the game without this feature. Then you end up with a very deep game tree that probably does not have any nice mathematical property or symmetry that would help you to effectively handle it. This is where it differs from the trees that arise from mathematical games.

You can use game theory to play StarCraft well (Monte Carlo, maybe?), but unless there is some strong form of rush that would quickly cut complexity of the tree, I am skeptical about solving it.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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