Neural Network Ressources

[_CPC_Herbert]

@pb4608

Since I started reading articles on Neural Networks and Q-learning, I have observed that a lot of people seem to think that you just “train” an artificial neural network and that it will work. As you explain in your article, it really is not that easy. The comparison is often made between a Neural Network and the way our brain works, but it must be noted that in the end, the similarity is limited to the names used.

In the context in which you use it, a neural network is indeed “merely” a function approximator with a lot of coefficients to tune.

I think it’s when I understood that NN are merely function approximators that I started understand what they are and how they worked really. Even in “classic” usage like for classification and supervised learning, there’s a hidden ideal input → output mapping function and training the NN is just about approximating it by tuning the parameters with gradient descent.

@pb4608

2. I believe you deviated from “Textbook” Q-learning.My understanding of NN design for Q-learning is the following : you provide as input to the NN a set of values describing the state and transition (S,T). The output of the Neural Network is a single value, which gives the expected reward after taking transition T.I understand that your NN design is slightly different : the input is the state S, and you have one output for each transition T.Both approaches seem similar because for each transition you can extract one value as the output and treat it as the expected future reward.Here is however where I think both approaches differ : in your case, the only place in the Neural Network where the calculation is different between two transitions is in the very last layer. Think about it : the first 5 hidden layers receive exactly the same input (the state S). Hence, it’s only in the very last layer that the coefficients will make a difference between all transitions. This doesn’t seem very efficient, as 5 layers of your neural network become (somewhat) useless.I’m curious to know if you could try the approach with the (S,T) input and only one output.

Well, this isn’t my idea. I believe it’s they way they do it in the DeepMind paper as well. I’m not sure about your concern though.

When the NN is updated, the reward gradient is back-propagated into it. So we update the last layer weights first, then the second-to-last, etc… Even if we would back-propagate the rewards one at a time (which we don’t anyway), the inputs of the last layer are the same for two different T but the output gradients aren’t.

We then compute the gradient of the inputs (and of the weights) of the last layer w.r.t. this output gradient. Both gradients are different for two different T, because the output gradients are different. As the last layer inputs gradient is then used as the outputs gradient of the second to last layer, we see that the reward differences are going to be propagated in the whole network recursively.

I may be wrong, and for the sake of discussion, the last layer of my network is also the only one that shows noticeable patterns. However, although the runner NN works OK with only one hidden layer, I could never make a blocker NN that converges with only one layer, whatever size I use.

@pb4608

3. You reference the “Experience Replay” technique from the Deepmind Paper. I have forgotten the name, but I saw a paper by Martin Riedmiller where he used a technique in which he explained that when most actions yield no reward, the NN may converge to 0 everywhere. The few datapoints where there is a reward give a huge error, but if they are rare this may minimize the overall error. In order to prevent this, the dataset was biaised toward using more datapoints where a reward is given. Do you have an opinion on trying this ?

I had also the intuition that making the good or bad moves stand out in the replay memory could help. So I tried inserting the moves in the memory accordingly to their reward so that good/bad moves would be replayed more often. I think it helped a little bit in the beginning of the training when random moves are chosen and when the NN only outputs random rewards, but it was mostly ruining everything around the end of the training when good/bad moves are known and we mostly want to refine the reward of the neutral moves that lead to good or bad moves. Maybe this could be done by also taking into account where we are in the training session.

But this is clearly a problem in the way training is done as well. For example, even training a runner with fixed rewards only on timeout or when CP is reached, without any other constraint is not working very well. I had to add a distance to CP limit and add a negative fixed reward when the pod was escaping too far, to help discarding such moves.

@pb4608

4. With your definition of rewards, there is a way to calculate some theoretical values for your NN’s output. For example, when the pod and the checkpoints are aligned, we know that the ideal trajectory is a straight line with 200 acceleration. This means that the Q value obtained in the two consecutive states should differ only by a factor alpha. Have you checked how close the expected rewards follow this theory in a few special cases as described ?

I guess, but I haven’t

@pb4608

5. When the pod validates a checkpoint, I understand that you shift the checkpoint positions in the input, and generate a new “next checkpoint + 2”. This is something I was afraid would not work, and around which I tried to work. I’ll definitely try your approach !

Yep, that’s it.

When a new initial game state is generated (initially or each time the pod loses), I create:

• Pod₀ position random in [0 16000] x [0 9000]
• Pod₀ speed random vector with random norm in [0 max_speed]
• Pod₀ direction random unit vector
• CP₀ position random in [0 16000] x [0 9000] so that 4 * point_radius < distance(CP₀, Pod₀) < max_train_distance / 2
• CP₁, CP₂ position random in [0 16000] x [0 9000] so that 4 * point_radius < distance(CP_n, CP_m) < max_train_distance

When the pod passes through CP₀, I shift the CPs and I generate a new CP₂ with the same rules as above. The pod’s next CP is always 0.

There’s also a Pod₁ that’s generated using almost the same rules as Pod₀ when I want to add a blocker to the game, all other pods are ignored.

@pb4608

6. Can you describe your blocker’s input for the NN, and the reward definition ?

Sure, it’s almost the same as the runner, only that the CP provided are the ones of the target runner and the runner’s position / speed / direction are also provided to it:

  inputs[0]  = dot(point{1, 0} * pod.dir, pod.spd) / max_speed;
  inputs[1]  = dot(point{0, 1} * pod.dir, pod.spd) / max_speed;
  inputs[2]  = dot(point{1, 0} * pod.dir, runner.pos - pod.pos) / max_distance;
  inputs[3]  = dot(point{0, 1} * pod.dir, runner.pos - pod.pos) / max_distance;
  inputs[4]  = dot(point{1, 0} * pod.dir, runner.spd) / max_speed;
  inputs[5]  = dot(point{0, 1} * pod.dir, runner.spd) / max_speed;
  inputs[6]  = dot(point{1, 0} * pod.dir, runner.dir);
  inputs[7]  = dot(point{0, 1} * pod.dir, runner.dir);
  inputs[8]  = dot(point{1, 0} * pod.dir, game::points[runner.next] - pod.pos) / max_distance;
  inputs[9]  = dot(point{0, 1} * pod.dir, game::points[runner.next] - pod.pos) / max_distance;
  inputs[10] = dot(point{1, 0} * pod.dir, game::points[runner.next + 1] - pod.pos) / max_distance;
  inputs[11] = dot(point{0, 1} * pod.dir, game::points[runner.next + 1] - pod.pos) / max_distance;
  inputs[12] = dot(point{1, 0} * pod.dir, game::points[runner.next + 2] - pod.pos) / max_distance;
  inputs[13] = dot(point{0, 1} * pod.dir, game::points[runner.next + 2] - pod.pos) / max_distance;

@pb4608

7. Are you still working on this ? I will definitely start again working on my version of a Q-learning NN, let’s see if I can come close to you

I got a little bit tired of waiting for the NN trainings to complete actually, I need to speed it up but it would require to write multithreaded NN training code, or GPU training code, or use a NN library that does it already, or buy a new and more powerful computer… In any case it’s not going to happen soon

But I don’t give up, and I will probably go back to it at some point. Also, its proved to work great on CSB, but I’m wondering if I could also make it work for other multiplayer games.

@pb4608

8. I maintain my proposal to provide you with a good AI against which you can train your own AI.

Noted, thanks

@pb4608

9. I’d be interested to have an example of how you designed your visualization tool. Would you be willing to share your code ?

Well sure, here it is: /* -*- C++ -*- include/005-drawing ------------------------------------------ */ - Pastebin.com. I used the cairo 2D drawing library, and the window initialization code is Linux specific… but cairo is portable and can work with any OS windowing system as long as you can provide it a supported drawable surface (for example a Win32 surface, or PNG image). Something more portable using SDL or SFML libraries for the window creation could certainly be written, but I didn’t want to spend too much time on it.

There’s a ENABLE_DRAWING preprocessor switch that allows me to write things like this in my CG codes for local debugging without compilation or runtime errors when running the code on CG:

debug(auto game_debug = draw::init(16000, 9000, 800, 450));
// [...]
debug({
  draw::circle(game_debug, state[0].pos, pod_radius, draw::rgba{1., 0., 0., 1.});
  draw::circle(game_debug, game::points[state[0].next], point_radius, draw::rgba{0., 1., 0., 1.});
  draw::circle(game_debug, game::points[state[0].next + 1], point_radius, draw::rgba{0., 1., 0., 1.});
  
  draw::arrow(game_debug, state[0].pos, state[0].pos + state[0].spd * 1000., draw::rgba{1., 1., 0., 1.});
  draw::arrow(game_debug, state[0].pos, state[0].pos + state[0].dir * 5000., draw::rgba{1., 0., 1., 1.});
  
  draw::circle(game_debug, state[1].pos, pod_radius, draw::rgba{1., 0., 0., 1.});
  draw::circle(game_debug, game::points[state[1].next], point_radius, draw::rgba{0., 1., 0., 1.});
  draw::circle(game_debug, game::points[state[1].next + 1], point_radius, draw::rgba{0., 1., 0., 1.});
  
  draw::arrow(game_debug, state[1].pos, state[1].pos + state[1].spd * 1000., draw::rgba{1., 1., 0., 1.});
  draw::arrow(game_debug, state[1].pos, state[1].pos + state[1].dir * 5000., draw::rgba{1., 0., 1., 1.});
});
// [...]
debug({
  draw::flush(game_debug);
  std::this_thread::sleep_for(std::chrono::milliseconds(16));
  draw::clear(game_debug, draw::rgba{0., 0., 0., 0.75});
});