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. 

18 March 2011

Across and UW

Time for an update. It seems the greater the gap between posts the harder it is to write a new post. But - no apologies, just action. Two major changes in my life have made life in Nairobi and my volunteer service much more enjoyable.

I started working full-time at Across in February. There is such an incredible difference between having a little work to do and having no work to do. I am happy to experience this difference at Across. The organization is all about holistic ministry in South Sudan. My job is part of Institutional and Organizational Development - spreading the word about Across to an international audience and sharpening the focus of our mission. A typical day includes editing documents written by others, compiling information for resource documents, and updating elements of the website. I feel like my computer skills are being used, and my desire to work alone or do things my own way is being kicked around in the dirt (N.B. a good thing). No word yet on if I will be traveling to South Sudan but I am eager to do so.

I just realized there is so much I want to share about my own evolving perspective on life and living. I really should use this blog as a medium for discussion, yes?

Anyway - the other major development is making a decision on graduate school. I have chosen to attend the University of Washington PhD program in Biostatistics. Of the schools I applied to, UW was the clear favorite (based on location, reputation, curriculum, and funding), despite being on the west coast away from the reasons I have to be on the east coast. I have two special agents doing housing reconnaissance in Seattle this spring, and I'm exploring a little each week to learn about the area. More to come!