Answers.Body: <p>I was able to make the game work and because of that I can say that the GA approach at least makes some sense. I did the following changes:</p>
  <ul>
  <li>Added crossover</li>
  <li>Increased generation size from 50 to 300</li>
  <li>Increased hidden layer size from 5 to 12 (I don't know does this actually make a difference)</li>
  <li>Increased mutation</li>
  <li>Added both players x and y velocity to input layer</li>
  </ul>
  <p>It is hard to train both of the players at the same time because after one of the players learns to play well, they start to dominate and that makes the learning stop.</p>
  <p>For the player that tries to catch (red), using the time it took to catch the opponent as a part of the fitness, was not a good idea because this seems to make the player (red) to rush. This also makes the fitness highest for those who had a weaker opponent.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-01-06T20:50:16.693Z
Answers.LastActivityDate: 2023-01-06T20:50:16.693Z
Answers.UserDisplayName: MaLa
Answers.Body: <p>Your approach should work in general, but there are a lot of key details that will make the difference between success and failure.</p>
  <p>The most major issue is a number of hyperparameters that you have effectively chosen, and that could make a difference to the project:</p>
  <ul>
  <li>Population size</li>
  <li>Architecture of neural network</li>
  <li>Starting values for neural network weights</li>
  <li>Scaling of NN inputs. With supervised learning you want the scale to be constrained to somewhere roughly inside -2 to +2, but with GA weight search, it will depend more on starting values and mutation</li>
  <li>Mutation amounts</li>
  <li>Crossover - by not having crossover in your GA design you are missing out on one of the potential strengths of GAs, and your solution is closer to random search which will take longer because you cannot for example combine one agent's correct behaviour in the top-left quadrant with another's in the bottom right.</li>
  </ul>
  <p>If you want to take the GA/NN crossover further, I recommend you look into the <a href="https://en.wikipedia.org/wiki/Neuroevolution_of_augmenting_topologies" rel="nofollow noreferrer">NEAT</a> system. It has a nice mechanism for handling combining two neural network &quot;parents&quot; to make a functional child.</p>
  <h2>Alternative #1 - Reinforcement learning</h2>
  <p>Reinforcement learning (RL) addresses the same basic problem - you don't know the correct outputs for a neural network to train from input/output pairs, but you can tell when a player has been successful. Instead of managing a population of player <em>policies</em> that you use to search the space of all possible behaviours, RL manages one policy (per player) and calculates how to change it to improve performance, based on observing results.</p>
  <p>In practice, RL is very effective at optimising this kind of game. You will want to start with some basics before tackling your tag game, but something based around Deep Q Networks will probably work very well for your environment. The dueling nature of your agents will mean you would need to write some custom agent code though, very few of the off-the-shelf DQN solutions are written for adversarial games and self-play.</p>
  <h2>Alternative #2 - Tree search</h2>
  <p>In your case it may be possible to discover the correct outputs, and train the neural network to learn them. If the movement is on a discrete grid (or effectively on that grid if you are using fixed movement increments), then you could use a <a href="https://en.wikipedia.org/wiki/Negamax" rel="nofollow noreferrer">negamax search</a> to discover the perfect movement strategy from any pair of starting positions, and use that to create a training dataset. As an example, if the grid was 20x20 then you would have roughly 400x400 = 160,000 training examples covering perfect play for the entire game.</p>
  <p>* Actually Negamax search will only work if play is turn-based, but there may be equivalent searches for simultaneous moves.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-01-05T18:39:29.110Z
Answers.Text: Thank you! What do you mean by "Starting values for neural network weights"? Currently my starting weights are random. Is there a better way to create starting weights?
Answers.UserDisplayName: MaLa
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-01-05T22:58:01.170Z
Answers.Text: @MaLa Random is fine, in fact usually required, but the range used can make a big difference on whether the resulting NN functions are likely to be useful for any specific problem - here's an article covering some options, although you should note this is more focused on supervised learning than GA/NN combination https://machinelearningmastery.com/weight-initialization-for-deep-learning-neural-networks
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-01-05T12:15:30.680Z
Answers.LastActivityDate: 2023-01-05T14:04:02.920Z
Answers.LastEditDate: 2023-01-05T14:04:02.920Z
Answers.UserDisplayName: Neil Slater
Body: <p>I have a simple game of tag, where red player tries to catch the blue player. Red player wins if it catches the blue player in under 10 seconds, but if not, then blue wins.</p>
  <p><a href="https://i.sstatic.net/q3LHx.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/q3LHx.png" alt="Tag game" /></a></p>
  <p>My goal is to teach the players to play the game well. Both of the players currently use neural network which has six inputs:</p>
  <ul>
  <li>x distance between players</li>
  <li>y distance between players</li>
  <li>x distance between player and left wall</li>
  <li>x distance between player and right wall</li>
  <li>y distance between player and top wall</li>
  <li>y distance between player and bottom wall</li>
  </ul>
  <p>one hidden layer which size is 5 and 4 outputs for moving up, down, left and right.</p>
  <p><strong>How should I approach training the players?</strong></p>
  <p>I am currently trying a genetic algorithm. I have chosen genetic algorithms because I do not have any training data, because I don't know the correct inputs and outputs.</p>
  <p>I am training the players at the same time. I create about 50 games (50 blue and 50 red players) and the player that wins, stays alive and creates child which has mutation. Mutation basically means that I change 0-2 weights about (-0.25)-(+0.25). I keep the populations at the same size by increasing the birthrate of the smaller (losing) population. This approach has not yet yielded good results. I can see a little progress, but a lot of the wins seem random.</p>
  <p><strong>Does my approach make sense?</strong></p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-01-05T11:46:46.927Z
Comments.Text: Does the blue player move deterministically in each game or randomly?  If it moves deterministically, a genetic approach will definitely converge quickly.  If it moves randomly, I'd use a reinforcement approach with a deep Q or double deep Q approach.
Comments.UserDisplayName: David Hoelzer
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-01-05T11:50:27.610Z
Comments.Text: @DavidHoelzer: The question clearly states that both players are being trained, not just the red one. The movement appears to be deterministic, but the attempted direction of travel is driven by the agents' respective decision processes which are being trained adversarially
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-01-05T13:05:18.697Z
Comments.Text: Thanks.  I apparently missed that the, "question clearly states."  @NeilSlater
Comments.UserDisplayName: David Hoelzer
Tags: <neural-networks><ai-design><game-ai><genetic-algorithms>
Title: How should I train the players in the game of tag?
UserDisplayName: MaLa
ThreadText: # How should I train the players in the game of tag?
  
  (Asked by: username_0 on 2023-01-05)
  
  I have a simple game of tag, where red player tries to catch the blue player. Red player wins if it catches the blue player in under 10 seconds, but if not, then blue wins.
  
  [![Tag game](https://i.sstatic.net/q3LHx.png)](https://i.sstatic.net/q3LHx.png)
  
  My goal is to teach the players to play the game well. Both of the players currently use neural network which has six inputs:
  
  * x distance between players
  * y distance between players
  * x distance between player and left wall
  * x distance between player and right wall
  * y distance between player and top wall
  * y distance between player and bottom wall
  
  one hidden layer which size is 5 and 4 outputs for moving up, down, left and right.
  
  **How should I approach training the players?**
  
  I am currently trying a genetic algorithm. I have chosen genetic algorithms because I do not have any training data, because I don't know the correct inputs and outputs.
  
  I am training the players at the same time. I create about 50 games (50 blue and 50 red players) and the player that wins, stays alive and creates child which has mutation. Mutation basically means that I change 0-2 weights about (-0.25)-(+0.25). I keep the populations at the same size by increasing the birthrate of the smaller (losing) population. This approach has not yet yielded good results. I can see a little progress, but a lot of the wins seem random.
  
  **Does my approach make sense?**
  
  **Tags:** neural-networks, ai-design, game-ai, genetic-algorithms
  
  > **Comments:**
  > **username_1**: Does the blue player move deterministically in each game or randomly?  If it moves deterministically, a genetic approach will definitely converge quickly.  If it moves randomly, I'd use a reinforcement approach with a deep Q or double deep Q approach.  
  > **username_2**: @username_1: The question clearly states that both players are being trained, not just the red one. The movement appears to be deterministic, but the attempted direction of travel is driven by the agents' respective decision processes which are being trained adversarially  
  > **username_1**: Thanks.  I apparently missed that the, "question clearly states."  @username_2  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_2 on 2023-01-05. Score: 2 | Accepted answer
  
  Your approach should work in general, but there are a lot of key details that will make the difference between success and failure.
  
  The most major issue is a number of hyperparameters that you have effectively chosen, and that could make a difference to the project:
  
  * Population size
  * Architecture of neural network
  * Starting values for neural network weights
  * Scaling of NN inputs. With supervised learning you want the scale to be constrained to somewhere roughly inside -2 to +2, but with GA weight search, it will depend more on starting values and mutation
  * Mutation amounts
  * Crossover - by not having crossover in your GA design you are missing out on one of the potential strengths of GAs, and your solution is closer to random search which will take longer because you cannot for example combine one agent's correct behaviour in the top-left quadrant with another's in the bottom right.
  
  If you want to take the GA/NN crossover further, I recommend you look into the [NEAT](https://en.wikipedia.org/wiki/Neuroevolution_of_augmenting_topologies) system. It has a nice mechanism for handling combining two neural network "parents" to make a functional child.
  
  ## Alternative #1 - Reinforcement learning
  
  Reinforcement learning (RL) addresses the same basic problem - you don't know the correct outputs for a neural network to train from input/output pairs, but you can tell when a player has been successful. Instead of managing a population of player *policies* that you use to search the space of all possible behaviours, RL manages one policy (per player) and calculates how to change it to improve performance, based on observing results.
  
  In practice, RL is very effective at optimising this kind of game. You will want to start with some basics before tackling your tag game, but something based around Deep Q Networks will probably work very well for your environment. The dueling nature of your agents will mean you would need to write some custom agent code though, very few of the off-the-shelf DQN solutions are written for adversarial games and self-play.
  
  ## Alternative #2 - Tree search
  
  In your case it may be possible to discover the correct outputs, and train the neural network to learn them. If the movement is on a discrete grid (or effectively on that grid if you are using fixed movement increments), then you could use a [negamax search](https://en.wikipedia.org/wiki/Negamax) to discover the perfect movement strategy from any pair of starting positions, and use that to create a training dataset. As an example, if the grid was 20x20 then you would have roughly 400x400 = 160,000 training examples covering perfect play for the entire game.
  
  \* Actually Negamax search will only work if play is turn-based, but there may be equivalent searches for simultaneous moves.
  
  > **Comments:**
  > **username_0**: Thank you! What do you mean by "Starting values for neural network weights"? Currently my starting weights are random. Is there a better way to create starting weights?  
  > **username_2**: @username_0 Random is fine, in fact usually required, but the range used can make a big difference on whether the resulting NN functions are likely to be useful for any specific problem - here's an article covering some options, although you should note this is more focused on supervised learning than GA/NN combination https://machinelearningmastery.com/weight-initialization-for-deep-learning-neural-networks  
  
  ---
  
  ### Answer by username_0 on 2023-01-06. Score: 2
  
  I was able to make the game work and because of that I can say that the GA approach at least makes some sense. I did the following changes:
  
  * Added crossover
  * Increased generation size from 50 to 300
  * Increased hidden layer size from 5 to 12 (I don't know does this actually make a difference)
  * Increased mutation
  * Added both players x and y velocity to input layer
  
  It is hard to train both of the players at the same time because after one of the players learns to play well, they start to dominate and that makes the learning stop.
  
  For the player that tries to catch (red), using the time it took to catch the opponent as a part of the fitness, was not a good idea because this seems to make the player (red) to rush. This also makes the fitness highest for those who had a weaker opponent.
  
  
  ---
  
  