Null move and LMR

[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

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

[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

[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%)

[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

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

[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

[rbarreira]

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

[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