History Heuristic experiments
Posted: 21 May 2006, 19:22Hi there 
,
I wanted to report my experiments since a long time, but never found time since today ;=) Maybe someone will find it interesting though the conditions are very special, and there is a possibility
that my tests have already been reported by someone else in the past:
- my engine (Milady) has just iterative deepening, alpha beta with pvs, qsearch, no transposition tables, no killertables (removed due to efficiency of history heuristic alone)
-it has no extension, no reduction (i.e no nullmove)
So it is very weak.
But I have done some experiments on history heuristic, let me try to describe it:
- I implemented 2 tables (64,64,17) of integers. the first 64 is for the from_square, the second is for the to_square, the 17 is for the maximum depth in alpha_beta (of course to adjust depending on the engine)
- during alpha-beta search, I'm doing the following
HHs(from,to,depth)+=Value
HHn(from,to,depth)+=1
each time Value>best_score andalso each time best_score>=Beta
- this table is then used for move ordering, just using
sort(move)+=HHs(from,to,depth)\HHn(from,to,depth), and only in
alpha_beta move generation
- this way I just add the mean score obtained so far inside the move ordering
- I have tried lot of other combinations, like avoiding captures, trying to add a constant value in case of beta cut-off, trying to add
a 2^(distance to horizon), trying to call HHs only in case of beta cut-off, or trying to call HHs even if the move is bad (why not to try to remember it as well ?), but nothing worked as well as my method
Hope you found something interesting here, any question/comment welcomed,
Yves
,
I wanted to report my experiments since a long time, but never found time since today ;=) Maybe someone will find it interesting though the conditions are very special, and there is a possibility
that my tests have already been reported by someone else in the past:
- my engine (Milady) has just iterative deepening, alpha beta with pvs, qsearch, no transposition tables, no killertables (removed due to efficiency of history heuristic alone)
-it has no extension, no reduction (i.e no nullmove)
So it is very weak.
But I have done some experiments on history heuristic, let me try to describe it:
- I implemented 2 tables (64,64,17) of integers. the first 64 is for the from_square, the second is for the to_square, the 17 is for the maximum depth in alpha_beta (of course to adjust depending on the engine)
- during alpha-beta search, I'm doing the following
HHs(from,to,depth)+=Value
HHn(from,to,depth)+=1
each time Value>best_score andalso each time best_score>=Beta
- this table is then used for move ordering, just using
sort(move)+=HHs(from,to,depth)\HHn(from,to,depth), and only in
alpha_beta move generation
- this way I just add the mean score obtained so far inside the move ordering
- I have tried lot of other combinations, like avoiding captures, trying to add a constant value in case of beta cut-off, trying to add
a 2^(distance to horizon), trying to call HHs only in case of beta cut-off, or trying to call HHs even if the move is bad (why not to try to remember it as well ?), but nothing worked as well as my method
Hope you found something interesting here, any question/comment welcomed,
Yves