戦略を盗む議論

組合せゲーム理論において、戦略盗用論証は、多くの2 人用ゲームにおいて、2 人目のプレイヤーが確実に勝てる戦略を持つことはできないことを示す一般的な論証です。戦略盗用論証は、余分な動きが決して不利にならない対称的なゲーム(どちらのプレイヤーも同じ動きのセットを持っていて、結果も同じなので、最初のプレイヤーは 2 人目のプレイヤーの戦略を「使用」できるゲーム) に適用されます。戦略盗用論証の重要な特性は、最初のプレイヤーが実際にそのような戦略を構築しなくてもゲームに勝つ (または引き分けになる可能性もある) ことができることを証明することです。したがって、勝利戦略の存在は証明されるかもしれませんが、その証明ではその戦略が何であるかについての情報は得られません。

この議論は矛盾を得ることによって成り立ちます。2 番目のプレーヤーには勝利戦略が存在すると想定され、その戦略を使用しています。しかし、大まかに言えば、任意の最初の動きをした後 (上記の条件では不利ではありません)、最初のプレーヤーもこの勝利戦略に従ってプレイする可能性があります。その結果、両方のプレーヤーが勝つことが保証されますが、これは不合理であり、そのような戦略が存在するという仮定と矛盾しています。

戦略窃盗は、1940年代にジョン・ナッシュが発明したもので、ヘックスゲームでは引き分けはあり得ないため、常に先手が勝つことを示すために考案された。^[1]しかし、ナッシュはこの手法を公表せず、ヨージェフ・ベックは、この手法を1963年の三目並べに関する論文で初めて公表したアルフレッド・W・ヘイルズとロバート・I・ジューエットに帰している。この論文では、ヘイルズ・ジューエット定理も証明されている。^{[1] [2]}この議論が当てはまるゲームの他の例としては、五目並べなどのm、n、kゲームが挙げられる。チョンプのゲームでは、戦略窃盗により、先手がどの長方形の盤面（1x1以外）でも勝利戦略を持っていることが示される。シルバー貨幣ゲームでは、戦略窃盗は、先手が「エンダー」と呼ばれる特定の位置で勝つことができることを示すために使用されている。^[3] これらすべての例では、証明は実際の戦略については何も明らかにしていません。

戦略窃盗の議論は、三目並べのゲームの例で、盤と勝ちの列のサイズに関係なく使用できます。^{[1] [2]} 2 番目のプレーヤー (P2) が勝利を保証する戦略S を使用しているとします。最初のプレーヤー (P1) は、任意の位置にX を置きます。 P2 は、 Sに従ってOを置いて応答します。 しかし、 P1 が最初のランダムなX を無視すると、 P1 は P2 の最初の動きの P2 と同じ状況になります。つまり、盤上に敵の駒が 1 つある状態です。 したがって、 P1 はSに従って移動できます。つまり、S が、無視されたXがすでに置かれる場所に別のX を置くように要求しない限りです。 しかし、この場合、 P1 は単に盤上の別のランダムな位置にX を置くだけであり、その結果、 1 つのXがSによって要求される位置にあり、別の X がランダムな位置にあり、新しい無視される駒になり、状況は前と同じになります。このように続けると、Sは、仮説により、勝利ポジション (重要でない無視された追加のXを含む) を生成することが保証されます。しかし、P2 は負けました。これは、P2 が勝利戦略を保証していたという仮定に反します。したがって、P2 のそのような勝利戦略は存在せず、三目並べは P1 の強制勝利か引き分けのいずれかです。(さらに分析すると、実際には引き分けであることがわかります。)

同じ証明は、どんな強いポジショナルゲームにも当てはまります。

チェスにはツークツヴァングと呼ばれる局面があり、その局面では、指す義務のあるプレイヤーは、それが許されるなら「パス」することを好む。このため、戦略盗用論はチェスには当てはまらない。^[4]現時点では、白と黒のどちらが最適なプレイで勝利を強制できるか、あるいは両プレイヤーが引き分けを強制できるかはわかっていない。しかし、チェスの研究者のほとんどが、白の最初の手は有利であると考えており、現代の高レベルゲームの統計では、白の勝率は黒よりも 約 10% ^{[引用が必要]高い。}

囲碁ではパスが認められている。開始位置が対称的（盤が空で、どちらのプレイヤーもポイントを持っていない）な場合、これは、最初のプレイヤーが最初の動きを放棄するだけで、2番目のプレイヤーの勝利戦略を盗むことができることを意味する。しかし、1930年代以降、^[5] 2番目のプレイヤーには通常、いくらかの補償ポイントが与えられ、開始位置が非対称になり、戦略を盗むという議論はもはや機能しなくなった。

このゲームにおける基本的な戦略は「ミラー ゴー」です。これは、2 番目のプレーヤーが、対戦相手の対角線上の動きと反対の動きを実行するというものです。このアプローチは、ラダー タクティクス、コ ファイト、またはボードの中央ポイントの制御を競うことで 打ち負かされる可能性があります。

戦略盗用論証は、2番目のプレイヤーの仮想的な勝利戦略から矛盾を導き出すことによって、2番目のプレイヤーが勝てないことを示します。この論証は、排中律によって引き分けが不可能なゲームでよく使用されます。しかし、この論証は最初のプレイヤーに明確な戦略を提供しないため、非構成的であると言われています。^[4]これにより、実際に勝利戦略を計算する方法という疑問が生じます。

chompのように到達可能な位置の数が有限であるゲームの場合、徹底的な探索によって勝利戦略を見つけることができます。^[6]しかし、位置の数が多い場合、これは非現実的かもしれません。

2019年、グレッグ・ボドウィンとオフェル・グロスマンは、戦略窃盗論法が使用された2種類のゲーム、最小ポセットゲームと対称メーカーメーカーゲームにおいて、勝利戦略を見つける問題がPSPACE困難であることを証明した。^[7]