Author: Dieter Buerssner
Date: 15:00:58 06/22/05
Go up one level in this thread
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? >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 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. 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 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). > >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. >>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. >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.