2012-11-30

差分評価できたっぽい。まだ、いろいろと改善できる点はありそう。
局面の評価値ハッシュと反復深化の組み合わせでややこしいことになっていた。

大損するのは All Node のときなので、2手目までにβCutされなければ、親ノードを非差分評価するようにしたら少し速くなった。静止探索は葉の数が少ないから、たぶん大丈夫。

差分計算に変えても実行時間の40%以上が局面評価。プロファイル解析 - スズメレンダラー・クマ将棋の開発日記のbonanza6の解析でも、局面評価関係50%以上を占めているのでこんなもんかな。

  %   cumulative   self              self     total
 time   seconds   seconds    calls  us/call  us/call  name
 31.11     17.16    17.16  3241519     5.29     5.29  Think::EvaluateNoDiff(Tree*)
 12.29     23.94     6.78  5369718     1.26     1.26  Think::EvaluateDiff(Tree*)
  6.67     27.62     3.68 10082210     0.37     1.99  int Think::hQuiescenceSearch<(Player_t)0>(Tree*, int, int, int, int, int, int)
  4.80     30.27     2.65  6196973     0.43     2.94  int Think::hQuiescenceSearch<(Player_t)1>(Tree*, int, int, int, int, int, int)
  4.48     32.74     2.47  5799714     0.43     5.48  int Think::hSearch<(Player_t)0>(Tree*, int, int, int, int, int)
  3.62     34.74     2.00 18314859     0.11     0.11  int Board::hisAttacked<(Player_t)1, (Player_t)0>(int)
  3.37     36.60     1.86  3802422     0.49     6.01  int Think::hSearch<(Player_t)1>(Tree*, int, int, int, int, int)
  3.01     38.26     1.66  2442370     0.68     0.83  Move Board::hMate1PlyMove<(Player_t)1, (Player_t)0>()
  2.42     39.59     1.34 13077431     0.10     0.10  int Board::hisAttacked<(Player_t)0, (Player_t)1>(int)
  2.37     40.90     1.31  3616838     0.36     0.42  Move Board::hMate1PlyMove<(Player_t)0, (Player_t)1>()
  1.95     41.98     1.08 10776565     0.10     0.13  void Board::hMakeMove<(Player_t)1>(Move)
  1.92     43.04     1.06  1439971     0.74     0.74  Move* Board::hGenTacticalMove<(Player_t)1>(Move*)
  1.79     44.02     0.99  4759717     0.21     0.21  Board::isAttackedAll(int, BitBoard&)
  1.41     44.80     0.78 10772358     0.07     0.07  void Board::hUnMakeMove<(Player_t)1>(Move)
  1.20     45.46     0.66  3661284     0.18     0.39  int Think::hSee<(Player_t)1>(Move)
  1.18     46.11     0.65  6817838     0.10     0.10  void Board::hUnMakeMove<(Player_t)0>(Move)
  1.13     46.74     0.63  6822194     0.09     0.12  void Board::hMakeMove<(Player_t)0>(Move)
  1.07     47.33     0.59  1399123     0.42     0.42  Move* Board::hGenTacticalMove<(Player_t)0>(Move*)
  1.03     47.90     0.57  5932759     0.10     0.51  Move Think::hGenNextQui<(Player_t)1>(Tree*, int, int)

先人のありがたいお言葉：

「KPPには、プロファイラによるとCPU時間の70%を要している。make_listは5%なので、これと併せると実に全体の75%を占める」（2009-10-01 - Bonanzaソース完全解析ブログ）
「今の差分計算はkppの二重ループのとこだけ差分化してて、make_listは毎回やっています」（Bonanza Feliz 中途半端解析ブログ: Ａ級リーグ指し手１号）
（Bonasseソース完全解析 diffeval.c について - ながとダイアリー）
「まずは手抜きで打手だけやってみます」（評価関数の差分計算に着手します - 小宮日記）
「npsは55kぐらいの局面が70kぐらい？」（評価関数の差分計算完成 - 小宮日記）
「玉を動かす指し手は全ての指し手の1/8ぐらいだと思うので、平均的には100回*7/8 + 1000回 * 1/8 = 212.5回程度のテーブル参照をしている計算」（週刊ひよこ将棋の計画 - ひよこ将棋、はじめました。）
「全体で３０％くらい速くなった」（KPPの差分評価メモ - スズメレンダラー・クマ将棋の開発日記）
- 図が大変参考になりました。
https://twitter.com/gou_koutaki/statuses/177081877834903552
https://twitter.com/gou_koutaki/status/274297733186191361
https://twitter.com/HiraokaTakuya/status/264309410644492288

sakurapyon’s blog

sakurapyon’s blog

KKP/KPPの差分評価