Home » Blogs » jlamothe's blog

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 5x5. 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 6x6, 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 7x7, 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 8x8 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 10x10, 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.

Knight's Tour

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.

Oh noes!

...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 8x8, which might be possible.

break up the problem into smaller solvable problems?

Split the 10x10 problem into 4 pathes on 4 5x5 boards. You know you can solve the 5x5 quickly so now you just have to see if it is possible to "leap" from one 5x5 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.

optimization idea

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 may be on to something.

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 5x5 either, 6x6 and 7x7 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.

abandoning subtrees

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.

maybe...

...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.

On second thought...

...I'd really only need to check the eight squares that can be moved to from the place that has just been moved to.

use a parallel representation of the board

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).