ある種の五目並べ型ゲームの必勝法の解明 2010年度

<center>(図１)</center>

<center>(図２)</center>

<center>(図３)</center>

<center>(図４)</center>

<center>(図５)</center>

ゲームで学ぶ数学　—ある種の五目並べ型ゲームの必勝法の解明—

娯楽数学への誘い
　勉強は苦しいもの、つまらないものであると思っている人が多いのではありませんか？確かにそういう側面も否定できませんし、特に受験勉強を終了したばかりの皆さんがそう思うのも無理もありません。しかし人生経験を積んでいくと、勉強ぐらい純粋で、役に立ち、面白いものは無いことが分かってきます。このポケットゼミは、ゲームの必勝法を通じて数学の面白さを実感してもらうと思い、開講しています。
　五目並べを簡単にしたゲームに「三並べ」があります。地方によっては「まるばつ」等の名前で呼ばれており、誰でも子供のころ一度は目にしたことがあるでしょう。図１のように３×３マスの盤面に先手は○、後手は×を交互に一つずつ書いていき、縦か横か斜めの連続３マスを先に独占した方が勝ちというものです。御存知のように、三並べは両者が最善を尽くせば引き分けに終わります。
　三並べ自体は盤面が小さく、場合の数も限られていますので、数学の素材として面白いものではありません。しかし数学者のフランク・ハラリイがこれを一般化し、たいへん面白いゲームを提案しました。以下ではこれを「一般化三並べ」と呼ぶことにします。

「一般化三並べ」とは何か
　一般化三並べは一つのゲームでは無く、様々な（そして無数の）ゲームの総称で、盤面のサイズは３×３だけでは無く、４×４、５×５、６×６…など様々なものを許します。そして作成するものも３連だけでなく、事前に与えられた任意の図形となります。具体例を見てみましょう。
　まずオリジナルの三並べでも使った３連から考えましょう。ただし目的は縦か横に３つ並べることとし、斜め３連は無視します（つまり作っても勝敗に無関係）。盤面が３×３ならば、両者が最善を尽くせば引き分けです。このことは斜めを許してもそうであることから分かりますね。では盤面を４×４にするとどうなるでしょうか。この場合は先手に必勝手順が存在します。先手は第1手を中央４マスのどれかに打てば、後手の第1手（注１）がどこであっても先手第２手で「両端の空いている２連」を作ることができるので、先手は第３手で必ず３連を作ることができます（図２参照、なお、先手は黒石で、後手は白石で表現しています）。４×４で先手必勝なので、それ以上の盤面でも同様に先手必勝であることになります。
　では次に作る形を変えましょう。例えば図３にあるような形はどうでしょうか？ハラリイはこれらを動物(Animal)と呼びました。図３の動物はそれぞれ４つのセル（細胞）から成っているので、４細胞動物と言われます。各動物は90度回転や裏返しをしたものも同じ動物と認めることとします。エリー(Elly)は３×３では引き分けですが、４×４では先手に必勝手順があります。ティッピー(Tippy)は少し面白くて、３×３でも先手必勝ですが完成には５手必要となり、４×４だと４手で済む必勝法があります。

証明のテクニック
　一番変わっているのがファッティー(Fatty)で、これはどんなに盤面が大きくても後手が上手くやれば引き分けに持ち込めるのです。このことを証明するにはどうした良いでしょうか？盤面はいくらでも大きく成り得る訳ですから、実際の戦略を書き下すことは無理そうに見えますが、実はペアリング戦略という便利な証明技術があります。それは以下の通りです。
　まず盤面が無限大である場合に証明できれば十分なことはお分かりですね。盤面が無限大だとすると、図４に示すように隣同士のマスを２つずつ組合せて畳を敷くことができます。このとき、任意のファッティは必ずどれかの畳を一つ含んでいなければならないことが分かります。従って後手は先手にどの畳も占有させないようにすれば良い、すなわち先手が１手打ったら、同じ畳の空いている側のマスに後手は打つようにすれば良いのです。これを続ければ、いつまで経っても先手はどの畳の占有できず、すなわちファッティーは作れないことになります。

未解決問題
　エリーやティッピーのように在る程度大きな盤面ならば先手に必勝法があるような動物を勝ち型(winner)、ファッティーのようにどんなに大きな盤面でも先手に必勝法が無いような動物のことを負け型(loser)、と呼びます。ほとんど全ての動物について勝ち型か負け型かは分類できているのですが、唯一、スネーキー(Snaky)と呼ばれている6細胞動物（図5）だけが、どちらか分かっておらず、この分野では有名な未解決問題です。
　それではスネーキーを除けば何も謎は無いのか、というとそんなことはありません。例えば、負け型であっても、先手がいくつか置き石（ハンディ）を許してもらえば勝ち型になります。例えば、ファッティーはハンディ１（すなわち先手の第一手の前にさらに１つ好きな場所に石を置くことができる）では相変わらず負け型ですが、ハンディ2では勝ち型になることが分かっています。また、勝ち型になりうる最小盤面、勝つ為の最小手数など、色々な考えることがあります。さらに複数の動物が与えられ、そのどれかを作れば勝ちとするルールにしたり、盤面を三角形や六角形に変えたり、様々な変形が考えられ、研究されています。

ゼミでは何をするか
　このゼミでは、その中で、比較的短時間で解決できそうなものに的を絞って取り組んで来ました。2009年度のゼミでは６×６の盤面上でのスキニー(Skinny)に取り組み、負け型になることをほぼ確かめることができました（注２）。ゼミの進め方は、最初は基礎知識を得る為に座学を行い、途中からは、学生同士の対戦を行います。勝敗と成績はほとんど無関係である（注３）ことは説明してあるのですが、やはり盛り上がります。そうして感触をつかんでいき、後半のグループディスカッションを経て証明を完成させていくのです。
今年度のテーマをどうするかは、この原稿を書いている時点では未定ですが、今年も元気な学生達と、楽しみながら未解決問題に挑めることを楽しみにしています。


注１：囲碁・将棋では「先手第１手→後手第２手→先手第３手→後手第４手→…」の様に数えるが、ここでは「先手第１手→後手第１手→先手第２手→後手第２手→先手第３手→…」のようなチェス式の数え方を採用する。
注２：もう少し時間をとって綿密に論証しないと、「証明した」と断言することはできません。
注３：好成績を挙げた学生には、少しですがボーナス点を加えたりしてはいます。