Null move and LMR

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.
Post Reply
lauriet
Posts: 162
Joined: Sun Nov 03, 2013 8:32 am
Contact:

Null move and LMR

Post by lauriet » Wed Mar 12, 2014 9:44 pm

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

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

Re: Null move and LMR

Post by hgm » Wed Mar 12, 2014 9:51 pm

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
Posts: 162
Joined: Sun Nov 03, 2013 8:32 am
Contact:

Re: Null move and LMR

Post by lauriet » Thu Mar 13, 2014 1:32 am

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
Posts: 820
Joined: Mon Jan 15, 2007 10:23 am
Location: Warsza
Contact:

Re: Null move and LMR

Post by PK » Thu Mar 13, 2014 8:01 am

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%)
Last edited by PK on Thu Mar 13, 2014 8:05 am, edited 1 time in total.

Daniel Shawul
Posts: 3749
Joined: Tue Mar 14, 2006 10:34 am
Location: Ethiopia
Contact:

Re: Null move and LMR

Post by Daniel Shawul » Thu Mar 13, 2014 8:05 am

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
Posts: 265
Joined: Thu Mar 09, 2006 12:07 am

Re: Null move and LMR

Post by Harald » Thu Mar 13, 2014 8:17 am

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
Posts: 162
Joined: Sun Nov 03, 2013 8:32 am
Contact:

Re: Null move and LMR

Post by lauriet » Fri Mar 14, 2014 1:44 am

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
Posts: 900
Joined: Tue Apr 27, 2010 1:48 pm

Re: Null move and LMR

Post by rbarreira » Fri Mar 14, 2014 6:45 am

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

lauriet
Posts: 162
Joined: Sun Nov 03, 2013 8:32 am
Contact:

Re: Null move and LMR

Post by lauriet » Fri Mar 14, 2014 11:59 am

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 :)

Post Reply