LMR tuning

[zd3nik]

I've wasted more time than I care to think about trying to optimize LMR. And by optimize I mean trying to find the best conditions in which to apply reductions.

There are a lot of different LMR ideas and implementations out there. Naturally no single LMR implementation is going to be the optimal choice for every engine. But I would like to find a solid base of dos and don'ts if possible.

So today I started doing some number crunching to try and gain some new insight into which moves to reduce and when. Here's how I've started the data collection process:

Code: Select all

for (move = 2nd move to last move) {
  if (not in check and depth > 1 and move is not cap or promo)
    increment column A
    if null window search with reduced depth > alpha
      increment column B
    if null window search with full depth > alpha
      increment column C
  endif
  ... cary on with normal search handling ... 
}

And here is an example of the numbers I'm collecting (so far). This example from a 10 ply search on startpos:

Code: Select all

Material(0),    4031,   100%
Material(1),    4031,   100%

A=Candidates
B=Reduced Depth Search > alpha
C=Full Depth Search > alpha

Data Point,  A,        B,    C
Candidates,  161178,   471,  550
SSE < 0,     47679,    15,   12 
SSE <= 0,    107496,   45,   27 
SSE > 0,     53682,    426,  523
SSE >= 8,    42812,    406,  491
SSE >= 16,   10893,    292,  411
IsKiller,    6025,     161,  257
Hist < 0,    156234,   245,  286
Hist <= 0,   156374,   246,  288
Hist > 0,    4804,     225,  262
Hist >= 8,   4544,     219,  258
Hist >= 16,  4272,     210,  248
Gives Check, 1234,     11,   10
Pawn Push,   40215,    85,   104
Pawn Lung,   33855,    81,   91
Knight Move, 29621,    194,  270
Bishop Move, 22971,    46,   27
Rook Move,   4560,     0,    0
Queen Move,  22829,    65,   56
King Move,   7127,     0,    2
0-0,         120,      0,    2
0-0-0,       0,        0,    0
MvNum 2,     2711,     70,   127
MvNum 3,     5007,     145,  196
MvNum 4,     5448,     74,   87
MvNum 5,     5622,     43,   39
MvNum 6,     5792,     23,   10
MvNum 7,     5832,     13,   14
MvNum 8,     5828,     21,   7
MvNum 9+,    124938,   82,   70

I'm hoping to uncover useful trends. For example, say moves of type X in the middlegame have a higher than average alpha increase rate so it's best *not* to reduce that case. Or column B and C values are often similar for moves of type Y during an endgame so that case is safe to reduce.

I haven't determined all the data points worth tracking yet. And I haven't yet determined how best to crunch the information.

This sort of thing takes a lot of time to churn through, and I'm just getting started. That's why I'm putting it out there now. Maybe someone has already done something like this and is willing to share their findings? Or perhaps somebody has ideas on what to look for and how to streamline the process? And maybe others would be able to take this method or some variation of it and use it to great effect in their own development process. etc...

STC

[jhellis3]

And by optimize I mean trying to find the best conditions in which to apply reductions.

You may want to approach it from the other direction; LMR everything and try to find what not to reduce.

[zd3nik]

And by optimize I mean trying to find the best conditions in which to apply reductions.

You may want to approach it from the other direction; LMR everything and try to find what not to reduce.

That's essentially what I'm doing. I do a reduced depth search on everything. But in order to know whether it was good or bad I also do a full depth search so I have something to compare the reduced depth results against.

[jhellis3]

The important thing to remember is to measure strength/time and not strength/ply.

[Ferdy]

I've wasted more time than I care to think about trying to optimize LMR. And by optimize I mean trying to find the best conditions in which to apply reductions.

There are a lot of different LMR ideas and implementations out there. Naturally no single LMR implementation is going to be the optimal choice for every engine. But I would like to find a solid base of dos and don'ts if possible.

So today I started doing some number crunching to try and gain some new insight into which moves to reduce and when. Here's how I've started the data collection process:

Code: Select all

for (move = 2nd move to last move) {
  if (not in check and depth > 1 and move is not cap or promo)
    increment column A
    if null window search with reduced depth > alpha
      increment column B
    if null window search with full depth > alpha
      increment column C
  endif
  ... cary on with normal search handling ... 
}

And here is an example of the numbers I'm collecting (so far). This example from a 10 ply search on startpos:

Code: Select all

Material(0),    4031,   100%
Material(1),    4031,   100%

A=Candidates
B=Reduced Depth Search > alpha
C=Full Depth Search > alpha

Data Point,  A,        B,    C
Candidates,  161178,   471,  550
SSE < 0,     47679,    15,   12 
SSE <= 0,    107496,   45,   27 
SSE > 0,     53682,    426,  523
SSE >= 8,    42812,    406,  491
SSE >= 16,   10893,    292,  411
IsKiller,    6025,     161,  257
Hist < 0,    156234,   245,  286
Hist <= 0,   156374,   246,  288
Hist > 0,    4804,     225,  262
Hist >= 8,   4544,     219,  258
Hist >= 16,  4272,     210,  248
Gives Check, 1234,     11,   10
Pawn Push,   40215,    85,   104
Pawn Lung,   33855,    81,   91
Knight Move, 29621,    194,  270
Bishop Move, 22971,    46,   27
Rook Move,   4560,     0,    0
Queen Move,  22829,    65,   56
King Move,   7127,     0,    2
0-0,         120,      0,    2
0-0-0,       0,        0,    0
MvNum 2,     2711,     70,   127
MvNum 3,     5007,     145,  196
MvNum 4,     5448,     74,   87
MvNum 5,     5622,     43,   39
MvNum 6,     5792,     23,   10
MvNum 7,     5832,     13,   14
MvNum 8,     5828,     21,   7
MvNum 9+,    124938,   82,   70

I'm hoping to uncover useful trends. For example, say moves of type X in the middlegame have a higher than average alpha increase rate so it's best *not* to reduce that case. Or column B and C values are often similar for moves of type Y during an endgame so that case is safe to reduce.

I haven't determined all the data points worth tracking yet. And I haven't yet determined how best to crunch the information.

This sort of thing takes a lot of time to churn through, and I'm just getting started. That's why I'm putting it out there now. Maybe someone has already done something like this and is willing to share their findings? Or perhaps somebody has ideas on what to look for and how to streamline the process? And maybe others would be able to take this method or some variation of it and use it to great effect in their own development process. etc...

STC

Interesting stuff. I am looking at the following as an example.

Code: Select all

MvNum 4,     5448,     74,   87

Out of that 74 how many are killers? How many are piece_type moves? what is its history or range of history score? Also are those 74 found in 87?
Other info to record is the value of alpha, and the reduced depth and the full depth values, the phase of the game, the presence of Queen, the presence of passer, the king safety value, still based on that MvNum 4 criteria.

What is SSE?

[AlvaroBegue]

What is SSE?

I'm sure he meant SEE. I've made that mistake myself.

[zd3nik]

What is SSE?

I'm sure he meant SEE. I've made that mistake myself.

Yep, SEE - Static Exchange Evaluation.

[zd3nik]

Interesting stuff. I am looking at the following as an example.

Code: Select all

MvNum 4,     5448,     74,   87

Out of that 74 how many are killers? How many are piece_type moves? what is its history or range of history score? Also are those 74 found in 87?
Other info to record is the value of alpha, and the reduced depth and the full depth values, the phase of the game, the presence of Queen, the presence of passer, the king safety value, still based on that MvNum 4 criteria.

Hi Ferdy, thanks for the suggestions. I hadn't considered tracking reduction depth and king safety. Those would both be very relevant.

Originally I was thinking of trying to pick out some specific combinations of attributes to track, like: mvNum + killer + hist score/range + game phase, etc. But quickly realized there were too many combinations to even consider trying to pick out the most relevant ones. So I've changed the model to something more like a typical clustering/classification feature vector. I kicked off a 20 game round robin last night and set one of the engines to record a feature vector for every reduced depth and full depth alpha increase. Here are the features I picked out and a couple example vectors:

id, mvNum, pvNode, color, depth, countMe, countOp, pawnMe, pawnOp, knightMe, knightOp, bishopMe, bishopOp, rookMe, rookOp, queenMe, queenOp, standPat, materialMe, materialOp, mvScore, histScore, killer, startPassed, endPassed, mvType, pcType, mvDist, mvDir, distOpKing, distMyKing, toRank
9, 10, 1, 1, 4, 6, 6, 7, 7, 1, 2, 2, 1, 2, 2, 1, 1, 16, 3617, 3617, 0, 35, 0, 0, 0, 3, 3, 2, 16, 4, 3, 3
74, 1, 0, 0, 4, 6, 6, 7, 7, 2, 1, 1, 2, 2, 2, 1, 1, 40, 3617, 3617, 66, 64, 1, 0, 0, 7, 12, 2, 1, 7, 2, 0

id isn't a feature value, it's a unique identifier for the postion. This is how reduced depth results and full depth results would be correlated.

mvNum is the move number within the generated move list, not the game move number. I opted to leave out game move number because I think material sum would be a more robust indicator of game stage. Game move number would just be noise in most cases I think.

Here is how the values are obtained (in case some of the labels aren't clear):

Code: Select all

const int stats[] = {
        moveIndex,
        pvNode,
        color,
        depth,
        pieceCount[color],
        pieceCount[!color],
        pieceCount[color|Pawn],
        pieceCount[(!color)|Pawn],
        pieceCount[color|Knight],
        pieceCount[(!color)|Knight],
        pieceCount[color|Bishop],
        pieceCount[(!color)|Bishop],
        pieceCount[color|Rook],
        pieceCount[(!color)|Rook],
        pieceCount[color|Queen],
        pieceCount[(!color)|Queen],
        standPat,
        (&#40;material&#91;color&#93; << 6&#41; >> 6&#41;,
        (&#40;material&#91;!color&#93; << 6&#41; >> 6&#41;,
        (&#40;move->GetScore&#40;) << 3&#41; >> 3&#41;,
        ((_hist&#91;move->GetHistoryIndex&#40;)&#93; << 3&#41; >> 3&#41;,
        IsKiller&#40;*move&#41;,
        passers&#91;move->GetFromName&#40;)&#93;,
        child->passers&#91;move->GetToName&#40;)&#93;,
        move->GetType&#40;),
        move->GetPc&#40;),
        move->GetFrom&#40;).DistanceTo&#40;move->GetTo&#40;)),
        move->GetFrom&#40;).DirectionTo&#40;move->GetTo&#40;)),
        move->GetTo&#40;).DistanceTo&#40;king&#91;!color&#93;),
        move->GetTo&#40;).DistanceTo&#40;king&#91;color&#93;),
        &#40;color ? &#40;7 - move->GetTo&#40;).Y&#40;)) &#58; move->GetTo&#40;).Y&#40;))
      &#125;;

On materialMe/Op, mvScore, and histScore I round the values into buckets. materialMe/Op is rounded to nearest multiple of 64. mvScore and histScore nearest multiple of 8 since the engine I'm doing this analysis with uses multiple of 8 positional scoring.

Anyway, now I will try doing some cluster analysis (such as kmeans and kmedoids clustering) on these feature vectors to try and find strong patterns. But I won't have time to start on it until next weekend probably.

I'll add your suggested features (reduction depth, king safety value) and create a new data set from a larger round robin. And I'll report back what I'm able to find after a little data mining.

If anyone would like the feature vectors I'd be happy to share them. I'd attach them to this post, but I don't see an option for adding attachments...

STC

PS.

I'm fairly hopeful this will yield at least a small amount of insight. For example, I watched the data for a couple games and noticed a pattern right away. Reduced depth queen moves when there are a lot of pieces still on the board almost always yield the same number (or more) alpha increases as full depth searches. And this seems to make sense. The queen is a very efficient attacking piece an doesn't require a lot of maneuvering to create a threat when there are supporting troupes on the board. So if moving her is going to have an effect, it will likely be just as effective at a reduced depth.

[zd3nik]

Well, I didn't find anything along the lines of what I wanted to find. There are no clearly identifiable patterns in which there's a higher than average number of fail lows or alpha increases.

However:

1. I only used data from 2 games (my laptop doesn't have enough memory to process data from more than 2 games). With such a small sample these results are hardly conclusive. I'll need to capture data from thousands of games and process them in batches. But given the amount of time this takes to do this I doubt I'll pursue it.

2. I did notice one very consistent pattern. The chess engine I'm using for this test is Clubfoot and it's history values for nearly all moves is consistently near the minimum allowed in it's history scheme. So Clubfoot's history values contain basically useless information.

Today I revised Clubfoot's history scheme to something new and so far the results look good. It's achieving higher search depths without any obvious tactical degradation. And 7 games into a 100 game round-robin the updated version of Clubfoot is 50/50 with an engine that Clubfoot usually only scores about 1 win every 10 games. That's not conclusive with so few games played out so far, but it's promising.

If the history heuristic change turns out to be an improvement then perhaps this experiment wasn't a complete waste of time.

STC