Solution:

Color the squares with three colors as follows:

```
0 1 2 0 1 2 0 $\ldots$ 2
1 2 0 1 2 0 1 $\cdots$ 0
2 0 1 2 0 1 2 $\cdots$ 1
```

The middle square is color $2$ (moving $999+1$ squares $E$ from the top left increases the color by $1$, then moving $999+1~S$ increases it by another $1$) and the square immediately $NE$ of it is also $2$. So both $P$ and $R$ start on color $2$. Note that any move increases the color by $1$ mod $3$, except for $P$'s special move which changes the color from $1$ to $0$.

Until $P$ has made this move, after each move of $P$, $P$'s color is always $1$ more than $R$'s color $(\bmod 3)$, so $P$ cannot win (irrespective of the moves made by either player). Immediately after he makes the special move for the first time, $P$ is on color $0$ and $R$ is on color $1$, so immediately after his move $P$'s color is now $1$ less than $R$'s color mod $3$. Again $P$ cannot win. But after $P$ has made the special move for the second time, $P$'s color is the same as $R$'s (mod $3$) immediately after $P$'s move.

Note that it takes $P$ at least $2001$ moves to complete his special move for the first time and at least $6002$ moves (in total) to complete his special move for the second time. This solves the first part of the question. Suppose $R$ just moves down to the bottom right and then moves in small circles (one move $NW$, one move $S$, one move $E$) waiting for $P$. It takes $P$ at least $6002 + 3999$ (moving from top left to the capture square, one square short of the bottom right) $= 10001$ to capture him, so $R$ makes at least $10000$ moves before being captured.

We claim that $P$ wins if he can get into any of the positions shown below relative to $R$, with $R$ to move $(*)$ :

```
X P X X X
P $\quad x \quad X \quad P \quad$ x
x $\quad x \quad R \quad x \quad$ x
X $\quad P \quad x \quad X \quad$ P
x x x $\quad$ x
```

It follows that $P$ can also win from the four positions below $(**)$ :

```
X X X P X X X
x $\quad x \quad x \quad x \quad x \quad x \quad$ x
X x x x x x x
P X X $\quad R \quad x \quad X \quad$ P
x $\quad x \quad x \quad x \quad x \quad x \quad$ x
x $\quad x \quad x \quad x \quad x \quad x \quad$ x
x $\quad x \quad x \quad P \quad x \quad x \quad$ x
```

For in each case at least one of $R$'s possible moves allow $P$ to move immediately into one of the winning positions at $(*)$. But $R$ can only make the other moves a limited number of times before running into the border. [That is obvious if the other two moves are $E$ and $S$. If they are $NW$ and $E$, then every $NW$ move takes $R$ closer to the top border, but his total number of $E$ moves can never exceed his total number of $NW$ moves by more than $2000$ because of the right border. Similarly, for $NW$ and $S$.]

Now let $d$ be the number of rows plus the number of columns that $R$ and $P$ are apart. It is easy to check that the positions in $(*)$ and $(**)$ represent the only possibilities for $d=2$ and $3$. We show that $P$ can always get to $d=2$ or $3$. For $P$ can always copy $R$'s move, so he can certainly move so that $d$ never increases. But one of $R$'s moves will always allow $P$ to decrease $d$ by $1$ or $2$. There are three cases to consider:

Case 1. If $P$ is east of $R$ and $R$ moves $E$, then $P$ moving $NW$ will decrease $d$ by $1$ or $2$. That is not possible if $P$ is in the top row, but then moving $S$ will decrease $d$ by $2$ unless $R$ is also in the top row. If both are in the top row, then $P$ moves $S$. Now after $R$'s next move, $P$ moves $NW$ which reduces $d$ by $2$.

Case 2. If $P$ is south of $R$ and $R$ moves $S$, then a similar argument shows that $P$ can always decrease $d$ by $1$ or $2$ in one or two moves.

Case 3. If $P$ is not south or east of $R$, and $R$ moves $NW$, then $P$ can always decrease $d$ by $1$ or $2$ by moving $S$ or $E$.

But repeated decreases by $1$ or $2$ must bring $d$ ultimately to $2$ or $3$ and hence to one of $(*)$ or $(**)$. So $P$ can always win.

It remains to prove the claim that $(*)$ are winning positions. The reason is that in each case $R$ has one move blocked off, so must make one of the other two. $P$ then copies $R$'s move, so next turn $R$ has the same move blocked off. Repeated use of the other two moves will bring him ultimately to one of the sides.

We start with the easiest case: in the two following positions. $R$ cannot move to $z$, so he must move east or south on each move. Hence he will (after at most $4000$ moves) reach the bottom right corner. He then loses moving out of it.

```
X P X
P z x
x X R
```

The other cases of $(*)$ are slightly more complicated. Starting from either of the two positions below, we show that $R$ must eventually reach the extreme left column.

```
w $\quad x \quad P \quad$ x
x $\quad R \quad z \quad$ x
x y x P
```

$R$ cannot move to $z$, so he can only make $NW$ and $S$ moves. But his total number of $S$ moves can never exceed his total number of $NW$ moves by more than $2000$ because he cannot move off the bottom of the board, so he must eventually reach the extreme left column. [If he reaches the bottom row at $y$, then $P$ can always move to $z$ to preserve the configuration. If $R$ reaches the top row by moving to $w$, then $P$ can always move to $z$ to preserve the configuration.]

Having reached the extreme left column he is forced to move south. Eventually moving to $y$ will take him to the corner. $P$ then moves to $z$ and $R$ is captured on his next move.

The final case to consider is the two positions below. $R$ cannot move to $z$, so must move $E$ or $NW$. A similar argument to the previous case shows that he must eventually reach the top row. Having reached it at $w$, $P$ moves to $z$. So $R$ is forced to move right along the top row. When he reaches the corner at $y$, $P$ moves to $z$ and $R$ is captured when he moves out of the corner.

```
W x x
x R y
P z x
X X P
```