【組み合わせゲーム理論】戦略拝借論証とは？ 内容・五目並べやHexへの応用まで解説
こんにちは！半沢です！
今回の記事では組み合わせゲーム理論における戦略拝借論証(strategy-stealing argument)について解説します。
戦略拝借論証は後手必勝でないことを示すかなり強力な証明法です。
今回の記事では戦略拝借論証の応用として，五目並べやHexといった有名なボードゲームを考えていきます。
難しい前提知識は特にいらないので，楽しみながら読んでいただけると嬉しいです。
それでは記事に参りましょう。
戦略拝借論証(strategy-stealing argument)
内容
戦略拝借論証(strategy-stealing argument)
後攻が必勝戦略を持つと仮定し，先攻がその必勝戦略を拝借できることを示すことで矛盾を導き，後手必勝にならないことを示す証明方法。
※“strategy-stealing argument”に対応する広く知られた日本語がなかったので，「戦略拝借論証」ではなく“strategy-stealing argument”で覚えた方が良いでしょう。
言葉の説明だけでは分かりにくいと思いますので，次節では\(\,m,n,k\,\)-ゲーム ( \(k\,\)目並べ )の例を見ていきましょう。
\(\,m,n,k\,\)-ゲーム ( \(k\,\)目並べ )
それでは実際に戦略拝借論証を使っていきましょう。
そのために〇×ゲーム(三目並べ)，五目並べを一般化した次の\(\,m,n,k\,\)-ゲームについて考えましょう。
定義
次の手順で進行されるゲームを\(\,m,n,k\,\)-ゲームと呼ぶ。
\([1]\,\) \(m\times n\,\)の長方形のマスに\(\,2\,\)人のプレイヤーが自分の色の石を交互に置く(先攻：黒，後攻：白)。
\([2]\,\) 先に\(\,k\,\)個の自分の色の石を縦・横・斜めのいずれかに並べた者を勝ちとする。
\([3]\,\)もし勝者が決まらず，長方形のマスの全てが石で埋まったときは引き分けとする。
また並べる石の数のみに着目する場合は\(\,k\,\)目並べと呼ぶ。
下図の左ような定番の〇×ゲーム(三目並べ)だと\(\,3,3,3\,\)-ゲーム，五目並べだと\(\,15,15,5\,\)-ゲームとなります。
※ルールによっては禁じ手がある場合がありますが，解析しやすくするためそのような場合は考えません。
さて，この\(\,k\,\)目並べに戦略拝借論証を使って次の命題を示しましょう。
命題1
\(k\,\)目並べは後手必勝ではない。
つまり先攻はうまく立ち回ることで勝利か引き分けに必ず持ち込める。
戦略拝借論証を使うので，まず後攻に必勝戦略があると仮定しましょう。
このときまず先攻(黒)はどこかランダムに黒の石を置きます。
そして先攻はこの石を「置かれていないもの」とみなし，後攻(白)に手番を移します。
先攻はそのように考えることで，あたかも先攻と後攻が逆転したかのように考えることができます。
そのため後攻の必勝戦略を使うことができます。
ここで，もちろん最初に置いた黒の石の影響を考慮する必要があります。
最初に置いた黒の石が，後攻から拝借した必勝戦略に影響するのは，
先攻が最初に置いた黒の石のところにその必勝戦略に従うために黒の石を置く必要があるときです。
しかしこのときも，最初に置いた黒の石をその手番で置いたとみなし，その手番で置く必要のある黒の石は再びランダムな位置におき，今度はこの石を置かれていないものとみなします。
このように先攻は無視する石を取り換えていくことで，後攻の必勝戦略を問題なく拝借することができます。
つまり先手必勝となり，これは後手必勝であることに矛盾します。
以上のような戦略拝借論証により，題意は示されました。\(\quad\square\)
〇×ゲーム(三目並べ)に慣れている方は，お互い最善を尽くすと引き分けになることを知っているので，この命題は分かりやすいと思います。
また先攻が勝利に持ち込むことができるか，引き分けに持ち込むことができるかは\(\,m\times n\,\)の長方形のマスの設定によります。
要望があれば，もう少し踏み込んで別の記事で書きたいと思います。
Hex
次の“Hex”というボードゲームも考えてみましょう。
定義
次の手順で進行されるゲームをHexと呼ぶ。
\([1]\,\) 下の図のような\(11\times 11\,\)の六角形のマスをひし形状に並べたボードで，
\(\,2\,\)人のプレイヤーが自分の色でマスを交互に塗る(この記事では先攻が赤，後攻が青とする)。
\([2]\,\) 先に自分の色で塗られたマスによって，ボードの向かい合った自分の色の辺をつなげた者を勝ちとする。
※ルールによっては\(\,13\times 13\,\)のボードなどで遊ぶ場合もあります。
今回の記事の内容は\(\,n\times n\,\)まで一般化できるので，最初からその場合で考えても良いです。
例えばゲームを進めて下の図のようになったとすると，赤の人の勝ちになります。
このHexも前節と同様に戦略拝借論証を用いて次の命題が示せます。
命題2
Hexは後手必勝ではない。
つまり先攻はうまく立ち回ることで勝利か引き分けに必ず持ち込める。
Hexについてはさらに次の強い命題が成り立つことが知られています。
命題3
Hexは先手必勝。
この命題3の証明は少々長くなるので，別のHexの記事で解説しています。
ざっくり言えばボードの図形的性質から「Hexは引き分けがない」ことを証明し，上の命題2と合わせることで命題3が得られます。
補足
ここまで\(\,m,n,k\,\)-ゲーム ( \(k\,\)目並べ )，Hexで戦略拝借論証が使えることを確認してきました。
この他，「チョンプ(wiki)」と呼ばれるゲームなどでも戦略拝借論証が使えます。
しかしこれまでのことを踏まえると分かるように，戦略拝借論証は構成的な証明でないことに注意してください。
つまり先攻がうまくやれば負けることはないと証明できても，どのようにすればそれを実行できるのかが分からないということです。
実際Hexの必勝戦略は未だ分かっていません。
このように戦略拝借論証は構成的でないというデメリットがあることに注意しておきましょう。
※五目並べはwikiによると明治時代の1899年に黒岩涙香という人が必勝戦略を発見したらしいです。
その必勝法を記した「聯珠真理 : 一名・五目並べ先手全勝法」は国立国会図書館デジタルコレクションで読めるようになっているので，興味がある方は読んでみると良いでしょう。
まとめ
今回の記事では戦略拝借論証(strategy-stealing argument)を解説いたしました。
内容は理解しやすいですが，「後手必勝でない」という強力な帰結を生む点が個人的には感動です。
もし「説明がわかりにくい」などご要望・ご感想がありましたら，
X（旧:Twitter）で#トイカラでつぶやいていただけると，できる限り対応します。
ここまで読んでいただき，ありがとうございました。
参考図書
- \([1]\) “Chomp”.Wikipedia.2023-12-11更新.https://en.wikipedia.org/wiki/Chomp.2025-03-02参照
- \([2]\) “五目並べ”.Wikipedia.2024-07-23更新.https://ja.wikipedia.org/wiki/%E4%BA%94%E7%9B%AE%E4%B8%A6%E3%81%B9.2025-03-02参照
- \([3]\) “聯珠真理 : 一名・五目並べ先手全勝法 – 国立国会図書館デジタルコレクション”.国立国会図書館.https://dl.ndl.go.jp/pid/861325/1/1.2025-03-02参照
