I read this article about how Knight's Tours in Chess could be found with a neural network, so as a programming exercise I tried implementing it. What I found, however, is that it diverges and fails to find a solution much more than it converges, and I can't see how what I've done is any different than what's shown.
As a simple example, imagine a 3x3 chess board. There are 8 possible squares a knight could move to, and 8 neurons, each of which have exactly two neighbors. All eight neurons are part of the final solution. However, imagine that one neuron is generated initially with an output of 0, and two neighbors each with outputs of 1. Even though all neurons should be part of the final solution and should eventually have an output of 1, this one has already reached a stable state by having two active neighbors, even though it is inactive. As a result, the graph as a whole never reaches a stable state and diverges.
Testing my current program over 10,000 trials on the easiest possible board (3x3), yields a convergence rate of only 8.3%. An 8x8 board diverges 99.9925% over 40,000 trials. Contrast that with the screenshot in the link showing divergence rates of only 3% for an 8x8 board.
What am I missing here?
EDIT: I discovered the problem. The wikipedia summary (which I originally read first) was incorrect. It says that every neuron should update its state each turn, but there's a short passage in the blog article that says only neurons which are active change their states. Upon making that change, my failure rates have crashed down to just 13% for an 8x8 board. Thanks for the help.