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.

Improve this question
$\endgroup$
12
  • $\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, 2017 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, 2017 at 21:19
  • $\begingroup$ @liangjy I am using tanh as an activation function for each neuron. $\endgroup$
    – Daniel
    Apr 11, 2017 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, 2017 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, 2017 at 10:26

1 Answer 1

Reset to default
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$
1
  • $\begingroup$ I’m pretty confident this is the answer! $\endgroup$
    – Nicholas James Bailey
    Jul 13, 2020 at 15:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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