Don wrote:diep wrote: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