やねうら王詰将棋ルーチンでミクロコスモスは解けますか?

ミクロコスモスというのは、1525手詰めとして知られている有名な長編詰将棋である。これが、やねうら王の新しい詰将棋ルーチンで解けるかどうかで言えば解ける。原理的には、メモリと時間が無限にあればどんな問題も解けるのが、この新しい詰将棋ルーチンであるから。

ところが、メモリと時間がどれだけ必要かと言うと試したことがないので私は知らない。

まず、時間がどれだけかかるかだが、やねうら王の詰将棋ルーチンでは合流を処理しない。合流を処理しない理由は、昨日の記事で詳しく書いたが、実戦詰将棋を検討する上で千日手絡みの問題が発生して、それがとても難しいからである。よほどの長編でない限りはそうそう合流しないので指し将棋の探索のleaf node(末端局面)で用いるには、合流を処理しても(それに伴う計算時間に見合わないので)しないほうが良いという意味もある。

しかし、ミクロコスモスでは、おそらく合流しまくっている。どれだけ合流するのかは私は知らないが、最初のほうの指し手で100回ぐらい合流するとしたら、100倍ぐらい局面を調べないと解けないことになる。探索速度がこちらのほうが2倍速いとしても、50倍の時間を要することになる。

ミクロコスモスは脊尾詰めで188,107,356(およそ2億)局面調べたところで解けるらしい。やねうら王のほうは2億局面ほど調べたところでOut Of Memory(メモリ不足)と表示して終了してしまったようである。

それで上のツイート主からしてみれば、「16GBも搭載しているPCなのに、何故これでメモリ不足になるのか!脊尾詰めなら解けるのに!脊尾詰めは1997年に発表された20年以上昔のソフトやぞ!」みたいな感じなのであろう。まあ、気持ちはわかるのだが…。

それでは、やねうら王の詰将棋ルーチンでミクロコスモスを解くのにメモリがどれだけ要するか上の「100倍ぐらい局面を調べないと解けない」に基づき、概算で計算してみよう。

やねうら王の詰将棋ルーチンでは、一度調べた局面を破棄しない。(と昨日の記事に書いた) これは、ガーベジコレクト(掃除)するのにも相応のコストが必要で、実際の探索部のleaf nodeから呼び出す時にはそんなに深くまで調べさせるわけではなくせいぜい300局面ほどしか調べさせないのでガーベジレクトする必要がないからである。

// 気が向いたら実装しようとは思ってはいるが、探索部で用いるのにそれを実装する必要性がないので…。

それで1つの局面を調べるとメモリをどれだけ消費するのだろうか。

3手の詰将棋100万局において統計をとったところ、一つの局面で、攻め方の平均分岐数(何手指し手があるかその平均)は7.15手、受け方は4.61手であった。念の為5手詰めでも調べたが、それほどかけ離れた数字ではなかった。そこでこの数字をそのまま使う。先後の平均は(7.15 + 4.61) / 2 = 5.88手であるな。

1局面の情報は何バイトであるかと言うと、まず子ノードの数(その局面の指し手の数)が必要である。
// 「ノード」(Node)というのはグラフ理論の用語。ここでは「局面」のことだと思ってほしい。

詰将棋においては最大でも100手ほどらしいのでこれは1バイトに収まる。それから、子ノードへ至る指し手。やねうら王では指し手は普通、24bit要する。つまりは3バイト。

それから、子ノードへのポインタ。その指し手を指した時の次のノード構造体がどれであるかを指し示さないといけない。ミクロコスモスではノード数は4バイトで表現できる値(4G = 約42億)を超えるであろうから、8バイトで保持しないといけない。やねうら王の詰将棋エンジンは、4Gを超えるノード数を扱いたい時は、後者の実装を選択することができる。(SolverTypeで64bitNodeSolverを選択すれば良い)

また、df-pnアルゴリズム(の亜種)である以上、局面のdn(disproof number:不詰の証明数)とpn(proof number:詰みの証明数)は保持している。これはその局面での詰ませやすさ(詰みを証明するのに調べないといけない局面数)、詰みにくさ(不詰を証明するのに調べないといけない局面数)を表現している。これは子ノードのdn,pnを集計したものが親ノードのdn,pnになる。全体のノードの数は4バイトで表現できる値(4G)に収まらないので、この集計する数も4バイトで表現できる値には収まらないことになる。よって、dn,pnも8バイトで保持することになる。

そうすると、1局面が、
64bitNodeSolver : 1 + 3 + 8 + 8×2 = 28バイト→これを繰り上げて32バイトにして使う。CPUはメモリに対して32バイト単位でアクセスするのが得意なので。
32bitNodeSolver : 1 + 3 + 4 + 4×2 = 16バイト。
ということになる。

ミクロコスモスを解くには、64bitNodeSolverが必要なので1局面の構造体が32バイトである。1局面の平均手数は 5.88手だったので、詰将棋で「1局面を調べる」(局面を展開する = ExpandNodeと呼ばれる)という探索行為を行うと、32バイト×5.88手 = 188.16バイトを要することになる。

ミクロコスモスを解くのに仮に「100倍ぐらい局面を調べないと解けない」だとすると、このとき、
188,107,356 × 100倍 × 188.16バイト のメモリが必要となる。

これは、3,539,428,010,496 = およそ3.5TBである。16GBで解けようはずがない。桁が3桁ほど足りてない。私からすると、合流を処理せず、かつ、調べた局面を全部メモリに保持したままですと書いている詰将棋エンジンで、なんでミクロコスモスがたったの16GBのメモリで解けると思ったの?ぐらいの感じではある。

こういう事情を知らない人にとっては、「最新の詰将棋ルーチンだから当然解けるだろ!」ぐらいに期待されていることはわかるし、期待に添えない点に対しては申し訳ないという気持ちもあるのだけども、まあ、上の計算過程から考えて、ガーベジコレクトなしでは16GBでは解けないことは端から自明ではないかということでこの記事を終えたい。

長編が省メモリで効率的に解けるわけではなく、短い詰将棋に関して不詰・詰めを100%間違わずに出力できることや、1スレッドでの探索にしては探索速度がすこぶる速いこと、実際の探索部に組み込みやすいこと(スレッドごとに異なる局面を詰探索させることができる)などが今回の詰将棋エンジン(詰将棋ルーチン)の特徴であるので、この詰将棋エンジンにとって、ミクロコスモスみたいな長編は一番苦手なジャンルの問題だと思う。

やねうら王詰将棋ルーチンでミクロコスモスは解けますか?」への10件のフィードバック

  1. プロ棋士にとって長手数の詰将棋とは51手以上だとどなたかが手の進まない将棋の解説のときに仰ってました。まぁ実戦では出現しない局面ばかりなので長手数の詰将棋は趣味の世界で対局には意味がないとのことです。
    練習は十数手の局面を一瞬で解くようなものをたくさん行うのが重要とどこかの団体の会長さんも仰ってたように思います。アマチュアだと3,5,7手詰めで十分とのことです。

    • 5手、7手と2手長くなるごとにrarity(≒実戦での出現頻度)が1/10ぐらいになるようなので、実戦で51手詰めが出現する確率は天文学的に低いでしょうからまあ通常は起こり得ないのかと…。(N手必死で良ければそれよりはるかに高い出現頻度のようなのですけども)

      • > 5手、7手と2手長くなるごとにrarity(≒実戦での出現頻度)が1/10ぐらいになる

        これは興味深い数字・・・!
        実戦というのは、多くが詰みまで指すAI限定での話でしょうか?

        • はい、詰みまで指すとして、先日のクリスマスプレゼントのコメント欄にあるように、詰みまでの手数が2手増えるごとに生成時間がおよそ10倍になっていたので、まあ、rarityもそんなものかと。

  2. >(スレッドごとに異なる局面を詰探索させることができる)

    なるほど〜
    リーフノードでのマルチスレッドの詰み探索とガベージコレクションの共存は難しそう…

    ということは、背尾詰めはシングルスレッドということでしょうか?

  3. あはは。ししょーがあのツイートを見ていたという方がビックリでした。^^;
    自分も後でリプライしようかと思っていました。

    後、何も知らないでこれを使う方への注意としては「最短詰めの解を求めるものではない」ということも言っておかないとですね。
    「3手で詰むのに5手って返ってくるやん!」と文句を言われても困りますもんね。^^;

  4. やねうら王詰将棋エンジンについて問い合わせです
    PC将棋スレからコピペします

    やねうら王詰将棋エンジンには落胆した 脊尾詰や柿木将棋が1秒以内で
    詰ます問題でも少し詰めにくい問題だと直ぐ詰まないと白旗をあげるようだ 
    例えば下記の詰パラ1月号の表紙の13手詰 (詰パラは藤井2冠の愛読書)
    sfen 8l/7b1/5pnp1/7k1/5+R3/9/9/9/9 b 4SNrb4g2n3l16p 1

やねうらお へ返信する コメントをキャンセル

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