6
$\begingroup$

I recently embarked on a very ambitious project and I have to say it has turned out a lot better than I expected, I succeeded in coding from scratch a neural network that plays checkers at a very acceptable level.

I have one problem though which prevents me from having a stronger AI, I guess some people would call it overfitting, I'm not sure if the term is correct in this situation.

The main issue is that after a certain amout of generations the weights become so great that the smallest change in the state of the board changes the evaluation of it drastically, effectively limiting any kind of nuanced analysis.

A bit more information:

Neural Network Structure:

Input layer is a series of indipendent layers which take as input a section of the board (1, 0.5, -0.5 and -1 are the inputs taken from the board).

I am using 2 hidden layers of approximately 30 and 10 nodes each, the output node is an evaluation of the board.

Genetic Algorithm

30 Neural Networks are generated randomly with weights from -0.2 to 0.2, they play 20 games against random opponents and they are rated accordingly (-2 points for a loss, -1 for a draw [120 moves with no winner] and 1 point for a win).

The 15 best are kept and copy/pasted on top of the 15 worst ones, then each weight of the new networks are mutated using the following equation:

$m' = m * e^{r*0.9} $

$w' = w * m' * r$

Where $m$ is the mutation parameter of that specific weight which starts off at 0.05, $r$ is a random standard Gaussian number and $w$ is the weight.

I hope someone here can help me figure out how to prevent the weights from going haywire after the 40th or so generation.

$\endgroup$
  • $\begingroup$ Try using activation functions (sigmoid/tanh) after your hidden layers or gradient clipping; these should limit the magnitude of your weight updates. $\endgroup$ – liangjy Apr 11 '17 at 21:09
  • $\begingroup$ @liangjy: There are no gradient calculations involved in this model's training. The weights are mutated randomly instead. For some reason, higher weight individuals are winning initial games, but it is not really clear why to me. $\endgroup$ – Neil Slater Apr 11 '17 at 21:19
  • $\begingroup$ @liangjy I am using tanh as an activation function for each neuron. $\endgroup$ – Daniel Apr 11 '17 at 23:43
  • 1
    $\begingroup$ The algorithm looks as much like particle swarm optimisation as a GA, due to amount of movement in the weights and lack of cross-over between selected parents to create offspring. Given the simplicity of the network and search algorithm, I would not expect much learning to happen at all. How are you measuring results such that you observe the agent "plays checkers at a very acceptable level"? $\endgroup$ – Neil Slater Apr 12 '17 at 7:49
  • $\begingroup$ @NeilSlater The testing of the actual strength of the network has been one of the issues, thankfully I've had a lot of people willing to test it out, none of them great checkers players by any means but they all reported having a lot of trouble beating the AI. Myself included, I have probably won about 5% of the games I've played against one of the networks in the 30-40th generation, but then again I'm terrible at checkers. I also tested it against some online checkers engine and it has beaten all of them. Against really advanced engines like cakeMD it struggles a lot in the end game. $\endgroup$ – Daniel Apr 12 '17 at 10:26
1
$\begingroup$

Full disclosure, I'm not at all an expert on genetic algorithms, so take this with a grain of salt.

First of all, I'm not sure the $r$ parameter in $w'=w*m'*r$ makes sense. You say it's a random standard Gaussian number, which means it could totally change the sign of $w'$. That seems bad. Am I understanding that correctly?

That aside, answering your actual question of controlling weights that get out of control: I would re-normalize the weights after each iteration, e.g. by dividing by its norm: $w'' = w' / ||w'||$. This will allow the weights to shift around, but will keep them from exploding.

| improve this answer | |
$\endgroup$
  • $\begingroup$ I’m pretty confident this is the answer! $\endgroup$ – Nicholas James Bailey Jul 13 at 15:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.