引き続き Tokyo Doves の記事です。板についてきました。今回は詰み局面の全列挙の方法について紹介します。
詰み局面の定義
詰みの定義を考えるために将棋を参考にします。将棋では「自分が何を指しても次に相手が自分の玉を取ることができる状態」を詰みと呼びます。同じように Tokyo Doves での詰みを考えると、「自分が何を指しても次に相手が自分のボスを囲むことができる状態」を詰みと定義するとよさそうです。以前の記事で議論したように1手で自滅しない手が存在するので、そのような手のうちどれを選んだとしても、その後相手が自分のボスハトを包囲するような手がある、という風に考えればよさそうです*1。この記事ではこの定義を Tokyo Doves での詰みとしておきます。
探索の方針
詰み局面を全列挙するには、詰み局面の可能性のあるものをすべて探索する必要があります。しかしルール上可能な局面は 通りぐらいあるので、これを全部確かめていたのでは日が暮れるどころか人類が滅びてしまいます*2。そこで局面数を数えたときと同様に、ハトの配置の形と、具体的にどの種類をどこに割り当てるかを分けて考えてみることにします。前回の記事をまだ読んでない方は読んでみてください↓
smooth-pudding.hatenablog.com
前回は、ハトの割り当て方の部分が理論的に計算できるので、全体の数え上げも一瞬で終わるという構図をしていました。つまりハトの配置の形自体の種類は大したことないということです。今回も割り当てのところを手軽にできる方法を考えます。(ハトの配置の形の列挙に関しては前回から新しいことは特にないので省略します)
ハト配置の形状が与えられたときの詰み局面の全列挙
前回同様、今回も理論的に片付けてハイ終わり・・・というわけにはいきません。今回はどのようにハトを置いたら詰み局面なのかをすべて列挙する必要があるので、実際に並べてみる必要があります。これは避けられない現実ですが、なるべく工夫して、並べる前から絶対に詰み局面ではないものを省いてみます。
まず、ハトを並べた時点で相手や自分のボスハトが包囲されているような局面は対象外です。詰み判定をする前にゲームが終了しているからです。なので、ハトを並べるときは、自分と相手のボスハトがいずれも包囲されていないような場所に置くことだけ考えればよいです。形状からどの位置が包囲される場所かは特定できます。例えば
| x | x | x | |
| x | x | x | |
| x | x | x | |
| x | x |
上記のような形状が与えられたとして、包囲されている場所を o に置き換えると
| x | x | x | |
| x | x | o | |
| x | o | o | |
| x | o |
となります。互いのボスハトは o 以外の場所に配置し、そのあとに残りのハトをどこに並べるかを考えれば良いことになります。
しかしこれだけでは焼け石に水で、抜本的に計算時間が劇的に短くなることはありません。やはり人類が滅びてしまいます。実は人類の滅亡を防ぐ方法、いえ人類が滅亡する前に詰み局面を全列挙するための妙案があります。その説明をするために、包囲度という概念を導入しておきます。
包囲度
盤面上にある特定のハトに対し、その包囲度は、そのハトの四方のうち、ハトがいたり壁があったりするのは何個あるか、という量として定義しします。例えば
| x | a | ||
| x | x | ||
| x | x | ||
| x |
以上の x の各位置にハトがいるとき、a のハトの包囲度は 2 となります。a の左隣にハトがいるのに加えて、上側は壁ができており、合わせて2方向が包囲されている、と数えます。もし
| x | a | ||
| x | x | ||
| x | x | ||
| x |
のように a の上側が壁でなければ、a の包囲度は1となります。
包囲度の言葉を使えば、自分が負ける条件は、自分のボスハトの包囲度が4となること、と表現できます。相手のボスハトの包囲度を4にしたら勝ち、とも表現できます。
詰み局面となるための必要条件
元の話題に戻ります。ハト配置の形状が与えられたとき、ハトを並べまくっていると時間が掛かりすぎるという話でした。実はハト配置の形状と自分のボスハトの位置のみから、即座に詰み局面となりえないと判断しうる性質があります。それが以下です。
ハトの配置の形状が与えられ、そのうち自分のボスハトの位置が確定しているとする。もし自分のボスハトを (合法的に) 動かした結果、ボスハトの包囲度が2以下になるような手があるならば、他のハトをどのように配置したとしても、詰み局面とはならない。
何言ってるか分からない人も多いと思うので、具体的に説明します。
| x | |||
| x | x | B | |
| x | x | x | x |
| x | x | x | x |
以上のように自分のボスハト B となんらかのハト x 11羽が配置されている場合を考えます。それぞれの x にどのハトが並ぶかは現時点では未定です。B が合法的に動ける方向は上方向または斜め上方向です(ボスハトをどう動かせるかについては x にどうハトが並ぶかに関係ありません)。例えば上方向に動かすと
| x | B | ||
| x | x | ||
| x | x | x | x |
| x | x | x | x |
となります。このときの自分のボスハトの包囲度は2です。動かした結果包囲度が2となるようなボスハトの動かし方がある、すなわち先ほどの性質の仮定を満たします。すると、現時点でまだ x にハトを並べていないにも関わらず、元の形状は絶対に詰み局面ではないことが判明してしまいます。
理解のために詰み局面が起こりうる形状についても考えてみます。例えば以下の配置はハトの並べ方によっては詰み局面となります。
| x | B | ||
| x | |||
| x | x | ||
| x | x |
ボスハトの合法的な動かし方は、左方向か下方向の2通りがあります。左方向に動かすと
| x | B | ||
| x | |||
| x | x | ||
| x | x |
となり、ボスハトの包囲度は3です。下方向に動かすと
| x | |||
| x | B | ||
| x | x | ||
| x | x |
となり、やはりボスハトの包囲度は3です。先ほどの性質の仮定を満たさないので、具体的に並べてみないと詰み局面があるかどうか分かりません。ちなみにどのように配置すると詰むかというと例えば
| b | B | ||
| x | |||
| c | d | ||
| x | x |
(b: 相手のボスハト, c: 相手のハジケハト, d: 相手のアニキハト, x: 残りの相手のハトいずれか)
が具体例になります。ボスハトが左や下に動くと即座にハジケハトが飛んできて敗北しますし、持っているハトをボスハトの隣に配置すると相手のボスハトやアニキハトが寄ってきてやはり敗北します。他に指せる手はないので、まさしく詰み局面です。
この性質の証明は後に行うとして、この性質が成り立っていることのありがたみを考えてみます。この性質は、一つひとつハトを並べずとも、ボスハトの動かし方を検査するだけで、ハト配置の形状をボツにできる可能性があると主張しています*3。与えられた形状に対してざっくりハトの欄の階乗ぐらい探索パターンがあることを考えれば、この方法でボツにできるだけでかなり強力そうであることが想像できるのではないかと思います。
詰みのための必要条件の証明
さて、前節で紹介した性質を証明していきます。証明は2ステップで実行します。
事実1: 相手のボスハトの包囲度を2以上上げる手は特殊な例外のみ
1手で相手のボスハトの包囲度をなるべく上げる方法を考えます。包囲度を上げるには、
- 相手のボスハトの上下左右隣にハトを移動させる
- 相手のボスハトの上下左右隣に壁を作る
のいずれかしかありません。このうち前者で包囲度を2上げることは不可能です。相手のボスハトの上下左右に新たにハトを2羽増やそうにも、動かせるのは1羽のみだからです。また前者と後者を組み合わせて包囲度を上げる方法もありません。ボスハトのすぐ隣に壁を作るには、ボスハトが接している方から反対側の壁にハトを移動させるか配置するかする必要があります。当然このハトは相手のボスハトに隣接しないので、ボスハトの隣にいるハトの数は変わりません。
したがって、相手のボスハトの包囲度を2以上上げるには、新たに2つ以上の壁をボスハトの上下左右のいずれかに作るしかありません。2つ以上と言いましたが、ひとつのハトが接することのできる壁は最大2つであり、4x4 の隅にいるパターンしかありません。よって、1手でボスハトの包囲度を上げる最大幅は2であり、2上げるには
| B | x | ||
| x | |||
| x | |||
| x | x | x | o |
上記の x, o の位置には元々ハトは一切おらず、1手によって o の位置にハトが移動するか手札から置かれるというパターンしかありません*4。それ以外のパターンだと包囲度は高々1しか上がりません。
事実2: 特殊な例外のケースは詰み局面を生まない
事実1の議論から、特殊な例外ケースを除いてボスハトの包囲度は1手で1までしか上がらないことが分かりました。このことから、もし自分のボスハトの包囲度が2以下の状態で相手の手番となった場合、特殊な例外ケースのパターンになっていない限りは、相手の1手で自分が敗北することはないと分かります。そこでここでは警戒すべき特殊な例外について考えてみます。例外ケースで次の相手の1手で自分が敗北するかもしれない局面は、以下の形になります。
| B | ① | ② |
| ③ | ④ | ⑤ |
| ⑥ | ⑦ | ⑧ |
相手の手番で⑧の右下が新たに埋まったタイミングで自分のボスハトの包囲度が4になるには、①と③が既に埋まっている必要があります。この配置の一手前について考えてみます。元々示したかった性質のことを思い出しておけば、自分の手番でボスハトを動かしてこの位置にやってきた場合のみ考えれば十分でしょう。
①, ③が埋まっていることを前提とすると、一手前は次のパターンのみを考えれば十分です*5。
(1)
| B | ① | ② | |
| ③ | ④ | ⑤ | |
| ⑥ | ⑦ | ⑧ |
(2)
| ① | ② | ||
| B | ③ | ④ | ⑤ |
| ⑥ | ⑦ | ⑧ |
(3)
| ① | ② | |
| ③ | B | ⑤ |
| ⑥ | ⑦ | ⑧ |
(1) や (2) のパターンのときはそれぞれ (2) や (1) に動かす手が合法で、いずれもボスハトの包囲度が2以下の1手で敗北し得ないパターン (=特殊な例外でないパターン) です。すなわち (1) や (2) は詰み局面ではありません。(3) の場合、⑤か⑦のいずれか一方は空欄である必要があり (そうでなければ既にゲームが終了している局面なので不適)、そちらの方向にボスハトを動かすとやはりボスハトの包囲度が2以下の1手で敗北しえないパターン (=特殊な例外でないパターン) となります。すなわち (3) は詰み局面ではありません。
以上の議論から、特殊な例外パターンからは詰み局面は生まれないことが分かりました*6。これにより晴れてボスハトを動かした結果包囲度が2以下となる手があるなら、詰み局面でないことが示されました。
全列挙の結果
ここまで紹介してきた手法とビットボードを使った高速な実装、また Rust コンパイラによる最適化を経ることで、現実的な時間 (たしか数日程度？) で全列挙することができました。ちょっと漏れがある疑惑が最近出てきているので正確な数値かどうかは若干怪しいのですが、平行移動・反転・回転で一致するものを除いた上で、詰み局面は全部で
ありました。*7(追記 (2022/11/12): 追試したら以下になりました:
より詳しく、フィールド上にいるハトの数に対応する局面数、および合計の局面数は以下のとおりになりました。)
次回以降、ここから出発した後退解析について紹介できるといいなぁと思っています。(が、まだ試行錯誤しながら探索中なのでいつになることやら・・・)
*1:細かいことを言えば同時にボスハトが囲まれてしまう手をどうするか問題があるのですが(ルールについて考えてみる回参照)、今回の記事の内容は(最後の局面数を除いて)そのときの裁定をどのように決めても正しいはずです。
*2:実は人類は滅びないかもしれませんが、数ヶ月とかかかりそうぐらいにはなります。
*3:正確には、形状とボスの配置の組み合わせをボツにするということです。同じ形状でも、あるボスハトの位置ならボツだが、別のボスハトの位置なら耐え、という状況はあり得ます。
*4:ここでは空欄は未定の意味であり、ハトがいないことは意味しません。
*5:左斜め上から来る手はボスハトが孤立しているので非合法。上や右斜め上は対称性から (2) や (3) で事足りる。
*6:より証明の内容に即した丹念な表現をすると、もし仮にボスハトをある方向に動かした結果の局面が例外パターン(包囲度が2で壁同時生成により包囲度4になる)に該当するとしても、別の方向に動かすことで包囲度が2以下の例外パターンでない状況を作れる、ということです。
*7:ここでは、自分の手の結果両者のボスハトが同時に囲まれた場合、自分が敗北するというルールを採用しました。
