Is LMR Sound.

[Don]

Actually I do not understand LMR. LMR depends on good move ordering. But good move ordering costs a lot of CPU Time. If move ordering is not perfect than the search depth of at least one move will be reduced while it shouldn't.

This should be:

If move ordering is not perfect and alfa-beta search algorithm is used, then the search depth of at least one move will be reduced while it shouldn't, if no fail-high is encountered before that move is reached.

So how big is the chance that a fail-high is encountered before a move is reduced by LMR ? At the root level there is never a fail-high when you start with alfa = -infinity, beta = infinity.

I did a study on this once, where I basically turned off LMR and simply noted the move number of the BEST move, whether it was a cutoff or not and kept statistics on it.

The numbers were impressive. The first move was the best move a surprisingly high number of times but if you combined the first N it was ridiculously high. And there was a nice progression downward, so that what the first move didn't catch, the second move caught "most" of the time, then the 3rd move and so on.

I don't have the numbers but they are buried in my email to Larry and this was a few years ago. But it is trivial to reproduce this study, why don't you give it a try?

I get the impression that you want this to be perfect and that you think it's a complete failure if you reduce the wrong move. If you are thinking that way then forget about building a strong program because EVERYTHING in computer chess is about amortized risk. If you extend a move, you are wasting time - how do you know you are extending the right move? Check extensions slow a chess program down and could prevent you from seeing tactics that don't involve any checks, what do you do about that? What about null move pruning? It's amortized risk.

What about your evaluation function itself? Do you have mobility? What if mobility is completely irrelevant for some piece? Once we played against Joel Benjamin in the hotel room (years ago with a different program) and my program place the rook on the 7th rank when it was useless. Should I remove the rook to the 7th bonus? (These days it's a much better rule, but it's still broken as are all positional heuristics in chess engines.)

The only thing you can reasonably do it to simply TRY things and see if they work. Take an idea that seems to make sense and TRY it. If it doesn't work then think about what it's weakeness are and how it can be improved. But the number one consideration is that everything in computer chess is a calculated risk, especially when it comes to pruning and reductions.

Incidentally, it's that way with people too. They miss things because their search is highly directed and highly selective. Do you think they should stop using a selective search?

Don

If move ordering is far from perfect, which normally is the case, and alfa-beta search algorithm is used, then the search depth of some moves will be reduced while it shouldn't, if no fail-high is encountered before that move is reached.

Yes, that is exactly how any speculative algorithm works.

Trial and Error method is an inefficient method of doing things if there are a lot of combinations.

If possible it's better to use a search direction [or gradient?].

I'm not sure what you are suggesting here but in Komodo and as well all strong programs there are untold trillions of combinations of weights and parameters that could be tested.

But trial and error combined with intuition and common sense for testing ideas is about the best you can hope for (well, I suppose you can hope for anything you want.)

Are you suggesting a specific algorithm based a "search direction or gradient?" The way we do LMR is probably FAR from optimal and I'm open to any ideas. We know that some programs modify the number of full depth moves and the reduction schedule based on stage of game and other things and we have tried many things that we think makes sense but doesn't actually help. Have you ever heard the expression, "the proof is in the pudding?"

Don

[Don]

Don,

I think you are wasting you're time here. We all know that and Henk does not listen.

Thomas ...

I'm not going to cut someone off who is asking questions, even if some of them seem stupid. You can see that he wants to learn or he would not be asking questions.

There was probably a time you and I had to struggle to wrap our heads around some concept too - that's just part of the process.

By the way, he has not been nasty to us, but we have been nasty to him.

Don

[tpetzke]

Hi Don,

the question itself is not stupid. And I'm willing to help him as well (and I did or at least tried).

But the question was answered, not only by one and not only once. Now it would be time to start the IDE, write some code to try things out.

If this triggers then more questions, fine. But without some own effort you don't wrap your head around a concept. Asking questions is just not enough.

Thomas...

[Don]

Hi Don,

the question itself is not stupid. And I'm willing to help him as well (and I did or at least tried).

But the question was answered, not only by one and not only once. Now it would be time to start the IDE, write some code to try things out.

I took that differently than you did. Sometime people play "devils advocate" as a way to get more information and to me it was clear he was considering everything we said.

But I can see how you might take his response as ignoring your suggestions.

If this triggers then more questions, fine. But without some own effort you don't wrap your head around a concept. Asking questions is just not enough.

Thomas...

[hgm]

So does it make sense to apply LMR when moves are ordered random(ly) ?

Ordering moves randomly is a very bad idea for other reasons than deciding which should be reduced. You want moves that have a high chance to be cut-moves ordered first.

Micro-Max comes close to it, however: its only move sorting consists of playing the hash move first. All other moves are played in move-generation order, which has no correlation with their quality. Captures have a higher chance of becoming hash moves, however, as micro-Max does IID in any node, and that always starts with a search at QS level, involving only captures. And that again always starts with the MVV/LVA-wise best capture.

But all the other moves are searched in arbitrary order. So it would not make sense to let LMR decisions depend on order. So it doesn't; micro-Max simply applies LMR all moves except captures and Pawn pushes. This caused a significant strength boost compared to not doing LMR.

[Henk]

Actually I do not understand LMR. LMR depends on good move ordering. But good move ordering costs a lot of CPU Time. If move ordering is not perfect than the search depth of at least one move will be reduced while it shouldn't.

This should be:

If move ordering is not perfect and alfa-beta search algorithm is used, then the search depth of at least one move will be reduced while it shouldn't, if no fail-high is encountered before that move is reached.

So how big is the chance that a fail-high is encountered before a move is reduced by LMR ? At the root level there is never a fail-high when you start with alfa = -infinity, beta = infinity.

I did a study on this once, where I basically turned off LMR and simply noted the move number of the BEST move, whether it was a cutoff or not and kept statistics on it.

The numbers were impressive. The first move was the best move a surprisingly high number of times but if you combined the first N it was ridiculously high. And there was a nice progression downward, so that what the first move didn't catch, the second move caught "most" of the time, then the 3rd move and so on.

I don't have the numbers but they are buried in my email to Larry and this was a few years ago. But it is trivial to reproduce this study, why don't you give it a try?

I get the impression that you want this to be perfect and that you think it's a complete failure if you reduce the wrong move. If you are thinking that way then forget about building a strong program because EVERYTHING in computer chess is about amortized risk. If you extend a move, you are wasting time - how do you know you are extending the right move? Check extensions slow a chess program down and could prevent you from seeing tactics that don't involve any checks, what do you do about that? What about null move pruning? It's amortized risk.

What about your evaluation function itself? Do you have mobility? What if mobility is completely irrelevant for some piece? Once we played against Joel Benjamin in the hotel room (years ago with a different program) and my program place the rook on the 7th rank when it was useless. Should I remove the rook to the 7th bonus? (These days it's a much better rule, but it's still broken as are all positional heuristics in chess engines.)

The only thing you can reasonably do it to simply TRY things and see if they work. Take an idea that seems to make sense and TRY it. If it doesn't work then think about what it's weakeness are and how it can be improved. But the number one consideration is that everything in computer chess is a calculated risk, especially when it comes to pruning and reductions.

Incidentally, it's that way with people too. They miss things because their search is highly directed and highly selective. Do you think they should stop using a selective search?

Don

If move ordering is far from perfect, which normally is the case, and alfa-beta search algorithm is used, then the search depth of some moves will be reduced while it shouldn't, if no fail-high is encountered before that move is reached.

Yes, that is exactly how any speculative algorithm works.

Trial and Error method is an inefficient method of doing things if there are a lot of combinations.

If possible it's better to use a search direction [or gradient?].

I'm not sure what you are suggesting here but in Komodo and as well all strong programs there are untold trillions of combinations of weights and parameters that could be tested.

But trial and error combined with intuition and common sense for testing ideas is about the best you can hope for (well, I suppose you can hope for anything you want.)

Are you suggesting a specific algorithm based a "search direction or gradient?" The way we do LMR is probably FAR from optimal and I'm open to any ideas. We know that some programs modify the number of full depth moves and the reduction schedule based on stage of game and other things and we have tried many things that we think makes sense but doesn't actually help. Have you ever heard the expression, "the proof is in the pudding?"

Don

Conjugate gradient method only gives local maxima. so that does not help when you want to find global maxima. Genetic algorithm gives a local maximum too. Simulated annealing is too slow. Maybe iterating over all local maxima until you get a global maximum ?

Requirement: all information must be enclosed in the parameters.
When using neural networks that means (nr of layers, nr of neurons per layer, weight 0 weigh 1 ... )

How big the global maximum (ELO rating) will be can be estimated.

The problem might be lack of computer power, time, money.

A very quick test is necessary for each trial (parameters) otherwise you may wait for years, but maybe in the meantime better solutions are reported by the optimizer.

[Henk]

(...)
My fail high condition is

if (score > upperbound)

Is that last condition ok?(...)

No the condition should be:

Code: Select all

if (score >= upperbound)

It does make a difference.

As I said you need a better understanding of the basics.

Steve

if I change the condition into score >= upperbound
other conditions must be changed too:
for instance:

score = -SelectQuiescence(depth - 100, -Value, -Value);
if (score > Value)
{
score = -SelectQuiescence(depth - 100, -ub, -lb);
}

must be changed into (score >= Value)

...

Yes, you must make it right.

Remember this, if the score is >= beta it's not an accurate score, it's a lower bound. The "real" score could be beta or it could be higher.

If the score is <= alpha it's also not necessarily the precise score, it's an upper bound. The "real" score could be alpha or it could be lower.

A zero width window is alpha = beta - 1 - it's zero width because there can be no integer scores between them.

If you are having issues put some asserts in your code, such as:

assert(alpha < beta);

You may or many not do the >= comparison of course depending on the context, but a fail low is alway <= alpha and a fail high is always >= beta.

You may adjust alpha for a given node during a search, in which case you might say,

if ( score > alpha ) alpha = score;

You would do that test AFTER testing for a beta cutoff:

if (score >= beta) return score;

At least this should be changed:

score = -QuiescenceSearch(depth - 100, -Value, -Value);
if (score > Value && score < ub)
{
score = -QuiescenceSearch(depth - 100, -ub, -lb);
}

to make it look like PVS or NegaScout

[Henk]

(...)
My fail high condition is

if (score > upperbound)

Is that last condition ok?(...)

No the condition should be:

Code: Select all

if (score >= upperbound)

It does make a difference.

As I said you need a better understanding of the basics.

Steve

if I change the condition into score >= upperbound
other conditions must be changed too:
for instance:

score = -SelectQuiescence(depth - 100, -Value, -Value);
if (score > Value)
{
score = -SelectQuiescence(depth - 100, -ub, -lb);
}

must be changed into (score >= Value)

...

Yes, you must make it right.

Remember this, if the score is >= beta it's not an accurate score, it's a lower bound. The "real" score could be beta or it could be higher.

If the score is <= alpha it's also not necessarily the precise score, it's an upper bound. The "real" score could be alpha or it could be lower.

A zero width window is alpha = beta - 1 - it's zero width because there can be no integer scores between them.

If you are having issues put some asserts in your code, such as:

assert(alpha < beta);

You may or many not do the >= comparison of course depending on the context, but a fail low is alway <= alpha and a fail high is always >= beta.

You may adjust alpha for a given node during a search, in which case you might say,

if ( score > alpha ) alpha = score;

You would do that test AFTER testing for a beta cutoff:

if (score >= beta) return score;

At least this should be changed:

score = -QuiescenceSearch(depth - 100, -Value, -Value);
if (score > Value && score < ub)
{
score = -QuiescenceSearch(depth - 100, -ub, -lb);
}

to make it look like PVS or NegaScout

Ok

score = -QuiescenceSearch(depth - 100, -Value-1, -Value);


I just forget Negascout and PVS I use for now NegaMax which seems simpler but I got an out of memory bug. I stop reporting, it makes no sense. I cannot make any valid statements.

[Don]

(...)
My fail high condition is

if (score > upperbound)

Is that last condition ok?(...)

No the condition should be:

Code: Select all

if (score >= upperbound)

It does make a difference.

As I said you need a better understanding of the basics.

Steve

if I change the condition into score >= upperbound
other conditions must be changed too:
for instance:

score = -SelectQuiescence(depth - 100, -Value, -Value);
if (score > Value)
{
score = -SelectQuiescence(depth - 100, -ub, -lb);
}

must be changed into (score >= Value)

...

Yes, you must make it right.

Remember this, if the score is >= beta it's not an accurate score, it's a lower bound. The "real" score could be beta or it could be higher.

If the score is <= alpha it's also not necessarily the precise score, it's an upper bound. The "real" score could be alpha or it could be lower.

A zero width window is alpha = beta - 1 - it's zero width because there can be no integer scores between them.

If you are having issues put some asserts in your code, such as:

assert(alpha < beta);

You may or many not do the >= comparison of course depending on the context, but a fail low is alway <= alpha and a fail high is always >= beta.

You may adjust alpha for a given node during a search, in which case you might say,

if ( score > alpha ) alpha = score;

You would do that test AFTER testing for a beta cutoff:

if (score >= beta) return score;

At least this should be changed:

score = -QuiescenceSearch(depth - 100, -Value, -Value);
if (score > Value && score < ub)
{
score = -QuiescenceSearch(depth - 100, -ub, -lb);
}

to make it look like PVS or NegaScout

Ok

score = -QuiescenceSearch(depth - 100, -Value-1, -Value);


I just forget Negascout and PVS I use for now NegaMax which seems simpler but I got an out of memory bug. I stop reporting, it makes no sense. I cannot make any valid statements.

If you want to avoid bugs, pass -beta, -alpha to the search. If you are using a window, first set up the window (just to avoid bugs) in two variables to make it crystal clear, the swap positions and negate them:

int lower = beta-1;
int uppper = beta;

score = -QuiescenceSearch(depth - 100, -upper, -lower );
if (score >= upper) { fail high cutoff }

I think this is wrong though:

score = -QuiescenceSearch(depth - 100, -Value-1, -Value);

I assume value is beta so you want to pass (value-1, value) which in negamax format would be:

score = -Quies( ...., -value, -(value-1) )

You want it to fail high if score >= value. Note the use of parenthesis because -value-1 is not the same as -(value-1)

Like I say, until this becomes second nature to you just set it up in variables first then pass the variables reversed and negated.

Don

[petero2]

I made a mistake:

lowerbound = alfa;
upperbound = beta;

My fail high condition is

if (score > upperbound)

Is that last condition ok?

That depends on what the rest of your search algorithm does.

The key idea in the alpha-beta algorithm is that you only need to know the exact score if the score is inside a certain range. Classically this range is defined as alpha < score < beta. However you could also make the substitution:

Code: Select all

minExact = alpha + 1
maxExact = beta - 1

and define the range as minExact <= score <= maxExact. (This assumes that the scores are integers, which is true in all chess programs I know of.)

A very simplified alpha-beta algorithm with the classical range definition could look like this:

Code: Select all

int search(int alpha, int beta) {
  for (all moves) {
    makeMove();
    int nextAlpha = -beta;
    int nextBeta = -alpha;
    score = -search(nextAlpha, nextBeta);
    unMakeMove();
    if (score > alpha) {
      alpha = score;
      if (score >= beta)
        return score;
    }
  }
  return alpha;
}

By making the above substitutions, the code would become:

Code: Select all

int search(int alpha, int beta) {
  return search2(alpha+1, beta-1);
}

int search2(int minExact, int maxExact) {
  for (all moves) {
    makeMove();
    int nextMinExact = -maxExact;
    int nextMaxExact = -minExact;
    score = -search2(nextMinExact, nextMaxExact);
    unMakeMove();
    if (score >= minExact) {
      minExact = score+1;
      if (score > maxExact)
        return score;
    }
  }
  return minExact-1;
}

I don't think there is any technical reason to prefer one implementation over the other. They would both search the exact same tree and produce the exact same score.

The search2 function does contain two additional arithmetic operations though, score+1 and minExact-1. A real implementation would likely want to test if the current range is a null window. This test is (beta<=alpha+1) in the classical implementation, but would become (maxExact<minExact) in the alternative implementation, so it would save one arithmetic operation. Anyway, I don't think the speed impact of these arithmetic operations would be measurable.

However there is a big practical reason to use the classical implementation, because that is what all existing literature I know of is using.