Hi,
This may be a simple question; even a stupid one. In the next version of my engine, I'm going to add more move ordering.
Now that I'm using a transposition table, I'm storing the best move in the hash table, in the same way as Bruce Moreland did on his site way back:
- I store hash table information when eval >= beta:
* depth
* flag BETA
* value of "beta"
* best move up until that point
- I store information just before returning alpha:
* depth
* flag EXACT if alpha was improved (eval > alpha), otherwise store flag ALPHA.
* value of "alpha"
* best move
So, the best move gets stored into the hash table.
When iterative deepening ends a run and then goes into the next one, all the best moves should still be in the hash table, unless they have been overwritten.
Now the question is: Is it still useful to implement "Try best move of the previous iteration first" if you have a hash table; i.e., is there a very large chance that so many best moves are overwritten, that this extra move ordering option is going to provide additional benefit, on top of ordering on the hash move alone?
Best move from previous iteration first: still needed with TT?
Moderators: hgm, Rebel, chrisw
-
- Posts: 2555
- Joined: Fri Nov 26, 2010 2:00 pm
- Location: Czech Republic
- Full name: Martin Sedlak
Re: Best move from previous iteration first: still needed with TT?
well, once you start implementing multi-pv (I'm sure you will as you seem to be a perfectionist), probing TT won't do.
so trying best n pv moves from previous iteration is natural.
typically you order other (non-pv) moves by number of nodes searched, because a move that is harder to refute is more likely to become a new PV move
however, Michael Sherwin proposed something else recently: namely to order the remaining moves by number of total beta cutoffs for side to move,
in fact I even measured some elo gain (3 elo), but only 10k games, there's probably more to it as you can gather more statistics.
so - root move ordering deserves special care
so trying best n pv moves from previous iteration is natural.
typically you order other (non-pv) moves by number of nodes searched, because a move that is harder to refute is more likely to become a new PV move
however, Michael Sherwin proposed something else recently: namely to order the remaining moves by number of total beta cutoffs for side to move,
in fact I even measured some elo gain (3 elo), but only 10k games, there's probably more to it as you can gather more statistics.
so - root move ordering deserves special care
Martin Sedlak