Split and discard the smaller pile

Idea. The losing positions for the player to move are exactly $n=2^k-1$. Alice wins unless the starting stack is one of those.

Step 1: from $2^k-1$, every move goes to a winning position. From $n=2^k-1$ the possible moves are $k^{\prime }\in [2^{k-1},2^k-2]$, and none of these numbers has the form $2^j-1$. So the opponent always receives a non-losing position.

Step 2: from any other $n$, you can move to $2^k-1$. If $2^k\le n\le 2^{k+1}-2$, move to $2^k-1$. That is allowed: $2^k-1\le n-1$, and $\lceil n/2\rceil \le 2^k-1$ because $n\le 2^{k+1}-2$.

Step 3: by induction, $n$ is losing for the player to move exactly when $n=2^k-1$.

Step 4: count. Up to 1000 the losing values are $1,3,7,15,31,63,127,255,511$: nine of them. So Alice wins with probability $$\frac{1000-9}{1000}=\frac{991}{1000}.$$