16 Jan 15
Originally posted by Paul Dirac IIMethinks I goofed on that one by double-counting the edges of the network.
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.
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.
17 Jan 15
Originally posted by Paul Dirac IIYikes, 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:
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.
69 1/3
63 7/23
58 6/25
53 25/27
18 Jan 15
Originally posted by Duncan ClarkePardon me blathering on about this problem, but I find it captivating. 🙂
Can this be solved as if it was a probability problem?
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?
18 Jan 15
Originally posted by Paul Dirac IIUsing "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:
Can someone prove my series above converges to 4?
M = S n (1/2)^(n-1)
This calculation is probably an exercise in high school analysis. I'll think about it some more.
18 Jan 15
1 edit
Originally posted by Paul Dirac III see my series is what they call arithmetic(o)-geometric:
This calculation is probably an exercise in high school analysis. I'll think about it some more.
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?
18 Jan 15
1 edit
Originally posted by Paul Dirac IIInstead 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 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?
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.