うらおミクロコスモスというのは、1525手詰めとして知られている有名な長編詰将棋である。これが、やねうら王の新しい詰将棋ルーチンで解けるかどうかで言えば解ける。原理的には、メモリと時間が無限にあればどんな問題も解けるのが、この新しい詰将棋ルーチンであるから。ところが、メモリと時間がどれだけ必要かと言うと試したことがないので私は知らない。時間がどれだけかかるかだが、やねうら王の詰将棋ルーチンでは合流を処理しない。合流を処理しない理由は、昨日の記事で詳しく書いたが、実戦詰将棋を検討する上で千日手絡みの問題が発生して、それがとても難しいからである。node(末端局面)で用いるには、合流を処理しても(それに伴う計算時間に見合わないので)しないほうが良いという意味もある。ミクロコスモスでは、おそらく合流しまくっている。どれだけ合流するのかは私は知らないが、最初のほうの指し手で100回ぐらい合流するとしたら、100倍ぐらい局面を調べないと解けないことになる。探索速度がこちらのほうが2倍速いとしても、50倍の時間を要することになる。うら王詰将棋ルーチン使ってみたが、メモリ16GB積んでいてもメモリ容量使い切って、ミクロコスモス(1525手詰め)が解けないのは、ちょっとショック。2020以前実施済みだが、脊尾詰だとほとんどメモリを使わずに1525手詰めが解ける。2020ミクロコスモスは脊尾詰めで188,107,356(およそ2億)局面調べたところで解けるらしい。Memory(メモリ不足)と表示して終了してしまったようである。それで上のツイート主からしてみれば、「16GBも搭載しているPCなのに、何故これでメモリ不足になるのか!脊尾詰めなら解けるのに!脊尾詰めは1997年に発表された20年以上昔のソフトやぞ!」みたいな感じなのであろう。気持ちはわかるのだが...。それでは、やねうら王の詰将棋ルーチンでミクロコスモスを解くのにメモリがどれだけ要するか上の「100倍ぐらい局面を調べないと解けない」に基づき、概算で計算してみよう。うら王の詰将棋ルーチンでは、一度調べた局面を破棄しない。nodeから呼び出す時にはそんなに深くまで調べさせるわけではなくせいぜい300局面ほどしか調べさせないのでガーベジレクトする必要がないからである。気が向いたら実装しようとは思ってはいるが、探索部で用いるのにそれを実装する必要性がないので...。それで1つの局面を調べるとメモリをどれだけ消費するのだろうか。3手の詰将棋100万局において統計をとったところ、一つの局面で、攻め方の平均分岐数(何手指し手があるかその平均)は7.15手、受け方は4.61手であった。念の為5手詰めでも調べたが、それほどかけ離れた数字ではなかった。そこでこの数字をそのまま使う。1局面の情報は何バイトであるかと言うと、まず子ノードの数(その局面の指し手の数)が必要である。「ノード」(Node)というのはグラフ理論の用語。ここでは「局面」のことだと思ってほしい。詰将棋においては最大でも100手ほどらしいのでこれは1バイトに収まる。それから、子ノードへ至る指し手。うら王では指し手は普通、24bit要する。それから、子ノードへのポインタ。その指し手を指した時の次のノード構造体がどれであるかを指し示さないといけない。約42億)を超えるであろうから、8バイトで保持しないといけない。うら王の詰将棋エンジンは、4Gを超えるノード数を扱いたい時は、後者の実装を選択することができる。number:詰みの証明数)は保持している。これはその局面での詰ませやすさ(詰みを証明するのに調べないといけない局面数)、詰みにくさ(不詰を証明するのに調べないといけない局面数)を表現している。これは子ノードのdn,pnを集計したものが親ノードのdn,pnになる。全体のノードの数は4バイトで表現できる値(4G)に収まらないので、この集計する数も4バイトで表現できる値には収まらないことになる。よって、dn,pnも8バイトで保持することになる。28バイト→これを繰り上げて32バイトにして使う。CPUはメモリに対して32バイト単位でアクセスするのが得意なので。