Answers.Body: <p>This looks like the kind of game that a Reinforcement Learning algorithm could learn to play. If you are learning from the game objects directly (as opposed to wanting to have the agent learn from viewing the screen), then it should be <em>relatively</em> straightforward to do so - by which I mean that it will involve some new concepts, a little maths, and maybe take you a few weeks to learn enough and run enough experiments on the AI to the point where you have something good. But at least you should not need a cluster of GPU servers to run your learner.</p>
  
  <blockquote>
    <p>However, I have no clue how to apply Q-learning to this task. For example, how could the coder possibly know what future reward another move will bring?</p>
  </blockquote>
  
  <p>That is a major part of RL - the algorithms that are part of RL all solve this issue. Therefore the coder does not need to know how to calculate future reward, just an immediate reward. For the example game, it looks like you can grant a reward of <span class="math-container">$+1$</span> for every frame where the player does not crash. An RL algorithm that can solve this environment should figure out through "trial and error" which actions will keep the game running. </p>
  
  <p>Q Learning achieves this by keeping track of estimates of future value and updating them across time steps - if action <span class="math-container">$a_1$</span> in state <span class="math-container">$s_1$</span> consistently leads to a later state <span class="math-container">$s_2$</span> with a high value, then Q learning will update its estimate of the value of <span class="math-container">$Q(s_1,a_1)$</span> to be high as well. The estimates start very poorly, but updates work their way back through time steps as the agent learns, and provided things don't go wrong, eventually it will learn that one action will lead to higher value than another, and it be able to consistently choose it.</p>
  
  <p>This is such a basic question that if you want to use RL, even if you find a library that implements the whole thing for you, that you clearly need to study some foundations of RL. There are a few different places you can do that. I can suggest two that I have used:</p>
  
  <ul>
  <li><p>The book by Sutton &amp; Barto. <a href="http://incompleteideas.net/book/the-book-2nd.html" rel="nofollow noreferrer">Reinforcement Learning: An Introduction</a></p></li>
  <li><p><a href="http://www0.cs.ucl.ac.uk/staff/d.silver/web/Teaching.html" rel="nofollow noreferrer">UCL lectures by David Silver</a>. These include videos on YouTube.</p></li>
  </ul>
  
  <p>Both are online, free and comprehensive introductions to the subject. You can find shorter, more direct introductions online if you search for e.g. "Q Learning Tutorial".</p>
  
  <p>Be prepared to spend hours just learning enough about the topic that you understand how to structure your data and interface with the game in order to create a learning environment for your AI.</p>
  
  <blockquote>
    <ol>
    <li>In this case, the player has infinitely many actions. How would I apply RL to this case?</li>
    </ol>
  </blockquote>
  
  <p>This is a good question. Some algorithms are better than others. Q Learning cannot work with infinitely many actions. However, you could choose a discrete set of mouse points - e.g. maybe 64 - at different angles and distances from the player (red dot) and try and get the values of those. That would allow you to try with Q learning, and is worth considering because RL that properly solves large action spaces is harder to understand and work with. You could look into the DQN algorithm for this. In short, the DQN algorithm uses history of actions and their immediate results to train a neural network to estimate the values of each action.</p>
  
  <p>If you really want to solve large action spaces properly, then you need to be looking into Policy Gradient methods. Two popular and effective PG algorithms are A3C and DDPG. These are tougher to learn and implement. They use neural networks to learn multiple functions, one of which is the <em>policy</em> - this directly selects which action to take, given a current state/observation.</p>
  
  <blockquote>
    <ol start="2">
    <li>Is RL a good approach to solving this task?</li>
    </ol>
  </blockquote>
  
  <p>It is definitely possible to use RL to do what you want. </p>
  
  <blockquote>
    <ol start="3">
    <li>Is there a handy Java library which would allow me to use a RL algorithm (as a block-box) to solve this problem?</li>
    </ol>
  </blockquote>
  
  <p>I could not find one on a brief search. To get started, you might want to look at <a href="https://github.com/chen0040/java-reinforcement-learning" rel="nofollow noreferrer">java-reinforcement-learning</a> which implements some of the algorithms from Sutton &amp; Barto, so would be a good starting point. Most of the other Java packages I found covered basics and learning material, but would not be plug-and-play for your game.</p>
  
  <p>If you do find a library, you will need to have learned enough basic RL to be able to follow how to use it.</p>
  
  <blockquote>
    <ol start="4">
    <li>Are there alternatives?</li>
    </ol>
  </blockquote>
  
  <p>One alternative that might work well for your game environment, and be a little easier to understand and implement would be to combine a policy function (like a neural network) with an evolutionary algorithm that tries out variations of the policy. The go-to algorithm here is probably NEAT, and it is capable of solving simple game agents effectively. Your game should be a reasonable fit for NEAT because the scoring system of survival time makes for a good fitness function.</p>
  
  <p>One thing that could really be worth trying before diving into the (very hard to understand) A3C and DDPG algorithms is the <a href="https://www.aaai.org/Papers/ICML/2003/ICML03-068.pdf" rel="nofollow noreferrer">Cross-Entropy Method</a>. It is a really simple RL agent that has some similarities to genetic algorithms (it selects "best" items, but instead of from the population, it is from random behaviour of the same individual), but doesn't always scale too well. However, it might work well for your game. </p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-04-04T05:08:08.960Z
Answers.Text: Incredible, in depth explanation of how to carry out a RL project for a difficult game. I was also curious about the Action Space mapping.
Answers.UserDisplayName: math_law
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-04-04T07:23:05.133Z
Answers.Text: @math_law The answer didn't go into specific action mapping for this game. Typically for policy gradient the policy network outputs the parameters of a probability distribution, which you can sample from. E.g. it might output the mean and variance for a Normal distribution for the steering direction. Some methods work with direct action output plus a noise function for exploration (DDPG). If you have a specific case, I suggest asking a new question on the site
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-10-25T18:51:30.257Z
Answers.Text: Thanks for your answer! I have 2 Months to get this all done. I am just a high-school student (in Germany), I hope I can crack the math. I was able to crack the math in BP, but I think this is one step higher
  
  I already tried NEAT - I tried to develop an ANN from scratch using Neat. This ANN should just play the game. It is not possible. It takes way to long for NEAT, the computing time with 10000 individuals is just tremendous...
Answers.UserDisplayName: TVSuchty
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-10-25T18:53:46.967Z
Answers.Text: @TVSuchty: Might be worth trying cross-entropy method, which is somewhere in-between NEAT and policy gradient methods. It doesn't evolve a population, but trains itself directly from the last batch of best efforts.
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-10-25T18:55:38.977Z
Answers.Text: Hey, I updated the comment. What level of education do you consider to be sufficient...
Answers.UserDisplayName: TVSuchty
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-10-25T18:59:25.970Z
Answers.Text: @TVSuchty: I would consider a *full* understanding of RL including all the maths to be equivalent to studying for a MSc. However, you don't need that - there are plenty of programmer's tutorials out there that should be accessible with A-level/High School maths. The main problem you will face is not so much of it will be in Java.
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-10-25T19:07:07.497Z
Answers.Text: @TVSuchty: Try cross-entropy method first. It is no harder than NEAT to understand, probably easier in fact. Another thing you can try is recording humans playing the game and training a regular NN to emulate them. Comparing these methods might still make a good project, even if the result is not a good AI. Emulating a human as a starting point could also significantly improve convergence times for other policy searches, if you re-use that NN as a starting point.
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-10-25T19:07:39.057Z
Answers.Text: Thanks for your evaluation! Then it can be done. I will try following your advice.
  Have an awesome day.
Answers.UserDisplayName: TVSuchty
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-10-25T18:44:20.877Z
Answers.LastActivityDate: 2019-02-15T16:53:25.833Z
Answers.LastEditDate: 2019-02-15T16:53:25.833Z
Answers.UserDisplayName: Neil Slater
Body: <p>I am trying to figure out how to use a reinforcement learning algorithm, if possible, as a "black box" to play a game. In this game, a player has to avoid flying birds. If he wants to move, he has to move the mouse on the display, which controls the player position by applying a force. The player can choose any position on the display for the mouse. A human can play this game. To get a sense what needs to be done, have a look at <a href="https://www.youtube.com/watch?v=k6xiqI60ztA" rel="nofollow noreferrer">this Youtube video</a>.</p>
  
  <p>I thought about using an ANN, which takes as input the information of the game (e.g. positions, speeds, radius, etc.) and outputs a move. However, I am unlikely to ever record enough training data to train the network properly.</p>
  
  <p>Therefore, I was thinking that a RL algorithm, like Q-learning, would be more suited for this task. However, I have no clue how to apply Q-learning to this task. For example, how could the coder possibly know what future reward another move will bring?</p>
  
  <p>I have a few questions:</p>
  
  <ol>
  <li><p>In this case, the player has infinitely many actions. How would I apply RL to this case?</p></li>
  <li><p>Is RL a good approach to solving this task?</p></li>
  <li><p>Is there a handy Java library which would allow me to use a RL algorithm (as a block-box) to solve this problem?</p></li>
  <li><p>Are there alternatives?   </p></li>
  </ol>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2018-10-25T17:54:44.967Z
Comments.Text: I can answer this, but there seems to be two questions here - a very basic one about how Q Learning works, and a more involved one about the size of the action space. Finding you a Java library is probably off-topic. Are you looking for a Java library because the game is written in Java, so this is a way to integrate it?
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2018-10-25T18:00:17.477Z
Comments.Text: @NeilSlater Would you please specify what you want me to do, then I will change it.  I am sorry if the question offended you in any way.
  
  What does it mean to reflect a question?
Comments.UserDisplayName: TVSuchty
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2018-10-25T18:06:59.690Z
Comments.Text: @TVSuchty I am already putting together an answer. I am not in any way offended. I want to check why you are asking for a Java library - I won't be able to find one for you, but I might be able to suggest something that works for you if I knew why you need that. Do bear in mind you have asked a quite broad question, about how to start a project, so any answers are also going to be broad pointers on how to get started.
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2018-10-25T18:16:31.690Z
Comments.Text: I need a java-library because I started writing in Java and I do not know how to write something cross-language. While I think my Java is advanced so far that I can fluently "speak" the language, my python is not. I use engoc right now, it has something about RL 
  
  http://heatonresearch-site.s3-website-us-east-1.amazonaws.com/javadoc/encog-3.3/org/encog/ml/world/learning/q/QLearning.html
  
  But I am not sure..
Comments.UserDisplayName: TVSuchty
Tags: <reinforcement-learning><game-ai><applications><java>
Title: How do I apply reinforcement learning to a game with infinitely many actions?
UserDisplayName: TVSuchty
ThreadText: # How do I apply reinforcement learning to a game with infinitely many actions?
  
  (Asked by: username_0 on 2018-10-25)
  
  I am trying to figure out how to use a reinforcement learning algorithm, if possible, as a "black box" to play a game. In this game, a player has to avoid flying birds. If he wants to move, he has to move the mouse on the display, which controls the player position by applying a force. The player can choose any position on the display for the mouse. A human can play this game. To get a sense what needs to be done, have a look at [this Youtube video](https://www.youtube.com/watch?v=k6xiqI60ztA).
  
  I thought about using an ANN, which takes as input the information of the game (e.g. positions, speeds, radius, etc.) and outputs a move. However, I am unlikely to ever record enough training data to train the network properly.
  
  Therefore, I was thinking that a RL algorithm, like Q-learning, would be more suited for this task. However, I have no clue how to apply Q-learning to this task. For example, how could the coder possibly know what future reward another move will bring?
  
  I have a few questions:
  
  1. In this case, the player has infinitely many actions. How would I apply RL to this case?
  2. Is RL a good approach to solving this task?
  3. Is there a handy Java library which would allow me to use a RL algorithm (as a block-box) to solve this problem?
  4. Are there alternatives?
  
  **Tags:** reinforcement-learning, game-ai, applications, java
  > **Comments:**
  > **username_1**: I can answer this, but there seems to be two questions here - a very basic one about how Q Learning works, and a more involved one about the size of the action space. Finding you a Java library is probably off-topic. Are you looking for a Java library because the game is written in Java, so this is a way to integrate it?  
  > **username_0**: @NeilSlater Would you please specify what you want me to do, then I will change it.  I am sorry if the question offended you in any way.  What does it mean to reflect a question?  
  > **username_1**: @TVSuchty I am already putting together an answer. I am not in any way offended. I want to check why you are asking for a Java library - I won't be able to find one for you, but I might be able to suggest something that works for you if I knew why you need that. Do bear in mind you have asked a quite broad question, about how to start a project, so any answers are also going to be broad pointers on how to get started.  
  > **username_0**: I need a java-library because I started writing in Java and I do not know how to write something cross-language. While I think my Java is advanced so far that I can fluently "speak" the language, my python is not. I use engoc right now, it has something about RL   http://heatonresearch-site.s3-website-us-east-1.amazonaws.com/javadoc/encog-3.3/org/encog/ml/world/learning/q/QLearning.html  But I am not sure..  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2018-10-25. Score: 2
  
  This looks like the kind of game that a Reinforcement Learning algorithm could learn to play. If you are learning from the game objects directly (as opposed to wanting to have the agent learn from viewing the screen), then it should be *relatively* straightforward to do so - by which I mean that it will involve some new concepts, a little maths, and maybe take you a few weeks to learn enough and run enough experiments on the AI to the point where you have something good. But at least you should not need a cluster of GPU servers to run your learner.
  
  > However, I have no clue how to apply Q-learning to this task. For example, how could the coder possibly know what future reward another move will bring?
  
  That is a major part of RL - the algorithms that are part of RL all solve this issue. Therefore the coder does not need to know how to calculate future reward, just an immediate reward. For the example game, it looks like you can grant a reward of $+1$ for every frame where the player does not crash. An RL algorithm that can solve this environment should figure out through "trial and error" which actions will keep the game running.
  
  Q Learning achieves this by keeping track of estimates of future value and updating them across time steps - if action $a\_1$ in state $s\_1$ consistently leads to a later state $s\_2$ with a high value, then Q learning will update its estimate of the value of $Q(s\_1,a\_1)$ to be high as well. The estimates start very poorly, but updates work their way back through time steps as the agent learns, and provided things don't go wrong, eventually it will learn that one action will lead to higher value than another, and it be able to consistently choose it.
  
  This is such a basic question that if you want to use RL, even if you find a library that implements the whole thing for you, that you clearly need to study some foundations of RL. There are a few different places you can do that. I can suggest two that I have used:
  
  * The book by Sutton & Barto. [Reinforcement Learning: An Introduction](http://incompleteideas.net/book/the-book-2nd.html)
  * [UCL lectures by David Silver](http://www0.cs.ucl.ac.uk/staff/d.silver/web/Teaching.html). These include videos on YouTube.
  
  Both are online, free and comprehensive introductions to the subject. You can find shorter, more direct introductions online if you search for e.g. "Q Learning Tutorial".
  
  Be prepared to spend hours just learning enough about the topic that you understand how to structure your data and interface with the game in order to create a learning environment for your AI.
  
  > 1. In this case, the player has infinitely many actions. How would I apply RL to this case?
  
  This is a good question. Some algorithms are better than others. Q Learning cannot work with infinitely many actions. However, you could choose a discrete set of mouse points - e.g. maybe 64 - at different angles and distances from the player (red dot) and try and get the values of those. That would allow you to try with Q learning, and is worth considering because RL that properly solves large action spaces is harder to understand and work with. You could look into the DQN algorithm for this. In short, the DQN algorithm uses history of actions and their immediate results to train a neural network to estimate the values of each action.
  
  If you really want to solve large action spaces properly, then you need to be looking into Policy Gradient methods. Two popular and effective PG algorithms are A3C and DDPG. These are tougher to learn and implement. They use neural networks to learn multiple functions, one of which is the *policy* - this directly selects which action to take, given a current state/observation.
  
  > 2. Is RL a good approach to solving this task?
  
  It is definitely possible to use RL to do what you want.
  
  > 3. Is there a handy Java library which would allow me to use a RL algorithm (as a block-box) to solve this problem?
  
  I could not find one on a brief search. To get started, you might want to look at [java-reinforcement-learning](https://github.com/chen0040/java-reinforcement-learning) which implements some of the algorithms from Sutton & Barto, so would be a good starting point. Most of the other Java packages I found covered basics and learning material, but would not be plug-and-play for your game.
  
  If you do find a library, you will need to have learned enough basic RL to be able to follow how to use it.
  
  > 4. Are there alternatives?
  
  One alternative that might work well for your game environment, and be a little easier to understand and implement would be to combine a policy function (like a neural network) with an evolutionary algorithm that tries out variations of the policy. The go-to algorithm here is probably NEAT, and it is capable of solving simple game agents effectively. Your game should be a reasonable fit for NEAT because the scoring system of survival time makes for a good fitness function.
  
  One thing that could really be worth trying before diving into the (very hard to understand) A3C and DDPG algorithms is the [Cross-Entropy Method](https://www.aaai.org/Papers/ICML/2003/ICML03-068.pdf). It is a really simple RL agent that has some similarities to genetic algorithms (it selects "best" items, but instead of from the population, it is from random behaviour of the same individual), but doesn't always scale too well. However, it might work well for your game.
  
  > **Comments:**
  > **username_0**: Thanks for your answer! I have 2 Months to get this all done. I am just a high-school student (in Germany), I hope I can crack the math. I was able to crack the math in BP, but I think this is one step higher  I already tried NEAT - I tried to develop an ANN from scratch using Neat. This ANN should just play the game. It is not possible. It takes way to long for NEAT, the computing time with 10000 individuals is just tremendous...  
  > **username_1**: @TVSuchty: Might be worth trying cross-entropy method, which is somewhere in-between NEAT and policy gradient methods. It doesn't evolve a population, but trains itself directly from the last batch of best efforts.  
  > **username_0**: Hey, I updated the comment. What level of education do you consider to be sufficient...  
  > **username_1**: @TVSuchty: I would consider a *full* understanding of RL including all the maths to be equivalent to studying for a MSc. However, you don't need that - there are plenty of programmer's tutorials out there that should be accessible with A-level/High School maths. The main problem you will face is not so much of it will be in Java.  
  > **username_1**: @TVSuchty: Try cross-entropy method first. It is no harder than NEAT to understand, probably easier in fact. Another thing you can try is recording humans playing the game and training a regular NN to emulate them. Comparing these methods might still make a good project, even if the result is not a good AI. Emulating a human as a starting point could also significantly improve convergence times for other policy searches, if you re-use that NN as a starting point.  
  > **username_0**: Thanks for your evaluation! Then it can be done. I will try following your advice. Have an awesome day.  
  > **username_2**: Incredible, in depth explanation of how to carry out a RL project for a difficult game. I was also curious about the Action Space mapping.  
  > **username_1**: @math_law The answer didn't go into specific action mapping for this game. Typically for policy gradient the policy network outputs the parameters of a probability distribution, which you can sample from. E.g. it might output the mean and variance for a Normal distribution for the steering direction. Some methods work with direct action output plus a noise function for exploration (DDPG). If you have a specific case, I suggest asking a new question on the site  
  
  ---
  
  