【将棋】着手可能な指し手の数を数え上げる
はじめに
将棋の初手は全部で30種類あります。そして、指し手の組み合わせは10^220（10の220乗）あるとも言われています。（※10^220については、諸説あるらしいですが…）
もちろん、10^220を全て数えることはできませんが、「最初の数手だけなら数えられるのでは？」と思い、以下のような問題を考えました。
今日は、これを考えていきます。
前提
まず、初手の合法手はすでに述べた通り、30種です。
(1) 後手2手目の合法手
これは簡単で、先手1手目の合法手のいずれを指しても、後手の駒を取ったり、そもそも後手の駒の利きに入る先手の駒はありません。
よって、後手2手目の合法手は、先手1手目と全く同じの30通り。
(2) 先手3手目の合法手
A) 3手目の最少パターン
先手1手目と3手目の各駒の利きの差分を考えます。上述の通り、1手目で最も駒の利きがあるものは飛車の6通りでした。そのため、この利きを減らすように指すことで、3手目の合法手を減らすことが可能と考えます。
1手目に▲3八Xを指すことで飛車の利きは1通りまで減らすことができます。この時、Xは銀もしくは金なので、それぞれの場合で数え上げを行っていきます。
ここで注意が必要なのは、各駒が動いた後のスペースに、別の駒が移動できるようになっている点を忘れずに数え上げる必要があるということです。たとえば、1手目▲3八銀の時、3手目の金は3八には行けなくなったが、代わりに3九に行けるようになります。
1手目▲3八銀の時、3手目に銀はどこにも移動できなくなる。したがって、銀の利きは-2となる。この時、3手目▲4九金の利きは1手目の金の利きと比べて±0である（金は3八には行けなくなったが、代わりに3九に行けるようになった点に注意）。ゆえに、1手目▲3八銀の時、3手目の合法手は30-5-2=23。
1手目▲3八金の時、同様に考えると、3手目に▲3九銀の利きが-1（3八に移動できない）、3手目▲3八金の利きは-2（4八のみ）。一方、3手目▲5九玉の利きは+1（4九が空いたため）。ゆえに、1手目▲3八金の時、3手目の合法手は30-5-1-2+1=23。
したがって、合法手が最も少なくなる1手目は▲3八金/▲3八銀で、3手目の合法手は23となることがわかります。（※巻末参照）
初手▲3八金はかなり珍しいですが、思い出されるのは「第二期叡王戦」PONANZA vs 佐藤天彦叡王（当時）ですね。
B) 3手目の最大パターン
最少パターンと同様に考えると、1手目で最も駒の利きが制限されている角の0通りをなるべく増やすように指すことで、3手目の合法手を増やすことができると考えられます。具体的には、1手目▲7六歩によって、2手目が何であっても、3手目の角の利きを、7七、6六、5五、4四、3三まで増やすことができるようになります。
ただし、2手目△3四歩の時にだけ、先手から角が2二まで進めるようになります。これによって、さらに先手は合法手を増やすことができます。よって、先手3手目の合法手を増やす進行は、▲7六歩△3四歩となります。
もう一つ注意が必要な点が以下のようなパターンです。
当たり前ですが、成/不成は選択可能であり、それぞれが合法手。分けて数える必要があります。
結局、3手目の合法手が1手目から以下の分だけ増えます。なお、3手目▲7五歩が着手可能となったが、これは「1手目▲7六歩を選ばなかった時の▲7六歩の分」と考えると、手数増には寄与しないので除外しています。
▲7七角
▲6六角
▲5五角
▲4四角
▲3三角 ▲3三角成
▲2二角 ▲2二角成
▲7七桂（！）
最後のトラップ（？）が▲7七桂です。1手目▲7六歩によって、左桂の移動可能範囲が0→1に増えたのを忘れてはいけません。
したがって、合法手が最も多くなる手は1手目▲7六歩、2手目△3四歩の時で、3手目の合法手は39となります。
(3) 1~3手目の合法手の組合せ
以上のような考え方で、合法手を数え上げていかないといけないのですが、案外全パターン網羅するのが大変だということが分かってきて、ちょっと止まっています。
たとえば、▲7六歩△8四歩の時、3手目の合法手は37（角+6、桂+1）になりますが、▲7六歩△4四歩のいわゆる「パックマン」の進行になると、3手目の合法手は35（角+4、桂+1）しかありません。
実は、パックマンの際の検証が不十分で、正しく数え上げられてないようですので、ここはまた後日検証したいと思います…（※検算中）
おわりに
ちなみに4手目はさらに複雑になることが分かっていて、たとえば▲7六歩△（任意）▲3三角/角成の進行となる場合、4手目は王手を避ける手でないといけないので、合法手が
▲3三角/角成を取る：△同桂、△同角
玉が逃げる：△6二玉、△5二玉
合い駒する：△4二銀、△4二金、△4二飛 ←忘れやすい
の7手しかありません。
さらに、先手5手目は、上記進行で角を持ち駒にしている場合、さらに「角を打つ」ということも可能になります。こうなると、さすがにすべてを書き出すのはかなり難しいですね。
将棋AIは実は裏でこういった場合の数もすべて拾い上げて探索している…のと同時に、人間はそこまですべては拾い上げてはいないけれど、有用な手を見つけ出しているという点については、引き続き掘り下げていきたいなと思っております。
（つづく）
※追記、修正履歴
2022/05/25：(2) A)の最少パターンを「▲3八金で計22種」と書いていましたが、計算間違いでした。実際は23となります。よって、「合法手が最も少なくなる1手目は▲3八金/▲3八銀で、3手目の合法手は23」でした。訂正してお詫びいたします。
この記事が参加している募集
課金してくれるととても嬉しいです。シェアしてもらっても嬉しいです。「いいね」も嬉しいですし、フォローも嬉しいです。要するに、どんなことでも嬉しいです。