Originally posted by Duncan Clarke171 is another "in the ballpark" number, but not the exact number.
Sorry, 171 is starting from any square.
The knight starts from a corner square, so there's a probability of 0.5 that it will return after 2 moves, which is very significant.
It may also return in 4 moves, with a lower probability.
I'll work on it...
On the previous page Duncan Clarke laid out an array of numbers that makes it easy to find the number of edges in the network. Add up Duncan's numbers and you get 336. But this counts each edge twice, so divide by 2 and see that there are 168 edges, which matches what my source says.
We need a definition from network/graph theory: the degree of a vertex is the number of edges attached to that vertex.
Step 2
A branch of mathematics called Markov chain theory is concerned with random walks. One can prove that for a Markov chain that is modeled by an undirected network, if all edges at a given vertex are equally weighted the mean return time M to get back to a starting vertex is given by
M = 2E/d
where E is the total number of edges in the network and d is the degree of the starting vertex.
We know from part 1 that for a knight moving on an 8x8 board, E = 168. Since a corner square has two knight moves available to it, d = 2. Thus
M = 2(168)/2 = 168.
Shallow Blue's experimental approach and Duncan Clarke's theoretical approach both came close!
The book moves on to other topics in Markov chain theory, but I have been goofing around with other chess-like things we can do with the formula given above in this post. I'll plop them into one or more posts below.
If anybody wants to try out some other calculations, we could agree to use this terminology I am making up for variations on the chess board.
Standard board = good old 8x8 chess board
Punctured board = 8x8 with the four central squares missing
Cylindrical board = 8x8 rolled and glued so that a1 abuts a8 and h1 abuts h8.
Semi-infinite board = a1 and a8 are the only corner squares; there are an infinite number of files east of the h file.
Double semi-infinite board = a1 is the only corner square; there are an infinite number of files east of h and an infinite number of ranks north of 8.
Fully infinite board = there are no corner squares; the starting square has an infinite number of squares north, east, south and west of it.
For a king on the standard board, I get E = 210. If we put the king in a corner square, d = 3, and so
M = 2(210)/3 = 140.
For king starting on a perimeter square that is not a corner square, d = 5 and so
M = 2(210)/5 = 84.
For a king starting on a central square of a standard board, d = 8 and so
M = 2(210)/8 = 54.
For a king on a fully infinite board, E = infinity and d = 8, so
M = 2(infinity)/8 = infinity.
In this case the king will sometimes return in finite time to its starting square, but sometimes will wander off and never come back, driving the mean to infinity. This is what wolfgang worried might happen to the knight on a standard board, but in fact the mean return time was finite in that case.
For a bishop on a semi-infinite board, E = infinity. If the bishop starts in a corner square, d = 7, and
M = 2(infinity)/7 = infinity.
Starting the bishop anywhere else can give a different d, but M will still be infinity.
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 than an undirected graph), the mean return time M is infinite. A way to prove this would be to find a formula for E(k) and d(k) where they are considered functions of the number k of squares on the board, and let k go to infinity.
Anybody?
For a knight on a cylindrical board, E = 208. If the knight starts next to an end of the cylinder, d = 4, and
M = 2(208)/4 = 104.
If the knight starts one file away from an edge of the cylinder, d = 6 and
M = 2(208)/6 = 69 1/3. Hey, finally got a non-integer.
If the knight starts two or more files from an edge of the cylinder, d = 8 and
M = 2(208)/8 = 52.