The drunkard knight's ride

If I knew the rules for moving pieces in 3D chess, I'd try out the formula on that.

Can someone work up a Klein bottle chessboard? 🙂

Originally posted by Paul Dirac II
For a rook on a standard board, E = 896. No matter what square you start a rook on, the degree d = 14.
M = 2(896)/14 = 128.

Same numbers hold if we put the rook on a cylindrical board.

Methinks I goofed on that one by double-counting the edges of the network.
This is my correction.

For a rook on a standard board, E = 448. No matter what square you start a rook on, the degree d = 14.
M = 2(448)/14 = 64.

Same numbers hold if we put the rook on a cylindrical board.

For a queen on a standard board, E = 728 (which is why I realized I had goofed on the number for a rook; a queen acts as rook + bishop) and d varies through 21, 23, 25, 27. This means M varies through
34 2/3
31 15/23
29 3/25
26 26/27

depending on the starting square.

Originally posted by Paul Dirac II
For a queen on a standard board, E = 728 (which is why I realized I had goofed on the number for a rook; a queen acts as rook + bishop) and d varies through 21, 23, 25, 27. This means M varies through
34 2/3
31 15/23
29 3/25
26 26/27

depending on the starting square.

Yikes, I goofed again, forgetting this time to apply the factor of 2 in the formula. Double those means for the queen on the standard board:
69 1/3
63 7/23
58 6/25
53 25/27

If Shallow Blue has the time to re-jigger his program to test any of the means I've calculated, that would be mighty fine.

Originally posted by Duncan Clarke
Can this be solved as if it was a probability problem?

Pardon me blathering on about this problem, but I find it captivating. 🙂

In order to try to connect the Markov chain theorem with something that looks more like probability, I am considering really simple cases.

Take a king at a1 on a board of only two squares, a1 and a2.

Markov: E = 1, d = 1; M = 2(1)/1 = 2.

Probability theory: With 100% probability, a1->a2. Then with 100% probability, a2->a1. Combining them, there is 100% probability that the length of the tour is always 2, so trivially the mean is also 2, in agreement with Markov theory.


Take a king at a2 on a board of three squares, a1, a2 and a3.

Markov: E = 2, d = 2; M = 2(2)/2 = 2.

Probability theory: With 50% probability, a2->a1. Then with 100% probability, a1->a2, finishing the tour. With 50% probability, a2->a3. Then with 100% probability, a3->a2, finishing the tour. So there are equal chances for two different paths, but each path has length 2, so the mean is trivially 2, in agreement with Markov theory.

Now place the king at a1 on the board of three squares, and we get something more interesting.

Markov: E = 2, d = 1; M = 2(2)/1 = 4.

Probability theory: With 100% probability, a1->a2. Then with 50% probability, a2->a3. Then with 100% probability, a3->a2. At this point, with 50% probability a2->a1, finishing the tour. But also at this point with 50% probability a2->a3, and so on. Let me use ^ to denote taking a power. The mean should be the weighted averages of the path lengths, i.e. the sum of:
(1/2) * 2
(1/2)^2 * 4
(1/2)^3 * 6
(1/2)^4 * 8
(1/2)^5 * 10
(1/2)^6 * 12
... (infinitely many terms)

Doing the powers, the mean is the sum of:
1
1
3/4
1/2
5/16
3/16
...

Adding up just the numbers explicitly shown above, the truncated sum is 3.75, which is getting close to the 4 from Markov theory.

Can someone prove my series above converges to 4?

Originally posted by Paul Dirac II
Can someone prove my series above converges to 4?

Using "S" as shorthand for the sum from n=1 to n=infinity, I see I can write the infinite series for the mean above as:

M = S n (1/2)^(n-1)

This calculation is probably an exercise in high school analysis. I'll think about it some more.

Originally posted by Paul Dirac II
This calculation is probably an exercise in high school analysis. I'll think about it some more.

I see my series is what they call arithmetic(o)-geometric:
http://planetmath.org/ArithmeticGeometricSeries

I can rewrite my series as 2S n (1/2)^n, and using formula (3) on that page, where q=1/2, and letting n go to infinity,
M = 2 (1/2)/(1-1/2)^2 = 4.

Voila.

Does anybody feel motivated to try working out the infinite series for a more complex case than just three squares on a single file?

Originally posted by Paul Dirac II
For a rook on a semi-infinite board, or a double semi-infinite board, or a fully infinite board, E = infinity and d = infinity.
M = 2(infinity)/infinity = indeterminate

I am going to conjecture that any time E and d are both infinite for some chess piece (we omit pawns which are irreversible, such that their network would be a directed graph rather ...[text shortened]... idered functions of the number k of squares on the board, and let k go to infinity.

Anybody?

Instead of defining k as the number of squares on the board, let me define k to be the number of edge squares on a square board, i.e. a k x k board.

For a rook on any square, d = 2(k-1). Each of the k^2 squares has 2(k-1) edges, and remembering to divide by 2 to account for double-counting of edges, E = (1/2) k^2 2(k-1). Then
M = 2E/d = 2 [(1/2) k^2 2(k-1)]/[2(k-1)] = k^2.
In the limit of infinite board size, k goes to infinity and M goes as the square of k, so M goes to infinity.

This proves my conjecture for the rook. The other pieces with infinite range (bishop and queen) could be handled in similar fashion.