# Collisions between rooks taking random flights on an N by M chessboard

I randomly place $k$ rooks on an (arbitrarily sized) $N$ by $M$ chessboard. Until only one rook remains, for each of $P$ time intervals we move the pieces as follows:

(1) We choose one of the $k$ rooks on the board with uniform probability.

(2) We choose a direction for the rook, $(N, W, E, S)$, with uniform probability.

(3) We choose a number of squares in which to move the rook along the direction chosen in  with uniform probability over the interval consisting of the rook's current position to the edge of the board.

(4) If the rook being moved collides with another piece while being translated in , just as in regular chess it will annihilate that piece and remain at the piece's former position.

NOTE - An alternative way of stating , , and  would be to say that the chosen rook samples all possible sets of moves, with uniform probability, and is unable to bypass other rooks without annihilating them and stopping at their former positions.

NOTE 2 - Gerhard Paseman is correct in suggesting that the original formulation for  and  will bias the rook towards shorter path lengths. This is in part due to the choice of direction in  not being weighted by the resulting possible number of choices in , and also the over-counting of positions in  due to the lack of consideration that there may be a collision. There are also problems with  near the board's boundaries where a direction can be chosen in which no move can take place. Instead of  and , I'll suggest that a better method would be to number all possible position that the chosen rook from  can occupy (keeping the collision constraint from  in mind), and then use a PRNG to select the next position.

What does the distribution look like for the number of time intervals, $P$, necessary for only a single rook to remain on the board?

• This really calls for an actual implementation and numerical experimentation! – Per Alexandersson Sep 23 '12 at 18:44
• @Per Alexandersson, Absolutely you're right. But I posted the question here because I would be really interested if there are any techniques for tackling this problem in lieu of simulations. – T.R. Sep 23 '12 at 19:19
• Actually, there are different ways of making things uniform while getting different distributions. Your choices 2 and 3 do not uniformly sample all moves open to a rook. Not only is there bias towards shorter directions but also towards impact. In spite of the responders efforts, I bet a graph or set of statistics showing what directions and lengths were taken (or what positions were occupied) would be markedly different with each implementation. Gerhard "Ask Me About System Design" Paseman, 2012.09.23 – Gerhard Paseman Sep 23 '12 at 23:27
• Also, I might suggest the literature on random walks in graphs. I am too ignorant to give a good pointer, but perhaps Brendan McKay (or maybe Douglas Zare or Igor Rivin?) knows the literature well enough to give you a start. A 14-regular graph on 64 vertices might give you the structure you desire, with tweaking to take care of stopping a rook upon collision. Gerhard "Ten Moves For Two Rooks?" Paseman, 2012.09.23 – Gerhard Paseman Sep 23 '12 at 23:33

To supplement Per Alexandersson's and Aaron Golden's data, here are two distributions for $4$ rooks on a $4 \times 4$ board (mean: 21.5 moves), and $8$ rooks on an $8 \times 8$ board (mean: 73.6 moves):  10,000 trials each. Now updated to count only moves that actually move a rook! Here is a $4 \times 4$ example that took $19$ moves. • (I miscounted the moves in the first version I posted.) – Joseph O'Rourke Sep 23 '12 at 20:26
• In your implementation are rooks allowed to choose non-moves, e.g. choosing to move 0 spaces or choosing to move past an edge of the board (then the move would be clamped, I guess). After some more debugging I'm seeing numbers similar to yours, but my average move counts are consistently slightly higher than yours. – Aaron Golden Sep 23 '12 at 21:22
• @Aaron: I did count an attempt to move off the board as a move. Another possible difference is that, if a rook moved into the board, and had $k$ possible steps to the edge of the board, I chose uniformly among $\lbrace 1,2,\ldots,k \rbrace$, i.e., not including $0$. – Joseph O'Rourke Sep 23 '12 at 23:41
• @Joseph O'Rourke, as a word of explanation for my original choice of , I was imagining that whatever was moving the rook wouldn't have global information about the rook's position on the board. To make an extremely tenuous connection, I thought of this question after reading a paper on how (GPS tracked) albatrosses' execute Lévy flights while engaging in foraging behavior: (pnas.org/content/early/2012/04/18/1121201109.abstract) – T.R. Sep 24 '12 at 12:07
• I bet the bulk of the movements come from resolving the position of two rooks on the board. Once statistics for two rooks are developed, I predict that k rooks will be easy to derive from the two rook situation. Gerhard "Also Selling Some Famous Bridges" Paseman, 2012.09.24 – Gerhard Paseman Sep 25 '12 at 0:38

Joseph O'Rourke beat me to it, but here is yet another set of data. This is starting from an 8x8 board completely filled with rooks. The x-axis is the number of moves needed to eliminate all but one rook. The y-axis is the number of times this number of moves was sufficient, divided by the number of trials (1,000,000). The random number generator in use is just C's standard library random mod whatever maximum is allowed for a given number, so the random numbers are not quite uniformly distributed. I should also note that in my implementation I am allowing a rook to choose to move in any direction, even if not all directions are available, so sometimes a step is taken in which no rook moves. This will increase the number of moves necessary by a little bit. The mean number of moves in my trials is 199.

For the 4x4 with 4 rooks case I get a mean of 31 moves. For the 8x8 with 8 rooks case I get a mean of 94 moves, and for a 2x2 board with 2 rooks I get a mean of 7 moves. My implementation now produces results that agree with Joseph O'Rourke's version. Previously my implementation had a bug that caused moves to be allowed one extra square to the East and one extra square to the South, causing my average move counts to be too high. • I got very similar graphs as well for the distribution of the number of moves needed. I used the same algorithm; sometimes, a move is not an actual move. – Per Alexandersson Sep 23 '12 at 20:21
• @Aaron: Now I altered my data to count only moves that actually move, so again our data is out of synch.:-) But I do think we are in accord in spirit now, even if not in the counting details. – Joseph O'Rourke Sep 24 '12 at 20:51
• @Joseph: Yes if I modify my version to avoid counting null moves I see the same mean move counts as you for the 4x4 (4 rooks) and 8x8 (8 rooks) case. – Aaron Golden Sep 25 '12 at 4:18
• @Aaron: Reassuring that the simulations all agree! – Joseph O'Rourke Sep 25 '12 at 11:59

Depending on the precise model (see NOTE 2), each rook has probability of order $1/n$ of capturing another in a given step (they need to be on the same row, and then the probability is $O(1)$. Note also that the positions of rooks are mixed very quickly (this random walk mixes in $O(1)$ steps.

This brings this process into the range of Kingman's coalescent. As $n\to\infty$, the model can be approximated as follows: When there are $k$ rooks left, each pair of rooks merge at rate $a/(kn)$, where $a$ is some constant that can be computed. T(he $1/k$ factor is from the probability that one of them is moved; If the rooks moves were timed independently it would not be there.) There are $\binom{k}{2}$ pairs.

The time until a single rook is left is roughly a sum of independent exponentials, which will be asymptotically concentrated near $2n\log(M)/a$, where $M$ is the initial number of rooks.

So, I did some numerical experiments on 4 rooks on a k times k board. Each data point is the mean of 500 runs.

The x axis is the width/height of the board, the y axis is the number of iterations needed for it to be only one rook left.

EDITED: So, I did some changes and now my data conforms with the others:

1) Choose rook. 2) Choose direction. 3) If direction does not allow moving in that direction, goto 2. 4) Move 1,2,.. or k steps in direction chosen, where k gives a boundary square.

I.e. this does not count non-moves (which the image ABOVE do).

The image below shows mean of 500 runs, k rooks on a k*k board, starting at k=1. • @Per: What does the data point mean for a $1 \times 1$ board? – Joseph O'Rourke Sep 24 '12 at 0:36
• Oh, right, I was too quick creating the graph; the first data point is 4x4, the next is 5x5, etc. – Per Alexandersson Sep 24 '12 at 5:52
• @jc Fixed, there was a difference in implementation. – Per Alexandersson Sep 25 '12 at 6:12
• @Per: Does that look to you like exponential growth? – Joseph O'Rourke Sep 25 '12 at 12:00
• @Joseph O'Rourke: I have no idea, really, I'll try a few more experiments. – Per Alexandersson Sep 25 '12 at 19:17

It occurred to me it might be of interest to see what happens if you start with a board completely clogged with rooks*, so I decided to pluck the lowest-hanging nontrivial fruit and examine the $2\times2$ case, which features 5 distinct states: the starting state $S$ with 4 rooks, a trio state $T$, a pair of doublet states $R$ and $D$ with the rooks lined up in a row or along a diagonal, respectively, and the quitting state $Q$ with just one rook.

In this set-up, state $S$ transitions in one step to $T$ (I'm assuming here that when you pick a rook at random, you actually have to move it). State $T$ transitions back to itself with probability 1/3, to $R$ with probability 1/3, and to $D$ with probability 1/3. State $D$ transitions to $R$ with probability 1, while $R$ transitions to $D$ with probability 1/2 and to $Q$ with probability 1/2. For the expected number of steps to get to $Q$, we thus have

$$E(S) = 1+E(T)$$ $$E(T) = 1 +{1\over3}(E(T)+E(R)+E(D)$$ $$E(D) = 1 + E(R)$$ $$E(R) = 1 + {1\over2}E(D)$$ from which one finds $E(R) = 3$, $E(D) = 4$, $E(T) = 5$, and $E(S) = 6$.

It seems doubtful that the expected values will be integers in general, but it might be worth checking the $2\times3$ and $3\times3$ cases, which ought to be doable. (The $2\times3$ case, which has 23 essentially different states, might be a good place to experiment with different conventions for the transition probabilities.) One thing worth noting: The states $R$ and $D$ are equiprobable when starting from $S$, but not if you create a 2-rook state from scratch by placing rooks at random. This makes me wonder what Joseph O'Rourke's histogram would look like if you started, say with 16 rooks on a $4\times 4$ board but didn't start counting moves until you were down to the last 4 rooks.

*I wrote all this up before I read Aaron Golden's answer carefully. His graph shows simulated results for the $8\times8$ case starting with 64 rooks, but he's allowing rooks not to move if they're on an edge of the board.