LMP

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
User avatar
flok
Posts: 199
Joined: Tue Jul 03, 2018 8:19 am
Full name: Folkert van Heusden
Contact:

LMP

Post by flok » Tue Jul 09, 2019 3:27 pm

Hi,

What is LMP and how does it work/is it implemented?
LMP, late move pruning not reduction.
I see mentions of it here and there but it is not described on the wiki.
www.vanheusden.com: Micah / Embla / PuppetMaster / DeepBrutePos / Pos / Feeks

User avatar
JVMerlino
Posts: 1003
Joined: Wed Mar 08, 2006 9:15 pm
Location: San Francisco, California

Re: LMP

Post by JVMerlino » Tue Jul 09, 2019 4:12 pm

Late Move Pruning can just as easily be thought of as "Maximally Aggressive Late Move Reduction". Instead of, as in LMR, reducing the remaining depth of a move by some amount depending on how late it is in the move order, you simply reduce the remaining depth to 0, no matter what the remaining depth is. I'm not 100% sure, but I believe some implementations drop straight to q-search at this point, while others abandon the line altogether.

The factors that go into the decision to prune a move are quite varied among engines that implement LMP. Since LMP is potentially more dangerous than LMR, it should be thoroughly tested.

Gerd Isenberg
Posts: 2127
Joined: Wed Mar 08, 2006 7:47 pm
Location: Hattingen, Germany

Re: LMP

Post by Gerd Isenberg » Tue Jul 09, 2019 7:34 pm

flok wrote:
Tue Jul 09, 2019 3:27 pm
Hi,

What is LMP and how does it work/is it implemented?
LMP, late move pruning not reduction.
I see mentions of it here and there but it is not described on the wiki.
Mentioned on the Futility Pruning page as Move Count Based Pruning aka Late Move Pruning (LMP) with reference post by Tom King.

Henk
Posts: 5825
Joined: Mon May 27, 2013 8:31 am

Re: LMP

Post by Henk » Tue Jul 09, 2019 7:56 pm

If you already have a good move you can prune everything
So need not be dangereuses
Of course iT failed in skipper engine
Probably because search narrowed too Much

Man this phone scrumbling my message

Dann Corbit
Posts: 10114
Joined: Wed Mar 08, 2006 7:57 pm
Location: Redmond, WA USA
Contact:

Re: LMP

Post by Dann Corbit » Tue Jul 09, 2019 8:07 pm

Henk wrote:
Tue Jul 09, 2019 7:56 pm
If you already have a good move you can prune everything
So need not be dangereuses
Of course iT failed in skipper engine
Probably because search narrowed too Much

Man this phone scrumbling my message
Caveat:
From:
https://en.wikiquote.org/wiki/Emanuel_L ... ite_note-2

"t is necessary always to bear in mind these prudential rules, viz.: having a good move, to seek for a better." Dominico Ercole del Rio, The Incomparable Game of Chess, trans. J.S. Bingham (London 1820), 35-36. Note Bingham incorrectly credits Ercole del Rio with work that was authored by Domenico Lorenzo Ponziani
Taking ideas is not a vice, it is a virtue. We have another word for this. It is called learning.
But sharing ideas is an even greater virtue. We have another word for this. It is called teaching.

Henk
Posts: 5825
Joined: Mon May 27, 2013 8:31 am

Re: LMP

Post by Henk » Tue Jul 09, 2019 8:21 pm

Assuming infinite budget

I score low on perfectionism so no need to discussie with me

Dann Corbit
Posts: 10114
Joined: Wed Mar 08, 2006 7:57 pm
Location: Redmond, WA USA
Contact:

Re: LMP

Post by Dann Corbit » Tue Jul 09, 2019 8:32 pm

Henk wrote:
Tue Jul 09, 2019 8:21 pm
Assuming infinite budget

I score low on perfectionism so no need to discussie with me
As soon as we move beyond alpha-beta in pruning, perfection has gone out the window.
Null move pruning is unsound. But darned if it doesn't work.
It was Rybka that invented the "drop straight into qsearch idea" and we must admit, it worked pretty well, especially at the time.
I remember Anthony Cozzie being somewhat astonished by the technique.

It is a good idea to prune a lot. The best engines have a branching factor below 2.
But we should not prune too much either.
Naturally, it's a delicate balance. Eloquently described for another game by Kenny Rogers:

"Every gambler knows
The secret to survivin'
Is knowin' what to throw away
And knowin' what to keep"
Taking ideas is not a vice, it is a virtue. We have another word for this. It is called learning.
But sharing ideas is an even greater virtue. We have another word for this. It is called teaching.

AndrewGrant
Posts: 489
Joined: Tue Apr 19, 2016 4:08 am
Location: U.S.A
Full name: Andrew Grant
Contact:

Re: LMP

Post by AndrewGrant » Tue Jul 09, 2019 8:51 pm

flok wrote:
Tue Jul 09, 2019 3:27 pm
Hi,

What is LMP and how does it work/is it implemented?
LMP, late move pruning not reduction.
I see mentions of it here and there but it is not described on the wiki.
For Ethereal ...

Code: Select all

// Step 12B. Late Move Pruning / Move Count Pruning. If we have
// tried many quiets in this position already, and we don't expect
// anything from this move, we can skip all the remaining quiets
if (   depth <= LateMovePruningDepth
    && quiets >= LateMovePruningCounts[improving][depth])
    skipQuiets = 1;

Code: Select all

static const int LateMovePruningDepth = 8;
static const int LateMovePruningCounts[2][9] = {
    {  0,  3,  4,  6, 10, 14, 19, 25, 31},
    {  0,  5,  7, 11, 17, 26, 36, 48, 63},
};

chrisw
Posts: 2104
Joined: Tue Apr 03, 2012 2:28 pm

Re: LMP

Post by chrisw » Wed Jul 10, 2019 7:16 am

Dann Corbit wrote:
Tue Jul 09, 2019 8:32 pm
Henk wrote:
Tue Jul 09, 2019 8:21 pm
Assuming infinite budget

I score low on perfectionism so no need to discussie with me
As soon as we move beyond alpha-beta in pruning, perfection has gone out the window.
There never was any perfection, since the default is to prune at the horizon (depth).
Pruning sacrifices some of the (otherwise full) width for more depth. Perfection is unattainable but trading width for depth appears to be the way to minimise imperfections. Maybe.

Null move pruning is unsound. But darned if it doesn't work.
stopping the search by running out of time is unsound too.

It was Rybka that invented the "drop straight into qsearch idea" and we must admit, it worked pretty well, especially at the time.
I remember Anthony Cozzie being somewhat astonished by the technique.

It is a good idea to prune a lot. The best engines have a branching factor below 2.
But we should not prune too much either.
Naturally, it's a delicate balance. Eloquently described for another game by Kenny Rogers:

"Every gambler knows
The secret to survivin'
Is knowin' what to throw away
And knowin' what to keep"

Post Reply