Here’s a puzzle I ran across today:
Start a knight at a corner square of an otherwise-empty chessboard. Move the knight at random by choosing uniformly from the legal knight-moves at each step. What is the mean number of moves until the knight returns to the starting square?
There’s a slick mathematical solution that I’ll give later.
You could also find the answer via simulation: write a program to carry out a knight random walk and count how many steps it takes. Repeat this many times and average your counts.
Related post: A knight’s tour magic square
def move_knight(start_point, step_til_now)
if start_point == [0, 0] and step_til_now != 0 then return step_til_now end
next_points = [
[2, 1],
[-2, 1],
[2, -1],
[-2, -1],
[1, 2],
[1, -2],
[-1, 2],
[-1, -2]
].map{|x| [start_point[0] + x[0], start_point[1] + x[1]]}
.select{|x| x[0] >= 0 and x[0] =0 and x[1] < 8}
return move_knight(next_points[Random.rand next_points.length], step_til_now + 1)
end
puts (1..10000).map{|x| move_knight([0, 0], 0)}.reduce(0){|s,v| s+v}/10000.
Seems around 170 steps.
This is just a stupid simulation.
I will try probability method later.
In my simulation, the average seemed to be about 42.
Looking forward to the mathematical solution…
Hi, GlennF, can you provide your source?
My simulation running 10 million walks averaged out at ~121. Maybe I have an error somewhere though.
Java:
import java.awt.Point;
public class KnightWalk {
public static void main(String[] args) {
Simulator sim = new Simulator();
double average = sim.start(10000000);
System.out.println("Average number of moves: " + average);
}
}
class Simulator {
private int moves = 0, returns = 0;
private Point pos = new Point(0, 0);
public double start(int lim) {
while (returns < lim) {
pos = makeMove(pos);
moves++;
if (pos.x == 0 && pos.y == 0) {
returns++;
}
}
return moves / (double) returns;
}
private Point makeMove(Point pos) {
Point newPoint;
do {
newPoint = (Point) pos.clone();
int move = (int) (Math.random() * 7);
switch (move) {
case 0:
newPoint.translate(1, 2);
break;
case 1:
newPoint.translate(2, 1);
break;
case 2:
newPoint.translate(2, -1);
break;
case 3:
newPoint.translate(1, -2);
break;
case 4:
newPoint.translate(-1, -2);
break;
case 5:
newPoint.translate(-2, -1);
break;
case 6:
newPoint.translate(-2, 1);
break;
case 7:
newPoint.translate(-1, 2);
break;
}
} while (newPoint.x 7 || newPoint.y 7);
return newPoint;
}
}
Gah! I did have an error. ……. I only used 7 of the different moves… (Up 2 and left 1 was omitted)
Apologies. New result: 167.97
//int move = (int) (Math.random() * 7);
int move = (int) (Math.random() * 8);
Adn 167.97 is remarkably close to the number of edges in the “Knight’s Graph“.
Let’s see. On the 16 corner squares the knight has 8 moves, on the 16 squares adjacent to these it has 6 moves, on the 20 squares adjacent to these it has 4 moves, on the 8 squares on the edge adjacent to the corner it has 3 moves, and on the corner it has 2 moves.
This is just a random walk on the graph where each square is a vertex and two vertices are adjacent if they are separated by a knight’s move. A random walk on this graph is a reversible Markov chain, as the transition matrix is symmetric, so the probability that the knight is in a given square is just 2/(total degree)= 2/336=1/168. The mean recurrence time is just the inverse of this, or 168 moves.
To deinst:
My intuition tells me you are right.
But your solution suggests that the result is irrelative to the start position. Am I right?
Priezt: I think he took that into account with the 2 in ‘2/(total degree)’ I.e. if you were in a centre block, which has 8 moves, then it would be 1/(8/336) for the total length, which is 42… Which I just verified is correct on another 10 million walks. deinst: you just made that so simple..
To Levi:
I tried to start from a 8-move block and end in a 6-move block.
The result was around 68.
How did this come out of the formula?
Pirezt: I just made a test case for that and my result was 2.8… To be honest, I think that when we make the path lead from one square to another square with a different probability, then we make the search asymmetric – which breaks the markov model (or makes it more complex, I have no idea tbh).
Hopefully deinst can help us.
Does the average exists?
answer is 168.
simulation, little more smart: https://gist.github.com/2644098
deinst :
the transition matrix is symmetric, so the probability that the knight is in a given square is just 2/(total degree)= 2/336=1/168. The mean recurrence time is just the inverse of this, or 168 moves.
1) what is “degree”? Number of edges?
2) what is “probability that the knight is in a given square” ? Should not it converge to 1/64.0, by number of squares?
3) why the formula is right, that expectation of path length is “number of all edges / number of input edges” ? I did quick look into wikipedia, by can’t catch the idea. ( http://en.wikipedia.org/wiki/Random_walk#Random_walk_on_graphs )
@dobokrot
1) The degree of a vertex is the number of edges incident on it.
2) No! Think of it this way, you have lots of knights the size of water molecules simultaneously moving about the chessboard, randomly choosing the next place to go. When the system reaches its steady state (it will, this is not obvious) then the flow in one direction across one edge is the same as the flow in the other. As the flow across an edge from a vertex is proportional to the number of knights on that vertex divided by the number of edges attached to that vertex, we see that for any two squares, the relative probability between two vertices is equivalent to the relative degree.
3) From the fact that the relative probabilities are proportional to the relative degrees, you see that a solution is that the probability is proportional to the degree (the fact that this solution is unique is ‘obvious’ from the physical intuition with the flow, but tricky to prove.)
@Levi If you break the symmetry, things get much more complex. With only 64 vertices, you can solve it with with linear algebra, but much bigger, and simulation is a better choice, and considerably easier.
I get an average of 9 moves, a median of 3.
You seem all to forget that the board size is limited (chess board is 8×8 fields big).
My source:
http://pastebin.com/6cg624uc
Deinst’s explanation (2) is amazing.
I think if I were going to simulate this, I would construct a sequence of state vectors S_n, each of length 64, giving the probability of being on each square after n moves. With the elements of S_n decreasing exponentially (no ???), sum(n*S_n) should converge pretty quickly to the answer (n0???).
Yes, the Markov chain solution is amazing. That’s the slick solution I had in mind.
As for simulation, the accuracy of your estimate after N simulations will be O( 1/sqrt(N) ).
@matthias your getnewy has a sign error in case 7
@Aakash Mehendale:
Thank you so much! I modified it to use the point-class Levi also used and also got to 168 and was already wondering where my error was :)
Maybe I’m just crazy, but since this is a potentially infinite random set, is it even possible to reliably determine the mean? After all, there is a possibility that the knight gets caught in an infinite loop and never returns to the original corner.
@Christopher Allen-Poole the knight returns almost surely, which is good enough for our purposes.
Christopher: It’s conceivable that the knight could get caught in an infinite loop, but this has probability zero. If executing a loop has probability p, the probability of executing that same loop k times in a row is p^k, so as k grows, this probability goes to zero.
For every N, there are paths of length N that do not return to the starting point. But as N grows, the probabilities of these paths decrease faster than their numbers increase, so the infinite sum defining the expected time converges.
Oops… sorry to cause folks distress earlier. I found the bug in my code… essentially I had accidentally restricted the possible knights moves to always be +- 2 steps horizontally and +-1 step vertically. With the bug fixed, I also get a mean of 168.
Convergence seems fast for O(1/sqrt(n)). I get 168 to 10 decimal points with 6925 iterations. Priezt is right, the answer depends on the start position, and is a function of the degree of the vertex, specifically 336/degree. So if you start near the center of the board, the mean to return is 336/8=42 moves. Also, (bishop, rook, queen, king, knight)=(40, 64, 69.33333, 140, 168). Starting from the corner, the bishop gets back soonest on average.
How many ways could a knight get caught in an infinite loop?
How many ways could a knight return to its starting position?
Are the two values the same?
Does an infinite sequence of moves exist avoiding loops?
I tried experimenting with connected graphs having various numbers of vertices and random connections. If the graph has E edges, and you start at a vertex with degree K, the mean return time is 2*E/K. Despite deinst’s efforts, it’s still not clear why to me.
Cool problem John. It looks like a classic example where generalizing the problem makes it easier to analyze and understand.
Followup statement: For every sequence of moves returning the knight to its starting position that you hand me, I can hand you one that differs by the last step and so does not return.
Christopher Allen-Poole is correct. The calculation of the mean is nonsense. The fact that simulation matched the Markov chain model has some of you fooled. Your programs avoid inifinite loops and your random number generators try to as well, the Markov model does the same thing under the hood too. So there is nothing amazing here to me about 168.
The problem is not stated clearly enough to get a rigorous answer and it is contrived in more ways than one.
These are my thoughts anyhow.
The “real-world” question is my favorite. I guess one could have faith that the knight returns more often than not; the likelyhood of this to me is almost surely absurd :-).
But surely, Jeff, that argument would apply to the geometric distribution, which _does_ have a well-defined mean?
I mean, if you could how many coin tosses it takes you to toss a head, you could say ‘what about tail, tail, tail…?’ – but it’s ok because the probability of your ‘different last step’ series gets vanishingly small and you end up with a geometric series that sums to two.
I imagine I’ve missed a subtlety in your argument, though – how would you have phrased the question differently?
I think Jeff’s point is valid. However, I also think that we can avoid the problem mathematically by limiting our event space to sequences of moves that terminate, i.e. those that do return to the origin. We can calculate the probability of each such path, and the (countably infinite and absolutely convergent) sum of their probabilities is 1.0. Whether or not this models the “real world” is a question that goes beyond math.
@SteveBrooklineMA
Limiting the event space makes the problem concise, but the Markov chain solution still lacks rigor.
To help you better understand my point I suggest reading a more conrete and meaningful application of Markov chains, namely on the Kruskal Count card trick. I think Lagaias co-authored a paper on it.
I tried to limit board size to 3*3 and 4*4, the formula still worked. Cool.
I really should read more about Markov chain.
@Colin Beveridge
You’ll just have to reread my followup statement above. It’s so lucid that I actually am a bit proud of myself for saying it.
A test to a mathematician is to explain it away in rigorous fashion … Good luck with that.
P.S. I know how to beat casino Roulette.
Plot twist: generalize it to an n x n board. What if it’s an infinite board?
Tadeu: See this Math Overflow question re infinite knight tours