Bonanzaのnps表記について
■ npsの意味するところ
コンピュータ将棋ソフトによって「nps」(nodes per second)という用語が意味するところはまちまちである。
Bonanza(バージョンは4.1.2で検証)の場合、npsの意味するところは、評価関数を呼び出した回数ではない。
それではnpsは何を意味するもので、npsのうち何%が評価関数を実際に評価する回数なのかを調べていく。
まず、evaluate(評価関数)の実行に要している時間は、プロファイラで調べたところ、CPU時間の70%程度だった。ひとことで言えば結構消費している。
しかし、evaluateは単にstandpatを返すだけのこともあるので、実際に局面の評価を行なった回数とは異なる。
そこで、
1) 探索したnode数
2) 1)のうち、evaluateを呼び出した回数
3) 2)のうち、実際に局面の評価を行なった回数
は、それぞれ別個に考える必要がある。
■ Bonanzaを実際に実行してみて測定する
ソースを見るとnpsは、探索したノード数(ptree->node_searched)を消費時間で割って算出している。(iterate.cの変数dnps)
このノード数が具体的に何を意味するかはあとで詳しく調べるとして、まず、初手98香と指して(定跡を外して)Bonanzaに普通の探索をさせた。
1) node_searched : 579015回
2) evaluate*1 : 1780234回
3) stand_pat*2 : 405814回発生
4) ehash_probe*3 : 578177回発生
5) eval*4 : 796243回
何故、1)のほうが2)より小さいのかは不明。nodeのカウントの仕方が違うのだと思う。[要調査]
言うまでもなく、2) = 3) + 4) + 5) 。
npsの値は、1)を思考時間で割り算して算出されるため、実際にevaluateが呼び出された回数[上記の2) ]の1/3ぐらいしかない。要するに将棋所などで表示されているBonanzaのnps×思考時間の3倍ぐらいevaluateは呼び出されていると解釈して良いのだと思う。
また同時に、1),5)の割合から、npsの表示値より4割増しぐらいの回数だけ、1秒間に局面を評価していると言えると思う。
5)のほうをnpsの計算するときに使っているコンピュータ将棋ソフトもあるから、考え直す必要があるのかも知れない。
■ 1回の局面評価に要する時間を調べる
Core 2 Duo 2.8GHzでは、上の思考をさせたとき、シングルスレッドで110Knps。(ただし、PGOはしていないのでこの値は配布されているBonanzaのバイナリより15%程度遅いと考えて欲しい。) すなわち、この思考に要した時間は、579015/110K = 5.26秒。
プロファイラによるとevaluateが思考時間の70%をしめるので、stand_pat,ehash_probeの時間はおおよそ無視できるとして、これは5)の時間である。すなわち、5.26秒×70% = 3.68秒 かけて、局面を796243回評価できるわけで、1回の局面評価には4.62μs(4.62×10E-6)を要しているという計算になる。
Bonanza 4.1.2の局面評価は、おおよそ1250回ほどループを回り、その1回のループのなかで2回の評価値の入ったテーブルへの参照を行なうので、2500回ほどテーブルへの参照を行なっていることになる。
4.62μsに2500回ということは、1回のテーブル参照は1.85ns(1.85×10E-9)で行なわれているということであり、1/1.85ns = 540M/s である。Core 2 Duo 2.8GHzの5clockに1回ぐらいのペースでテーブル参照が行なえている計算になり、これはL1,L2 cacheにテーブルが入っている可能性が高いためだと思われるが、すこぶる高速にアクセスできていると言えると思う。
■ Bonanzaのnpsの定義をソースから読み解く。
evaluateのなかで、evaluateを呼び出された回数をカウントするためにneval_calledという変数をインクリメントしている。
ptree->neval_called++;
しかし、この変数は、iterate.cのなかで
Out( " n=%" PRIu64 " quies=%u eval=%u rep=%u %u(chk) %u(supe)\n", ptree->node_searched, ptree->nquies_called, ptree->neval_called, ptree->nfour_fold_rep, ptree->nperpetual_check, ptree->nsuperior_rep );
と出力している。しかし、これはnpsの表示とは無縁である。
npsの表示に使っている変数はiterate.cのなかにあるdnpsという変数で、これは
dnps = 1000.0 * (double)ptree->node_searched;
dnps /= (double)( elapsed + 1U );
となっている。すなわち、探索したノード数(node_searched)を今回の思考のために使った時間で割って算出している。
では、node_searchedはどこでインクリメントしているのだろう。
・quiesrch.c(静止探索)のなかで、静止探索1回につき、1回インクリメント。
ptree->node_searched += 1; ptree->nquies_called += 1;
・search.c(探索)のなかでインクリメント。この直後に次のような条件で、evaluateを呼び出している。
ptree->node_searched++;
if ( ply >= PLY_MAX-1 )
{
value = evaluate( ptree, ply, turn );
if ( alpha < value && value < beta ) { pv_close( ptree, ply, no_rep ); }
MOVE_CURR = MOVE_NA;
return value;
}ちなみに、この直後に書かれているplyは探索深さ。PLY_MAXは探索する深さの上限。(shogi.hで、PLY_MAXは48がdefineされている。)
上のソースをざっと見た限りは、npsの計算は確かに探索ノード数っぽい。探索ノード数よりevaluateのほうが呼ばれた回数が多いというのは、要するにevaluateが気軽に呼ばれすぎているということだろう。
どれくらい気軽に呼ばれるかと言うと、
・null-move pruningのため
・futility pruningのため
・LMR風reductionのため (指し手進めた直後)
などである。詳しいことは機を改めて検証する。
■ まとめ
今回はBonanzaのnpsについて簡単に調べた。
・nps計算のもととなる探索ノード数は、評価関数が呼び出された回数ではない。
・nps計算のもととなる探索ノード数は、比較的素直なノード数のカウントと言える。
・探索ノード数より評価関数を呼び出された回数のほうが多い。
・評価関数(evaluate)は気軽に呼ばれすぎ。
・evaluateは、呼ばれたうち2割ぐらいはstand_patでreturnするし、そこで終了しなかった場合でも4割ぐらいはehash_probeでreturnする。だから、実際に局面を評価する回数は、evaluateが呼び出されたうちの45%程度。この回数は探索ノード数より4割ほど多い程度。
