あいかわらず Tokyo Doves の解析にドハマりしているぷりんです。
ゲームの進行について考察していると、以下の性質に気づきました。
ここで「自滅する手」とは、その手を指すことで相手の手番に移る前に自分のボスハトが囲まれた状態になることを指します。
この記事ではこの性質について証明していきます。
自滅する手
あなたの手番で、以下のような盤面を考えます。
B | x | |
x | x | |
x |
ここで B はあなたのボスハト、x はなんらかのハトがいるとします。以下、同様の記法を採用します。あなたがボスハトを右下に動かす手は当然合法ですが、実際に実行すると
x | ||
x | B | x |
x |
となり、あなたの負けとなります。このように、実行すると即座にあなたのボスハトが囲まれてしまう手が存在します。もし仮に、ある手番のときに、このような自滅する手しかないとしたら、相手の手番に回る前に敗北することが確定してしまいます。
この記事の目標は、千日手禁止ルールが無い条件の下で、実は自滅しない手が必ずあることを示すことです。これが示されれば、勝敗が確定するのは、必ずいずれかのプレイヤーが自分が勝つ手を選択したときである、ということが分かります。解析がスッキリして便利ですね。
考えるべき状況の整理
大筋で行うことは反例探しの旅です。「この盤面だとどの合法な手でも自滅する手しかない」といった盤面を探し、まったく見つからないことが分かれば主張の証明完了です。
まず自分に手番が回ってきたということは、自分のボスハトの四方がハトで囲まれている状況ではない、ということになります。もし仮に四方のうち空いているマスに自分のボスハトを動かす手が合法なら、元いた位置がちょうどボスハトの四方の空きマスの役割を果たすので、これは自滅しない手です。
言葉では分かりにくいので図にします。例えば以下の状況のときを考えます。
x | x | |
x | B | |
x | x |
ボスハトの右側が空欄になっていて、さらにボスハトを右側に動かす手は合法です。実際に右側に動かすと
x | x | |
x | B | |
x | x |
このような盤面になります。このときボスハトの左側は必ず空欄になるはずです。なぜなら、そこはまさに先ほどまでボスハトがいた場所で、移動したことによって空欄になっているからです。よってこれは自滅しない手です。
したがって考えるべき状況は、自分のボスハトを四方のいずれに動かす手も合法でない場合のみとなります。
空欄があるのに動かすのが合法でない場合というのはどういう状況でしょうか?ハトを動かす際は、ルール上4つの判定がなされます。
- その移動はそのハトの種類から決まる移動条件に合致するか
- 移動先または移動経路に障害となるハトはいないか*2
- 移動した結果、盤面のサイズは4x4のスペースに収まるか
- 移動した結果、いずれかのハトが孤立*3しないか
これらの条件をすべてクリアしたら、その移動が合法な手となります。
改めて今回のボスハトを動かす場合について考えましょう。1つ目と2つ目の条件は明らかにクリアします。3つ目は「壁が元々ある場合はその方向は空欄とはみなさない」とすることで*4、ハトの移動によって盤面のサイズが広がることはないことが分かるので、やはり条件を満たすことが分かります。よって肝になるのは4つ目の条件となります。つまり自分のボスハトを四方のいずれの空欄に動かそうとしても、孤立するハトが出るという状況を考えればよいです。
さらに踏み込んで、ボスハトを動かすことで孤立するハトが生まれるのはどういうときか考えます。当たり前ですが、ボスハトを動かした場合でも、他のハトは一切移動しません。つまりボスハト以外との間の隣接関係は全く変化しません。ということは、ボスハトが移動したことによってあるハトが孤立するためには
- 移動前にはボスハトと辺または角で接していた
- 移動後にボスハトと辺でも角でも接しなくなった上、ほかのハトとも辺でも角でも接していなかった
が重なる必要があります。1つ目の条件から、孤立候補のハトは移動前のボスハトの位置の八方の隣接マスにしかいないことが分かり、2つ目の条件から「ボスハトを仮に取り除くと孤立する」という条件を満たす必要があります。
以上を踏まえて、具体的にいくつかのパターンに分けて考えていきます。
ボスハトが4x4の隅にいるとき
元からボスハトが孤立している状況では手番が回ってこないため、ボスハトの周辺にはすくなくとも1羽のハトがいます。またボスハトの周辺にハトが2羽以上いる場合、それら同士で辺または角で接しているため、ボスハトを取り除いても孤立しません。したがって考えるべき状況は
(1)
x | x |
B | x |
および
(2)
x | |
B |
の2通りです。いずれもボスハトを右に動かす手が合法です。
ボスハトが4x4の隅にはいないが縁に接しているとき
ボスハト周辺で孤立しうるハトがあるような場合のみ列挙すると、以下の6通りになります。
(1)
x | ||
x | B | x |
(2)
x | ||
x | B | x |
(3)
x | ||
x | B |
(4)
x | x | |
B |
(5)
x | x | |
B | x |
(6)
x | x | x |
x | B | x |
それぞれ例えば(1)~(5)は上方向への移動が、(6)は右方向への移動が合法となります。
ボスハトが隅にも縁にもいないとき
これまでと同じ考え方で、9通りのパターンが考えられます*5。これまでと同様、それぞれについてすぐに合法と分かる動きを考えるのですが、実は合法な動きが必ずしも特定されないものが以下の3パターンあります。
(1)
x | ||
B | ||
x |
(2)
x | x | |
B | ||
x |
(3)
x | x | |
B | ||
x | x |
いずれの場合についても「対角に位置するハトのペアであって、ボスハトを取り除くと同時に孤立するものが存在する」が満たされることが、合法な移動がないための必要十分条件となります。もし「~~が存在しない」なら、孤立しうるものたちがいる方向にボスハトを移動すれば合法ですし、「~~が存在する」なら、どう動かしても孤立するハトが生まれてしまって合法でなくなります。
ここから先は具体的にハトを並べる必要があります。ですが、ひとつだけ探索の手がかりとなる条件を出すことができます。
もし仮に手持ちのハトがいるとします。すると(1),(2),(3)のどのパターンでも、ボスハトの周辺のいずれかには配置できます。元の目的は「自滅しない手がある」ことを示すことだったので、この場合は考えなくてよいことが分かります。すなわち、「すべての手が自滅する手である」という状況があるとしたら、その時点であなたのハトはすべて盤面上になくてはなりません。さらに、ルール上相手のボスハトも当然盤面上に存在する必要があるため、都合7羽のハトが少なくとも盤面上にいる場合を考えればよいことになります。
この手がかりを元に、各パターンについてより具体的に並べてみます。
パターン(1)
ボスハトの周辺の2羽はどちらも「ボスハトを取り除くと孤立する」ようにする必要があります。そのようなパターンは以下の2通りのみとなります。
(1-a)
y | y | ||
x | y | ||
B | |||
x |
(1-b)
y | |||
x | |||
B | |||
x | y |
ここで y はハトがいる、または空欄とします。以下でも同様の記法を採用します。いずれでも盤面上に7羽のハトが存在しえないので、いずれも考える必要のないパターンです。(すなわち手札からボスハトの横に出す手が合法)
パターン(2)
対角に位置するハトを「ボスハトを取り除くと孤立する」ような状態にするパターンは以下の3通りです。
(2-a)
y | |||
x | |||
B | |||
x | x | y |
(2-b)
y | y | ||
x | y | ||
B | |||
x | x |
(2-c)
y | y | ||
x | x | y | |
B | |||
x |
(2-a)は7枚のボスハトが存在できないので不適です。(2-b),(2-c)はギリギリ7羽のハトが存在できます。ただ x, y たちのうちいずれかの自分のハトは動かせるため、これが自滅しない手となります。具体的には、アニキハト、ヤイバト、トツハトあたりを上下左右のいずれかに1マス動かす操作を考えればよいでしょう。
パターン(3)
右上と左下を孤立候補とするパターンと、左上と右下を孤立候補とするパターンの2通りが考えられます。
(3-a)
y | |||
x | x | ||
B | |||
x | x | y |
(3-b)
y | y | ||
x | x | y | |
B | |||
x | x |
(3-a)は最大7羽です。xのいずれかにはアニキハト、ヤイバト、トツハトのいずれかが居るので、上下左右のいずれかの方向の合法な動かし方があります。
(3-b)は最大8羽です。yはすべてハトか、1つだけ空欄です。もしyのひとつが空欄なら、やはりxのいずれかにアニキハト、ヤイバト、トツハトのいずれかが居るので、上下左右のいずれかの方向の合法な動かし方があります。yがすべてハトの場合、yに上記3ハトが集まっていない場合は同様の論法で合法な自滅しない手があることが分かりますし、集まっている場合でも隅でないyを動かす手が合法な自滅しない手となります。
これですべての場合を調べ尽くしました。どの場合でも、自滅しない合法な手が必ずありました!
まとめ
以下をポイントに自滅しない手を探索しました:
- 基本的にボスハトが上下左右に移動する手があること
- ボスハトの周りに孤立ハト予備軍がいる場合のみ要注意なこと
- その場合でも手札から出したり適当な別のハトを動かすことで自滅しないこと
その結果、常に自滅しない手があることが分かりました。晴れてスッキリ探索ができて私は嬉しいです。
次回は局面数の見積もりみたいな話をしたいです。