I hate Bishop

結論を先に述べると、$N=6$のとき$3$、$N \geq 8$かつ$N$が偶数のとき$N-2$が答えです。

まず、このゲームは後手から見ると「いかに「同一の局面」を作るか」というゲームになっています。そして、ポーンは一度進むと二度と戻れません。 すなわち、ポーンが動いてしまうと、それ以前に現れた局面は二度と現れることが無くなります。このため、後手の第一の目標は「ポーンが動く余地をなくすこと」となります。

それに対して、先手の最適な戦略は何でしょうか。これは必ずしも自明ではありませんので、次のように考えます。 先手のポーンを$k$マス目まで進めるとき、「ポーンが動けなくなる」までの先手の手数を$f(k)$、その後ルークを動かす際の実現可能な最長手数を$g(k)$とします。 $k$の取りうる値は、先手がポーンを最低$1$回は動かさなければいけないことと、上記の考察より後手は一直線にポーンを前進させることから、$3 \leq k \leq \frac{N}{2}$に限られます。 題意の答えは、この和の最大値になります。

$f(k)$を求めます。先手が$k$マス目までポーンを進出させるとき、後手は後手側から見ると$N-k$マス目まで進出させています。 ポーンは最初$2$マス目にありましたので、先手が$k-2$手、後手が$N-k-2$手を指しています。ここで、先手はできればポーンが動けなくなる局面を遅らせたいため、 後手の最後のポーン前進を待って先手も最後のポーン前進を行うのがよいです。（それまでは、適当にルークを動かして手待ちをします。また、それ以上待とうとすると後手のポーンを$k$マス目で止められません。） この時、先手の最後の着手は$N-k-1$手目になりますので、$f(k)=N-k-1$です。例外は$k=3$のときで、この場合のみ、先手の最後のポーン前進が、最初の$1$手でもあるため、「手待ち」が使えません。 そのため、単に後手の$N-k-2$手目をもってポーンが動けなくなります。

$g(k)$を求めましょう。この時、重要な事実が一つあります。「ルークが移動しうるマスの数」（すなわち、ポーンの後ろに確保された「自陣のマス数」）を見ると、先手は$k-1$個、後手は$N-k-1$個となっていますが、 $k \leq \frac{N}{2}$より、後手は必ず先手以上のマス数の「自陣」を確保できます。

（この条件は、$N$が奇数のとき破れます。その場合、以下の考察が適用されず、後手はより繊細な「最善手」を見つけ出す必要に迫られます。 この最善手の構築が"I hate Bishop (Very Hard)"の主題です。）

議論を簡単にするため、先手の「自陣」、後手の「自陣」のそれぞれのマスに、プレイヤーから見て順に番号が付けられているとします。 すなわち、先手のルークはマス$1,2, ... ,k-1$のいずれか、後手のルークはマス$1,2, ... k-1,...,N-k-1$のいずれかにいます。 明らかに、先手は自らのルークを「今まで置いたことのないマス」に移動させる限り安全にゲームを続けられます。 後手の主眼は、先手のマスが尽きたとき、すなわち先手がマス$1$にルークを戻さざるを得ないときに、 次の手でゲームを終わらせられるかどうか、です。そして、これは可能です。後手は単に、先手のルークと同じ番号のマスにルークを移動させ続けることで、 先手が「既に訪れたマス」にルークを戻した瞬間にゲームを終わらせられる状態を保ち続けることが出来ます。 従って、この状態で先手が確保しうる手数$g(k)$は、$k-1$となります。

以上より、$k\geq 4$のとき常に$f(k)+g(k) = N-2$であり、$k=3$のとき$f(k)+g(k) = N-3$です。 $N=6$の時のみ、先手は$k=3$以外を選択する余地がないため、$N-3=3$が答えとなり、それ以外の偶数に対しては例えば$k=4$を選択しうるため、$N-2$が答えとなります。