チェスも、将棋も、囲碁も、コンピューターが人間に勝利して久しいですが、「コンピューター」つまり「計算機」というからには、それぞれのゲームに対して何らかの「計算」をして、一つ一つの手を指しているわけです。
メディアではよくコンピューター将棋などについて華々しく紹介されるけれども、じゃあ実際にそれらがどういう計算をしているのか？ということについては何も知らないという人がほとんどじゃないかと思います。
今回はそんなゲームのコンピューター対戦につながる初歩の初歩、ゲームを「計算する」とはどういうことなのか、というお話です。
この記事は、「数学ゲーム Advent Calendar 2018」20日目の記事です。
ゴドマチ
「ゴドマチ」という対戦パズルゲームがあります。略さず言うと「合同を待ちながら」。はい。そういうことです。
考案者の方によるルール解説はこちら↓
ゴドマチ自体の説明は上の記事にすべて書いてありますが、一応こちらでも説明しておきましょう。
ゴドマチは２人で遊ぶゲームです。用意するものはペンと方眼紙。
２人のプレイヤーはまず、決められた個数の正方形が繋がった形を、各々が自由に用意します。
２人いるので２つの図形ができるわけです。図の例では正方形は15個ですね。この状態から始まる勝負を「ゴドマチ15単位マッチ」と呼びます。
ここからゲームスタートです。じゃんけんなどで先手後手を決め、交互に行動します。
プレイヤーは自分のターンで、２つの図形からそれぞれ「合同（同じ形）」で一つ一つは「連結（ひとつながり）」な図形を削らなくてはなりません。こういうことです。
青の部分が削ったところです。これを交互に繰り返して、図形をどんどん削っていきます。このとき、削られて残る方の図形もひとつながりになっていなければいけません。穴は空いててもOKです。また、「一マスだけ削る」のも「合同」で「連結」という条件に当てはまっているのでOKです。
さらに一手進めた局面（状態）が上です。そして、最終的な勝利条件は「残った図形も合同にすること」です。実は上図の局面はあと一回削ると合同な図形を残せるのですが、どう削ればいいかわかるでしょうか？
正解は以下です。このように合同な図形で削ると（「3」と書いてある青の部分）、
２つの合同な図形が残りました（黒の部分）。こうなったら、最後に削った先手（青）の勝ち、ということです。たったこれだけ。シンプル！
2018年1月19日に考案されたゲームで、まだ生まれたばっかりなのですがこれがまあ面白いのです。自分の周りではこれが紹介された瞬間すぐさま受容され瞬く間にブームになりました。
実際にやってみると、プレイの前半はまだ選択肢が多すぎるのでアレなんですが、終盤になると一気に試合が進む感じがしてヒリヒリします。基本的に先読みの勝負なのでかなり頭を使うゲームです。
プレイしてみたい方はwebアプリもありますので良かったらどうぞ。
さてこのゴドマチ、
正規形ゲームであり、
不偏ゲームであり、
二人零和有限確定完全情報ゲームです。
二人零和有限確定完全情報ゲーム
いきなりやばい単語を発してしまってすいません。ゲームの種類を表す言葉なのですが、やばいですね。情報盛りすぎ。スタバの注文かよ。Wikipediaにその名前で記事があるのですから仕方ありません。二人零和有限確定完全情報ゲーム - Wikipedia
スリジャヤワルダナプラコッテとか、ピカソの本名とか、バンコクの正式名称とかやたら覚えてるやつクラスに一人はいましたけど、そういう人に与えたら大喜びしそうな名前です。
この言葉は、一人ずつ手番が訪れる（同時に指す、ということがない）ゲームのうち、「二人ゲーム」であり、「零和ゲーム」であり、「有限ゲーム」であり、「確定ゲーム」であり、「完全情報ゲーム」であるもののことを表しています。そしてゴドマチはこれらの条件をすべて満たしているというわけです。ひとつずつ確認してみましょう。
「二人ゲーム」
プレイヤーが二人ということです。「先手」「後手」とだけ言えばプレイヤーは一意に定まります。
「零和（ぜろわ）ゲーム」
「プレイヤーの誰かが得した分だけ、別の誰かが損をする」ようなゲームということです。二人ならば、一方が得した分だけもう一方は損をします。
全部のゲームがそうじゃないのと一瞬思えるかも知れませんが、「親の総取り」みたいな要素があったりすると、零和ゲームにならないことがあります。
「有限ゲーム」
プレイヤーの取りうる行動が有限個であるようなゲームです。ゴドマチは有限ゲームですが、「（マス目を無視して）好きな形に削ってもいい」みたいなルールに変えてしまうと、指しうる手が無限にあるため無限ゲームになります。
「確定ゲーム」
サイコロや、シャッフルしたカードを引くなど、ランダム要素を含まないゲームということです。ゴドマチにはランダム要素はないので確定ゲームです。
「完全情報ゲーム」
どのプレイヤーにとっても、隠されている情報がないゲームということです。麻雀で言う手牌、ポーカーで言う手札などの非公開情報があると、不完全情報ゲームとなります。ゴドマチはすべての情報が全員に公開されているので完全情報ゲームです。
これらをもって、ゴドマチは二人零和有限確定完全情報ゲームであることがわかります。
組み合わせゲーム
さて、これらの条件のうち「二人」「確定」「完全情報」という条件だけは少なくとも持っているゲームを、より一般に「組み合わせゲーム」と言います。組み合わせゲームは数あるゲームの中でも特に分析しやすく、それ故に特に研究が進んでいる分野です。
組み合わせゲームの中でも二人零和有限確定完全情報ゲーム、その中でもさらに「正規形」で「不偏」なゲームだと、より便利に使える分析のための道具立てが知られています。
むしろこっちの条件こそが今回の本題なのです。インパクトあるので二人零和有限確定完全情報ゲームの紹介を先にやっちゃったけど。
「正規形」と「不偏」とは、以下のような概念です。
「正規形ゲーム」
「打つ手がなくなったほうが負け」のゲームです。「相手を行動不能に追いやるゲーム」と言うこともできるでしょう。「順形」とも言います。ゴドマチは合同にした瞬間に終了するので正規形です。
そうでないゲームは「逆形」と言い、つまり「負けるが勝ち」のゲームです。
「不偏ゲーム」
プレイヤーによって打てる手が変わらないゲームです。「仮に先手がパスしたとしたら、後手は先手が打ち得た手を全て打てる」ようなゲームであると言うこともできるでしょう。
例えばオセロは白黒の別があるので不偏ゲームじゃないですね。将棋も囲碁も違います。それに対してゴドマチは先手と後手とで同じ手を打ち得るので不偏ゲームです。「不偏」というのは「偏りがない」ということで、名は体を表わしています。
この「不偏」という性質は特に重要です。実は、不偏ゲームであればどんなゲームでも、すべての局面に対してその局面が「先手必勝」であるか「後手必勝」であるかが判定できるのです。
「局面」というのはそのゲームのある一つの状況のことであり、「盤面」とも言います。そして、ある局面が「先手必勝」であるとは、その局面からゲームをスタートしたときに、最善の手を打ち続ければ先手が必ず勝つような局面である、ということを意味します。
「すべての局面が先手必勝か後手必勝か判定できる」。これはすごいことを言ってます。局面ごとの判定さえできていれば、プレイヤーは常に「後手必勝」の局面になるように（相手に後手必勝の局面を渡すように）指し続ければ勝てるわけです。これは言うまでもなく「必勝法」です。
この「必勝法」を与えてくれる道具が、タイトルで言及した「グランディ数（Grundy number）」というわけなんです。ここからはそのグランディ数を見ていきます。
グランディ数（Grundy number）
グランディ数とは、不偏ゲームの各局面に対して定義される値です。例えば5単位のゴドマチにおける以下の局面
に対するグランディ数は「3」、以下の局面だと
「0」となってます。
そしてなんと、いいですか？ なんとですよ？
このグランディ数が「0」のときは後手必勝、「0でない」ときは先手必勝なのです。すごい単純！！！！
つまりグランディ数が3である上の図の局面は先手必勝、下の図は後手必勝だというわけです。そんなこと分かっちゃっていいの？って感じですが、分かっちゃうんですね。グランディ数を求めさえすれば。
そうなると実際はどのような計算によってこの数値が決定しているのかが気になってくるわけです。ある局面のグランディ数は、
「その局面から一手でたどり着ける局面のグランディ数に含まれていない最小の0以上の自然数」
で決定されます。はい。何だかよくわかりませんね。そんなときは具体例です。以下のような3単位マッチで見てみましょう。
ここから一手でたどり着ける局面をすべて描くと、以下のようになります。
回転、鏡像、平行移動は同一視するので本質的にはこの二つだけです。
そしてまず、終了局面のグランディ数を「0」と定義します。右側の二つの局面はどちらも合同なのでどちらも終了局面ですね。
ここで、左側に書かれてあるもともとの3単位の局面に注目します。
ここから一手でたどり着ける局面は、言うまでもなく右側に書かれている二つの局面です。この二つの局面のグランディ数は、どちらも0でした。ということで、左側の3単位の局面のグランディ数は、「一手でたどり着ける局面（右の二つ）のグランディ数に含まれていない最小の自然数」ということで「1」と決定されるわけです。
1は0ではないので（あたりまえ）、先手必勝です。この局面をよく見ると、どう削っても合同になる、つまりどう削っても勝てるという形になっているので、先手必勝なのはあたりまえっちゃあたりまえです。
もう一つ具体例で見てみます。アルファベットの「W」と「T」のような形の局面（左上）から一手ずつ手を進めた状況を樹形図で書くと、以下のようになります。
終了している（合同になっている）局面には0がつけられます。
そこからグランディ数の付け方のルールに則り一つずつさかのぼって、1と2がつけられます。確かに、「その局面から一手でたどり着ける局面のグランディ数には含まれていない最小の自然数」がつけられていることをご確認ください。
最後にもとの「W・T」の局面のことを考えるわけですが、ここから一手でたどり着ける局面のグランディ数を見るとそれぞれ「2」と「1」になっていますね。というわけで「W・T」のグランディ数は、そこに含まれていない最小の自然数ということで「0」と決定されるわけです。樹形図を全部見るのではなくて、一手先「だけ」を見て決定するわけですね。
グランディ数が0なので「W・T」は後手必勝局面です。つまり自分の手番になったときにこの盤面になっていれば、負け確というわけです。逆に言えば、相手にこの形にして渡してしまえば勝ち確です。相手が「W・T」からどのように一手進めても、その次の一手で合同にできることは、樹形図を見ても明らかですね。
このグランディ数こそが、「ゲームを計算する」ことの内実の一つだったわけです。
ただ、必勝法を判定できるのはすごいことなんですが、実際には「ある局面から一手でたどり着ける局面すべて」と、さらに「より小さい局面のグランディ数」がすべて計算されていないと、その局面に対するグランディ数は計算できないため、そう簡単な話ではありません。単純に言って、局面が大きければ大きいほど（一手でたどり着ける局面が多いほど）計算量は爆発的に増加するわけです。
世の中そう甘くはないってことですね。
ゴドマチの定石
甘くない世の中ですが、実はゴドマチ5単位マッチに関してはグランディ数は完全に解析済みです。つまり、5単位ならばどの局面でも先手必勝か後手必勝かが判明しています。それを表にしたものがこちらにございます。
アルファベットは5個の正方形を並べた形（「ペントミノ」といいます）につけられた名前です。それぞれがどういう形なのかはこちらをご参照ください→ペントミノ - Wikipedia
必勝判定において大事なのは「0かそうでないか」でした。そこで、0に注目してこの表を見てみると、「X」の列に特に0が多いことに気づかされます。もっと言うと、「X」と枝分かれのない形（直鎖形）、という局面はすべて0（後手必勝）になっています。
つまり、自分の手番で「X」と「直鎖形」が残るように削れば必ず勝てる、というわけです。
これはいい「定石」です。これを知っているのといないのとでは、ゴドマチ終盤の戦い方に如実な差が出ます。語呂のように「X-直鎖（エックスちょくさ）」と覚えてしまうとよいでしょう。
5単位における後手必勝形の数は限られているため、ゴドマチが強くなりたいなら全部覚えてしまってもいいと思います。X-直鎖以外の後手必勝形は、この表によれば「『I』と『F or U or W or Z』」と「『W』と『T or V』」です。こちらも語呂的に「I-FUWZ（アイ−フウズ）」「W-TV（ダブルテレビ）」と覚えてしまうと、かなり有利にことを運べるでしょう。
（「X-直鎖」「アイフウズ」「ダブルテレビ」という名づけは、数学イベント「数学デー」常連さんのみうらさんによるものです。「ダブルテレビって炙りカルビみたいで楽しい」と言っていました）
この「定石」、当然もっと多い単位数に対しても覚えておけばより有利になれるわけです。しかし、そこは先述の通り、盤面が大きければ大きいほど計算量はどちゃくそ増加するので、定石の方も爆発的に増加してすぐ人間の覚えられる範囲を超えてしまいます。
6単位以上に対しては、いくつかお気に入りのものを選んで覚えておくくらいが関の山でしょう。今のところは。
ところで、ゴドマチにおけるグランディ数の完全解析は実は9単位までしかできていないそうです。これを多いと見るか少ないと見るかは人それぞれですが、いつも15単位マッチをよくやっている身としては少ないとも思えるし、ノノミノ（9個の正方形を並べた形）が1285個もあることを思えば多いとも思えます。これからのゴドマチ研究の発展に期待するところです。
おわりに
今回は、ペンと方眼紙さえあればすぐできて楽しい対戦パズル「ゴドマチ」と、不偏ゲームの核心「グランディ数」のご紹介でした。グランディ数の強力さ、そして「ゲームの局面を入力すると数値が出てくる」というエモさがなんとなく伝わったでしょうか。決して「二人零和有限確定完全情報ゲーム」と言いたいだけの記事ではなかったことはお分かりいただけたと思います。
せっかく新たに入手した概念なのですから、他の不偏ゲームに対してはどうなっているだろうとか、ゲーム以外にもグランディ数を考えられるものはないだろうかとか考えてみると楽しいと思います。
それでは今回はこのへんで！
