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

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

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

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

さっそく、やねうら王詰将棋ルーチン使ってみたが、メモリ16GB積んでいてもメモリ容量使い切って、ミクロコスモス(1525手詰め)が解けないのは、ちょっとショック。 https://t.co/AMQgjbRdnI pic.twitter.com/g6MADsRMm4

— 肝属兵衛 (@tesso_1970) December 29, 2020

以前実施済みだが、脊尾詰だとほとんどメモリを使わずに1525手詰めが解ける。やねうら王詰将棋ルーチンは、思考を残す事でメモリ食いしちゃうのかな？ pic.twitter.com/uYkjgIYFQo

— 肝属兵衛 (@tesso_1970) December 29, 2020

ミクロコスモスは脊尾詰めで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スレッドでの探索にしては探索速度がすこぶる速いこと、実際の探索部に組み込みやすいこと(スレッドごとに異なる局面を詰探索させることができる)などが今回の詰将棋エンジン(詰将棋ルーチン)の特徴であるので、この詰将棋エンジンにとって、ミクロコスモスみたいな長編は一番苦手なジャンルの問題だと思う。