21 March 2011

Knight's Path algorithm

Here is something I have been thinking about recently. (Warning: math/cs ahead.)

The Knight's Path Problem is something every computer science student tackles at some point, with the aim of writing a computer algorithm (that is, a series of steps to find a solution) to have a knight jump around a chess board and complete the circuit without jumping on the same square twice. Some people may define the problem differently. I ask a related question.
Given a random starting position, and assuming the knight makes random, legal moves without revisiting any position twice, what is the probability distribution of the path lengths?
A path length is defined as the number of moves the knight is able to make before getting stuck. Thus, the probability distribution of the number of path lengths tells us how likely a certain number of moves is to occur.

To begin, we tell the computer, "Computer, pick a random starting point." And the computer picks a position, such as (4,5), that corresponds to a square on an 8x8 chess board. (Note: we can generalize this to any size board.) Then, the algorithm (the Al Gore rhythm) randomly picks the next jump - based on how the knight moves (L-shape), the knight's position (won't jump off the board), and what squares have already been visited (won't go back). The algorithm stops when there are no more legal moves.

We can run the algorithm many times, say 10,000 times, and look at the distribution of path lengths.


What does this curve - the probability distribution function - tell us about the algorithm? 

If we look at a path length of 50, we see it has a probability of around .01, or 1%. Thus, we expect the algorithm to return a path length of 50 about 1% of the time.

The path length frequency peaks around 40, and there are very few path lengths less than 5 or greater than 60. (Of course, 1 <= path length <= 64.) 

One important feature of all probability distribution functions (PDFs) is that the area under the curve is always 1, which is i.o., since the likelihood of any event in the sample space occurring is 100%. 

I will post at least once more on this topic - keyword: optimize. 

1 comment:

  1. So, did you ever find a solution that met the requirement of landing in every square? Nicely done!

    ReplyDelete