1
$\begingroup$

There is a lot of introductory literature about artificial intelligence for time and space discrete games, like chess. A few fundamental methods are offered:

  • Minimax to depth $n$ with an evaluation function will pick a move that reliably leads to the outcome best according to that evaluation function after $n$ further moves. There is a whole industry of building evaluation functions, but the principle is simple.

  • A monolithic policy function simply weighs all possible moves and picks the heaviest. It will commonly be a fancy neural network. There is a whole industry of building policy functions, but the principle is simple.

  • Weighted random search learns by playing randomly many times and giving more weight to those moves which lead to victory more often. There is a whole industry of building the distribution of random moves, but the principle is simple.

None of these methods apply to games played in continuous space (or a finely enough discrete space) or continuous time (or a discrete time where interesting events are sparse). An example of such a game is StarCraft.

There are two methods a computer plays StarCraft:

  • A bespoke handcrafted algorithm with many moving parts, such as build order, path finding, micro control. This is expensive because you need a lot of human effort and expertise.

  • A neural network that takes screen pictures to mouse clicks. This is expensive because you need a lot of hardware and electricity.

So, anyone can write an entertaining, if not dominating, artificial intelligence for a discrete game, but only very few can afford to write an artificial intelligence for a continuous game that is any better than inept. This is a sad conclusion.

Is there anything I am missing? Are there any helpful methods out there that I have not mentioned? Is there a way to adapt discrete methods to continuous games? 

It seems that the difference in principle is that, in continuous games, we need to create a new move from scratch every time instead of picking out of a small set. If we simply create random moves, many of them will be inadmissible — trying to build stuff that cannot be afforded, sending units to unreachable places. Of those which are admissible, the majority will be meaningless random walking of units. The subset of moves that have any measurable meaning is tiny, and even the best single move has only tiny effect on the outcome. If we could make the computer generate a small amount of plausible moves, then we can apply discrete methods. But how do we teach the computer to generate plausible moves?

$\endgroup$
6
  • $\begingroup$ RL works fine in continuous state space, what you are referring to are tree based/search based methods, which are obv hard to apply in continuous cases $\endgroup$
    – Alberto
    Commented Jun 11 at 10:04
  • $\begingroup$ @Alberto   I know one can teach a snake to gather fruits with reinforcement learning, or something such. I am not sure if this would work for games where all the reward is concentrated in the end. Would it? $\endgroup$ Commented Jun 11 at 11:29
  • $\begingroup$ RL is an algorithm that does not make any assumption on the reward function, except that they are in $R$ (thus no $+-\infty$), so yes it can work $\endgroup$
    – Alberto
    Commented Jun 11 at 14:52
  • $\begingroup$ @Alberto If you write an answer explaining the application of reinforcement learning to a realistically complicated continuous problem (like StarCraft), I shall give you a vote at once. $\endgroup$ Commented Jun 13 at 20:36
  • $\begingroup$ I mean... deepmind.google/discover/blog/… ... they probably know better than me $\endgroup$
    – Alberto
    Commented Jun 13 at 20:42

0

You must log in to answer this question.

Browse other questions tagged .