Author: Robert Hyatt
Date: 12:49:21 01/21/04
Go up one level in this thread
On January 21, 2004 at 15:07:11, Sune Fischer wrote: >On January 21, 2004 at 14:28:14, Robert Hyatt wrote: > >>>But actually, your example is interesting as well. >>>Say we concatenate two PVs, one very much shorter than the other (from a much >>>less deep search), why should that give us problems? >> >>Simple. One could search below position H and produce a best score and best >>move. The second could produce a fail-low. No best move. > >Incorrect. >That would mean it wasn't a PV node, which I've assumed it is. Not incorrect. The first time you searched it, it was a PV node. But you _do_ realize that other root moves can lead to that _same_ position later and _not_ be PV nodes, right??? That is the problem here... > >I can't speak for you, but tend to update the search flag also when I record a >new entry. >;) This is happening in the _same_ iteration. The "search flag" was my idea in the first place so you might suspect that I have been doing that part right for a _long_ time. > >So you do have an exact score and a move from both, my question, which I'm about >to repeat for the 100th time, is "why would that be nonsense"? Again, see above. You are somehow missing the point that two different moves from the root (or anywhere else in the tree) can lead to the _same_ position in the same iteration. With a different depth remaining or with the same depth remaining. With different alpha/beta bounds or the same bounds. But when you change _anything_ at a position, you can change the best move that the search will find there. Here we are talking about changing the bound, so that one search might fail high, another might fail low, and the third might produce a true score, all because of different bounds at the same position because we reach there from different parts of the tree. Then change the depth remaining and you get a further change in the result. > >>Or a different >>best move. > >What's the harm in that? If I as a chess player tell you "don't do that, it wins a pawn" and you ask to see the PV, but I give you a PV that doesn't win a thing, or which loses a pawn, what do you conclude? that's the "harm". The PV and score are _tied_ together. The PV is the path leading to a position that actually _produced_ the score. If it doesn't then it causes the questions that started this thread in the first place. > >>You have the score from the first search below H, and either the >>best move from a different search below H with a different depth, > >Sure, but we are talking about the PV's here, not the score. No we are talking about _both_. The search _can_ return two pieces of information (in Crafty it does return both). Namely the score, and the path (PV) you follow to reach the position that produced that score. A PV without a score, or a score without a PV isn't the issue. Again, go back to the beginning of this thread. "Shredder produced a PV and score but the PV lost a piece while the score didn't show that." That's what the thread started about, and that has been what I have been discussing ever since. > >>or else >>no move there at all... > >*PV* nodes! Do you realize that you can reach my position H while searching the PV and store the PV move? Then you can reach H from a _later_ search of a different root move, and store a "fail low" there because you have a higher draft or a different window? Somehow we are not talking about the same alpha/beta/minimax tree search space. This is not really a tree, it is a very complex graph with lots of places where different paths merge. > >>>They are both PVs so seperately they are ok, why shouldn't they be ok together? >>> >> >>PV A goes with score A. >> >>PV B goes with score B. >> >>but in the case above, PV B goes with score A. > >The score and pv does not necessarily go together, that's true. >But the PV shouldn't be nonsense in itself. But it already has been shown to be such. People have been criticizing shredder's PVs as occasionally containing nonsense moves. People criticized deep blue in 1996 and 1997 for the same reason. It _can_ be nonsense for the reasons I have already given. Note that again, nonsense -> a PV that does _not_ go with the score. IE if I give a score of +3, but the PV only shows winning a pawn, is that rational? Yet it can easily happen. > >>I can't debug that. > >Well we all have our limitations >;) First let's get past your limitation of understanding the basic graph theory of the minimax tree search space. :) > >>>I suppose it is possible the window is way off in one case (e.g. a mate window) >>>and somehow getting mated turns into a PV which we then glue up with a PV from a >>>different window showing a draw score.. :) >> >>That is one of many odd cases that happen, yes. But if you look back over >>the CC literature, you will find lots of questions about PVs when they are >>constructed in this fashion. Deep Blue was but one case where oddball moves >>showed up because they had no choice in how to get their PV since the chess >>processors did not supply one. > >Hand waving Bob, please come up with a tangible example! > >Don't talk me wrong, show me wrong. :) Go to the first post in this thread. It had a position, a PV and a score. QED. Or look at the deep blue questions about their PVs. Same problem. This problem is intuitively obvious once you _really_ understand the search space being traversed. Remember that the hash table is actually called the "transposition/refutation table" for a reason. Transpositions as in the idea of searching a graph with different pathways to the same position. Yet each different pathway can bring a different information set to that position and produce a different result. That key position can be overwritten many times as you reach it with different alpha/beta bounds, search depth remaining due to different numbers of checks in the path, etc... > >>>But I suspect this would be unusual, basicly I don't see how the same position >>>can produce such different yet _exact_ scores?? >>> >> >> >>DIfferent "depth remaining". Caused by two different orders of moves leading >>up to the position, each having a different number of checks. Sit at a board >>and set up the pieces so that you look at a root position where you want to play >>two moves by either side to get to my position "H" as described previously. IE >>perhaps Bc3+ Kf5 Kh2 Kf4. One check, one extension. What happens when you >>search Kh2 Kf5 Bc3 Kf4? One less check, one less extensions, a completely >>different subtree below that position since it will be one ply shallower the >>second time around. > >If your point is that you can search the same position with different remaining >depths due to transpositions then...: I know that! Then why are we arguing about the problem of this position getting overwritten with different results _after_ the PV and best move have already been found for this position? Now this key table entry gets overwritten with something different and when you come back later and try to probe to find the PV, when you get here you get a signature match, but that is all, the move may or may not go with the actual PV. There may be no move at all in fact. > >It doesn't answer my question which very eloquently frased is: "so what?". > >It leads to a different position than the one related to the score, but that >doesn't explain "buggy PV's". A precise definition then. A "buggy PV" is a PV that does _not_ go with the best score returned by the search. Yet you claim it does because you show both the best score and that PV. There is an implied connection between the two, otherwise why are you showing that PV at all. But if it doesn't quite match, then it is wrong. How wrong? Depends on the position. In the post that started this thread, it was a _piece_ wrong. Now perhaps shredder tries to do the impossible and find the best move at fail-low positions and he stores that when he stores a fail-low condition. That will certainly produce grossly ugly moves since by definition there is _no_ best move at a fail-low position. And picking a random move there is going to produce some very interesting and obfuscated PVs. But even if you don't dance with witchcraft and try to do that, the PV should _still_ go with the score perfectly or else there is a flaw. If you want to say that flaw is not that important, that's ok. I have made _many_ such concessions in Crafty, such as in the SEE stuff, in the evaluation, and elsewhere. A chess program will never be perfect and I don't sweat that myself. however, I happen to believe that it is important for lots of reasons to have a PV that goes _precisely_ to the node where the score was produced, not only because of avoiding a lot of user-based questions like the post that started this thread, but for my own debugging. If the score seems out of bounds on what I think is reasonable, I can get to the _exact_ position that produced it, and most of the time see why I was wrong and the score is correct due to some tactic or positional idea I had overlooked. But at other times, I find that a positional bonus is getting added when it should not, but without the _exact_ position to work with, I would not find it as such positional terms are usually right in most cases due to previous debugging sessions. It is the exceptions that require later fixes... > >>>>The hash is path-independent. The tree below a node is _not_ path >>>>independent, from repetition to 50-move-rule to search extensions that >>>>may or may not be done depending on the order of moves in the path. >>> >>>Yes that's true, that is always an issue with the hash. >>>I think it is a small issue in this context though, "grasping for straws" come >>>to mind :) >> >>Nope. > >I sure hope you _are_ grasping for straws, because your program as well is mine >is based on path independent scores from the hash. Mine isn't except for draws, which is a known problem. however, that does not affect debugging. The program simply misses a draw because it doesn't realize a repetition is buried in the pseudo-path from the hash table hit to the unseen terminal node that produced that result. I can deal with that and it is another example of a case where I have chosen to ignore inaccuracy since I see no viable way of fixing that. But for the original PV issue, I _never_ have bogus moves in my PV. I do occasionally have a PV that is short, but when that happens, I indicate that with the now well-known <HT> output to show that there would have been more in the PV if it had not been for a hash table hit. IE the only use for the <HT> is to inform the user that the PV is incomplete. But what is displayed _never_ has a wrong move anywhere. It can't. > >If this is enough to cause serious problems for the PV then imagine what it must >be doing to our search! I don't disagree. That is why I start clearing the scores in the hash table after 40 moves with no pawn push or capture, I have drawn several games that were winnable, due to hash confusion around the 50-move-rule. Of course for repetitions there is no known fix, so you just stumble every now and then but keep going. > >I think we can only assume (and hope) that it can be ignored. There is no other viable choice. You can hash the path. And kill transpositions completely since there will no longer be a transposition if the thing is path dependent. > >> Just explaining a problem that has been well-known for a _long_ time. >>Surely you don't think that this idea came up recently? People have already >>criticized DB's PVs because they had strange moves in them for this very >>reason. At one point HiTech did this I believe. I can recall others talking >>about the same odd behavior back in the late 70's/early 80's as memory became >>big enough to make hashing more viable... > >I think you are comparing apples and oranges now. >I'm not trying to construct a PV from a hardware produced search. No, but it is not apples and oranges. DB probes the hash tables on each node to find the best approximation to the PV. The stuff searched by the chess hardware has no hash table and the PV for the hardware part of the search doesn't exist. IE if you look at their log files, the PVs they show are _all_ done in software, with the hardware adding on another N plies beyond the last move shown as a PV. You are doing _exactly_ the same thing. First you search, you later decide to display a PV and you stomp through the hash table to find the PV moves as best you can. That is _exactly_ what they do. And they get bogus moves here and there. I've never tried to quantify how often a bogus move shows up, I've never cared since I don't do it that way and I never get one. > >-S.
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.