move count based pruning

[zamar]

(1) each move has features that can be analyzed to determine whether or not it should be searched at all, or whether or not it should be reduced (or extended). This characteristic is independent of where the move gets ordered. Yes, moves near the front of the list should be better than moves near the back. But does the _position_ in the list mean anything other than the last move ought to be worse than the first? By how much is important, but not considered when just using a move's position.

(2) The more moves you search at a node, the more likely this node is an ALL node., The idea YBW parallel search is based on, in fact, except that YBW is extremely conservative and assumes that after one move has been searched without a fail-high, this is an ALL node. And from measuring, we know this is correct somewhere around 90% of the time. The more moves you search at a node, the higher this percentage will go (if there are 40 moves, and you search just 1 and don't get a fail-high, then 90% of the time on average, you are not going to get a fail-high at all. If, instead, you search the first 5 moves, then that 90% will rise significantly. But not to 100% You only get to 100% if you search every move before declaring this is an ALL node.

I think all posters agree that optimal solution for LMR/LMP is hybrid of (1) & (2) because both provide important statistical information.

In fact Stockfish uses (1) for LMP, it has certain classes of moves which it refuses to prune (castling moves and moves which some way prevents threatmove found through null move search)

But for LMR it is much more difficult to find those move classes to make (1) work. How could you identify a potential noncapturing move which cut-offs at normal depth and doesn't cut-off at reduced depth. This is really the critical question and I don't have any clue where to start... All ideas are welcomed.

[Don]

Bob,

To keep this fairly short I just want to make a single observation which I think you are either missing completely or ignoring.

The value of the moves that you try cannot be considered in isolation - they have CONTEXT. You cannot say move X is a great move without considering the other moves that are available. If a move wins a pawn, but all the other moves deliver checkmate, then the move which wins the pawn is a blunder - a stupid move that should not be considered.

In the context of pruning and reductions, I believe the primary principle that should guide a search is that you only need to include the single best move available. Nothing else matters and anything else that is included beyond this is a complete waste of CPU resources.

Since it is impossible to know for sure that you have included the best move, one must "play it safe" by including other moves, just in case they happen to also be best. What separates the men from the boys is the degree to which you can find a good compromise and not throw out the baby with the bathwater.

Here is a quiz for you:

1. The move e6 wins a pawn. Is it a good move?
2. The move Ng3-h1 puts the knight in the corner. Is it a good move?
3. The move O-O helps develop the rook. Is it a good move?

The answer to every one of these questions should be, "I don't know."

And that would be true even if I supplied more information. For example if I told you the knight on g3 was in no danger, or it was being attacked, the answer is still the same - you cannot tell me if this move is good or bad because you know nothing about the other moves. All of those moves are good if there is nothing better on the board and all of them are bad if something better is available.

So this idea that you can take some move and do some kind of analysis on it to determine if it should be reduced or not sounds like a fantasy to me - or at best a VERY CRUDE measurement. Unless it also considers the other moves available.

A moves position in the move list is a powerful paradigm which indeed considers moves in their proper context. Nobody is going to say it's perfect, it is a crude measurement too. But tell me that you have a program that does not take any crude measurements and I'll call you a liar. I cannot see how this qualifies as being "too crude" but most of the brain-dead evaluations rules in all chess programs (including your programs) are not.

So in my opinion what you are doing is saying that this is crude so it shouldn't be done. That's like saying we should not have pawn structure in our programs because it's a crude measurement.

I know that Crafty has mobility based on giving weights to some squares more than others. I could easily point out major flaws in that system - but I'll bet is still works pretty good doesn't it?

[Don]

(1) each move has features that can be analyzed to determine whether or not it should be searched at all, or whether or not it should be reduced (or extended). This characteristic is independent of where the move gets ordered. Yes, moves near the front of the list should be better than moves near the back. But does the _position_ in the list mean anything other than the last move ought to be worse than the first? By how much is important, but not considered when just using a move's position.

(2) The more moves you search at a node, the more likely this node is an ALL node., The idea YBW parallel search is based on, in fact, except that YBW is extremely conservative and assumes that after one move has been searched without a fail-high, this is an ALL node. And from measuring, we know this is correct somewhere around 90% of the time. The more moves you search at a node, the higher this percentage will go (if there are 40 moves, and you search just 1 and don't get a fail-high, then 90% of the time on average, you are not going to get a fail-high at all. If, instead, you search the first 5 moves, then that 90% will rise significantly. But not to 100% You only get to 100% if you search every move before declaring this is an ALL node.

I think all posters agree that optimal solution for LMR/LMP is hybrid of (1) & (2) because both provide important statistical information.

In fact Stockfish uses (1) for LMP, it has certain classes of moves which it refuses to prune (castling moves and moves which some way prevents threatmove found through null move search)

But for LMR it is much more difficult to find those move classes to make (1) work. How could you identify a potential noncapturing move which cut-offs at normal depth and doesn't cut-off at reduced depth. This is really the critical question and I don't have any clue where to start... All ideas are welcomed.

I think this boils down to a single principle, how certain are we of our decision? Komodo does not reduce certain kinds of moves either, and in principle this is wrong - but we do it because we don't know how to accurately measure it's impact.

Komodo does not reduce captures. But most captures are just stupid blunders! Still, we do not reduce because we are lazy. We don't know how to properly judge whether it's just a blunder or it's a profound move. Captures are disruptive and have complex interactions that are difficult to measure.

I think also that captures tend to have smaller trees, so there is less motivation to attempt speculative pruning.

[bob]

(1) each move has features that can be analyzed to determine whether or not it should be searched at all, or whether or not it should be reduced (or extended). This characteristic is independent of where the move gets ordered. Yes, moves near the front of the list should be better than moves near the back. But does the _position_ in the list mean anything other than the last move ought to be worse than the first? By how much is important, but not considered when just using a move's position.

(2) The more moves you search at a node, the more likely this node is an ALL node., The idea YBW parallel search is based on, in fact, except that YBW is extremely conservative and assumes that after one move has been searched without a fail-high, this is an ALL node. And from measuring, we know this is correct somewhere around 90% of the time. The more moves you search at a node, the higher this percentage will go (if there are 40 moves, and you search just 1 and don't get a fail-high, then 90% of the time on average, you are not going to get a fail-high at all. If, instead, you search the first 5 moves, then that 90% will rise significantly. But not to 100% You only get to 100% if you search every move before declaring this is an ALL node.

I think all posters agree that optimal solution for LMR/LMP is hybrid of (1) & (2) because both provide important statistical information.

In fact Stockfish uses (1) for LMP, it has certain classes of moves which it refuses to prune (castling moves and moves which some way prevents threatmove found through null move search)

But for LMR it is much more difficult to find those move classes to make (1) work. How could you identify a potential noncapturing move which cut-offs at normal depth and doesn't cut-off at reduced depth. This is really the critical question and I don't have any clue where to start... All ideas are welcomed.

I think this boils down to a single principle, how certain are we of our decision? Komodo does not reduce certain kinds of moves either, and in principle this is wrong - but we do it because we don't know how to accurately measure it's impact.

Komodo does not reduce captures. But most captures are just stupid blunders! Still, we do not reduce because we are lazy. We don't know how to properly judge whether it's just a blunder or it's a profound move. Captures are disruptive and have complex interactions that are difficult to measure.

I think also that captures tend to have smaller trees, so there is less motivation to attempt speculative pruning.

Some of us _do_ reduce certain types of captures, for the record. Ditto for checks.

[Don]

(1) each move has features that can be analyzed to determine whether or not it should be searched at all, or whether or not it should be reduced (or extended). This characteristic is independent of where the move gets ordered. Yes, moves near the front of the list should be better than moves near the back. But does the _position_ in the list mean anything other than the last move ought to be worse than the first? By how much is important, but not considered when just using a move's position.

(2) The more moves you search at a node, the more likely this node is an ALL node., The idea YBW parallel search is based on, in fact, except that YBW is extremely conservative and assumes that after one move has been searched without a fail-high, this is an ALL node. And from measuring, we know this is correct somewhere around 90% of the time. The more moves you search at a node, the higher this percentage will go (if there are 40 moves, and you search just 1 and don't get a fail-high, then 90% of the time on average, you are not going to get a fail-high at all. If, instead, you search the first 5 moves, then that 90% will rise significantly. But not to 100% You only get to 100% if you search every move before declaring this is an ALL node.

I think all posters agree that optimal solution for LMR/LMP is hybrid of (1) & (2) because both provide important statistical information.

In fact Stockfish uses (1) for LMP, it has certain classes of moves which it refuses to prune (castling moves and moves which some way prevents threatmove found through null move search)

But for LMR it is much more difficult to find those move classes to make (1) work. How could you identify a potential noncapturing move which cut-offs at normal depth and doesn't cut-off at reduced depth. This is really the critical question and I don't have any clue where to start... All ideas are welcomed.

I think this boils down to a single principle, how certain are we of our decision? Komodo does not reduce certain kinds of moves either, and in principle this is wrong - but we do it because we don't know how to accurately measure it's impact.

Komodo does not reduce captures. But most captures are just stupid blunders! Still, we do not reduce because we are lazy. We don't know how to properly judge whether it's just a blunder or it's a profound move. Captures are disruptive and have complex interactions that are difficult to measure.

I think also that captures tend to have smaller trees, so there is less motivation to attempt speculative pruning.

Some of us _do_ reduce certain types of captures, for the record. Ditto for checks.

Which verifies what I said, that I think it's WRONG to not reduce some of those moves. Komodo does not reduce them because we don't know how to safely do it.

So what are your rules for reducing captures and checks?

[bob]

Bob,

To keep this fairly short I just want to make a single observation which I think you are either missing completely or ignoring.

The value of the moves that you try cannot be considered in isolation - they have CONTEXT. You cannot say move X is a great move without considering the other moves that are available. If a move wins a pawn, but all the other moves deliver checkmate, then the move which wins the pawn is a blunder - a stupid move that should not be considered.

In the context of pruning and reductions, I believe the primary principle that should guide a search is that you only need to include the single best move available. Nothing else matters and anything else that is included beyond this is a complete waste of CPU resources.

Since it is impossible to know for sure that you have included the best move, one must "play it safe" by including other moves, just in case they happen to also be best. What separates the men from the boys is the degree to which you can find a good compromise and not throw out the baby with the bathwater.

Here is a quiz for you:

1. The move e6 wins a pawn. Is it a good move?
2. The move Ng3-h1 puts the knight in the corner. Is it a good move?
3. The move O-O helps develop the rook. Is it a good move?

The answer to every one of these questions should be, "I don't know."

And that would be true even if I supplied more information. For example if I told you the knight on g3 was in no danger, or it was being attacked, the answer is still the same - you cannot tell me if this move is good or bad because you know nothing about the other moves. All of those moves are good if there is nothing better on the board and all of them are bad if something better is available.

So this idea that you can take some move and do some kind of analysis on it to determine if it should be reduced or not sounds like a fantasy to me - or at best a VERY CRUDE measurement. Unless it also considers the other moves available.

A moves position in the move list is a powerful paradigm which indeed considers moves in their proper context.

You will have to explain that one to me. I see no "context" other than "this is a move's relative position within the whole group" which doesn't say a thing about whether that move is good, bad, or just plain ugly.

Nobody is going to say it's perfect, it is a crude measurement too. But tell me that you have a program that does not take any crude measurements and I'll call you a liar. I cannot see how this qualifies as being "too crude" but most of the brain-dead evaluations rules in all chess programs (including your programs) are not.

So in my opinion what you are doing is saying that this is crude so it shouldn't be done. That's like saying we should not have pawn structure in our programs because it's a crude measurement.

I know that Crafty has mobility based on giving weights to some squares more than others. I could easily point out major flaws in that system - but I'll bet is still works pretty good doesn't it?

You are sort of getting my main point.

As far as mobility goes, square-by-square is even better, as we did in the last versions of Cray Blitz. We could pull it off with no cost thanks to vectors, which we don't have on Intel. The CB idea would be good on Intel, but it would be expensive, and the cost more than offsets the accuracy gain, because I have tried the CB approach already. It is just too slow. Our current approach is somewhat of an "approximation" that is less costly, and less accurate. But one day, we want to do it accurately, just as I do (as a human). I don't just count squares. I look at how useful the squares are.

But back to the move list order...

Given this:

1. Nxf6
2. Qxe6
3. h7
4. Nf3
5. d4
6. Qxa7

Can you tell anything about which moves are good and which are bad, just based on the above "ordering"? I will only say that they are ordered based on a static evaluation. But I am not supplying those scores. So which should be reduced, extended, or left alone?

What if all win material? What if all but Nxf6 lose major material? That's my point. Sorting the moves in order is a good idea (at times) because of alpha/beta pruning. But once sorted, just using the relative position within the list only has one good effect... that being that the more more moves you search in any single node, the more confident you become that it is an ALL node. So yes, in that limited context the idea makes sense. Try to reduce the effort as you become convinced the effort is wasted.

The down side is that you tend to force a node to become an ALL node by doing this, because as you reduce moves you lose the ability to see why the moves are actually better than expected even though they appear at the end of the list according to static criteria.

My point about the "L" in "LMR" is that "L" only addresses the effort issue, and not the accuracy. There must be a better way that addresses both. I've been trying ideas off and on. Some are much worse. A few are just as good. So far, nothing is better. But I'm not going to stop trying, because the current "L" approach has a ton of holes. What if today's 24+ ply searches were _really_ equivalent to 24-ply searches from (say) the 90's??? Those would be seriously strong programs. We've gone from 12 plies to 24 plies, which ought to be worth 1200 Elo. Based on +100 per ply. We are nowhere near that. So there is a lot left to be discovered. We had 2600+ programs in 1994. 16 years and 12 additional plies later, we are seeing maybe 3000 rated programs? We've almost fallen into the Intel approach of 10 years ago where the goal was max mhz, not max instructions per second. Now it is max depth, without regard to the quality that ought to come with such huge depth improvement. Sure it is easier to take the current approach. I'm not willing to copy ip* and friends verbatim, assuming that what they are doing is optimal (or even just good). My intent is to test ideas with games, and decide what works, what does not, and proceed from there.

I simply raised an issue that is significant with this "move list position affecting pruning/reduction" discussion. I may well die not having made any progress. But it won't be from not looking. Just not succeeding.

[bob]

(1) each move has features that can be analyzed to determine whether or not it should be searched at all, or whether or not it should be reduced (or extended). This characteristic is independent of where the move gets ordered. Yes, moves near the front of the list should be better than moves near the back. But does the _position_ in the list mean anything other than the last move ought to be worse than the first? By how much is important, but not considered when just using a move's position.

(2) The more moves you search at a node, the more likely this node is an ALL node., The idea YBW parallel search is based on, in fact, except that YBW is extremely conservative and assumes that after one move has been searched without a fail-high, this is an ALL node. And from measuring, we know this is correct somewhere around 90% of the time. The more moves you search at a node, the higher this percentage will go (if there are 40 moves, and you search just 1 and don't get a fail-high, then 90% of the time on average, you are not going to get a fail-high at all. If, instead, you search the first 5 moves, then that 90% will rise significantly. But not to 100% You only get to 100% if you search every move before declaring this is an ALL node.

I think all posters agree that optimal solution for LMR/LMP is hybrid of (1) & (2) because both provide important statistical information.

In fact Stockfish uses (1) for LMP, it has certain classes of moves which it refuses to prune (castling moves and moves which some way prevents threatmove found through null move search)

But for LMR it is much more difficult to find those move classes to make (1) work. How could you identify a potential noncapturing move which cut-offs at normal depth and doesn't cut-off at reduced depth. This is really the critical question and I don't have any clue where to start... All ideas are welcomed.

I think this boils down to a single principle, how certain are we of our decision? Komodo does not reduce certain kinds of moves either, and in principle this is wrong - but we do it because we don't know how to accurately measure it's impact.

Komodo does not reduce captures. But most captures are just stupid blunders! Still, we do not reduce because we are lazy. We don't know how to properly judge whether it's just a blunder or it's a profound move. Captures are disruptive and have complex interactions that are difficult to measure.

I think also that captures tend to have smaller trees, so there is less motivation to attempt speculative pruning.

Some of us _do_ reduce certain types of captures, for the record. Ditto for checks.

Which verifies what I said, that I think it's WRONG to not reduce some of those moves. Komodo does not reduce them because we don't know how to safely do it.

So what are your rules for reducing captures and checks?

For checks, if SEE < 0 I don't extend, and do reduce it. Was worth several Elo as posted here a month or so ago. Last version released (23.3) was about +60 better than 23.2, this was one of the useful changes... For captures I believe it is the same idea. If SEE is < 0, then that move is searched after good captures, killers, etc, and is subject to reduction. Still got to tweak the reduction for passed pawns also, probably the same idea when I get to testing it.

[Don]

Bob,

To keep this fairly short I just want to make a single observation which I think you are either missing completely or ignoring.

The value of the moves that you try cannot be considered in isolation - they have CONTEXT. You cannot say move X is a great move without considering the other moves that are available. If a move wins a pawn, but all the other moves deliver checkmate, then the move which wins the pawn is a blunder - a stupid move that should not be considered.

In the context of pruning and reductions, I believe the primary principle that should guide a search is that you only need to include the single best move available. Nothing else matters and anything else that is included beyond this is a complete waste of CPU resources.

Since it is impossible to know for sure that you have included the best move, one must "play it safe" by including other moves, just in case they happen to also be best. What separates the men from the boys is the degree to which you can find a good compromise and not throw out the baby with the bathwater.

Here is a quiz for you:

1. The move e6 wins a pawn. Is it a good move?
2. The move Ng3-h1 puts the knight in the corner. Is it a good move?
3. The move O-O helps develop the rook. Is it a good move?

The answer to every one of these questions should be, "I don't know."

And that would be true even if I supplied more information. For example if I told you the knight on g3 was in no danger, or it was being attacked, the answer is still the same - you cannot tell me if this move is good or bad because you know nothing about the other moves. All of those moves are good if there is nothing better on the board and all of them are bad if something better is available.

So this idea that you can take some move and do some kind of analysis on it to determine if it should be reduced or not sounds like a fantasy to me - or at best a VERY CRUDE measurement. Unless it also considers the other moves available.

A moves position in the move list is a powerful paradigm which indeed considers moves in their proper context.

You will have to explain that one to me. I see no "context" other than "this is a move's relative position within the whole group" which doesn't say a thing about whether that move is good, bad, or just plain ugly.

I'm trying to come up with a clear way to express the concept. We are each looking at this differently. You see moves as "good" or "bad" in isolation. For instance if I gave you a position and asked you whether Ng5 was a good move, how do you judge that? I think if the move hangs the knight you call it "bad" and if it captures an undefended pawn you call it "good."

But I say it's undefined unless I am allowed to also consider the other moves too. If Ng5 hangs the knight, but opens up the king and every other moves leads to checkmate, then Ng5 is a GOOD move. Do you see the difference now?

Likewise, if Ng5 wins a pawn outright you call it "GOOD", but if some other moves wins a queen outright, I call Ng5 a BLUNDER! There is a world of difference between your simplistic definition and this better definition.

You cannot just look at one move in isolation and call it good or bad without knowing about all the others. That is what I mean when I use the term, "context." You judge moves without providing any context but I feel that without context you cannot judge the value of the moves.

I think I know why you have this issue. Most of the time if a move wins something it will still come out as good even by my definition. And if a move places a piece en-prise it will usually be bad by my definition. Usually is the operative word here. Usually, but not always. So it's easy to get lazy and just consider those definitions as absolute but they are not.

Suppose you are in a position where every single move loses material? You would simplistically label them ALL as "bad." But any good chess player in this kind of position would still try to maximize his chances by choosing the move which gives him the best chance of surviving, even if that chance was slim. So taken in the proper CONTEXT, when presented with a list of moves (whether in a winning or losing or even position) you can always label some of them good and the rest bad. If you do this well, spend most of the effort on the "good" moves, then you can have a very good search.

Nobody is going to say it's perfect, it is a crude measurement too. But tell me that you have a program that does not take any crude measurements and I'll call you a liar. I cannot see how this qualifies as being "too crude" but most of the brain-dead evaluations rules in all chess programs (including your programs) are not.

So in my opinion what you are doing is saying that this is crude so it shouldn't be done. That's like saying we should not have pawn structure in our programs because it's a crude measurement.

I know that Crafty has mobility based on giving weights to some squares more than others. I could easily point out major flaws in that system - but I'll bet is still works pretty good doesn't it?

You are sort of getting my main point.

As far as mobility goes, square-by-square is even better, as we did in the last versions of Cray Blitz. We could pull it off with no cost thanks to vectors, which we don't have on Intel. The CB idea would be good on Intel, but it would be expensive, and the cost more than offsets the accuracy gain, because I have tried the CB approach already. It is just too slow. Our current approach is somewhat of an "approximation" that is less costly, and less accurate. But one day, we want to do it accurately, just as I do (as a human). I don't just count squares. I look at how useful the squares are.

But back to the move list order...

Given this:

1. Nxf6
2. Qxe6
3. h7
4. Nf3
5. d4
6. Qxa7

Can you tell anything about which moves are good and which are bad, just based on the above "ordering"?

Absolutely! Assuming that your move ordering is perfect, I can say with certainty that the FIRST move is not just good, but it's the best move!

If your move ordering is good but not perfect, I can say that the first move you listed is with high probably a good move, and more likely than all the others to be the best move.

If you believe the move order is good, I can with VERY HIGH confidence say the best move is with very high probability one of the first N moves!

I think your hangup here is that I don't have some kind of "score" so I cannot tell you if Qxa7 is just as good (or almost as good) as Nxf6. But I'm telling you that IT DOES NOT MATTER! If Qxa7 is just as good as Nxf6 then does it matter which one I search? If I have searched the best move, then the others are completely irrelevant.

I think you have this idea that if there are a lot of good moves that they all MUST be searched. Or that if every move is bad you do not need to search them at all. But that is not the case. In tree search what is important is only that you search the best move of the choices you have. If they are all losing moves you STILL have to search the best one or you will not have an accurate picture of how good the parent position is. And it's just as important that you make sure you have not overlooked the best one, even if none of them are particularly appealing.

I think you believe that if a move is losing it should not be searched, but that is erroneous. A move should not be searched if it's WORSE than the best move, but it's absolute value is not relevant.

Let me put it another way. If you suspect that EVERY moves drops material, you still have to search the position in order for the alpha/beta procedure to properly score ancestor positions. You cannot just say, "all of these moves stink so I don't have to try any of them."

I will only say that they are ordered based on a static evaluation. But I am not supplying those scores. So which should be reduced, extended, or left alone?

The answer depends on my confidence in your move ordering scheme, and static move ordering is not very good, so I would have to say that a lot of them should be searched.

But the principle is the same, I would probably try the first N moves and reduce the rest, but N would be high because the move ordering is pretty lousy.

What if all win material? What if all but Nxf6 lose major material? That's my point.

How come you think you can now count moves and compare them against each other? In your scheme it should not matter how many win or lose material. It either wins material or it loses material and that is your criteria for determining whether to reduce or not.

What do you do in the case where ALL moves lose material? Do you reduce every move? What do you do if they ALL win material, do you go brute force on every move?

Sorting the moves in order is a good idea (at times) because of alpha/beta pruning. But once sorted, just using the relative position within the list only has one good effect... that being that the more more moves you search in any single node, the more confident you become that it is an ALL node. So yes, in that limited context the idea makes sense. Try to reduce the effort as you become convinced the effort is wasted.

That's not the main point however. At all nodes you have the best potential for reducing the search.

I think we both want the same thing - to never reduce moves that have a realistic chance of being important. But your criteria should give some weight to the statistical evidence that you can get for free.

The down side is that you tend to force a node to become an ALL node by doing this, because as you reduce moves you lose the ability to see why the moves are actually better than expected even though they appear at the end of the list according to static criteria.

My point about the "L" in "LMR" is that "L" only addresses the effort issue, and not the accuracy. There must be a better way that addresses both. I've been trying ideas off and on. Some are much worse. A few are just as good. So far, nothing is better. But I'm not going to stop trying, because the current "L" approach has a ton of holes. What if today's 24+ ply searches were _really_ equivalent to 24-ply searches from (say) the 90's??? Those would be seriously strong programs. We've gone from 12 plies to 24 plies, which ought to be worth 1200 Elo. Based on +100 per ply. We are nowhere near that. So there is a lot left to be discovered. We had 2600+ programs in 1994. 16 years and 12 additional plies later, we are seeing maybe 3000 rated programs? We've almost fallen into the Intel approach of 10 years ago where the goal was max mhz, not max instructions per second. Now it is max depth, without regard to the quality that ought to come with such huge depth improvement. Sure it is easier to take the current approach. I'm not willing to copy ip* and friends verbatim, assuming that what they are doing is optimal (or even just good). My intent is to test ideas with games, and decide what works, what does not, and proceed from there.

I simply raised an issue that is significant with this "move list position affecting pruning/reduction" discussion. I may well die not having made any progress. But it won't be from not looking. Just not succeeding.

[bob]

Bob,

To keep this fairly short I just want to make a single observation which I think you are either missing completely or ignoring.

The value of the moves that you try cannot be considered in isolation - they have CONTEXT. You cannot say move X is a great move without considering the other moves that are available. If a move wins a pawn, but all the other moves deliver checkmate, then the move which wins the pawn is a blunder - a stupid move that should not be considered.

In the context of pruning and reductions, I believe the primary principle that should guide a search is that you only need to include the single best move available. Nothing else matters and anything else that is included beyond this is a complete waste of CPU resources.

Since it is impossible to know for sure that you have included the best move, one must "play it safe" by including other moves, just in case they happen to also be best. What separates the men from the boys is the degree to which you can find a good compromise and not throw out the baby with the bathwater.

Here is a quiz for you:

1. The move e6 wins a pawn. Is it a good move?
2. The move Ng3-h1 puts the knight in the corner. Is it a good move?
3. The move O-O helps develop the rook. Is it a good move?

The answer to every one of these questions should be, "I don't know."

And that would be true even if I supplied more information. For example if I told you the knight on g3 was in no danger, or it was being attacked, the answer is still the same - you cannot tell me if this move is good or bad because you know nothing about the other moves. All of those moves are good if there is nothing better on the board and all of them are bad if something better is available.

So this idea that you can take some move and do some kind of analysis on it to determine if it should be reduced or not sounds like a fantasy to me - or at best a VERY CRUDE measurement. Unless it also considers the other moves available.

A moves position in the move list is a powerful paradigm which indeed considers moves in their proper context.

You will have to explain that one to me. I see no "context" other than "this is a move's relative position within the whole group" which doesn't say a thing about whether that move is good, bad, or just plain ugly.

I'm trying to come up with a clear way to express the concept. We are each looking at this differently. You see moves as "good" or "bad" in isolation. For instance if I gave you a position and asked you whether Ng5 was a good move, how do you judge that? I think if the move hangs the knight you call it "bad" and if it captures an undefended pawn you call it "good."

I don't think like that at all. I _always_ consider a move in the context of the current position. What I don't see you explaining at all is this: You have a list of moves. The moves at the bottom are considered "bad" and can be reduced or pruned. Why? Suppose the actual score difference between move 1 and move 40, after you do a normal search for each, is only 0.05??? So what makes reducing the last move a good idea compared to reducing all but the first, since they end up so close together? There are lots of similar cases. The point being that the last move in the list can be a lemon, or it can be good, but only slightly worse than the first. One can't tell based on the position in the list.

But I say it's undefined unless I am allowed to also consider the other moves too. If Ng5 hangs the knight, but opens up the king and every other moves leads to checkmate, then Ng5 is a GOOD move. Do you see the difference now?

See my above point. You simply do not get the point that the moves position in the list means _nothing_ except that by some quantitative measure, it is worse than the moves above it and better than the ones below. How much better or worse? Nothing you are saying tells me, because the L in LMR just means "moves near the bottom get reduced, moves near the top don't". That's the part I do not like. In an average position, you find 38 moves, according to almost all AI books. Are the last 20 moves always losers? Are the first 5 always good? I say that in some situations, all 38 are good, in some cases all 38 are bad, and in others that "boundary" could be anywhere up or down the list. if you consider more than the slot the move is in, then you are addressing my concern. If you only consider the slot, then you are not. And clearly the idea behind the "L" in "LMR" does not. It only addresses the point that the more moves you search, the more likely all are bad and you want to reduce the effort required to get rid of all of 'em.

Likewise, if Ng5 wins a pawn outright you call it "GOOD", but if some other moves wins a queen outright, I call Ng5 a BLUNDER! There is a world of difference between your simplistic definition and this better definition.

The problem is, _your_ "definition" says _nothing_ about the move's position in the move list. You are giving the exact reason I do not like this approach, because a move's goodness or badness is independent of where it is in the move list, and is a function of the position and the other moves that are available. How can you decide that "OK, move 15 and on are bad and get reduced more", in _every_ possible position???

You cannot just look at one move in isolation and call it good or bad without knowing about all the others. That is what I mean when I use the term, "context." You judge moves without providing any context but I feel that without context you cannot judge the value of the moves.

So, once again, tell my why a move's position in the move list has _anything_ to do with your comment above? We are not talking about looking at the sort score for a move to make a decision, we are talking solely about looking at the position within the move list, which is not much in the way of useful information.

I think I know why you have this issue. Most of the time if a move wins something it will still come out as good even by my definition. And if a move places a piece en-prise it will usually be bad by my definition. Usually is the operative word here. Usually, but not always. So it's easy to get lazy and just consider those definitions as absolute but they are not.

Suppose you are in a position where every single move loses material? You would simplistically label them ALL as "bad." But any good chess player in this kind of position would still try to maximize his chances by choosing the move which gives him the best chance of surviving, even if that chance was slim. So taken in the proper CONTEXT, when presented with a list of moves (whether in a winning or losing or even position) you can always label some of them good and the rest bad. If you do this well, spend most of the effort on the "good" moves, then you can have a very good search.

Nobody is going to say it's perfect, it is a crude measurement too. But tell me that you have a program that does not take any crude measurements and I'll call you a liar. I cannot see how this qualifies as being "too crude" but most of the brain-dead evaluations rules in all chess programs (including your programs) are not.

So in my opinion what you are doing is saying that this is crude so it shouldn't be done. That's like saying we should not have pawn structure in our programs because it's a crude measurement.

I know that Crafty has mobility based on giving weights to some squares more than others. I could easily point out major flaws in that system - but I'll bet is still works pretty good doesn't it?

You are sort of getting my main point.

As far as mobility goes, square-by-square is even better, as we did in the last versions of Cray Blitz. We could pull it off with no cost thanks to vectors, which we don't have on Intel. The CB idea would be good on Intel, but it would be expensive, and the cost more than offsets the accuracy gain, because I have tried the CB approach already. It is just too slow. Our current approach is somewhat of an "approximation" that is less costly, and less accurate. But one day, we want to do it accurately, just as I do (as a human). I don't just count squares. I look at how useful the squares are.

But back to the move list order...

Given this:

1. Nxf6
2. Qxe6
3. h7
4. Nf3
5. d4
6. Qxa7

Can you tell anything about which moves are good and which are bad, just based on the above "ordering"?

Absolutely! Assuming that your move ordering is perfect, I can say with certainty that the FIRST move is not just good, but it's the best move!

And if a frog had pockets, he'd carry a gun and never worry about snakes in the pond. But move ordering is _not_ perfect. In reality, we hope that moves near the top are better than moves near the bottom. And I'd hope I don't need to point out how many moves near the bottom turn out to be good. Take WAC #141 and look at the Qf4 move that is best, but is almost certainly ordered right at the bottom of the list.

If you'd just read my question above, you didn't answer it. What is it that makes moves below some magic point bad, and moves above that magic point good, particularly when the magic point is _static_ for _all_ positions in the tree???

If your move ordering is good but not perfect, I can say that the first move you listed is with high probably a good move, and more likely than all the others to be the best move.

If you believe the move order is good, I can with VERY HIGH confidence say the best move is with very high probability one of the first N moves!

I think your hangup here is that I don't have some kind of "score" so I cannot tell you if Qxa7 is just as good (or almost as good) as Nxf6. But I'm telling you that IT DOES NOT MATTER! If Qxa7 is just as good as Nxf6 then does it matter which one I search? If I have searched the best move, then the others are completely irrelevant.

Think about your statement above for a minute. "Does it matter which?" Absolutely it _does_ matter. If you search the right one first, and now magically the second (really best) falls below your magic number for position in the list that causes it to be reduced, then you miss it completely. My point, exactly. I don't play like that as a human for obvious reasons. So you have two reasonable moves, why does one get searched deeper than the other, just because one is one one side of some oddball boundary (L value in LMR) and the other is on the other side? Their ordering scores are close. Why not treat both the same since the ordering score says they are the same? Yet that is not what is being done.

I think you have this idea that if there are a lot of good moves that they all MUST be searched.

Yes I do have that idea. Good moves need to be searched to be sure that my PV is as accurate as possible and I don't make mistakes due to simple lack of searching the good moves my opponent might play against me. If I get a cutoff on one, of course the rest can be ignored. But I want to reduce effort on lousy moves, and search normal moves to usual depth, and perhaps even extend a few really good moves to search them even deeper than normal.

Or that if every move is bad you do not need to search them at all. But that is not the case. In tree search what is important is only that you search the best move of the choices you have. If they are all losing moves you STILL have to search the best one or you will not have an accurate picture of how good the parent position is. And it's just as important that you make sure you have not overlooked the best one, even if none of them are particularly appealing.

And if you randomly search some of those moves to D, and some to D-2, and a few more to D-3, and even a few more to D-4, you _really_ have a good picture of what is going on? Only if those reduced moves really are not going to be a part of what happens.

I think you believe that if a move is losing it should not be searched, but that is erroneous. A move should not be searched if it's WORSE than the best move, but it's absolute value is not relevant.

I almost believe what you say. I believe, for example, that if I am within 3-4 plies of the frontier, and I am down a queen, I can safely prune moves that don't recapture a major part of that missing material back. But notice that I am using the score (material gain or loss of a specific move) along with the alpha bound which reflects the current state of the game, to decide whether the move can be tossed. Not the move's position in the move list, which is not used in pruning decision or reduction decision at all...

Let me put it another way. If you suspect that EVERY moves drops material, you still have to search the position in order for the alpha/beta procedure to properly score ancestor positions. You cannot just say, "all of these moves stink so I don't have to try any of them."

Sure I can. If the moves are bad, and the current beta bound tells me that these moves are not going to help, I can dump every last one of them. Safely.

I will only say that they are ordered based on a static evaluation. But I am not supplying those scores. So which should be reduced, extended, or left alone?

The answer depends on my confidence in your move ordering scheme, and static move ordering is not very good, so I would have to say that a lot of them should be searched.

But the principle is the same, I would probably try the first N moves and reduce the rest, but N would be high because the move ordering is pretty lousy.

What if all win material? What if all but Nxf6 lose major material? That's my point.

How come you think you can now count moves and compare them against each other? In your scheme it should not matter how many win or lose material. It either wins material or it loses material and that is your criteria for determining whether to reduce or not.

What do you do in the case where ALL moves lose material? Do you reduce every move? What do you do if they ALL win material, do you go brute force on every move?

I think you got it... I see several things that should be used to make reduction or pruning decisions. alpha value which tells me how good or bad the best I have so far is, a score for each move so that I have some idea of how the move will affect the game. Perhaps other things like "does this disrupt the king?" or "does this create an advanced passed pawn?" Or "does this trade the last piece, leaving us in a potentially won or lost pawn ending?"

Sorting the moves in order is a good idea (at times) because of alpha/beta pruning. But once sorted, just using the relative position within the list only has one good effect... that being that the more more moves you search in any single node, the more confident you become that it is an ALL node. So yes, in that limited context the idea makes sense. Try to reduce the effort as you become convinced the effort is wasted.

That's not the main point however. At all nodes you have the best potential for reducing the search.

I think we both want the same thing - to never reduce moves that have a realistic chance of being important. But your criteria should give some weight to the statistical evidence that you can get for free.

The down side is that you tend to force a node to become an ALL node by doing this, because as you reduce moves you lose the ability to see why the moves are actually better than expected even though they appear at the end of the list according to static criteria.

My point about the "L" in "LMR" is that "L" only addresses the effort issue, and not the accuracy. There must be a better way that addresses both. I've been trying ideas off and on. Some are much worse. A few are just as good. So far, nothing is better. But I'm not going to stop trying, because the current "L" approach has a ton of holes. What if today's 24+ ply searches were _really_ equivalent to 24-ply searches from (say) the 90's??? Those would be seriously strong programs. We've gone from 12 plies to 24 plies, which ought to be worth 1200 Elo. Based on +100 per ply. We are nowhere near that. So there is a lot left to be discovered. We had 2600+ programs in 1994. 16 years and 12 additional plies later, we are seeing maybe 3000 rated programs? We've almost fallen into the Intel approach of 10 years ago where the goal was max mhz, not max instructions per second. Now it is max depth, without regard to the quality that ought to come with such huge depth improvement. Sure it is easier to take the current approach. I'm not willing to copy ip* and friends verbatim, assuming that what they are doing is optimal (or even just good). My intent is to test ideas with games, and decide what works, what does not, and proceed from there.

I simply raised an issue that is significant with this "move list position affecting pruning/reduction" discussion. I may well die not having made any progress. But it won't be from not looking. Just not succeeding.

[Don]

I don't think like that at all. I _always_ consider a move in the context of the current position. What I don't see you explaining at all is this: You have a list of moves. The moves at the bottom are considered "bad" and can be reduced or pruned. Why? Suppose the actual score difference between move 1 and move 40, after you do a normal search for each, is only 0.05??? So what makes reducing the last move a good idea compared to reducing all but the first, since they end up so close together? There are lots of similar cases. The point being that the last move in the list can be a lemon, or it can be good, but only slightly worse than the first. One can't tell based on the position in the list.

You continually made it seem that you don't have any interest in the values of the moves relative to each other. So it's a relief to see that you are not quite as clueless as I had believed about this particular point.

I think you are now trying to make the point that if the scores of a move are close that you should not reduce any of them. Is that right or wrong?

My answer is that if moves late in the list are scoring very close to moves late in the list, it doesn't matter if you prune. I don't care if a miss a good move but instead play a different move that is just as good. The results are the same.

So I guess I'm saying the distribution of "plausibility scores" has only a minor effect one how many moves you should look at. In ALL cases, if you want a really strong program you must prune aggressively.

But I say it's undefined unless I am allowed to also consider the other moves too. If Ng5 hangs the knight, but opens up the king and every other moves leads to checkmate, then Ng5 is a GOOD move. Do you see the difference now?

See my above point. You simply do not get the point that the moves position in the list means _nothing_ except that by some quantitative measure, it is worse than the moves above it and better than the ones below. How much better or worse? Nothing you are saying tells me, because the L in LMR just means "moves near the bottom get reduced, moves near the top don't". That's the part I do not like.

I now understand your point of view - even if I don't fully agree with you.

But I believe you are obsessing over this unduly. It's probably the case that the relative difference in scores (by some quantifiable measurement) has some impact on which exact moves you look at, but as I just pointed out there is a bit of a feedback or corrective effect. If ALL the moves are good, you can prune quite severely and still know you are including a good move. So I don't see what the big deal is.

One thing I want to point out that it is FAR easier to compare moves than to produce accurate estimates of their scores. This is sort of a computer chess fundamental principle in my opinion. I'm not saying there is not some value in pruning what superificially appears to be "really bad" moves, but it would be easy to take this too far.

And I still think its wasteful to not take advantage of good move ordering. This is not useless information by any means and it should be taken advantage of.

You also said this:

And if a frog had pockets, he'd carry a gun and never worry about snakes in the pond. But move ordering is _not_ perfect. In reality, we hope that moves near the top are better than moves near the bottom. And I'd hope I don't need to point out how many moves near the bottom turn out to be good. Take WAC #141 and look at the Qf4 move that is best, but is almost certainly ordered right at the bottom of the list.

LMR is a form of highly speculative pruning so what you do is play the odds. I know that move ordering is not perfect but you HAVE to reduce something in order to get the huge performance (in speed) benefit and I'm certainly not going to ignore useful information that I can utilize just because I can find examples of where it is wrong once in a while.

If you'd just read my question above, you didn't answer it. What is it that makes moves below some magic point bad, and moves above that magic point good, particularly when the magic point is _static_ for _all_ positions in the tree???

I'm not going to sit here and tell you I have found the perfect formula, I haven't. What I actually do is not perfectly consistent with my philosophy but it's almost impossible to make that happen.

My philosophy in a nutshell is this. First of all, try not to reduce the best move. Secondly, try to reduce every move you can, even really good moves, as long as you have not reduced the best one. And finally, if you DO reduce the very best move, it's probably ok if you have still included a very good move.

The devil, as they say, is in the details. Notice that I never mentioned the actual score relative to other moves. There could be some slight gain by doing so, but I'm pretty sure I would have a difficult time making anything major out of that.

So you have two reasonable moves, why does one get searched deeper than the other, just because one is one one side of some oddball boundary (L value in LMR) and the other is on the other side? Their ordering scores are close. Why not treat both the same since the ordering score says they are the same? Yet that is not what is being done.

If you have a serious hangup with oddball boundaries, you should not be involved in computer chess. I assume you do some form of futility pruning no? How did you choose your cutoff value? If you are so uncomfortable with "boundaries" then how is it that you can forward prune a whole tree branch if the score is X, but if the score is X-1 you have to search it? Isn't that a rather artificial boundary?

To answer your question, if they are both the same score then if I search one and reduce the other I save time. Isn't that the whole idea of LMR?

I think it's stupid to search moves endlessly brute force just because some score estimate is nearly the same. At some point you have to be a man and make a decision and pick some arbitrary (but presumably well tuned set of rules) that work well. Please don't try to tell me that nothing you do in Crafty is arbitrary or boundary-less.

I think you have this idea that if there are a lot of good moves that they all MUST be searched.

Yes I do have that idea. Good moves need to be searched to be sure that my PV is as accurate as possible and I don't make mistakes due to simple lack of searching the good moves my opponent might play against me. If I get a cutoff on one, of course the rest can be ignored. But I want to reduce effort on lousy moves, and search normal moves to usual depth, and perhaps even extend a few really good moves to search them even deeper than normal.

I think this is wrong. Everything is a tradeoff so sure you can search more moves in order to "sure" that you don't throw out a move but you don't get a free ride - you have to pay for this safety with a slower search.

I have an idea for you. Don't reduce ANY moves, then you won't make any mistakes due to accidentally throwing out a good move.

And if you randomly search some of those moves to D, and some to D-2, and a few more to D-3, and even a few more to D-4, you _really_ have a good picture of what is going on?

Yes.

Only if those reduced moves really are not going to be a part of what happens.

Please don't keep saying "randomly search" as there is nothing random about it.

But yes, this is basically how Komodo works. I reduce more as I progress through the move list.

I think you believe that if a move is losing it should not be searched, but that is erroneous. A move should not be searched if it's WORSE than the best move, but it's absolute value is not relevant.

I almost believe what you say. I believe, for example, that if I am within 3-4 plies of the frontier, and I am down a queen, I can safely prune moves that don't recapture a major part of that missing material back. But notice that I am using the score (material gain or loss of a specific move) along with the alpha bound which reflects the current state of the game, to decide whether the move can be tossed. Not the move's position in the move list, which is not used in pruning decision or reduction decision at all...

I will think of giving something like that a try in Komodo.

Let me put it another way. If you suspect that EVERY moves drops material, you still have to search the position in order for the alpha/beta procedure to properly score ancestor positions. You cannot just say, "all of these moves stink so I don't have to try any of them."

Sure I can. If the moves are bad, and the current beta bound tells me that these moves are not going to help, I can dump every last one of them. Safely.

For the sake of this discussion, alpha and beta should be ignored. It's understood that all kinds of shortcuts are possible when you factor in alpha and beta but it's not relevant to this discussion. Komodo knows about alpha and beta of course and takes the window into consideration in it's decisions about which moves to reduce or forward prune.