How effective is move ordering from TT?

[syzygy]

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.

With perfect move ordering there is no need to search anymore

[Don]

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.

You are doing it wrong. Figuring out how to do it right was one of the big breakthroughs for us. We probably spend a week in man hours or more on this.

Doing it the classical Jonathan Schaeffer way is no good - that won't help you.

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.

[Don]

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.

We really cannot talk sensibly about this because each person implements things differently and a given program may respond differently to some identical change.

So in other words it's meaningless to speak in generalities such as "history doesn't work" etc. For Komodo history is HUGE and incredibly important but saying that your program "uses history" doesn't mean much unless you know how it's being used. Do it wrong and it's useless, which probably applies to almost anything.

[Don]

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.

Vincent,

I believe that LMR is useless UNLESS you have excellent move ordering. The entire premise of LMR is that a beta cutoff will usually occur right away, or not at all and this depends a LOT on move ordering. To get the very most out of LMR the BEST move should be very near the front of the list most of the time.

So LMR does NOT cover up bad move ordering, in fact it's just the opposite.

[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.

Vincent,

I believe that LMR is useless UNLESS you have excellent move ordering.

If i make the distinction between different issues then you'll see we probably disagree less than you'd guess.

First of all LMR works magnificent for engines that have a worthless move ordering, as it will search them a ply or 5 deeper or so meaning their mainline gets checked quite deeper. This delivers them elo. Especially at those superbullet search depths where they tactically are so weak that a few plies extra to check your PV of course kicks major butt.

Further trying the worst move first is not necessarily a bad idea always; in nearly any given position the move Bxh7 might just give away a bishop, yet IF it's a tactical win here you'll be very happy if it's the first move you try.

In all other positions though it'll reduce the search tree SIGNIFICANTLY if you try such useless crapmove first, as we try it at the full depth (minus normal reduction) and after capturing it back we soon stumble upon series of nullmoves of our opponent which is a piece up.

The entire premise of LMR is that a beta cutoff will usually occur right away, or not at all and this depends a LOT on move ordering.

Elowise we don't disagree but search depth wise: "how much it delivers",
is heavily depending upon having a BAD move ordering.

If we try the best move first we might win more elo, yet we'll win less plies of course.

To get the very most out of LMR the BEST move should be very near the front of the list most of the time.

So LMR does NOT cover up bad move ordering, in fact it's just the opposite.

You're just speaking elowise here now from a piece of paper. That's not reality of search though. For most engines LMR works because they have such a crap move ordering, yet they do try captures pretty soon and some do not reduce any capture in fact.

With a near to non existing evaluation function combined that means that in a given position that's lowerbound, the biggest chance we've got to get it above alpha, is by doing a capture.

I've got extensive statistics done on when and why reductions work or do not work. Those statistics i already started back in 1999 by the way.

So besides a huge search depth, the few times that most engines get a fail high it's gonna be a capture which initiates further sequences. In other words a bad move ordering really helps them as they still benefit from that effect of searching the mainline deeper meanwhile the few cases that from mainlines viewpoint a position where you normally spoken reduce bigtime picks up something, statistical odds are so much against you that you select the best moves; in fact it's beneficial to most then to have a crap ordering. In fact if we already ASSUME we have a crap move ordering with big odds we don't select the best move, it's better to do the most stupid move with LMR, as that'll give a quicker cutoff by means of nullmove for our opponent and will reduce the search tree significantly more in nodes, meanwhile we already knew we would not try the best move as non-reduced move.

You understand what i try to make clear?

LMR works better if you have a total crap move ordering.

The best proof of this is your own engine. It's tactical way weaker than any other engine that's close in elo to yours.In short all the reductions or forward pruning you do it just doesn't manage to select the best moves at all.

There's not a position that Diep doesn't find plies sooner than Komodo, provided both engines can find it.

Yet you DO benefit a lot from searching deeper with Komodo.

Just for fun you can try this experiment. In each innernode P where you'd be using LMR, first turn off hashtables and other table storage (such as to killermoves) and especially your node counter. Determine in a slowish manner the best moves using a PV type window.

Of course the 'selection of bestmoves' you do with a reduced depth to not blow up the experiment too much and also to reflect reality (as it's realistic it would be from a previous iteration).

Then select those moves as first and continue your LMR search from there, so NOT reducing the few bestmoves yet.

Now count how many nodes you need to finish the ply.

Of course the 'benefit' you have in such case is that flipping nodes (that flip from upperbound to lowerbound) might reduce the search tree, but you'll clearly measure that suddenly your LMR reduced search needs a lot more nodes as the first few moves probably are causing a bigger dilemma to your search.

elowise seen the moves that really matter where to pick the best move first is your PV nodes and direct childnodes of them.

Might be interesting to experiment around PV with some different windows finding the best moves actually...

Yet the whole point is, if you do this, just like i did, you'll figure out LMR suddenly wins you less plies with Komodo, which proves my point.

Vincent

[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.

You are doing it wrong. Figuring out how to do it right was one of the big breakthroughs for us. We probably spend a week in man hours or more on this.

Doing it the classical Jonathan Schaeffer way is no good - that won't help you.

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.

Don, Your program is kind of a beancounter that relies heavily positoinal upon piece square tables.

In diep i've got all kind of noise. Not necessarily helping always, (implemented at years 90 not before 4 AM not seldom), but it's noise that is responsible most for how strong Diep plays. That's why i put in that much work to order moves at the time to order diep's moves.

The combination of this all renders of course history table total useless.

I do hope you agree with me that history table is a LONG TERM move ordering concept, do you?

Well for Diep i can prove that it's very difficult to get those to work, as of course these head to head compete with the hashtable.

To quote Frans Morsch why the monte carlo effect occured at some other program more than i had it occur with Diep: "You're really researching each iteration the previous tree with Diep".

If you print out how history table orders for Komodo you'll see it's following the same logics like your piece square tables.

So with some chesslogics, the hashtable and the killermoves, that should render the history table pretty useless then.

Just for an experiment do this: order your moves instead of with hashtable, iwth your evaluation function and a good working 'SEE' (i'm sure you have one - the hyatt definition of SEE i refer to).

Then tell me whether that orders your moves better than your history table and by how much...

If we would do next experiment Diep versus Komodo. We both remove our piece square tables and have the engines play.

Komodo probably loses 1000 elopoints or so then playing Diep. Diep will lose really a lot less than Komodo elowise. It's still 2600+ then or so in case of Diep i bet.

It's not even a contest. It's gonna be a 100% butchering of Komodo.

Now you might say this is not fair compare, and it isn't, as i have far more chessknowledge in Diep than you have in Komodo, probably a factor 100+ more or so. Yet that should give you an indication that ordering Diep's moves doesn't work with a simple heuristic like history table, which basically reflects your piece square tables and tuning for that given position.

Diep doesn't play at accurate tuning. It plays at knowledge. That's a total different concept - and sure i hope to also add some more accurate tuning - in fact more important than parameter tuning for diep is 'upgrading' buggy years 90 patterns that still are in.

A week ago i fixed a pattern that regurarly gave a bonus for passed pawns. I couldn't trace back exactly when i had written that EXACT code - but it was before end 1996...

Fixed: august 2012...

Yet at the moment that the exact parameter tuning is not the battle between the engines, but the massive weight of the evaluation function, you really can no longer predict by means of a generic function called history tables, the exact value of each move generated by the evaluation function...

Chessknowledge and hashtables and killermoves then are the key to succes.

oh by the way - i hardly dare to ask it. Does Komodo use IID?

[Don]

Don, Your program is kind of a beancounter that relies heavily positoinal upon piece square tables.

You could not be more incorrect. We have piece square tables in Komodo that are a very minor part of Komodo and get very small weights but Komodo puts a huge emphasis on getting the evaluation right with hundreds of evaluation terms that are carefully balanced to produce a find positional chess program. I personally believe that Komodo has the best evaluation function of any chess program in the world. It's search is great too, but the search is not the strongest aspect of Komodo. Having said that, it's probably far better than 99% of the thousands of chess programs out there.

In diep i've got all kind of noise. Not necessarily helping always, (implemented at years 90 not before 4 AM not seldom), but it's noise that is responsible most for how strong Diep plays. That's why i put in that much work to order moves at the time to order diep's moves.

The combination of this all renders of course history table total useless.

I do hope you agree with me that history table is a LONG TERM move ordering concept, do you?

I do not understand what you mean by that terminology. Komodo ages the history dynamically, when means the values in the table tend to always be relevant.

Well for Diep i can prove that it's very difficult to get those to work, as of course these head to head compete with the hashtable.

To quote Frans Morsch why the monte carlo effect occured at some other program more than i had it occur with Diep: "You're really researching each iteration the previous tree with Diep".

If you print out how history table orders for Komodo you'll see it's following the same logics like your piece square tables.

wrong again! We have experimented with move ordering many times and one experiment was the use the piece square tables for move ordering - a naive experiment but we had to try it to be thorough. Our move ordering was horrible with piece square tables - almost as if there was no correlation at all.

We also tried using the piece square tables for a quick estimate of the score to use in things such as lazy evaluation. I knew that was no good but Larry nagged me to try it - in fact every few weeks he gets some idea based on using the piece square table to estimate the score - such as forward pruning margins, etc. He always thinks that will be a good estimate but he is always wrong as there is virtually no correlation. The piece square tables in Komodo only provide very crude guidance, basically used to break ties and measure piece centralization and such things as penalizing flank pawns, etc. They get very little weight because and they don't correlate to our dynamic evaluation.

So with some chesslogics, the hashtable and the killermoves, that should render the history table pretty useless then.

Just for an experiment do this: order your moves instead of with hashtable, iwth your evaluation function and a good working 'SEE' (i'm sure you have one - the hyatt definition of SEE i refer to).

Then tell me whether that orders your moves better than your history table and by how much...

If we would do next experiment Diep versus Komodo. We both remove our piece square tables and have the engines play.

Komodo probably loses 1000 elopoints or so then playing Diep. Diep will lose really a lot less than Komodo elowise. It's still 2600+ then or so in case of Diep i bet.

It's not even a contest. It's gonna be a 100% butchering of Komodo.

That's not a good test to run. We run Komodo vs Diep (without modification) at any time control you choose, equal hardware, equal hash. This will be a butchering of Diep I am positive.

The best way is for each of us to send a binary to someone we both trust and let them run the test and report the result. You will lose and have some excuse for why.

Now you might say this is not fair compare, and it isn't, as i have far more chessknowledge in Diep than you have in Komodo, probably a factor 100+ more or so. Yet that should give you an indication that ordering Diep's moves doesn't work with a simple heuristic like history table, which basically reflects your piece square tables and tuning for that given position.

Total amount of knowledge is not what is important, it's the QUALITY of the knowledge that is. Komodo tries to have the most balanced evaluation function possible, and probably much more knowledge than most programs. I don't believe in quantity but Komodo evolved to have a lot of knowledge anyway - probably because every piece of knowledge in Komodo is needed. I tried removing knowledge in Komodo to get speed and we were not able to remove ANYTHING without noticing that it weakened Komodo, at least slightly.

Diep doesn't play at accurate tuning. It plays at knowledge. That's a total different concept - and sure i hope to also add some more accurate tuning - in fact more important than parameter tuning for diep is 'upgrading' buggy years 90 patterns that still are in.

Tuning IS a form of knowledge. You need to tune what you have. Thinking that a knight is worth more than a queen is a lack of knowledge. Silly example but this illustrates the point - knowledge means "knowing" and knowing what the probably weights should be is a very important piece of knowledge too.

You mentioned "patterns" - that may be the next thing that we get into - but Komodo is a very young program and we have focused on having a very sound program with an excellent grasp of the fundamentals. We don't have a lot of tricky code to determine if a piece is trapped or whether some thematic pattern exists in the position - like any endeavor you start with the fundamentals, get that right first, then move on to other things. However few programs have the fundamentals correct including Diep and even Komodo, but I believe Komodo comes the closest.

A week ago i fixed a pattern that regurarly gave a bonus for passed pawns. I couldn't trace back exactly when i had written that EXACT code - but it was before end 1996...

Fixed: august 2012...

Yet at the moment that the exact parameter tuning is not the battle between the engines, but the massive weight of the evaluation function, you really can no longer predict by means of a generic function called history tables, the exact value of each move generated by the evaluation function...

Chessknowledge and hashtables and killermoves then are the key to succes.

oh by the way - i hardly dare to ask it. Does Komodo use IID?

Yes - but it's a very minor benefit for Komodo. There is code for doing IID in non-pv nodes but it's currently comented out - that code comes and goes .....

[lkaufman]

If we would do next experiment Diep versus Komodo. We both remove our piece square tables and have the engines play.

Komodo probably loses 1000 elopoints or so then playing Diep. Diep will lose really a lot less than Komodo elowise. It's still 2600+ then or so in case of Diep i bet.

It's not even a contest. It's gonna be a 100% butchering of Komodo.

Now you might say this is not fair compare, and it isn't, as i have far more chessknowledge in Diep than you have in Komodo, probably a factor 100+ more or so. Yet that should give you an indication that ordering Diep's moves doesn't work with a simple heuristic like history table, which basically reflects your piece square tables and tuning for that given position.

Just for fun I decided to check out your claim. I'll assume for round numbers that Diep on one core is 2600 by IPON standards (correct me if I'm way off) and we'll round Komodo down to 3000. I made a version of Komodo 5 with all the piece square tables zeroed out, and rated it against the normal Komodo at 10" + 0.1". Fast games, but still average depth in the 11 to 12 ply range, probably good enough to earn the IM title in human tournaments, or at least FM. The elo loss was 190, giving it a rating of 2810, still miles above DIEP with piece square tables. I only played a couple hundred games, so the margin of error is large, but I'm not interested in a precise rating, just ballpark. But even this is not fair, because Komodo does depend on the tables somewhat for the king; in particular it may not want to castle without piece square tables. So I made another version that restored piece square tables just for the king, and the rating came out 2920, only 80 below normal and 320 above DIEP. Now I admit that at longer time limits the elo loss might be somewhat greater, but I doubt that it would grow by more than 50% at a time limit such as IPON uses for example (5' +3"). As the time limit grows, the number of draws increases, so this should counteract any tendency of the elo loss to grow with depth. Also the rating loss was probably much exaggerated by the self-testing, as you yourself have often pointed out. If both were run against DIEP, the loss should be much smaller.
So while Komodo may lose far more than DIEP if piece square tables are removed (I'll take your word for this), the loss will still leave Komodo far above DIEP, with or without such tables.

[Rebel]

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.

Vincent,

I believe that LMR is useless UNLESS you have excellent move ordering.

If i make the distinction between different issues then you'll see we probably disagree less than you'd guess.

First of all LMR works magnificent for engines that have a worthless move ordering, as it will search them a ply or 5 deeper or so meaning their mainline gets checked quite deeper. This delivers them elo.

Engines with a worthless move ordering will reduce the wrong moves. That is a bad receipt for elo improvement. Don is right, the better your move ordering, the more secure the LMR reductions.

[hgm]

Micro-Max has a very poor move ordering (no killer, no history; it just does 1) null move, 2) hash move, 3) best MVV/LVA capture, 4) other captures in unspecified order, 5) non-captures in unspecified order). Yet LMR worked great. It reduces all non-captures that are not Pawn moves.