Author: Vasik Rajlich
Date: 03:39:43 06/23/05
Go up one level in this thread
On June 22, 2005 at 18:00:58, Dieter Buerssner wrote: >On June 22, 2005 at 06:51:58, Vasik Rajlich wrote: > >Thanks for your thoughts, Vasik! Some few comments below. > >>On June 21, 2005 at 13:44:14, Dieter Buerssner wrote: >> >>>On June 21, 2005 at 04:37:50, Vasik Rajlich wrote: >>> >>>>This is a great point, which I became aware of some time ago. The problem >>>>becomes serious when you start using really small aspiration windows. Another >>>>way to think of it is that you are effective putting null moves into your >>>>principal variations. (It takes a bit of thinking to understand this, but that's >>>>the effect.) >>> >>>I obviously did not think enough about it yet. Can you elaborate on this? I see >>>no principal difference yet, between fail hard/soft or large/small aspiration >>>window. To me it looks simple (yet). Either you trust null move fail highs, or >>>you don't. We don't do the null move search at beta+margin, we do it at beta, >>>because we are convinced, that when we get a fail high there, it is a good >>>pruning decision. We are of course aware, that we get wrong pruning by this now >>>and then, and we live with it, because we are convinced, that advantages >>>outweigh disadvantages. >>> >> >>Ok, this is where things get interesting. >> >>First a few disclaimers: >> >>1) If you are using PVS with "big enough" root windows, this might be >>interesting, but it won't be useful. >>2) You certainly shouldn't stop null-moving at beta. The question is about the >>windows. >>3) These things take some thinking-through. I have never yet read a truly >>accurate critique of MTD (f). In principle MTD (f) should save nodes - the >>question is, at what cost. >> >>Anyway, consider the following position: >> >>[D] 2bq1rk1/pp1n1p2/n3pPpp/3pP3/Pbp4B/4Q3/rPP1B1PP/RN1N2K1 w KQkq - 0 1 >> >>Sorry, I know it's a ridiculous position - but this stuff will happen in the >>normal search of course. >> >>White is down a rook, but first we do a quiescence search and find that white >>can play 1. Rxa2 and come out of quiescence search with a score of ~ +0.0. A >>one-ply search also comes to this conclusion. >> >>Now we do a two-ply search: >> >>Search (Rxa2, [-1.00, +1.00]): -- (since we see now that 1. Rxa2 loses to 1. .. >>Bc5) >>Search (Qxh6, [-1.00, +1.00): -- (since 1. .. null fails high) >> >>Everything else fails low. Now we do open the window and re-search: >> >>Search (Rxa2, [-99.0, -1.01]): returns -5.00 (the result of 1. Rxa2 Bc5) >>Search (Qxh6, [-99.0, -1.01]): ++ (null move no longer possible, so we see that >>black is getting mated) > >In a two ply search? Why should we see mate here in a two ply search? > Ok, make it search depth X. :) The point is that you need to discover at the same depth that 1. Rxa2 loses to 1. .. Bc5 as to see that 1. Qxh6 mates (without null move). >>Everything else fails low. > >>So - we return a best move of Qxh6, with an expected score of -1.01. > >>In a PVS engine, I guess you're used to taking a PV by taking scores which come >>from non-null-window searches, but in MTD (f) you don't do this. In MTD (f), >>your PV consists of positions which failed both high and low. (No non-PV >>positions fail in both directions.) At each position in the PV which failed both >>high and low, your PV move is the fail-high move. Hence, your PV for the above >>example is 1. Qxh6 (null) - and your score would be the exact material score >>after that sequence. > >Ok, I believe I got the idea. I still cannot see, what it has to do with the >size of the aspiration window. In typicaly PVS implementations, the above could >not happen, even when you decided to start with a very small window, and with >every fail (high or low) at the root, you increase the window by one. I can I am not sure if I understand correctly. If you don't open the window completely, you will still see the problem. For example: Search (Rxa2, [-1.00, +1.00]): -- (since we see now that 1. Rxa2 loses to 1. .. Bc5) Search (Qxh6, [-1.00, +1.00): -- (since 1. .. null fails high) Everything else fails low. Now we do open the window and re-search: Search (Rxa2, [-2.0, -1.01]): -- (1. Rxa2 Bc5 is better than that) Search (Qxh6, [-2.0, -1.01]): -- (1. Qxh6 null still fails high) Search (Rxa2, [-3.0, -2.01]): -- (1. Rxa2 Bc5 is better than that) Search (Qxh6, [-3.0, -2.01]): -- (1. Qxh6 null still fails high) Search (Rxa2, [-4.0, -3.01]): -- (1. Rxa2 Bc5 is better than that) Search (Qxh6, [-4.0, -3.01]): -- (1. Qxh6 null still fails high) Search (Rxa2, [-5.0, -4.01]): -- (1. Rxa2 Bc5 is better than that) Search (Qxh6, [-5.0, -4.01]): ++ (finally 1. Qxh6 null won't get you to -5.0 and you fail high) I think I just didn't understand what you meant. see, >that you can get contradicting results, when you adjust both bounds at a time. >And at that time the engine might decide to just trust one of the two >contradicting results. Often engines just widen one side, and let the other side >set (mine does). Then the worst case is, that you get ++ followed by -- or the >other side around and end up with totally open window. > >I have tried it the other way, too. When search fail high at +100, setting alpha >to +100 (actually I used +99, but that is another - although related - story, >and I was not happy with the result. Perhaps not tested well either. > Aha. Yes, indeed, this will solve all of these problems. However, aren't you worried about wasting nodes? If you know the upperbound/lowerbound at the root, why not use it? One other thing to note: if you use the bounds from the HT to constrict your search bounds, you re-introduce the problems. For example: Search (Rxa2, [-1.00, +1.00]): -- (since we see now that 1. Rxa2 loses to 1. .. Bc5) Search (Qxh6, [-1.00, +1.00): -- (since 1. .. null fails high) Everything else fails low. Now we do open the window and re-search: Search (Rxa2, [-99.0, +1.00]): -- (1. Rxa2 Bc5 is better than that) and now we do: Search (Qxh6, [-99.0, +1.00]): We play 1. Qxh6, notice that the HT tells us that the upperbound is -1.01 (because of the null move), and constrict beta for the node after 1. Qxh6 to -1.01 (from white point of view). >While writing this answer, I think your point actually got rather clear to me - >thanks! :-) I cannot comment on MTD(f) specific things - while I have a rough >idea, how it works, I really never thought into it carefully. > If you're expanding the windows at one end only (instead of sliding them), then you don't need to. If you are sliding them but they are big, it's a very small issue. If you are sliding them and they are small (MTD (f) is this approach taken to the extreme), then this issue is huge. >>If you think about the PVS version of this search, I think you would conclude >>that the "rightful PV" for the above search was also 1. Qxh6 (null). After all, >>we did search past 1. Qxh6. What was the move that gave us the lowerbound for >>the response to 1. Qxh6? It was the null move. >> >>In other words, your search thinks that the best move is 1. Qxh6, and that the >>best response is to pass. >> >>Of course, it's not clear that having null moves in the PVs is such a problem. >>You might try in Yace treating a null move as any normal move and seeing how >>much the level drops - it might not be much. > >You mean searching null move at [alpha,beta] and not [beta-1, beta]? Otherwise >null move will always give an out of bounds answer, and will trigger a research >further up. As I noted before, when strictly adjusting both bounds, a >contradiction can arise. Then also a policy must be defined, how to resolve this >contradiction (trust one or the other, or research with more opened windows). > Yes, that's what I meant. >> >>The point is that this issue was caused by the small root window. Because of >>this small window, you came to the position after 1. Qxh6 thinking that white's >>lower bound was -1.00 - but that wasn't true. The point is that in a PVS engine, >>your search bounds are untrue to the extent that you might need to re-search. As >>you can imagine, this problem is much bigger in MTD (f). >> >>I don't know how clear all of this is. The general point is that as the root >>windows get smaller, the issue of fake alpha-beta bounds becomes bigger. > >Have to think about this last point more. At the moment, I am not totally >convinced yet (again, not arguing abot MTD(f)). > >I see (rarely) ++ followed by -- at the root (and the other way around). Because >I only enlarge the window, this issue will always get resolved. But it of course >comes also with a prize tag. > Yes, exactly. I guess in PVS it doesn't matter so much but I don't really like the idea of just expanding the window rather than sliding it - it seems like just the "easy way out". >>>This will solve wrong zero repetition draw scores by HTs. The prize will be very >>>high (my guess). Also my guess: much more often than not, those draw scores will >>>be correct in the end, even when for the specific path and search depth they may >>>be not. >>> >> >>I need to really think about this. My problem here is that the scores could be >>"really" wrong, in the sense that further search won't eliminate them. I really >>don't like the idea of having such scores in the HT. > >Neither do I. Vasik, you are obviously very good in finding concrete positions >to illustrate such arguments. Would be really intrested, to see an example here. >To make it not too complicated, we should assume a game played by an engine (not >some analysis of another game, where a player might not mind for one or the >other reason, to go through one repetition, and later improve his position). >Perhaps, one could even consider different chess rules - first repetition is >draw. > Actually, I just spent some half-hour or so thinking about this and my (temporary) conclusion is that indeed, this form of HT corruption is of the type which _does_ get solved by deeper search. I am not sure if that's what you were saying but anyway I am inclined after all to ignore it. Let me try to explain the reasoning. First of all, it's easy to come up with a position where you corrupt the HT for one specific iteration. Let's take everyone's favorite example, Fine #70: [D] 8/k7/3p4/p2P1p2/P2P1P2/8/8/K7 w - - Now, we start searching: 1. Kb1 (only) Kb7 2. Kc1 (only) Kc7 3. Kd1 (only - although Kb1 also wins by transposition) Kd7 4. Kc2 (only) Kc7 5. Kd3 (only) Kb6 The winning move here is 6. Ke3, but we have the bad luck to first try 6. Kc4. Now, black plays 6. .. Ka6 and the only move which keeps the win is repeating with 7. Kd3 (7. Kc3 and 7. Kb3 are already real draws). The problem is that black then plays 7. .. Kb6 and gets a 0.00 score. Note the key point: this 0.00 score is assigned to the following position: [D] 8/8/k2p4/p2P1p2/P1KP1P2/8/8/8 w - - This position is of course winning for white. I am not sure if having this score in the HT is already enough to prevent the position from being solved - but it gives black a bunch of new defensive possibilities. For example: 1. Kb1 Kb8 2. Kc2 (only) Kb7 3. Kc3 (only) Kb6 and now the normal win is 4. Kc4 but our hash table thinks that in this case 4. .. Ka6 draws. However, there is an interesting point here. Let's imagine that we couldn't solve this position at some iteration because of the bogus entry in the HT. Now, let's go to the next iteration. We again follow the first variation 1. Kb1 (only) Kb7 2. Kc1 (only) Kc7 3. Kd1 (only - although Kb1 also wins by transposition) Kd7 4. Kc2 (only) Kc7 5. Kd3 (only) Kb6 (let's call this position A) We already know that 6. Kc4 "draws", so we only play try 6. Ke3. The position after 6. Kc4 Ka6 never makes it into the hash table for this iteration (ie. with a high-enough remaining depth). I was trying to think of what it would take for the position after 6. Kc4 Ka6 (or something like it) to always make it into the HT at every iteration. I think you need the following: 1) Some position A. 2) The best move from A leads to B. 3) B is winning (for white, let's say) 4) However, from B, black can force white to go to A 5) A is drawn with best play (by playing to B) As described this way, condition #5 is impossible. Without condition #5, the bogus draw score for position B will get dropped from the HT as soon as the search learns how to win position A. Anyway this is a bit disorganized but at the moment I think that storing these 0.0s in the HT is a problem which is solved by more search. Vas >>Most other forms of HT corruption gradually diminish with more search. > >I agree. Although it can be tricky, when extending heavily (by purpose, in one >path, we might have the same remaining depth for several moves. The extensions >my be path dependent - recapture for example is by definition). > >Recently I investigated a pawn endgame position, where yace reached its maximum >depth of 127 plies. Position was clear draw - Yace showed stupid score. Turned >out it was because of interaction of HTs with 50 moves rule. I have seen similar >cases, where this was "self repairing". But in this particular case, it wasn't. >Doing some additional precautions before hash cutoffs (half moves without >capture/pawn move done already + remaining depth >= 100 prohibits cutoff from >HT) probably has solved it in theory. However the search "hang" at 100 plies, >then until I lost patience. > >Regards, >Dieter
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.