edaxの置換表は1エントリ192バイト 24バイト(192bit)で、パラメータh(ただし )を受け取って、2.25 個のエントリをメモリに確保します。(2.25 2.0625と中途半端な値なのは、3種類のテーブルを使い分けているためです)デフォルトはh=21です。最小値のh=10にした場合、大きさは単純計算で約443 51KBになります。この大きさでは探索がめちゃくちゃ非効率になるんだろうなと思いこんでいましたが、実際試したところそうでもありませんでした。
以下は実験結果です。
- i5-7400
- 1年前くらいにビルドしたedax
- fforum-60-79完全読み
- h=10とh=21を同時にではなく片方ずつ走らせた
h=10の場合 ( -n 1 l 60 h 10 -solve fforum-60-79.obf )
# | depth|score| time | nodes (N) | N/s | principal variation ---+------+-----+--------------+-------------+----------+--------------------- 1| 24 +20 0:02.123 72731214 34258697 c2 B4 a4 B5 b8 B6 b3 2| 25 -14 0:03.991 136638662 34236698 G1 h6 H5 h3 B7 a8 D7 3| 27 +28 1:06.431 2337281357 35183594 E8 h5 H2 f7 A3 a2 D7 4| 27 -02 0:33.084 1400723145 42338385 F2 f1 C8 b8 D2 d1 G7 5| 27 +20 2:16.815 5159947303 37714778 B4 h6 H7 f7 B5 a6 6| 28 +10 4:14.072 9680960313 38103216 g1 H1 h2 H3 h4 H7 a5 7| 28 +30 3:01.408 6584206879 36295019 h3 E1 g4 G5 f1 8| 28 +22 4:39.972 10119623233 36145126 h3 E8 a6 F7 b6 A4 c7 9| 30 +28 21:18.760 41480608536 32438150 e8 D8 a5 H5 a4 A6 b3 10| 30 +00 7:43.130 16761152666 36191032 h3 H5 a2 A3 a5 A1 g2 11| 30 -24 1:17.396 2497576443 32270097 e3 F3 e8 G8 g3 G4 h4 12| 31 +20 9:23.139 17123691973 30407576 D2 a5 E2 h4 B3 13| 31 +24 53:33.858 106508195403 33140293 E1 f1 H5 h3 G1 f7 14| 31 -04 20:59.928 45885561042 36419193 G4 h6 E8 h5 G7 h8 G3 15| 31 -30 1:36:56.862 183881154781 31611744 F1 d1 C1 d8 B6 e8 C8 16| 32 +14 3:22:16.458 452762950808 37306020 d2 H8 d1 C1 c2 17| 32 +32 7:58:23.752 922599899127 32142136 a3 A2 b3 18| 34 +34 1:17:03.995 148981322525 32219179 b7 A5 a7 19| 34 +08 1:08:25.921 139248536500 33914081 f1 G1 a2 F3 20| 36 +64 0:06.199 187928918 30316005 d7 H2 h8 G1 g8 G7 d8 ---+------+-----+--------------+-------------+----------+--------------------- fforum-60-79.obf: 2113410690828 nodes in 17:33:27.294 (33436184 nodes/s).
h=21の場合 ( -n 1 l 60 h 21 -solve fforum-60-79.obf )
# | depth|score| time | nodes (N) | N/s | principal variation ---+------+-----+--------------+-------------+----------+--------------------- 1| 24 +20 0:01.625 48623514 29922162 c2 B4 a4 B5 b8 B6 b3 2| 25 -14 0:03.227 96479978 29897731 G1 h6 H5 h3 B7 a8 D7 3| 27 +28 0:37.071 1087819867 29344228 E8 h5 H2 f7 A3 a2 D7 4| 27 -02 0:25.841 977664575 37833852 F2 f1 C8 b8 D2 h3 B7 5| 27 +20 1:13.044 2382018714 32610738 B4 h6 H7 f7 B5 a5 D2 6| 28 +10 5:07.360 10236493800 33304574 g1 G7 c8 H1 h2 D8 a5 7| 28 +30 1:27.713 2737168216 31205958 h3 E1 g4 G5 f1 G1 f2 8| 28 +22 3:05.550 6084624924 32792374 h3 F8 a6 A5 f7 G6 b6 9| 30 +28 16:07.081 25880362470 26761318 e8 D8 a5 H5 a4 H6 b3 10| 30 +00 2:36.389 4780894606 30570530 h3 H5 a2 A3 a5 A1 g2 11| 30 -24 0:46.389 1237608124 26678914 e3 F3 e8 G8 g2 F2 g4 12| 31 +20 4:20.382 6822196039 26200721 D2 a5 E2 h4 B3 b6 C8 13| 31 +24 32:29.660 52344624795 26848079 E1 f1 H5 h3 G1 f7 H2 14| 31 -04 5:51.877 11251037955 31974349 G4 h6 E8 h5 G7 h8 G3 15| 31 -30 48:27.632 73904989901 25417587 F1 d1 C1 d8 B6 e8 C8 16| 32 +14 59:05.968 120241764530 33909433 d2 D1 h5 H8 h2 B5 d8 17| 32 +32 1:58:09.752 179160564075 25270357 a3 A2 b3 B6 e1 H4 e2 18| 34 +34 55:48.837 87152722897 26024773 b7 A5 a7 E8 e7 A8 b2 19| 34 +08 37:16.241 64330548902 28767270 f1 G1 a2 F3 c1 F5 a7 20| 36 +64 0:01.345 29085426 21624852 d7 D8 h8 H4 g7 F2 g8 ---+------+-----+--------------+-------------+----------+--------------------- fforum-60-79.obf: 650787293308 nodes in 6:33:02.984 (27595630 nodes/s).
h=10だとnodes(読み切るまでに探索した局面の数)は2倍~4倍とかになっていますが、N/s(1秒間あたりの探索局面数)が数割増えています。置換表全体がキャッシュに乗りうるので妥当でしょう。
評価関数のパラメータを小さくする方法
edaxの評価関数自体の説明はこれとかが詳しいです。
もしオセロの初心者がEdaxの評価関数を読んだら - Qiita
評価関数のパラメータは226315*61*2要素のint16_t型配列に格納されていて、そのままだと約56MBです。最後の"*2"は黒側と白側のプレイヤーから見た場合ごとの値でして、符号が反転されてるだけみたいな感じなので、省略しようと思えば等価な結果を維持しつつ省略できます。2番目の"*61"は空白マスの数(=ゲームの進行度)ごとに異なるパラメータにしてあるものです。近い進行度のパラメータは平均してしまえばパラメータ数を減らせます(が、元の評価関数と等価ではなくなります)。
パラメータの最小値と最大値はそれぞれ[-2736, 2613]です。
全パラメータ値を2べき数になるように丸めて、かつ絶対値32未満の値は全部ゼロに丸めるとかしても、完全読みまでの探索局面数はほぼ変わりませんでした。以下は実験結果です。edaxを私が適当にいじったコードにfforum40-59を途中まで解かせたものです。
h=10, パラメータに手を加えない場合
depth|score| time | nodes (N) | N/s | principal variation ------+-----+--------------+-------------+----------+--------------------- 20 +38 00:00.466 12156948 26087871 a2 B1 c1 PS b6 C7 a7 22 0 00:01.101 31135531 28279319 h4 A3 a2 G6 g5 H5 f8 22 +06 00:01.399 38898038 27804172 g2 H1 c2 G1 f1 D2 23 -12 00:04.035 103307640 25602884 g3 H6 h5 C7 g7 H8 23 -14 00:01.272 30148768 23701861 b8 G5 d2 A3 b7 A8 a7 24 +06 00:15.954 460326682 28853371 b2 C1 g5 H4 h6 G4 b1 24 -08 00:03.147 89810965 28538597 b3 C1 b1 A3 b2 H3 a5 25 +04 00:00.998 28776680 28834348 g2 B8 b7 A2 a5 B2 g3 25 +28 00:08.715 212344400 24365393 f6 G5 g3 F2 h4 H5 h3 26 +16 00:18.538 494738501 26687803 e1 H4 g6 H6 h5 G4 b2
h=10, 最近傍2べき数へ丸めた場合
depth|score| time | nodes (N) | N/s | principal variation ------+-----+--------------+-------------+----------+--------------------- 20 +38 00:00.427 11913534 27900548 a2 B1 c1 PS b6 C7 a7 22 0 00:01.164 34469110 29612637 h4 A3 a2 G6 g5 H5 f8 22 +06 00:01.320 39203367 29699520 g2 H1 c2 G1 f1 D2 23 -12 00:04.159 103926798 24988410 g3 H6 h5 C7 g7 H8 23 -14 00:01.492 32933003 22073058 b8 G5 d2 A3 b7 A8 a7 24 +06 00:16.458 469465971 28525092 b2 C1 g5 H6 g4 H3 b1 24 -08 00:03.420 96862525 28322375 b3 C1 b1 A3 b7 G7 a5 25 +04 00:01.289 39126801 30354384 g2 B8 b7 A2 a5 B2 g3 25 +28 00:08.912 217675881 24425031 f6 G5 g3 F2 h4 H5 h3 26 +16 00:19.661 528606175 26886026 e1 H4 g6 H6 h5 G4 b2
h=10, 最近傍2べき数へ丸め、絶対値32未満の値は全てゼロにした場合
depth|score| time | nodes (N) | N/s | principal variation ------+-----+--------------+-------------+----------+--------------------- 20 +38 00:00.385 11739796 30492976 a2 B1 c1 PS b6 C7 a7 22 0 00:01.034 33581599 32477368 h4 A3 a2 G6 g5 H5 f8 22 +06 00:01.199 37593608 31354135 g2 H1 c2 G1 f1 D2 23 -12 00:01.540 40451669 26267317 c7 H4 h5 B8 b7 A8 23 -14 00:01.816 44839684 24691455 b8 G5 d2 A3 b7 A8 a7 24 +06 00:15.279 453722125 29695799 b2 C1 g5 H6 g4 H3 b1 24 -08 00:03.494 106354476 30439174 b3 C1 b1 A3 b2 H3 a5 25 +04 00:01.054 33844793 32110809 g2 B8 b7 A2 a5 B2 g3 25 +28 00:08.460 226893910 26819611 f6 G5 g3 F2 h4 H5 h3 26 +16 00:15.944 455651690 28578254 e1 H4 g6 H6 h5 G4 b2
h=10, 最近傍2べき数へ丸め、絶対値32未満の値は全てゼロにして、空きマス数4つごとに区切って平均化した場合
depth|score| time | nodes (N) | N/s | principal variation ------+-----+--------------+-------------+----------+--------------------- 20 +38 00:00.413 12939393 31330249 a2 B1 c1 PS b6 C7 a7 22 0 00:01.004 32424064 32294884 h4 A3 a2 G6 g5 G7 f8 22 +06 00:01.209 38093236 31508052 g2 H1 c2 G1 f1 D2 23 -12 00:03.830 104595798 27309607 g3 H6 h5 C7 g7 H8 23 -14 00:01.355 34276650 25296420 b8 G5 d2 A3 b7 A8 a7 24 +06 00:17.429 506933268 29085619 b2 C1 g5 H4 h6 G4 24 -08 00:03.711 109704623 29562011 b3 C1 b1 A3 b7 G7 a5 25 +04 00:01.214 39935299 32895633 g2 B8 b7 A2 a5 B2 g3 25 +28 00:09.355 243263550 26003586 f6 G5 g3 F2 h4 H5 h3 26 +16 00:16.862 467434470 27721176 e1 H4 g6 G4 h5 H6 b2
32~2048の2べき数は7通りなので、符号付きでも4bitで表現できます。頑張れば評価関数と置換表を全てキャッシュに収められるかもしれません。