将棋の局面数は10の220乗だと言われることがあります。実は、この見積もりは正しくないとされており、実際の局面数はもっと小さいと推定されています。この「220乗」説の検討は次回にまわすとして、今回は将棋の局面数をざっくりと見積もってみたいと思います。

将棋の局面数については、篠田正人先生の見積もりが有名であり、「将棋における実現可能局面数について」（pdfファイル）という論文において、10の60乗以上70乗未満と下限・上限を厳密に算出し、さらに68～69乗程度ではないかという推測を述べておられます。篠田先生は数学者らしく“はさみうち”の方法を用いて慎重に見積もっておられるのですが、ここでは、物理学的な近似計算を用いて大胆に見積もりたいと思います。

まずは、以下の仮定で局面数を計算します。

1. 王手については考慮しない。
2. 持ち駒、成り／生駒、先手／後手駒は全ての数の組み合わせの場合に分けて積算する。
3. 持ち駒以外は、歩、と、桂、成桂、香、成香、銀、成銀、飛、龍、角、馬、金、玉の順にそれぞれ先手駒、後手駒の順で盤に配置する。
4. 最初の歩を配置する時の空きマスは、全空きマスの8/9で近似する。2枚目以降は全空きマスの8/81ずつ減らしていく（二歩のため）。
5. 最初の桂を配置する時の空きマスは、全空きマスの7/9で近似する。2枚目以降は空きマスが1ずつ減る。
6. 最初の香を配置する時の空きマスは、全空きマスの8/9で近似する。2枚目以降は空きマスが1ずつ減る。

ここで、仮定4～6において、歩・桂・香の配置の数を算出する際に近似を使っていることに注意してください。これらは本来は、既に置かれている駒の配置が詳細に分かっていないと正確な計算ができないのですが、ここでは、配置の情報は使わずに、平均値を用いて近似しています。この計算は、手でやろうとすると大変ですが、コンピュータにやらせると簡単です。

結果として、\[6.15 \times 10^{69}\]という数値が得られます。この数字は、篠田先生の上限の見積もりに近い値です。

この計算では、王手を考慮に入れていないため、王手放置の違法局面が含まれてしまっています。王手放置局面を取り除くには、最後に後手玉を配置する際に先手駒の利きのないマスに限定する必要があります。空きマスの中に先手駒の利きのない配置可能マスがどれくらいあるのかは局面の駒の配置に依ってきてしまうのですが、簡単に平均を見積もるとおおよそ3割程度になります（盤上に全駒の半数の20枚の先手駒が配置されている時の平均的な利きの割合）。

結果的に、王手放置局面を取り除くと、大体10の69乗という見積もりになります。

さらに、篠田先生は「初期局面から到達可能であるか」という点も考えておられるのですが、ここではそこには深入りしません。

ただし、「王手放置を経由しないと作れない」というような明らかに無理がある局面が少数ながらも存在することを考慮すると、少し下方修正が必要で、最終的には10の68～69乗程度という見積もりになります。この結果は、偶然にも篠田先生の推測とピッタリと一致しています。

江戸時代の算術書である「塵劫記」によると、10の68乗は「無量大数」と呼ばれます（※写本によっては88乗という説もあります）。これは「塵劫記」に記された数の最大の位であり、これより上の位は日本には存在しません。日本の数の最大位が将棋の局面数と同じだというのは、中々によくできた話です。

ちなみに、平均的な銀河にある原子の数はおおよそ10の69乗個くらいです。将棋の局面数は銀河にある原子の数と同程度ということもできるでしょう。ちなみに、宇宙には少なくとも10の11乗個の銀河があるとされていますので、残念ながら宇宙には及びません。

さて、ここで見積もった局面の中には「絶対にありえないだろ」というような局面が大量に含まれています。初期局面から原理的に到達できないものもあるでしょうし、到達可能であっても、どう考えてもありえないような手筋を経ないと作れない局面も沢山あります。むしろ、人間的に「ありえそう」に感じる局面の方が圧倒的に少ないというのが実情でしょう。

人が「ありえない」と感じる局面で最も数が多いのが「成り駒が多くある」局面だと思います。成り駒は作るのが大変であり、通常は大量にできることはありませんので、成り駒がウヨウヨしている局面を見ると「ありえない」と感じるわけです。

そこで、思い切って、成り駒を全て禁止した上で同じ手法で局面数を見積もってみると、約10の54～55乗という結果になります。この辺りが「ありえそうな」局面の数の下限になっているのではないでしょうか。

最後に、これらの数字を元にして、完全解析にかかる時間を見積もってみましょう。

ここでの完全解析は、全ての局面を調べ上げるのではなく、ミニマックス原理に基づいて「両者最善が先手勝ち／後手勝ち／引き分けのどれになるのか」を判定するだけに留めることにします。この場合、探索（合法手生成）が必要な局面数は、理想的に上手くやれば、10の30乗程度で済むと推測されます。

一秒間の探索局面数（NPS）を10の14乗とすると（※2016年の現時点では高性能機一台で10の7～8乗程度）、10の30乗の局面を探索するには、約3億年かかることになります。これが完全解析が現実的ではないと言われる所以です。ただし、現時点では予測できない根本的な技術革新があれば、もっと短時間で済むようになる可能性も否定はできません。

「局面数はゲームの複雑性を測る指標である」と言われることがありますが、これは完全解析を念頭においての考え方だと思われます。完全解析がほぼ不可能だとみなされる局面数であるのならば、もはや「局面数の多寡はゲームの複雑性とは関係しない」と言えるのではないでしょうか。この場合、ゲームの複雑性というのは、数理を離れて、工学的な領域の話題となり、局面評価の技術的な難易度の話に帰着されるのだと思います。特に、機械と人とを比較する場合には、両者の間の相対的な能力差の話になりますので、純粋に技術の問題になります。

以上、今回は将棋の局面数について駒の配置の数から考えました。ざっくりとした見積もりでは、将棋の局面数は10の68～69乗程度であり、成り駒を禁止しても10の54～55乗程度になります。

次回は、「一手ごとの分岐から考えると局面数はどうなるのか」ということについて考えてみたいと思います。

-------------------

追記（2016年4月1日、ただし、エイプリルフールにあらず）

本文に記した完全解析の見積もりについて、補足します。

必要な局面数が「理想的に上手くやれば、10の30乗程度で済む」というのは、こういう見積もりでした。

1. 実現可能局面数は篠田先生の下限値の10の60乗を採用。
2. アルファベータ法で理想的順序なら実現可能局面数の平方根となり、10の30乗。

しかし、今になって考えると、この見積もりはさすがに甘すぎたのではないかと感じています。理由は以下の2点です。

1. 合流局面について全て記憶して利用できると暗黙に仮定しているが、10の30乗の局面ですら、現実的には不可能である。
2. 一つの局面が、ある枝では評価が不要であっても、別の枝では評価が必要であることがあるため、合流局面を省いた後にさらにアルファベータ法の平方根を適用するのは、あまりにも非現実的である。

特に記憶容量の問題は深刻であり（※記憶を利用しない手法を取ると計算量はさらに膨大に増えます）、探索時間以上にそちらの方が問題なのではないかと今は考えています。