King on reduced chessboard $2\times 2$ moving randomly, what is the probability that it ends up in one of the corners after $1000$ moves?

After $n$ moves, the probabilities of the three squares other than the starting square are equal by symmetry. Let $p_n$ be the probability of being in the lower right square after $n$ moves. Then the probability of being in the upper left after $n$ moves is $1-3p_n$.

We can find a simple recursion here. To reach the lower right square on the $(n+1)$th move, we must be in one of the other three squares (probability $1-p_n$) after the $n$th move, and then make the correct move from there (probability $\frac13$). Thus $p_{n+1}=\frac13(1-p_n)$.

If $e_n=p_n-\frac14$, we then get $e_{n+1}+\frac14=\frac13(\frac34-e_n)=\frac14-\frac13e_n$, so $e_{n+1}=-\frac13 e_n$. Since $p_0=0$ and $e_0=-\frac14$, we get $e_{1000}=-\frac14\cdot \left(-\frac13\right)^{1000}=\frac{-1}{4\cdot 3^{1000}}$ and $p_{1000}=\frac14-\frac{1}{4\cdot 3^{1000}}=\frac{3^{1000}-1}{3^{1000}\cdot 4}$.

There it is. Exact, even.

The following is a Markov chain approach, since OP tagged it:

There are two states: 1) Not being in the bottom right corner, and 2) being in brc. The transition matrix is $$A=\begin{pmatrix}2/3&1\\1/3&0\end{pmatrix}$$ What is being asked is the value of $$p=\begin{pmatrix}0&1\end{pmatrix}\cdot A^{1000}\begin{pmatrix}1\\0\end{pmatrix}=\frac{1}{4}\begin{pmatrix}0&1\end{pmatrix}\begin{pmatrix}1&-1\\1&3\end{pmatrix}\begin{pmatrix}1&0\\0&(-\frac{1}{3})^{1000}\end{pmatrix}\begin{pmatrix}3&1\\-1&1\end{pmatrix}\begin{pmatrix}1\\0\end{pmatrix}=\frac{1}{4}\left(1-\frac{1}{3^{1000}}\right)$$ The column $(1,0)$ refers to the starting state of 1) and the left-most $(0,1)$ refers to the end-state 2), with a thousand transitions in between.