The drunkard knight's ride

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...

Originally posted by Duncan Clarke
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...

171 is another "in the ballpark" number, but not the exact number.

Thinking again. The knight has 6 possible 2nd moves, so the chance to returning on move 2 is 1/6.

Originally posted by Duncan Clarke
Thinking again. The knight has 6 possible 2nd moves, so the chance to returning on move 2 is 1/6.

Since at least one person is actively working on this, I may hold off another day on presenting the answer.

Originally posted by Paul Dirac II
Since at least one person is actively working on this, I may hold off another day on presenting the answer.

Just a guess: 64*pi

😉

Originally posted by wolfgang59
Just a guess: 64*pi

😉

Hey, that method worked for you four months ago on a different problem I posed. 😛

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.

Sticking with the knight as the chess piece so that E remains 168, but putting the knight onto a central square of the standard board (like d4) which has degree 8, the mean return time is
M = 2(168)/8 = 42.

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 punctured board, I get E = 186.

If the king starts on an external corner (such as a1),
M = 2(186)/3 = 122.

If the king starts next to the puncture (such as d3), d = 6, and
M = 2(186)/6 = 61.

(All means are integers so far.)

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.

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.