Page 1 of 1
Null move and LMR
Posted: Wed Mar 12, 2014 10:44 pm
by lauriet
Hey everyone.
I've been looking at reduction methods for my engine and had a question I'm sure someone can answer.
LMR reduction, for instance, is part of the recursive search call. So each time the next ply is looked at, the bad moves are only search by, say, 2 less ply. And again in the next call and so on. Doesn't this mean that the bad move search deteriorates to only a few ply? The PV may be search to say 12 and the bad moves to only 4. Maybe this IS the idea, but it seems like a drastic reduction. Of course this is only for the bad moves of the bad moves of the bad moves etc.
Thanks
Laurie
Re: Null move and LMR
Posted: Wed Mar 12, 2014 10:51 pm
by hgm
Indeed, it is drastic. But it seems to work. With a fixed-depth search + QS you would perhaps reach 8 ply, at 1Mnps. To do better on the PV, the nodes must come from somewhere. So most branches will be searched a lot less deep than 8 ply.
Re: Null move and LMR
Posted: Thu Mar 13, 2014 2:32 am
by lauriet
I've read some previous threads and it does make sense, especially in view of how a human plays....search a few candidate moves deeply and just glance at dumb moves.
Does that mean that the search tree would get shallower as you move to the right hand side (later moves in the move list)
Laurie
Re: Null move and LMR
Posted: Thu Mar 13, 2014 9:01 am
by PK
Classic LMR reduced all late moves by the same amount. Modern implementations do exactly what you say: later moves are reduced more. Stockfish uses a formula where both move number and remaining depth are taken into account.
Because nobody wants to end up with an engine that is tactically blind, some moves never get reduced. Usually these are captures, checks, moves while in check, sometimes also moves with good history scores or threat evasions.
In cases where reduced move unexpectedly scores above alpha, re-search to normal depth is carried on, but it happens fairly rarely (last time I measured it in my engine, it was below 2%)
Re: Null move and LMR
Posted: Thu Mar 13, 2014 9:05 am
by Daniel Shawul
For a mathematical analysis of null move and lmr tree shapes and perft counts, you can look at my _very informal_ attempt to summarize both in this paper
https://dl.dropboxusercontent.com/u/552 ... runing.pdf
Re: Null move and LMR
Posted: Thu Mar 13, 2014 9:17 am
by Harald
Code: Select all
This is a typical node in the search tree with a depth of 10
and the search depth of the next ply generated in a fixed depth search.
10
9 9 9 9 9 9 9 9 9 9 9 9 9 9 9
This is a typical node in the search tree with a depth of 10
and the search depth of the next ply generated by late move reduction.
We assume that we have a good move order heuristic with the most
important moves first (left) and the bad moves last (right).
10
9 8 8 7 7 7 7 6 6 6 6 6 6 6 6
This is another typical node with LMR near the horizon.
The q-search pops in with a random depth.
3
2 1 1 Q Q
1 Q Q Q Q Q Q Q Q Q Q
QQQQQQ QQ Q QQ Q
Q Q
This is the shape of a search tree of fixed depth of 4
seen from a larger distance. There might be some shorter
ends with a mate or stalemate (m).
x
ooo
xxxxxxxxx
oooooooooomooooooo
QQQQQQQQQQQQ QQQQQQQQQQ
This is a shape of a search tree (depth=8) with LMR.
x
ooo
xxxxxxxxx
oooooooooooooooooo
xxxxxxxxxxxxxxxxQQQQQQQ
oooooooooooQQQQQQQ
xxxxxxxxQQQQQ
ooooQQQQ
QQQQ
This is a shape of a search tree with LMR and some extensions.
x
ooo
xxxxxxxxx
oooooooooooooooooo
xxxxxxxxxxxxxxxxQQQQQQQ
oooooooooooQQQoQQQ
xxxxxxxxQQxQQ xxx
ooooQoQQ Q oQQ
xQQQ m Q
Q
In reality with a branching factor of 20 to 40 there are
many more nodes. Too much for ASCII art.
Re: Null move and LMR
Posted: Fri Mar 14, 2014 2:44 am
by lauriet
Thanks guys, Im getting the idea now. I don't want to add anything to my program until I understand it.
I think I could implement it, but could anyone help with some sample documented code (Imagine you are explaining to a 5 year old)
Im guessing its something like:
if MoveNumber > something then
Result = ABsearch(A,B, Depth -2, Position)
else
Result = ABsearch(A,B Depth-1, Position)
Regards
Laurie
Re: Null move and LMR
Posted: Fri Mar 14, 2014 7:45 am
by rbarreira
lauriet wrote:Thanks guys, Im getting the idea now. I don't want to add anything to my program until I understand it.
I think I could implement it, but could anyone help with some sample documented code (Imagine you are explaining to a 5 year old)
Im guessing its something like:
if MoveNumber > something then
Result = ABsearch(A,B, Depth -2, Position)
else
Result = ABsearch(A,B Depth-1, Position)
Regards
Laurie
http://www.glaurungchess.com/lmr.html
Re: Null move and LMR
Posted: Fri Mar 14, 2014 12:59 pm
by lauriet
Hi guys,
Tonight I tried.....(code from the max nodes)
IF ThreeFoldDraw THEN
Score := DrawScore(White)
ELSE
IF LMR(Index, Depth) THEN
BEGIN
Score := BlacksScore(Alpha, Beta, Depth - 2);
IF Score > Alpha THEN
Score := BlacksScore(Alpha, Beta, Depth - 1);
END
ELSE
Score := BlacksScore(Alpha, Beta, Depth - 1);
seems to be giving me 2 extra ply of search.
Maybe I can narrow the window on the LMR search.
Ive only played one game and it seemed to play better, so I will need to play another 10,000 more
