Don wrote:bob wrote:Don wrote: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.