History Heuristic - a new idea on an old idea?

Code, algorithms, languages, construction...
Post Reply
thevinenator
Posts: 68
Joined: Tue Jun 02, 2015 11:02 pm
Real Name: Vince

History Heuristic - a new idea on an old idea?

Post by thevinenator » Thu Nov 19, 2015 10:27 pm

Early on in the coding of my chess program, i implemented the HH code...

Code: Select all

   if ( score >= beta ) { // cutoff
      if ( isNonCapture (move) )
         history[side2move][move.from][move.to] += depth*depth; // 1 << depth
... 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?
"An Engine's strength flows from the Search. But beware, pruning, extensions, reductions; the dark side of the Search are they. Once you start down the dark path, it will dominate and consume you, as it has to so many developers before.” -- Yoda

hyatt
Posts: 1242
Joined: Thu Jun 10, 2010 2:13 am
Real Name: Bob Hyatt (Robert M. Hyatt)
Location: University of Alabama at Birmingham
Contact:

Re: History Heuristic - a new idea on an old idea?

Post by hyatt » Fri Nov 20, 2015 11:08 pm

I have always done it that way. If value > alpha, I update history counter for the new best move, and if value >= beta, I reduce the counters for all the moves that were tried and did not fail high...

H.G.Muller
Posts: 190
Joined: Sun Jul 14, 2013 10:00 am
Real Name: H.G. Muller

Re: History Heuristic - a new idea on an old idea?

Post by H.G.Muller » Sun Nov 22, 2015 10:07 am

Most engines use PVS, and in PVS almost all nodes are searched with a null window, where improving alpha automaticially implies a cutoff. About 0% of the nodes in a tree are PV nodes with an open window. Awarding a few extra history points in those nodes has no effect.

The crux about history is that it is one of the few non-local move-ordering techniques. Killers are purely local, based on the result in a sibbling node. That makes their success rate quite high, but it limits their scope. History allows the search to learn from pars in the tree that are quite distant. It picks out moves that globally are a good idea irrespective of the details of the position.

Post Reply