History Heuristic - a new idea on an old idea?
Posted: Thu Nov 19, 2015 10:27 pm
Early on in the coding of my chess program, i implemented the HH code...
... right off of the CPW website but eventually replaced it with a 2 move killer list which tested to be more efficient. I set the HH code aside thinking I wouldn't need it again.
Recently I reviewed the youtube video series "Programming a chess engine in C" (https://youtu.be/bGAfaepBco4?list=PLZ1Q ... tZHVbT-2hg) and the author of that series used the HH whenever Alpha was improved. Same basic code, different place in the search structure. I thought I had used the HH incorrectly the first time but it seemed odd to me since I only recall seeing HH in the context of tracking cutoff candidates. But hey, something else to try so I added to my code. The code now has 2-move killers for beta cutoffs and the HH code for alpha improvements.
Slight digression to make a point:
In my code, I don't presort the generated moves, but assign a score and a score type to each them as they are added to the move list. When it comes time to make a move, the move list is scanned and the next best candidate is selected. It is then marked so that it won't be selected again. This is faster than ordering ALL the moves up front since in practice we are hoping that we won't have to scan through more than a few moves before a cutoff.
when it comes time to make the move the moves are selected in the following order:
if there is a hash move, find it in the move list and mark it as a made move and make the move. keep in mind this move might not otherwise be the best move if it wasn't in the hash. the rest of the moves are selected in this order:
MVV-LVA captures
is the move one of the two killers
the move with the best HH score
and finally, the move with the best board square score. (hopefully we don't need to get this far)
...un-digress
it turns out that using the HH for alpha improvements actually helps the search a LOT.
The only reason I can think of is, that if the killer moves don't produce a cutoff, and since the HH scores moves that are better than nothing but not the best (that gets stored in the hash with an exact score), they are better candidates to try since cream rises to the top, so to speak.
I did some additional internet searching but didn't find anything definitive regarding keeping track of moves that improve alpha. I haven't yet contacted the author of the video series to find out where he got the idea, but it definitely appears to work in my implementation.
Humility check: Is this idea called something else and I just missed finding it?
Does/has anybody else tried this?
Code: Select all
if ( score >= beta ) { // cutoff
if ( isNonCapture (move) )
history[side2move][move.from][move.to] += depth*depth; // 1 << depthRecently I reviewed the youtube video series "Programming a chess engine in C" (https://youtu.be/bGAfaepBco4?list=PLZ1Q ... tZHVbT-2hg) and the author of that series used the HH whenever Alpha was improved. Same basic code, different place in the search structure. I thought I had used the HH incorrectly the first time but it seemed odd to me since I only recall seeing HH in the context of tracking cutoff candidates. But hey, something else to try so I added to my code. The code now has 2-move killers for beta cutoffs and the HH code for alpha improvements.
Slight digression to make a point:
In my code, I don't presort the generated moves, but assign a score and a score type to each them as they are added to the move list. When it comes time to make a move, the move list is scanned and the next best candidate is selected. It is then marked so that it won't be selected again. This is faster than ordering ALL the moves up front since in practice we are hoping that we won't have to scan through more than a few moves before a cutoff.
when it comes time to make the move the moves are selected in the following order:
if there is a hash move, find it in the move list and mark it as a made move and make the move. keep in mind this move might not otherwise be the best move if it wasn't in the hash. the rest of the moves are selected in this order:
MVV-LVA captures
is the move one of the two killers
the move with the best HH score
and finally, the move with the best board square score. (hopefully we don't need to get this far)
...un-digress
it turns out that using the HH for alpha improvements actually helps the search a LOT.
The only reason I can think of is, that if the killer moves don't produce a cutoff, and since the HH scores moves that are better than nothing but not the best (that gets stored in the hash with an exact score), they are better candidates to try since cream rises to the top, so to speak.
I did some additional internet searching but didn't find anything definitive regarding keeping track of moves that improve alpha. I haven't yet contacted the author of the video series to find out where he got the idea, but it definitely appears to work in my implementation.
Humility check: Is this idea called something else and I just missed finding it?
Does/has anybody else tried this?