2
$\begingroup$

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

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?

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ Jan 5, 2023 at 11:46
  • 1
    $\begingroup$ @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 $\endgroup$ Jan 5, 2023 at 11:50
  • $\begingroup$ Thanks. I apparently missed that the, "question clearly states." @NeilSlater $\endgroup$ Jan 5, 2023 at 13:05

2 Answers 2

2
$\begingroup$

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 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 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.

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – MaLa
    Jan 5, 2023 at 18:39
  • 1
    $\begingroup$ @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 machinelearningmastery.com/… $\endgroup$ Jan 5, 2023 at 22:58
2
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .