Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

1 Answer

up vote 1 down vote accepted

The article you link to admits that the algorithm is not guaranteed to find a knight's tour:

However, there are many other solutions that would satisfy the network that are not knight's tours. For example, the network could discover two or more small independent circuits within the knight's graph. In addition, there are certain cases that will cause the network to diverge (never become stable)....

In fact, the probability of obtaining a knight's tour on an n x n board virtually vanishes as n grows larger. Takefuji, at the time of his publication, only obtained solutions for n <= 20. Parberry was able to obtain a single knight's tour out of 40,000 trials for n = 26. I obtained one knight's tour out of about 200,000 trials for n = 28 (three days' worth of calculation on my Pentium IV). Parberry wisely asserts that attempting to find a knight's tour for n >= 30 using this method would be futile.

EDIT: Others have tried to implement this algorithm. One reports that he had to change the algorithm to get valid solutions. See http://stackoverflow.com/questions/1551157/knights-tour-using-a-neural-network and http://www.yacoby.net/programming/knights-tour.html for one programmer's experience.

share|improve this answer
    
The screenshot in the link shows divergence rates of 3% for an 8x8 board. I'm getting divergence rates of 99.9925%. There's gotta be more to this. –  Strill Dec 3 '11 at 14:06
    
You may be confusing "converges" with "finds a knight's tour" and confusing "stable solution" with "knight's tour". How many of your trials did not halt? Another possibility is that you've made an error in your code -- but then we're talking about a programming question that may not be suitable for this forum. –  Doug Chatham Dec 3 '11 at 14:23
    
When I say "diverge", I mean it reaches a situation where the state increments infinitely on one or more neurons. In other words, 99.9925% of my trials on the 8x8 board did not halt. I understand the potential for programming mistakes, but I came here because I confirmed that what my program was doing was exactly what I intended for it to do, and that what I intended is obviously wrong. I gave the example for a 3x3 board in the OP to illustrate how easy it is to diverge. –  Strill Dec 3 '11 at 14:31
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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