Body: <p>There is a lot of introductory literature about artificial intelligence for time and space discrete games, like chess. A few fundamental methods are offered:</p>
  <ul>
  <li><p>Minimax to depth <span class="math-container">$n$</span> with an evaluation function will pick a move that reliably leads to the outcome best according to that evaluation function after <span class="math-container">$n$</span> further moves. There is a whole industry of building evaluation functions, but the principle is simple.</p>
  </li>
  <li><p>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.</p>
  </li>
  <li><p>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.</p>
  </li>
  </ul>
  <p>None of these methods apply to games played in continuous space <em>(or a finely enough discrete space)</em> or continuous time <em>(or a discrete time where interesting events are sparse)</em>. An example of such a game is StarCraft.</p>
  <p>There are two methods a computer plays StarCraft:</p>
  <ul>
  <li><p>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.</p>
  </li>
  <li><p>A neural network that takes screen pictures to mouse clicks. This is expensive because you need a lot of hardware and electricity.</p>
  </li>
  </ul>
  <p>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.</p>
  <p>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?</p>
  <p>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?</p>
  <p>A case in point is the <a href="https://en.wikipedia.org/wiki/Navigation_mesh" rel="nofollow noreferrer">navigation mesh</a> technique that sidesteps the problem of smooth path finding by finding paths in a discrete approximation of the given smooth space. Is this the best we can do?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2024-06-11T10:04:14.297Z
Comments.Text: 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
Comments.UserDisplayName: Alberto
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2024-06-11T11:29:20.520Z
Comments.Text: @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?
Comments.UserDisplayName: Ignat Insarov
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2024-06-11T14:52:23.677Z
Comments.Text: 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
Comments.UserDisplayName: Alberto
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2024-06-13T20:36:53.937Z
Comments.Text: @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.
Comments.UserDisplayName: Ignat Insarov
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2024-06-13T20:42:41.747Z
Comments.Text: I mean... https://deepmind.google/discover/blog/alphastar-mastering-the-real-time-strategy-game-starcraft-ii/ ... they probably know better than me
Comments.UserDisplayName: Alberto
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2024-06-14T00:29:45.690Z
Comments.Text: Ah, that is what I had in mind when I mentioned expensive neural networks that take screen pictures to mouse clicks. I looked at their research article a while ago and I remember it was an impressively complicated neural network that took days if not weeks to train. What I am looking for is something as *«naturally efficient»* as the minimax algorithm for discrete games.
Comments.UserDisplayName: Ignat Insarov
Tags: <game-ai><continuous-state-spaces>
Title: How do I make an artificial intelligence for a game played on a continuous board?
UserDisplayName: Ignat Insarov
ThreadText: # How do I make an artificial intelligence for a game played on a continuous board?
  
  (Asked by: username_0 on 2024-06-11)
  
  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?
  
  A case in point is the [navigation mesh](https://en.wikipedia.org/wiki/Navigation_mesh) technique that sidesteps the problem of smooth path finding by finding paths in a discrete approximation of the given smooth space. Is this the best we can do?
  
  **Tags:** game-ai, continuous-state-spaces
  
  > **Comments:**
  > **username_1**: 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  
  > **username_0**: @username_1   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?  
  > **username_1**: 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  
  > **username_0**: @username_1 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.  
  > **username_1**: I mean... https://deepmind.google/discover/blog/alphastar-mastering-the-real-time-strategy-game-starcraft-ii/ ... they probably know better than me  
  > **username_0**: Ah, that is what I had in mind when I mentioned expensive neural networks that take screen pictures to mouse clicks. I looked at their research article a while ago and I remember it was an impressively complicated neural network that took days if not weeks to train. What I am looking for is something as *«naturally efficient»* as the minimax algorithm for discrete games.  
  
  ---
  
  ## 0 answers
  
  