08. 4×4の盤で遊ぶ四目並べ -五目並べより難しい?-

※この原稿を読む前に, 『 5 × 5 の盤で遊ぶ五目並べ―五目並べ不敗伝説― 』を先に読んで下さるようお願いします.

 

三目並べはご存知ですね. 三目並べは 3 × 3 の形に並べられた9個のマスに, 二人のプレイヤーが交互に○と×を書き込むゲームです. 先手が○, 後手が×を交互に書いていったとき,縦横斜めに並んだ3つのマスのどれかに自分の記号をすべて, 先に書き込んだプレイヤーの勝ちです.

以下では, 4 × 4 の盤で遊ぶ四目並べに, 先手必勝の手順が無いことを証明します. 実はこの証明は, なかなか厄介なのですが, 巧妙な数学を使うことで証明が可能になります.

 

まず 4 × 4 のマス目で遊ぶ四目並べについて考える前に, ErdÖs と Selfridge (1973)(1)によって提案された, 一般化されたm 目並べの引き分けの証明法を解説しましょう.

 

まずm 目並べを一般化した Maker-Breaker ゲームを紹介します. このゲームは Maker と Breaker と呼ばれる2人でプレイします. ゲーム自体は3目並べを一般化したようなものを想定しながら, 以下を読んで下さい. 有限個のマス目からなる集合をV とします. Maker と Breaker はV 中のマス目を交互に1つずつ取ります. 1度取られたマス目は2度取ることはできません. 集合V 中のm 個のマス目からなる集合で, m 個すべてを Maker が取ったら勝利となるものを, 勝利集合と呼びましょう. いま勝利集合はあらかじめ与えられているとし,勝利集合すべてを集めたものをW と書きます. すなわち, W にはV 中のm 個からなるマス目の部分集合がいくつか入っています. 例えば下記の 3 × 3 の盤で遊ぶ3目並べならば,

a b c
d e f
g h i

V = {a, b, c, d, e, f, i} となり

W = { {a, b, c}, {d, e, f}, {g, h, i}, {a, d, g}, {b, e, h}, {c, f, i}, {a, e, i}, {c, e, g} } となっています.

 

このゲームでは, Maker がW 中の勝利集合のうちどれかが, 自分の取ったマス目の集合中に入ってきたとき, Maker の勝ちとします. Maker が勝つことなく, すべてのマス目が2人のプレイヤー(のどちらか)に取られてしまいゲームが終了したら, Breaker の勝ちとします.通常のm 目並べと違い, このゲームでは, Breaker が勝利集合(のどれか) を取っても Breaker の勝ちとはなりません. 以下では先手は Breaker で, 後手は Maker というゲームについて考えます. このとき, 次の性質が成り立ちます.

 

定理:勝利集合の数(W の要素数) が2m未満ならば, 先手の Breaker は, 後手の Maker の勝利を阻止できる(つまり Breaker に必勝手順が存在する).

この定理は次のように示されます. まずゲームの途中の状態を, Maker がそれまでに取ったマス目の集合, Breaker がそれまでに取ったマス目の集合, どちらのプレイヤーにも取られていないマス目の集合, に分けて表すことにしましょう. ここで各マス目に, 次のように数字を割り当てます. それが Maker のものなら1を, Breaker のものなら0を, どちらのものでもなければ1/2を割り当てます.

 

ある勝利集合W ∈ W について, 勝利集合W の重みを, W 中のマス目に対応する数字をすべて掛け合わせたものとします. 上記の例で, 最上段{ a, b, c } の勝利集合の重みは 1 × 1/2 × 1 =1/2となり, 最下段{ g, h, i } の勝利集合の重みは 1/2 × 1/2 × 0 = 0 となっています. 重みが0となっている勝利集合は, その中のマス目(の1つ以上) が Breaker に取られてしまっているので, Maker はそれを使って勝つことはもうできません.

勝利集合すべての重みの総和を, その状態(盤面)のポテンシャルと呼ぶことにします. Makerが勝利している状態では, 少なくとも1つの勝利集合は重みが1となりますので, ポテンシャルは1以上となります. (ただしこの逆, 『ポテンシャルが1以上ならば Maker は勝っている』は成り立ちません.)

Breaker は, このポテンシャルをできるだけ下げるような戦略を取るのが良さそうです. では実際にBreaker はどのマス目を取れば良いのかを考えましょう. ここではマス目の重要度を次のように定義します. マス目x ∈ V が, まだどちらのプレイヤーにも取られていないとき, x の重要度を「x を含む勝利集合すべての重みの総和」と定義します. 以下ではx の重要度をP(x ) と書きます.

もし Breaker が次の手番でマス目x を取れば, マス目x に対応する数字は0となり, x を含む勝利集合はすべて重みが0になります. すなわち, ポテンシャルはP(x ) だけ減少します. 逆に Maker が次の手番でマス目x を取れば, マス目x に対応する数字は1/2から1に変わり,x を含む勝利集合はすべて重みが2倍になります. すなわち, ポテンシャルはP(x ) だけ増大します.

 

さてここで推奨される Breaker の戦略は『重要度の最も大きいマス目を取る』という戦略です. ある状態(盤面)A1 におけるポテンシャルがP1 だったとしましょう. まだどちらのプレイヤーにも取られていないマス目の中で, 重要度が最大のマス目(の1つ) をx とし, Breaker がx を取ったとします. このときの状態(盤面) をA2 とすると, A2 におけるポテンシャルはP1 − P(x ) となります. その次の手番で Maker が取ったマス目をy と書きましょう. 状態A1 でのy のポテンシャルP(y ) は, 明らかにP(y ) ≤ P(x ) を満たします. 状態A2 でのy のポテンシャルをP′(y ) と書くと, A2 はA1 の1ヶ所のマス目の数字が1/2から0になったものなので, P′(y ) ≤ P(y ) が成り立ちます. すると, Maker がマス目y を取ったあとのポテンシャルは

 

P1 − P(x ) + P′(y ) ≤ P1 − P(x ) + P(y ) ≤ P1 − P(x ) + P(x ) = P1

 

を満たします. すなわち, 盤面A1 から Breaker と Maker が一手ずつプレイすると, (Makerがどんな手を打っても) そのポテンシャルは同じかより小さくなることが分かります.

 

これで証明はほとんど終わりです. 定理の条件である『勝利集合の数|W| が2m 未満』が成り立つと, ゲームの開始状態でのポテンシャルは ( 1/2 )m・|W| < 1 となります. Breaker が常に重要度最大のマス目を取るという戦略を採用するならば, Maker がどんなマス目を選んでもポテンシャルは同じか減少します. このとき Maker が勝利したと仮定すると, 勝利した状態のポテンシャルは1以上となりますので, 1未満の初期ポテンシャルから(同じか)減らすことによって1以上のポテンシャルが得られたことになり矛盾します. ゆえに, Maker が勝利することはありえません.

 

では ErdÖs -Selfridge の定理を用いて, 4 × 4 マスで遊ぶ四目並べに先手必勝手順が無いことを示してみましょう. マス目の集合V は下記の16個のマスからなり, 勝利集合W は10個のマス目の部分集合からなります.

a 12 a a14
a21 a22 a23 a24
a31 a32 a33 a34
a41 a42 a43 a44

V = {a11, a12, a13, . . . , a44},
W = {
{a11, a12, a13, a14}, {a21, a22, a23, a24},
{a31, a32, a33, a34}, {a41, a42, a43, a44},
{a11, a21, a31, a41}, {a12, a22, a32, a42},
{a13, a23, a33, a43}, {a14, a24, a34, a44},
{a11, a22, a33, a44}, {a14, a23, a32, a41},
   }

 

盤面に何も石が置かれていない状態でのポテンシャルは ( 1/2 )4・10 = 10/16 となります. 先手の○はMaker, 後手の×は Breaker となります. 残念ながら, ErdÖs -Selfridge の定理では Maker が後手, Breaker が先手ですので, そのまま定理を適用することができません. そこで, 先手の○が一手打ったところからゲームがスタートするとしましょう.

先手がどこかに○を1つ書くと, 最大で3つの勝利集合に1つの○が書かれます(例えば対角線上のマス). そのため, 先手が○を1つ書いた状態でのポテンシャルは, 高々

1・(1/2)3・3 + (1/2)4・7 =(6+7)/16 = 13/16 < 1

となります. このあと Breaker である後手の×は, 『重要度の最も大きなマス目に×を書く』という戦略を取れば, ポテンシャルを(毎回自分の手番の直前で測れば) 増加させることなくゲーム進行できます. ゆえにすべてのマス目が印で埋まったとき, (最後に書かれるのは Breaker の×ですから) 盤面のポテンシャルは1未満となります. この時点でもし Maker である先手の○が4つ直線に並んでいたら, ポテンシャルは1以上となっている筈ですので, そのような事はありません. すなわち, Maker である先手の○は勝つ事ができません.

3×3マスで遊ぶ3目並べに先手必勝手順が無いことは, 残念ながら ErdÖs -Selfridge の定理の考え方を使って示すことができません. これは, ErdÖs -Selfridge の定理で扱っている Maker-Breaker ゲームと3目並べのルールの違いです. すなわち, Maker-Breaker ゲームでは, Breaker は Maker の勝利を阻止することでしか勝つことが出来ません. これに対し3目並べでは, 直線に3目並べる事で後手も勝つことができます. 実はこの可能性があるからこそ, 3目並べで後手は引き分けに持ち込むことができます. 実際, 3 × 3 のマス目で遊ぶ3目並べで, 『先手は3目並べれば勝ち, 後手は先手が3目並べるのを阻止すれば勝ち』としたゲームは, (引き分けではなく) 先手必勝の手順があります(考えてみて下さい).

(1)P. ErdÖs and J. L. Selfridge, On a combinatorial game, J. Combinatorial Theory Ser. A, 14 (1973), 298-301.