前回の記事「将棋の局面数　１：局面数は無量大数」では、「駒の配置から将棋の局面数を見積もる」ということを考えました。今回は、「一手ごとの分岐から考えると局面数はどうなるのか」ということを考えてみたいと思います。

実は、前回の記事の冒頭で触れた「将棋の局面数は10の220乗」という説は、分岐に基づく推測に由来します。すなわち、将棋の一局面における合法手の平均は約80手であり、将棋の平均手数は約115手であるから、\[80^{115} \approx 10^{219}\]となり、約220乗だというわけです。

この計算方法はとても不可解であり、筆者にはよく理解できません。合法手の平均が約80手だというのはいいとして（参照：「ゲームとしての将棋のいくつかの性質について」）、なぜ平均手数が出てくるのでしょうか。この計算式の依って立つ仮定に基づくと、局面数はべき乗で増えていくことになるわけですから、平均手数ではなくて最大手数にしないと局面数を見積もることはできないはずです。また、最大手数ならば、平均手数とは異なり、棋譜集には依存せずに下限値も分かります。さらに、最大手数を使うと、とてつもない数字が出てきてしまうことになり、仮定の問題点が明確になるという利点もあります。

実際に、前回の記事で示した通り、駒の配置から見積もられた将棋の局面数は10の68～69乗程度であり、この分岐による見積もりは、最大手数を平均手数まで落としたとしても、明らかな過大評価になってしまっています。

それでは、どこが間違っていたのでしょうか？

この仮定の最大の問題は、合流局面の存在を考えずに、ずっと局面数がべき乗で増えていくと考えたところにあります。一度数えた局面は、次に出てきた時には、二重に数えてしまうことになるため、本来は消してしまわないとなりません。既出局面の数が局面数よりもずっと少なければ、合流局面は無視できるかもしれませんが、既出局面の数が局面数に近くなると、合流局面の割合が大きくなって、新規局面がべき乗で増えるという事はなくなるわけです。

実際、将棋の局面数を10の68乗として、一局面の合法手を80手とすると、大体35手で将棋の局面数に達して、新規局面が出なくなるという計算になります。もちろん、実際には、初期局面から35手でたどり着けない局面も沢山ありますので、手数に対する新規局面数の分布は、初期局面から最短の手数で作れる局面の数の分布になるわけです。この分布は、合法手の平均とも、最大手数とも、平均手数とも、何の関係もありません。

さて、以上のことから、分岐から局面数を見積もるのが難しいということが分かります。分岐から局面数を見積もるには、合流局面の数を考えなければならず、合流局面の数を考えることは局面数を見積もることよりもずっと大変だからです。

しかしながら、このことは逆に考えると、局面数が分かっているのならば、分岐を考えることで合流局面数についての推測ができるということを示唆しています。

実際にやってましょう。

前回の記事に記したように、10の68～69乗の局面数というのは「ありえない」ような局面を大量に含んだものでした。成り駒を禁止すると約10の54～55乗となりますが、ここでは、さらに数を絞って、10の50乗の「ありえそうな」局面を考えることにしましょう。ここで、50乗という数字に深い意味はありません。以下の議論は、局面数を変えても、数値が変わるだけで同じように進めることができます。

最初の30手は合流局面も多いので、合流局面を除いた時の平均分岐数を2に設定しておくとすると、30手終了時には約10の9乗個の局面が現れます。多くの将棋ソフトの定跡ファイルの登録局面数は10の5～6乗個程度ですが、定跡を外れた後の変化の局面まで考えると、ここでの30手目までに約10の9乗個の局面というのは特に多いとは言えないでしょう。

その後の平均分岐の数を3に設定してみます。これは、各局面で平均的に3手くらいの指し手を候補として考える時の将棋の可能性の世界に該当します。将棋ソフトの平均分岐数が3くらい（ソフトにより2～5）という話もありますので、将棋ソフトが見ている将棋の世界と考えてもいいかもしれません。

31手目以降、3の累乗で合計10の50乗の局面数に到達するには116手までかかります。途中での投了局面の影響を考慮しても、この116手というのはあまり変わりません（実際に補正計算もやってみたのですが、説明が煩雑になる割に結果があまり変わらないので省略します）。ちなみに、平均分岐数3の代わりに、2の場合には166手、4の場合には98手になります。

ここで重要なことは、116手目以降には新規局面はほとんど現れないということです。つまり、それ以降の局面は、分岐による可能性の世界のどこかにすでに存在していて、手数をかけて遠回りをして合流したという解釈になります。

この結果は、かなり意外だと感じられる方が多いのではないでしょうか。例えば、「持久戦になっても局面が複雑になるわけではなく、両者手損の遠回りをして急戦の局面に合流するだけ」と書くと、「そんなわけないだろ」という感じられる方がほとんどでしょう。実際、多くの手数をかけないとたどり着けない局面も存在するため、その点でこの話には検討の余地があるのですが（特に分岐数が多い場合）、簡易的な見積もりとしては、このような結果になるということです。

以上、今回は将棋の局面数について分岐の観点から考えてみました。

10の68～69乗という局面数は膨大に感じられますが、そんな数でも分岐の累乗は意外と簡単に食い尽くしてしまいます。将棋の“樹”は、ただ枝が広がっていくような単純な構造にはなっておらず、各枝が複雑に合流しあった迷宮のような構造になっており、その構造は、平均分岐数3といった大胆な枝狩りを行った場合でさえ、消えることはありません。今回の見積もりは、そのようなことを示唆していると言えます。