How effective is move ordering from TT?

[hgm]

This depends on the size of your TT, and the replacement algorithm. For a heavily overloaded TT, the entries close to he leaves could have been overwritten.

[tpetzke]

I previously used the mate killer and 2 (non mate) killer-slots, and concluded with extensive testing that the mate killer was useless (if not harmful) and so was the second killer

This is probably a conclusion from testing a lot of games at very fast time controls. The deeper you search the less useful history becomes and it is much less work to maintain two killer slots than a history table with all that scaling and aging.

We are talking about a tiny percentage of nodes where either technique has any effect so the less work you spend here the better.

Thomas...

[asanjuan]

the killer move heuristic isn't very useful, it only gives a small improvement over a proper implementation of History ordering. History and Killer are a bit redundant in a way, so if you have to choose one or the other it should be History (much more general and scalable)

really???
Then your tests might have someting wrong...
or you have tried something different to History heuristic, but you call it history.
I have rebuilt entirely my engine and i focused in good move ordering from the start. I can say that the killer heuristic is too much better than history by a big margin.
You can't start with history without having killers first.

[diep]

Currently my move ordering is:
PV move.
LVA/MVA.

With no pruning techniques except of course for Alpha/Beta...my engine can complete depth 8 in around 15s.

I am wondering what improvement I can expect if I added TT Hash move.
PV Move
TT Hash
LVA/MVA

Here is my engine (JAVA Applet)

www.mytopcoder.com/gmol

Thanks in advance!

Doing a classic search with alfabeta, knowing you have the PV move,
then TT hash is rather interesting to have already at a few plies search depth. Biggest win of it is in endgame and for your move ordering.

If you have already a sophisticated move ordering, impact of hashtable at 8 ply search depth is a lot less, except for endgame.

Biggest searchdepth win for you will be using nullmove, especially last 3+ plies or so.

In computerchess there is not 1 absolute truth. What will work at 8 ply search depth genius might be a loser at bigger search depths.

Hashtable is one of those things that's an unmissable feature,
assuming access to RAM is fast, and with java that sure is the case.

You don't need a huge one for 8 plies. So to speak 512KB is already a lot then.

The big winner at that search depth is nullmove, especially qsearch nullmove.

You can do there at top of search if alfa is not infinite (PV) then :
score = -qsearch(xside,-beta,-beta+1);

if( score >= beta ) return score; // fail soft, return beta in case of fail hard

This quiescencesearch nullmove will win you most plies in an easy and relative safe manner.

[diep]

the killer move heuristic isn't very useful, it only gives a small improvement over a proper implementation of History ordering. History and Killer are a bit redundant in a way, so if you have to choose one or the other it should be History (much more general and scalable)

really???
Then your tests might have someting wrong...
or you have tried something different to History heuristic, but you call it history.
I have rebuilt entirely my engine and i focused in good move ordering from the start. I can say that the killer heuristic is too much better than history by a big margin.
You can't start with history without having killers first.

In Diep, history doesn't work. Killermoves work genius though.

History is a long term move ordering, just using chessknowledge works better there for Diep.

Killermoves basically is short term, though i also use a longterm killer.
the short term killers work best there.

History in principle is fighting against the hashtable move, and of course loses that fight.

If you don't have a well working program, history table sure will work great for you.

In fact there is many chess engines that didn't do big effort for their move ordering and history tables work well there as well.

It might or might not work well for you. Just test it carefully.

[lucasart]

History in principle is fighting against the hashtable move, and of course loses that fight.

Not sure what you mean. In my move sorting scores, the History evolves in a range [-Hmax,+Hmax] that has no overlapping with captures or the TT move (which is always first).

How does your History mplementation work ?

[diep]

History in principle is fighting against the hashtable move, and of course loses that fight.

Not sure what you mean. In my move sorting scores, the History evolves in a range [-Hmax,+Hmax] that has no overlapping with captures or the TT move (which is always first).

How does your History mplementation work ?

I tried many different history implementations, based upon authors who said it worked for them in manner XYZ. Not sure they like their tricks revealed here. In not a single variation of that it ever worked though.

I can statistically prove history to not work for Diep if that is what you mean.

All i say is this: i tested it extensively and i retested it every few years at different search depths.

Yet we know 1 thing for sure: it's a long term move ordering concept and Diep already is having a couple of thousands of lines of code to order moves using chess knowledge.

It's obvious that something generic like history heuristics cannot work then as they are very generic long term and transpositiontable already works long term and a lot better there.

Basically in Diep nothing works that's long term. Only something short term ordering works. The long term ordering gets totally outgunned by chessknowledge and hashtable.

In fact first 10 iterations IID doesn't work either, that's how well the move ordering basically works, despite that it's time to again improve it as last big changes in it were around 1998 or so...

Please realize todays Diep has a branching factor of under 2.0 and Diep isn't razoring/futility and simply uses R=3 for nullmove and uses a 1 ply reduction for its reductions.

Most engines with similar branching factor they prune a lot more...

[diep]

The best way to compare move ordering is by turning off all your selectivity except for nullmove.

So just nullmove + hashtables.

No other forward pruning. And i disagree with Bob that hashtables are a form of forward pruning... ...as you remove a transposition you already searched so in the first place it belongs to a part of the search space you already searched to that depth...

Reason i wouldn't want to turn off hashtables nor nullmove is because otherwise we aren't gonna get some serious search depth and because when searching fullwidth 100% would have the disadvantage that any extension you do blows up the search tree too much - nullmove will avoid that.

If you forward prune last few plies and aren't doing nullmove there, keep it turned on.

That is a good comparision IMHO, though of course no replacement for the real thing.

You'll see then that LMR and such selectivity basically hide at many programs a very imperfect move ordering.

If authors like Don comment on that: "i don't need a good move ordering as LMR works magnificent for me so i save out time where you lost probably over a year building your move ordering at the time", there is no way to refute that argument from his viewpoint. Note this is a fictional example. Just an example.

[tpetzke]

You'll see then that LMR and such selectivity basically hide at many programs a very imperfect move ordering.

That is a real bad example, because LMR will reveal any bad move ordering scheme. If you have the good moves at the end of the list they are reduced by LMR. In the best case then you have to research them or in the worst case you miss something important.

With perfect move ordering LMR is very powerful because you reduce lines that do not influence the outcome of the search.

Thomas...

[diep]

You'll see then that LMR and such selectivity basically hide at many programs a very imperfect move ordering.

That is a real bad example, because LMR will reveal any bad move ordering scheme. If you have the good moves at the end of the list they are reduced by LMR. In the best case then you have to research them or in the worst case you miss something important.

With perfect move ordering LMR is very powerful because you reduce lines that do not influence the outcome of the search.

Thomas...

If you order worst move first, LMR searches you plies deeper.

If you order very well, LMR hardly gives you any search depth win of course,
because those lines that do not influence outcome of search you will nullmove away anyway.