AdamStelmaszczyk / gtsa / 359 / 1
88%
master: 88%

DEFAULT BRANCH: master
Ran
Files 8
Run time 0s
Badge
Embed ▾
README BADGES
x

If you need to use a raster PNG badge, change the '.svg' to '.png' in the link

Markdown

Textile

RDoc

HTML

Rst
coverage: 89.964% (-0.1%) from 90.071%
359.1

push

travis-ci

AdamStelmaszczyk 
Remove history heuristic

On Isola, 10 seconds to get a move from initial state:

With history heuristic:

tests/play_isola.o
goodness: 111 time: 0.00s move: 3, 6, 3, 5, 2, 1 nodes: 21 leafs: 20 beta_cuts: 0 cutBF: -nan tt_hits: 0 tt_exacts: 0 tt_cuts: 0 tt_firsts: 0 tt_size: 1 ht_size: 235 max_depth: 1
goodness: -38 time: 0.00s move: 3, 6, 3, 5, 2, 0 nodes: 99 leafs: 77 beta_cuts: 18 cutBF: 2.06 tt_hits: 1 tt_exacts: 1 tt_cuts: 0 tt_firsts: 0 tt_size: 21 ht_size: 475 max_depth: 2
goodness: 92 time: 0.02s move: 3, 6, 3, 5, 2, 0 nodes: 930 leafs: 827 beta_cuts: 44 cutBF: 2.82 tt_hits: 6 tt_exacts: 6 tt_cuts: 0 tt_firsts: 12 tt_size: 96 ht_size: 1787 max_depth: 3
goodness: -9 time: 0.15s move: 3, 6, 3, 5, 3, 1 nodes: 5261 leafs: 4101 beta_cuts: 673 cutBF: 2.03 tt_hits: 269 tt_exacts: 66 tt_cuts: 197 tt_firsts: 28 tt_size: 896 ht_size: 3238 max_depth: 4
goodness: 49 time: 0.89s move: 3, 6, 4, 5, 3, 1 nodes: 38145 leafs: 31664 beta_cuts: 3246 cutBF: 3.53 tt_hits: 1529 tt_exacts: 451 tt_cuts: 978 tt_firsts: 449 tt_size: 5036 ht_size: 5554 max_depth: 5
goodness: -18 time: 4.99s move: 3, 6, 4, 5, 3, 1 nodes: 195710 leafs: 147367 beta_cuts: 24413 cutBF: 3.30 tt_hits: 17356 tt_exacts: 2124 tt_cuts: 14411 tt_firsts: 1270 tt_size: 32650 ht_size: 7745 max_depth: 6

WIthout:

goodness: 111 time: 0.00s move: 3, 6, 3, 5, 2, 1 nodes: 21 leafs: 20 beta_cuts: 0 cutBF: -nan tt_hits: 0 tt_exacts: 0 tt_cuts: 0 tt_firsts: 0 tt_size: 1 max_depth: 1
goodness: -39 time: 0.00s move: 3, 6, 3, 5, 2, 1 nodes: 97 leafs: 75 beta_cuts: 18 cutBF: 1.94 tt_hits: 1 tt_exacts: 1 tt_cuts: 0 tt_firsts: 0 tt_size: 21 max_depth: 2
goodness: 91 time: 0.01s move: 3, 6, 2, 5, 3, 1 nodes: 1303 leafs: 1144 beta_cuts: 95 cutBF: 4.00 tt_hits: 12 tt_exacts: 12 tt_cuts: 0 tt_firsts: 7 tt_size: 146 max_depth: 3
goodness: -18 time: 0.03s move: 3, 6, 4, 5, 3, 1 nodes: 6805 leafs: 5467 beta_cuts: 774 cutBF: 3.31 tt_hits: 342 tt_exacts: 82 tt_cuts: 238 tt_firsts: 39 tt_size: 1020 max_depth: 4
goodness: 50 time: 0.20s move: 3, 6, 4, 5, 3, 1 nodes: 59228 leafs: 48333 beta_cuts: 5058 cutBF: 4.58 tt_hits: 3620 tt_exacts: 734 tt_cuts: 2732 tt_firsts: 638 tt_size: 7035 max_depth: 5
goodness: -19 time: 0.92s move: 3, 6, 2, 5, 3, 1 nodes: 251047 leafs: 188074 beta_cuts: 30534 cutBF: 3.62 tt_hits: 24609 tt_exacts: 3816 tt_cuts: 19717 tt_firsts: 2208 tt_size: 39962 max_depth: 6
goodness: 49 time: 6.58s move: 3, 6, 3, 5, 3, 1 nodes: 2262853 leafs: 1758500 beta_cuts: 193642 cutBF: 5.41 tt_hits: 246225 tt_exacts: 29470 tt_cuts: 196674 tt_firsts: 27486 tt_size: 245310 max_depth: 7

Depth 7, not 6. Depth 6 reached in 0.92s not 4.99s. Sorting is a slow operation.

CutBF sligtly worse without HH, however on the depth 6, the difference is not huge, 3.30 with HH vs 3.62.

HH might be worth its cost (sorting), but perhaps in particular games and with longer time limit.

On https://chessprogramming.wikispaces.com/History+Heuristic there is a remark:

Random Noise?

However, all of those statements were made at the time when typical search depth was much lower than today. Nowadays some authors say that given enough search depth, history heuristic produces just a random noise [5] , whereas Ed Schröder, advocated not taking into account the cutoffs from the last couple of plies.

753 of 837 relevant lines covered (89.96%)

1506604.34 hits per line

Source Files on job 359.1