0
$\begingroup$

(* edited as per comments below *)

I've been working on the expected number of moves a lone knight on a chess board needs to make to get from position (i,j) on a chess board to position (8,8) at the upper right corner. I am using the expression for the number of moves to get from position $(i,j)$ to $(k,l)$ as $$ E_{i,j}=1+\frac{1}{N_{i,j}} \sum_{\begin{array}{c}(i',j')\in N_{i,j}\\(i',j')\neq (k,l)\end{array}}E_{i,j} $$ and then solving the resulting 64 equations for the variables $E_{i,j}$. See Link to Quora for description. I then round to integers and place the number of moves in each square of the chess board: enter image description here For example, it takes an estimated 213 moves to move from position (1,1) to (8,8). And it takes 168 (estimated) moves to even start at (8,8) and return to (8,8).

I was wondering if someone could explain the obvious diagonal symmetry of the numbers. For example, starting at the top right is 168 moves then diagonally, (202) and (202) then 196, 208, 196, and so fourth. It seems somewhat similar to Pascal's Triangle and was wondering if that's related to this problem.

Thanks, Dominic

$\endgroup$
  • 1
    $\begingroup$ Is the last $196$ a typo? Btw. Pascals triangle can pop up in random walks sure. $\endgroup$ – Natural Number Guy Dec 17 '19 at 16:15
  • $\begingroup$ Thanks for commenting, if you're referring to (6,8) and (8,6)=196 I believe those are correct although I'm new to this type of calculation and may have made a mistake in the coding. I'll look into random walks and Pascal's Triangle too. $\endgroup$ – Dominic Dec 17 '19 at 17:28
2
$\begingroup$

A single $1,2$ move by a knight feels 'asymmetrical', and so the symmetry may at first sight be surprising from that perspective.

However, note that the expected number of moves that you re calculating is a function of all possible moves the knight could be making, and for every move the knight can make, there is a 'mirror' move that the knight can make as well. Or, more to the point: for every path a knight may take, you can mirror that path in the bottom-left-to-top-right diagonal.

For example, the first move from $(1,1)$ can go to $(2,3)$ or to $(3,2)$, which are the 'mirror' moves of each other when mirrored in the diagonal. Likewise, moving from $(2,3)$ to $(3,5)$ in the one case would be mirrored by going from $(3,2)$ to $(5,3)$ in the other case.

Indeed, every sequence of moves has a perfect mirror, and since the choice of moves is perfectly random, each of these mirror sequences is equally likely. So, from that perspective, the symmetry is in fact easily explained.

If you still don't see it, here is one more thing that you could do: Start the knight on $(1,1)$, and record for all possible subsequent moves, how many times a knight could have visited a square for each of the squares given all possible moves/paths. Thus, at the start, the $(1,1)$ square has a value of $1$, and all other squares a value of $0$. After he first move, the $(1,1)$, $(2,3)$, and $(3,2)$ squares all have a value of $1$. After two moves, $(1,1)$ will have a value of $3$ (you can go back to $(1,1)$ from both $(2,3)$ and $(3,2)$), and a bunch more squares will have a value of $1$ ... but I think you'll quickly find that the number remains symmetrical along the diagonal ... and the expected number of moves (which is function of all possible paths) is therefore symmetrical as well.

$\endgroup$
  • $\begingroup$ Thanks for that Bram. I did word it wrong above: I meant each square represents the expected number of moves to get to square (8,8). I do have confirmation from other sources that (1,1)=213 and (8,8)=168 so those two in my plot are correct. Will edit above. $\endgroup$ – Dominic Dec 18 '19 at 12:47
  • $\begingroup$ Sorry, above I meant, "the number in each square in the diagram above represents the expected number of moves to get from that square to square (8,8). $\endgroup$ – Dominic Dec 18 '19 at 13:14
  • $\begingroup$ @Dominic Aha! Yes, now it all makes sense! Of course it would take exactly one more move to get from $(1,1)$ to $(8,8)$ as opposed to going from $(2,3)$ or its mirror $(3,2)$ to $(8,8)$ given that you have to go through (and can only go through) $(2,3)$ or its mirror. Likewise, it obviously takes one extra move to go from $(8,8)$ to $(8,8)$ as opposed to going from $(6,7)$ or its mirror $(7,6)$ to $(8,8)$ as the former has to go through, and can only go through $(6,7)$ or its mirror. $\endgroup$ – Bram28 Dec 18 '19 at 14:41
  • $\begingroup$ @Dominic The $209$ for $(1,7)$ is still a little surprising given the $210$ for $(2,5)$, the $206$ for $(3,6)$, and the $207$ for $(3,8)$: you'd expect that to be $\frac{1}{3}\cdot 210 + \frac{1}{3}\cdot 207 +\frac{1}{3}\cdot 206$ which is a bit below $208$, but I assume those are whole-number-rounding artefacts?. $\endgroup$ – Bram28 Dec 18 '19 at 14:43
1
$\begingroup$

Thought I would post my results of the suggestion above by Bram to determine how often each square is visited starting at (1,1): I wrote a recursive Mathematica routine (code below) which begins counting at (1,1) then branching to all the other squares according to the neighbors of each square. So as above, (1,1)=1 at first then (2,3)=1, (3,2)=1, then branch to the position (2,3) having neighbors {{3, 5}, {4, 4}, {4, 2}, {3, 1}, {1, 1}, {1, 5}} so count those, do the same for (3,2), then count all those neighbors and so on. Here are the results after 7 recursions which does indeed exhibit diagonal symmetry: $$ \left( \begin{array}{cccccccc} 906 & 536 & 1892 & 746 & 1936 & 516 & 1221 & 216 \\ 556 & 2380 & 910 & 3064 & 948 & 2724 & 612 & 1221 \\ 2228 & 866 & 4482 & 1338 & 4447 & 940 & 2724 & 516 \\ 982 & 3650 & 1558 & 4724 & 1576 & 4447 & 948 & 1936 \\ 2337 & 1320 & 4806 & 2032 & 4724 & 1338 & 3064 & 746 \\ 908 & 3857 & 1344 & 4806 & 1558 & 4482 & 910 & 1892 \\ 1845 & 788 & 3857 & 1320 & 3650 & 866 & 2380 & 536 \\ 283 & 1845 & 908 & 2337 & 982 & 2228 & 556 & 906 \\ \end{array} \right) $$

sumMatrix = Table[0, {8}, {8}];
Quiet@Table[v[i, j] =., {i, 1, 8}, {j, 1, 8}];
getNeighbors[i_, j_] := 
  Select[{i, j} + # & /@ {{1, 2}, {2, 
      1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1}, {-2, 1}, {-1, 2}}, 
   1 <= #[[1]] <= 8 && 1 <= #[[2]] <= 8 &];
tMatrix = Table[getNeighbors[i, j], {i, 1, 8}, {j, 1, 8}];

tallyVisits[current_, max_] := Module[{},
   If[max > 0,
     neighbors = tMatrix[[current[[1]], current[[2]]]];
     (sumMatrix[[#[[1]], #[[2]]]]++) & /@ neighbors;
     tallyVisits[#, max - 1] & /@ neighbors;
     ];
   ];
matrixSet = {};
totalSet = 7;
For[j = 1, j <= totalSet, j++,
  sumMatrix[[1, 1]] = 1;
  tallyVisits[{1, 1}, j];
  newMatrix = {};
  For[i = 1, i <= 8, i++,
   AppendTo[newMatrix, sumMatrix[[9 - i]]];
   ];
  AppendTo[matrixSet, newMatrix];
  ];
myList = (# // MatrixForm) & /@ matrixSet
$\endgroup$
  • $\begingroup$ Did that help in making it clear to you why it's all symmetrical? Interesting numbers by the way ... what strikes me is the 'high'/'low' alternation ... basically, any $(x,y)$ with $x+y$ being odd has a relatively high number, compared to the even $x+y$'s ... which feels very surprising to me: given that a knight moves from an 'even' to an 'odd', you'd expect those numbers to be similar .... Oh! I see: if you calculate the numbers for the very next generation, all the 'even' ones would be 'high', and all the odd ones 'low'! $\endgroup$ – Bram28 Dec 18 '19 at 14:50
  • $\begingroup$ Too bad these numbers don;t reflect the numbers from the other matrix ... I don;t know why they would, but I thought maybe ... I guess not. You just get the symmetry! Thanks for doing this :) $\endgroup$ – Bram28 Dec 18 '19 at 14:51
  • $\begingroup$ Yes, thanks Bram. I see now why they're symmetrical. $\endgroup$ – Dominic Dec 18 '19 at 17:52
0
$\begingroup$

One more update if I may: This time I ran a 10,000 sample Monte-Carlo run for each square (simply randomly select neighbors until the destination of (8,8) is reached and do this 10,000 times for each square and find the mean. The plot below shows the estimated times and the difference between the estimated time and the Monte-Carlo results: enter image description here

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.