SEE on non-capture moves in main search

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Tord Romstad
Posts: 1808
Joined: Wed Mar 08, 2006 8:19 pm
Location: Oslo, Norway

Re: SEE on non-capture moves in main search

Post by Tord Romstad » Mon Apr 02, 2007 6:51 pm

JP wrote:I don't get why you turn LMR off during move ordering tests.
There are two main reasons:

With LMR on, it is not possible to determine whether move ordering scheme A is better than move ordering scheme B simply by comparing node counts for a big number of positions, because the move ordering affects the average number of reduced moves per node. It is possible that move ordering scheme A will consistently give smaller trees than move ordering scheme B simply because scheme A results in a bigger number of moves being reduced. Scheme A will be a bit faster, while scheme B will be a bit more precise. Which of the two performs better in actual play can only be determined by playing a huge number of test games.

The most obvious example of this phenomenon is the ordering of losing captures. I, like most other programmers, never reduce captures, regardless of their position in the move list. If losing captures are searched early (for instance between the equal captures and the killer moves), the average number of reduced moves per position will go down compared to when they are searched late (at the end of the move list, for example).

The second problem is that LMR warps the shape of the tree in essentially random ways. A tiny change in move ordering will often change the the score, the PV, or even the best move for a given position at a search to depth N. The number of nodes may easily differ by a factor of 2 or more. Of course this sort of thing occurs without LMR as well, but not nearly as often. The variance for all sorts of statistics is much bigger with LMR on, which means that you need a much bigger set of tests before you can make any statistically valid conclusions.

Tord

Peter Fendrich

Re: SEE on non-capture moves in main search

Post by Peter Fendrich » Mon Apr 02, 2007 7:53 pm

The testing methodology here is interesting.
I agree (without doing the math) that the variance with LMR is much bigger than other techniques such as Null moves, futility and sofort even if the combination effects are hard to really grasp.
The problem you have is that by testing move ordering without LMR you may get that scheme A gives less nodes but in practical play scheme B will reduce more and that might be a good effect in real play. So in the end you still have to test them both in real games.

I don't know how big number of positions we need to get reliable move ordering tests with LMR on. If it is in the magnitude of 1000 or 2000 it might be good idea.

Right now I test with 350 positions and I use 2 different LMR settings, one restrictive and one more aggressive. I am trying to draw som conclusions of the material. If the differences are not too big which is the normal case I test them both in real play.

User avatar
hgm
Posts: 23616
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: SEE on non-capture moves in main search

Post by hgm » Mon Apr 02, 2007 9:01 pm

If I unerstand Tord correctly, the important point is that LMR is not a technique that preserves the quality of the search, while other techniques for move ordering (and even R=2 null-move pruning to a large extent) are guaranteed to find the same move and score.

So with LMR switched on, you can minimize the tree size, but that is meaningless if you don't at the same time measure the quality of the search. Because you might have been eroding the quality faster than the node count, so the smaller tree might actually be worst. Because by the time you have increased the depth to play at the same level again, it might actually be a larger tree with that move ordering.

OTOH, for trees where the move ordering has no effect on the tactical strength, the smaller tree is automatically the better, and you are not faced with the problem of recalibrating the tactical strength before you can compare them.

Peter Fendrich

Re: SEE on non-capture moves in main search

Post by Peter Fendrich » Mon Apr 02, 2007 9:30 pm

LMR quality is not a matter of true or false. LMR does what all reduction techniques does as well as the extentions does. They interact closely with the move ordering and reshapes the tree. The combination effects of all these together are not clear to any human on this earth. The more variance we have the more positions we need to get reliable (enough) results.
The main difference is that LMR reshapes the tree in a higher respect than other of the (well known) techniques do. So it is a matter of how many positions we need to get reliable results. Maybe it is 2000, maybe it is 2 millions - I don't know. If there is no upper limit. LMR can not be used in real play either.

User avatar
hgm
Posts: 23616
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: SEE on non-capture moves in main search

Post by hgm » Tue Apr 03, 2007 8:46 am

Even if you take an infinite number of positions it would still be meaningless if you did not measure tactical strength. Because you would select the move ordering systematically to reduce more moves by LMR, by putting poor, but non-reducible moves (like bad captures) in front, just to put interesting moves to a place in the list where they can be reduced. That makes the tree smaller, but the interesting lines shorter.

Peter Fendrich

Re: SEE on non-capture moves in main search

Post by Peter Fendrich » Tue Apr 03, 2007 10:29 am

Don't underestimate my abilities here :)
There is no need to act stupid even if it is possible...
Captures are a very special and easy to detect cases.

What you say is in general applicable to every move ordering test, LMR on or off. There are other pruning methods.
If you look above you will see how I am trying to capture this effect.

IMHO There are no magic silver bullits here. If we test move ordering without LMR and rely on that only we will miss the cases where LMR is hurt by the winning scheme. If we test with LMR on we must be observant to the riscs you mentioned.

I also forgot to say that every program doesn't use LMR and hstory values in the same way. That will of course make a difference in the impact of this in move ordering tests.

Tony

Re: SEE on non-capture moves in main search

Post by Tony » Tue Apr 03, 2007 10:54 am

hgm wrote:Even if you take an infinite number of positions it would still be meaningless if you did not measure tactical strength. Because you would select the move ordering systematically to reduce more moves by LMR, by putting poor, but non-reducible moves (like bad captures) in front, just to put interesting moves to a place in the list where they can be reduced. That makes the tree smaller, but the interesting lines shorter.
In addition, most people "optimize" their LMR (and also make it safe) by fe not reducing the first 4 moves. If one is sure that there are no bad captures in the first moves, the 4 might be lowered to 3

ie current LMR use is not optimal, while for the former situation it is.

Tony

bob
Posts: 20478
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: SEE on non-capture moves in main search

Post by bob » Tue Apr 03, 2007 9:23 pm

JP wrote:Don't underestimate my abilities here :)
There is no need to act stupid even if it is possible...
Captures are a very special and easy to detect cases.

What you say is in general applicable to every move ordering test, LMR on or off. There are other pruning methods.
If you look above you will see how I am trying to capture this effect.

IMHO There are no magic silver bullits here. If we test move ordering without LMR and rely on that only we will miss the cases where LMR is hurt by the winning scheme. If we test with LMR on we must be observant to the riscs you mentioned.

I also forgot to say that every program doesn't use LMR and hstory values in the same way. That will of course make a difference in the impact of this in move ordering tests.
That's why I test as I do. I adhere to the old idea "dance with the one that 'brung' ya."

Since I use LMR, I test with it. Otherwise something can hurt more with LMR and help without LMR. So occasionally disabling LMR to see if the program gets weaker is a good sanity check. But I would never test by adding new ideas while disabling others, because the interactions between those two sets of things is critical to capture when trying to decide which is better.

bob
Posts: 20478
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: SEE on non-capture moves in main search

Post by bob » Tue Apr 03, 2007 9:24 pm

hgm wrote:Even if you take an infinite number of positions it would still be meaningless if you did not measure tactical strength. Because you would select the move ordering systematically to reduce more moves by LMR, by putting poor, but non-reducible moves (like bad captures) in front, just to put interesting moves to a place in the list where they can be reduced. That makes the tree smaller, but the interesting lines shorter.
I would hope nobody tests like that. I run real-game tests. I run tactical suites. And try to make sure that neither has been hurt by additions...

User avatar
hgm
Posts: 23616
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: SEE on non-capture moves in main search

Post by hgm » Tue Apr 03, 2007 9:29 pm

I hoped so too... :lol:

But for testing move ordering on a pure alpha-beta tree it is actually the quickest way, as you know that the move order won't affect the moves and scores at the root. So playing real games would just introduce statistical noise, that you would have to painstakingly average out by a sqrt(N) law...

Post Reply