以前の記事「将棋の局面数 ２：分岐の迷宮」のコメント欄において、Ulyemon様に教えていただいたのですが、「10の220乗」という数は、「将棋の局面数」を表すのではなく、「将棋であり得る棋譜の数」を表しているという説があるようです。確かに局面数ではなくて棋譜数を表しているのだとしたら、合流局面を考慮する必要はありません。しかし、本当に将棋の棋譜数は「10の220乗」なのでしょうか？ 今回は、将棋の棋譜数について考えてみたいと思います。
本題に入る前に、Ulyemon様にご紹介いただいたWikipediaの「Game complexity」の項目に記してあることについて簡単に紹介します。
「ゲームの複雑性」を測る指標には「state-space complexity（状態空間複雑性）」「game-tree complexity（ゲーム木複雑性）」等があります。前者は、初期局面から到達可能な局面の数（実現可能局面数）のことです。後者は、完全解析で先手勝ち／後手勝ち／引き分けを決める際に、枝狩りや合流局面を考慮せずに全幅でミニマックス探索をする時の終端局面（leaf node）の数のことであり、要するに棋譜数のことです（調べると、棋譜数のことだと明確に示している文章もあるのですが、Wikipediaの書き方だと曖昧で、もしかすると一般的な定義が確定していないのかもしれません）。これらは、あくまでも数学的な定義であり、数理的に解くこと（完全解析等）を考えない場合には意味のない数字になるだろうということは以前の記事に記した通りです。
さらに、上述のWikipediaの「game-tree complexity」の小項目には、一部のゲームに適用できる妥当な下限値の見積もり方法として、平均分岐数の平均手数乗（「10の220乗」の算出式）が書かれています。つまり、「10の220乗」というのは、棋譜数の見積もりではなくて、棋譜数の下限値の見積もりであったというわけです。これなら筆者も納得できます。
結局のところ、「10の220乗」というのは元々は「棋譜数の下限値」の見積もりであったものが、いつの間にか「局面数」や「棋譜数」の見積もりと勘違いされて世に広まってしまったということなのでしょう。
さて、本題の将棋の棋譜数の見積もりに戻ります。
まずは、感覚をつかむために、最大手数を256手に限定した場合（256手ルール）で考えてみましょう。
基本的には各手数ごとに局面数は平均分岐数のべき乗で増えていきます。平均分岐数は80だとします（参照：「ゲームとしての将棋のいくつかの性質について」）。
ただし、各手数ごとに終局する棋譜が出てきますので、その分だけ局面数は減り、棋譜数が増えることになります。最大手数に到達したら、全てが終局となって、その時の局面数は棋譜数に加算され、残った局面数はゼロになります。
各手数における終了／未終了棋譜の割合は、棋士棋譜集（2015年11月版）における手数分布から算出します。手数分布は「手数分布はガンマ分布で近似できるか？」の記事にあるものと同じものです。
計算された未終了棋譜の割合を以下に図示します。手数の大きいところでデータにばらつきがありますが、後に示すように、これから見せる結果には大きな影響はありません。
さて、計算結果は以下のようになります。黒点がその手数までの棋譜数であり、青点がその手数における局面数です。縦軸は、常用対数になっていますので、10の何乗であるかを示しています。
平均手数である116手目を見ると、その手数の局面数は約10の220乗になっており、これが棋譜数「10の220乗」説の数字に対応しているものと思われます。しかしながら、これはあくまでも下限値であり、棋譜数はその後もべき乗的に増えていって、最終的な棋譜数は約10の483乗に達します。
以上の計算を、未終了棋譜割合を定数P（ただし、最大手数でのみ0とする）に簡単化した上で、最大手数をnに一般化してみましょう。
平均分岐数をBとすると、棋譜数Kは\[K = B^{n} P^{n - 1} + (1 - P) B \frac{(B P)^{n - 1} - 1}{B P - 1}\]となります。さらに、\[n \gg 1,~~ B P \gg 1,~~ P \sim 1\]の時、棋譜数は\[K \approx B^{n} P^{n - 1} \approx (B P)^{n}\]となり、最後の局面数で近似できることになります。実際に、n = 256、B = 80、P = 0.97（平均手数における未終了棋譜割合）とすると、約10の483乗となって、上記の結果と一致します。
棋譜数の常用対数を取ると、\[\log_{10}{K} \approx n \log_{10}{(B P)} = A~ n\]となるため、棋譜数が10の何乗であるかは最大手数nに比例しています。ここで、平均分岐数Bと平均未終了棋譜割合Pの値については様々に議論の余地があるものと思われますが、それは基本的に比例係数Aの値の集約されることになります。Pが1に近いことを鑑みると、比例係数Aの値は1.8～2.0程度であると推測できます。
以上のことから、最大手数が分かれば、棋譜数が見積もれることが分かりました。
さて、将棋の最大手数はどれくらいなのでしょうか？
勝負としての将棋であるのならば、自然と決着の方に進むものなのですが、ここで考えているのは対局者が互いに協力して最大手数を目指した場合にどれくらいの手数まで進めるのかということです。
将棋には千日手があり、同一局面は3回までしか許されませんので、手数は有限です。しかし、他に手数を制限するルール（256手ルール等）がないとすると、将棋の局面数の3倍、すなわち10の69乗程度までは手数を伸ばせる余地があります。
仮に最大手数を10の69乗とすると、棋譜数は10の“10の69乗”乗程度ということになります。文字だと分かりにくいですが、数式表記だと、\[10^{10^{69}}\]であり、矢印表記を使うと、10↑10↑69ということです。普通に紙に書こうとすると、ゼロが10の69乗、すなわち銀河の原子数分だけ必要になりますので、まあ無理でしょう。
ちなみに、局面数を最大に活かす手数であるのならば、局面の手数配置の数によって上限を見積もることもできます。この場合は、10の69乗の階乗ですので、スターリングの公式により、約10の“10の71乗”乗（10↑10↑71）程度ということになり、上記の推測と矛盾しない結果になります。
以上、今回は将棋の棋譜数について考えました。将棋の棋譜数の常用対数は最大手数に比例しており、256手ルールの場合には棋譜数は約10の483乗、特に上限手数の縛りがない場合には、最大で10の“10の69乗”乗程度まで増える可能性があることが分かりました。
-------------------
追記（2016年4月2日）
「将棋の局面数 ２：分岐の迷宮」の記事のコメント欄において、mak様が指摘されたことを少し敷衍して記します。
局面の合流を無視する時、t手目の次の局面数n(t + 1)は、t手目の全て局面からの分岐数の和になりますので、\[n(t + 1) = \sum_{k(t) = 1}^{n(t)} b(t, k(t))\]と書き表せます。ここで、k(t)は手数tにおける局面を指定する数（1からn(t)まで）、b(t, k(t))はk(t)で指定される局面の合法手の数です。
この式は、\[n(t + 1) = n(t) M(t) = \prod_{s = 0}^{t} M(s)\]のように書き直せます。ここで、\[M(t) = \sum_{k(t) = 1}^{n(t)} \frac{b(t, k(t))}{n(t)}\]は、その手数における平均分岐数を表しています。
「相加平均は相乗平均以上である」という数学の定理を使うと、\[n(t + 1) = \prod_{s = 0}^{t} M(s) \leq [ \sum_{s = 0}^{t} \frac{M(s)}{t + 1} ]^{(t + 1)} = [ L(t) ]^{(t + 1)}\]となります。ここで、L(t)はt手までの各手数における平均分岐数の平均であり、全局面の分岐数の平均である本文中のBとは別のものなのですが、tが十分に大きければ、\[L(t) \approx B P\]となると予想されます。
つまり、本文中の見積もりは少し大き目に出ている可能性があるということです。
ただし、式中の全てのMが、Lや(B P)に近い値であるのならば、上記の不等式は等号で近似することができます。各手数には膨大な数の局面が存在しているため、序盤を除けば、ほぼ等号成立に近い状態になっている可能性が高いと思われます。
また、未終了棋譜割合についても、序盤を除けば、本来はほとんど手数には依らないと考えられますので、棋譜データを使うよりも、定数Pでおいた見積もりの方がいいのかもしれません。
