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

Question

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 [2] 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 [3], just as in regular chess it will annihilate that piece and remain at the piece's former position.

NOTE - An alternative way of stating [2], [3], and [4] 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 [2] and [3] will bias the rook towards shorter path lengths. This is in part due to the choice of direction in [2] not being weighted by the resulting possible number of choices in [3], and also the over-counting of positions in [3] due to the lack of consideration that there may be a collision. There are also problems with [2] near the board's boundaries where a direction can be chosen in which no move can take place. Instead of [2] and [3], I'll suggest that a better method would be to number all possible position that the chosen rook from [1] can occupy (keeping the collision constraint from [4] 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?

Answer 1

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.
     

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

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.