将棋の探索空間の広さについて

将棋の探索空間はどれくらいの広さなのでしょうか。

チェスの場合、1手から最終局面までの手順数(探索空間)は10の120乗程度と言われている。将棋の場合は、10の220乗。一度取った相手の駒を使うことができるため、とたんに増えてしまう。囲碁は盤面の広さもあって10の360乗である。

将棋対決・第1回  チェスコンピュータからの応用でもアマ20級

上の記事に見られるような「10の220乗」というのが定説になっています。

ところが、一定以上の棋力を持つプレイヤーに限定する場合、桁違いに狭いというのが私の考えです。10の220乗どころか、10の50乗すらいかないと私は思っています。

やねうら王では探索をしない場合、プロの棋譜との指し手一致率は、以下のようになっています。

Prediction(%) = 43.5828, 64.8331, 75.9408, 82.7774, 87.3075, 90.4403, 92.6531, 94.2629, 95.4584, 96.3543, 97.0501, 97.5901

 

root(探索開始局面=現在の局面)から1手進めて評価値が一番大きくなる局面に行くためのrootでの指し手が、プロの棋譜と一致する確率が43.5828%です。

rootから1手進めて、評価値が2番めに大きくなる局面に行くためのrootでの指し手も加えると、プロの棋譜と一致する確率は64.8331%だというわけです。

12手目まで入れると97.5901%。探索なしで98%近く一致するって凄くないですか?持ち駒があるから(駒を打てるから)指し手の組み合わせはチェスより圧倒的に多いはずの将棋でこれなんです。

当然、ここに探索を加えればさらにプロの棋譜との指し手一致率は上がっていきます。depth = 10(探索深さ10)で探索させたとき、上位5手がプロの棋譜と一致する確率は95%を超えます。

プロの棋譜からポカのような指し手や、終盤でコンピューターが読み切れる局面以降を除けばさらに一致率は上がります。そう考えると将棋は指し手の組み合わせは多いですが、比較的すぐに(20手ぐらい指し手を進めると)駄目になってしまう変化が大変多いゲームで、仮に中盤で200通りの指し手があろうと、その

  • 96%ぐらいの指し手は10手以内に悪くなるような明らかな悪手
  • 1%ぐらいの指し手は10手〜20手ぐらい進めると悪くなるような悪手
  • 1%ぐらいの指し手は20〜30手ぐらい局面を進めると悪くなる悪手
  • 2%ぐらいがほぼ先後互角の形勢の局面にいく指し手(あるいは30手以上進めないと悪くならない悪手)

みたいなバランスではないかと思います。

私の考えでは30手進めて互角の局面に行く指し手は平均的には2つか3つぐらいしかなく、仮に3つだとして120手付近で終局するとしたら、1.79×10^57しかその組み合わせがないことになります。

コンピューターの場合、終盤は40〜60手ぐらい先の勝ちも読み切れますので読みきった時点で終局だと考えていいなら平均的には初手から数えて80手目ぐらいで終局していることになると思います。また、指し手の平均分岐数が3ではなく2だとしたら、2^80 = 1.21×10^24しかないことになります。

「将棋の完全解析をしようと考えたとき、宇宙にある原子の数を超える局面数があるのでそれを保存する記憶媒体は存在せず不可能だ」という意見を耳にしますが、10^24ぐらいなら50年後ぐらいにはなんとかなるかも知れませんね。


将棋の探索空間の広さについて” への2件のコメント

  1. なかなかの考察だと思います
    棋力が高まると選択肢は狭まりそうですね

    ちなみにコメント欄の必須項目からメールアドレスを外してくれると助かります 代わりにスパム対策の認証システムを置いた方がよいかもしれません
    意図的にメールアドレス欄を設けているのであれば、それで大丈夫です

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です