05. Brige It ゲームの必勝法 -知らない奴はカモってしまえ-

数理経済学者 David Gale によって提案されたゲーム Bridge It について紹介しましょう.これは図1のような盤に先手と後手が交互に, 縦または横の線分を引いていくゲームです.

図1: Bridge It の盤.

図1: Bridge It の盤.

ただし先手は(縦または横に)隣り合う黒丸を, 後手は(縦または横に)隣り合う白丸を結ぶ線分を引くことしか許されず, またそれまでに引かれた線分と交差する線分は引くことができません. また一度引かれた線分は消すことができません. 先手は最右列の黒丸(のどれか)と最左列の黒丸(のどれか)を結べば勝ちです. 後手は最上段の白丸(のどれか)と最下段の白丸(のどれか)を結べば勝ちです. 図2は先手(黒丸) が勝利している例です.

図2: 先手(黒) の勝利.

図2: 先手(黒) の勝利.

先手が左右をつなぎ, 後手が上下をつないでいる状態が同時には起こらないことは直観的に分かっていただけると思います. 実はこのゲームに引き分けはありません. すなわち『これ以上線分を引くことが出来ない状態』においては, 先手または後手のどちらかが勝利しています. これは例えば, 先手が最左列と最右列をつなげられていないとしたとき, 最左列から到達できる黒丸と線分を取り除くと, 境界となっている後手の線分を使って, 後手は最上段から最下段へたどりつくことができるからです(図3).

図3: 後手が勝利している例.

図3: 後手が勝利している例.

以上よりこのゲームには引き分けがありません. 実はこのゲームには先手必勝の手順が存在します. 以下これを説明しましょう.

このゲームでは, ペアリング戦略と呼ばれる方法が有効です. 以下これを説明しましょう.まず Bridge it は, 図4のような絵を鉛筆で書いて, 先手は(まだ)鉛筆で書かれている線分を1本選んでボールペンでなぞる, 後手は(まだ)鉛筆で書かれている線分を1本選んで消しゴムで消す, というゲームだと考えることができます. 最右列内の点を結ぶ枝と最左列内の点を結ぶ枝は, 先手にとってつなげても無意味な枝であるため取り除いてあります.

図4: 鉛筆で描かれた絵.

図4: 鉛筆で描かれた絵.

先手の必勝戦略は, 1手目で図5中の左上の太線をつなぎ, 2手目以降は両向き矢印の一方の枝を消されたら他方の枝をつなぐというものです.

では, このペアリング戦略が先手必勝手順となっていることを示しましょう. 先手が図5のペアリング戦略をとったとき, 後手が勝利していると仮定して矛盾を導きます. 後手が勝利しているということは, 後手には最上段から最下段への(有向)道P が存在しています. これは先手が選ぶ枝からなるグラフにおいては最上段から最下段までの箱(小さな正方形) の連なりに対応します(図6参照).

図5: 先手のペアリング戦略.

図5: 先手のペアリング戦略.

図6: 道P に対応する箱の連なり.

図6: 道P に対応する箱の連なり.

各箱について, ペアリング戦略でどのような枝を選ぶかを考えると, 図7のように3種類があり, それぞれに Lbox, Mbox, Ubox と名前を付けます.

図7:Lbox, Mbox, Ubox

以下では, 後手の最上段から最下段への(有向)道P は, 次の(1)(2)(3)をすべて満たすことを示しましょう.

(1) 道P が Lbox に入るのは, 必ず右か下の枝からである.
(2) 道P が Mbox に入るのは, 必ず上か下の枝からである.
(3) 道P が Ubox に入るのは, 必ず左か上の枝からである.

まず, 上記(1)(2)(3)が満たされるならば, 道P が箱を通過するパターンは図8に示すものしか存在しないことに注目して下さい.

図8:道P が箱を通過するパターン

では上記(1)(2)(3)が成り立つことを, (有向)道P にそった帰納法で示しましょう. 道P が最初に通過する箱は(先手は初手で左上隅の横の枝を選んでいるため) Mbox か Ubox であり, (2)(3)は成り立っています(もちろん(1)も成り立っています). 次に道P が通過するk 個目の箱x は(1)(2)(3)を満たしていると仮定して, k + 1 個目の箱y も(1)(2)(3)を満たすことを示しましょう. 以下では背理法を用います.

 

(1-a) 箱y が Lbox で道P が左の枝から入った場合.
このとき箱x は箱y の左にあります. Lbox の左は必ず Lbox より, 箱x は Lbox です.箱x より道P が出る際は, x が(1)を満たすことより, x の上か左の枝を通過します. これは箱x が箱y の左にあることに矛盾します.

(1-b) 箱y が Lbox で道P が上の枝から入った場合.
このとき箱x は箱y の上にあります. Lbox の上は Lbox か Mbox であり, 箱x は Lbox か Mbox となります. 箱x より道P が出る際は, x が(1)と(2)を満たすことより, 下の枝を通過することはありません. これは箱x が箱y の上にあることに矛盾します.
上記より箱y が Lbox ならば, 道P が箱y に入るのは, 右か下の枝からであり, (1)が成り立ちます.

(2) 箱y が Mbox の場合も, (1)と同様な手順で道P が箱y に入るのは上か下の枝からであることが示されます.

(3) 箱y が Ubox の場合も, (1)と同様に道P が箱y に入るのは左か上の枝であることが示されます.

 

これにより, 後手は上下をつなぐことが出来ません. 引き分けが無いことより, これ以上線を引くことが出来ない状態において, 先手は左右をつなげることができている筈です.