Feb
20
Chess Pathfinder 1.1
So, after a talk on IRC with @flying_squirrel (Darcy), I decided to add a progress indicator to the program. This indicator would tell me what estimated percentage of the total number of permutations the program had exhausted and display this information in increments of 1%. As it turns out, this wasn’t very helpful. Let me explain:
Starting from the upper left hand corner (0, 0) the smallest board on which a path can be found has dimensions of 5×5. A path is found after exhausting somewhere between 1-2% of the possible permutations. As I mentioned in my previous blog entry, my computer essentially calculates this instantly.
If we increase the size of the board to 6×6, we don’t even use up 1% of the possible permutations and the result is still calculated in an imperceptibly small amount of time.
By the time we increase to 7×7, we’re still using less than 1% (I’m assuming much less) of the possible permutations, but the result takes a few fractions of a second to calculate.
At 8×8 it gets really interesting. The gauge still doesn’t register (as expected) but I let the program run for about a minute or so with no result.
This would seem to indicate that as the size of the board increases, the percentage of permutations that we need to exhaust decreases (I’m assuming exponentially) but the amount of time needed increases (also exponentially… which I kind of expected).
From this we can extrapolate that at a size of 10×10, I will probably die before the program reaches a conclusion. If there’s a better way of calculating this it’ll either involve a radical optimization of the existing program or (more likely) writing a new one from scratch.
Once again, here’s my code and documentation.
As a matter of interest, I left the original program running in the background. We’re currently sitting at 18+ hours with (surprise) still no result.
EDIT – 13 Feb 2011:
The source code and documentation were lost. I found the source cached on Google (it’s now hosted at GitHub) and regenerated the documentation.
Subscribe to RSS Feed
Follow us on Twitter
Our Mailing Lists
Visit Kwartzlab TV
…so right after posting this, a power surge knocked my computer off-line, killing the program.
Not that it would likely have done me any good anyways, but it does sadden me a little.
I’m trying again at 8×8, which might be possible.
Split the 10×10 problem into 4 pathes on 4 5×5 boards. You know you can solve the 5×5 quickly so now you just have to see if it is possible to “leap” from one 5×5 complete path to the next region and create a complete path from a non-corner entry point and end up close enough for a knight to jump to the next unfinished region.
That’s actually not a bad idea.
I can foresee a couple challenges that will present. For starters the function doesn’t have a predefined board size. In fact there’s not even any guarantee that both dimensions are the same, so I can’t guarantee it’ll break down neatly, but it’s definitely an idea to chew on for a while.
I don’t have to break it down into 5×5 either, 6×6 and 7×7 work nicely as well (probably also smaller boards with differing dimensions – I haven’t tried that yet). I can probably find a way to “tile” larger boards.
The trick (as you mentioned) will be making sure that the end position can make the hop, and then not getting boxed in.
Thanks.
On further thought, another idea to consider might be to try to weight the directions of the hops so that the piece has a tendency to concentrate in a specific region. That way I can prevent the last few spots that need filling from being scattered all over the board. Hopefully, this would result in more processor cycles being used per iteration, but fewer overall iterations because there would be less backing up.
instead of having 8 possible moves for each square, have a lookup table that tells you the legal moves at each square, your code is wasting time figuring this out anew each time (think what happens in a corner or edge!).
To gain insight into the search, dump the current path/board once in a while. You may notice that there are ways to prune the search tree by abandoning entire subtrees of the search by seeing where the program gets stuck searching fruitlessly.
You hit on an idea, if you have a board with an unreachable “hole”, you can abandon that line of search since you will never be able to complete the path. An unreachable hole is a position without another hole within a knight’s jump.
…but I can’t see a way of doing this without checking every empty space after every iteration. I would tend to think that the amount of cycles needed to do this at each iteration would outweigh what it would save me in the long run. :/
Still worth a shot though.
…I’d really only need to check the eight squares that can be moved to from the place that has just been moved to.
Each position counts the number of empty squares that can jump into it. On each move, updating this parallel board is fairly simple and on each update, if you find an empty square with zero, you can abandon that subtree (backtrack).
This is a well-known problem, usually known as the “Knight’s Tour”.
The Wikipedia article on it describes a couple interesting solutions.
Another interesting chess problem is the Eight Queens problem: place eight queens on a chessboard in such a way that none of them are attacking any others.