Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Bug-free fail soft must pass return_type

Author: Vasik Rajlich

Date: 03:51:58 06/22/05

Go up one level in this thread


On June 21, 2005 at 13:44:14, Dieter Buerssner wrote:

>On June 21, 2005 at 04:37:50, Vasik Rajlich wrote:
>
>>On June 20, 2005 at 16:19:19, rasjid chan wrote:
>>
>>>On June 20, 2005 at 14:58:14, Dieter Buerssner wrote:
>>>
>>>>On June 19, 2005 at 12:38:09, Vasik Rajlich wrote:
>>>>
>>>>>On June 19, 2005 at 11:25:24, rasjid chan wrote:
>>>>>
>>>>>>   I apologize I can never understand how to analyse the way search() intereacts
>>>>>>   with set board positions. But I understand now, also from dieter's reply,
>>>>>>   that fail-soft value need not be strictly correct UB / LB;  ie some
>>>>>>   risk may be taken.
>>>>>>
>>>>>
>>>>>I don't think Dieter is saying this. An UB should always be an UB - if you have
>>>>>to make a mistake, you set it too high. This happens for example with lazy eval,
>>>>>or using a margin for pruning in q-search.
>>>>
>>>>I fear, I don't fully understand Rasjid's statement neither Vasik's reply.
>>>>I think, correctly implemented fail soft search gives always correct bounds.
>>>>They are of course not the strictest bounds, one would like to have.
>>>>
>>>
>>>Actually I too did not completely understand Vasic's reply; it seems
>>>contradictory.
>>>
>>>I mentioned you because of your reply about skipping futile moves:-
>>>
>>>  if (move-likely-futile...){
>>>    best = alpha;//added by me
>>>    continue;
>>>  }
>>>
>>>Your reply seemed to indicate(optimist_score..margin)some don't always set
>>>best = alpha; My simple understanding of this is that when best is set to
>>>anything less than alpha and if finally we fail-low and soft with this best,
>>>then there is a "risk" as it is a guess of a fail-low and soft UB. So I presume
>>>others do allow some margin of risk. Vasic probably too misunderstood.
>>>
>>
>>Actually I see now that I interpreted the original statement correctly. :)
>>
>>You never want to set a fail soft score which is "too aggressive" and therefore
>>has a chance to be incorrect. You are willing to have "not the strictest" bounds
>>as Dieter says.
>>
>>Of course, you might in some really rare cases set an incorrect fail soft score,
>>such as if you underestimate the margin. I guess the formal rule should be: you
>>should never set a fail soft score which is riskier than the risk you already
>>have with failing low/high in the first place. For example, if you use "margin"
>>to prune in quiescence search, then you should remove "margin" from the softness
>>of your bounds, etc ..
>
>Yes. I think, my courrected code sample did it correctly. One might also note,
>that "remove from softness" in the last sentence means "add to the score".
>

Yes.

>>>>Also, with fail soft you will search different trees. You can also visit the
>>>>same node with different bounds at the same root depth. Perhaps with one bound,
>>>>you get a null move fail high, while with the other (higher bound) will not be
>>>>enough for the null move to fail high. It may turn out, that this null move fail
>>>>high was actually "wrong" (search without null move would have shown, that the
>>>>score of this node is worse than you have expected). But again, this situation
>>>>can also arise in fail hard search (for example when you use a different HT
>>>>size). I'd guess, that the chance of something like this happening is higher in
>>>>fail soft - but it should be low enough to not matter (other than by some random
>>>>noise).
>>>>
>>
>>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)

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.

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.

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.

>
>>>>About the REP3 - I had no time yet, to read this carefully (this became a really
>>>>huge thread ...). You might want to google for "Dennis Breuker thesis". He shows
>>>>a concrete example in detail, and explains why things go wrong there because of
>>>>hash and repetition of position. You could try to probe your suggestions against
>>>>that scenario.
>>>
>>>The specific case of rep3 which Vasic ignored is simple.
>>>He hashed FL and soft when best == 0, but this 0 comes from rep3 FH and soft
>>>from the ply above. So Vasic's 0 as the FL and soft score(is a correct UB) is
>>>correct for the particular search.
>>>
>>>Hashing the search would give HT path-dependncy corruption. I suggested passing
>>>down a _rep3_flag as this path-dependency may just propagate downwards. All
>>>hashing may be corrupted as we never know when such dependency may be
>>>inherited from above and passed down unless we keep a _rep3_flag. I think
>>>it may happen also for FH/exact.
>
>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.

Most other forms of HT corruption gradually diminish with more search.

>This is not the only problem we have with the interaction of HTs and repetion. I
>think Breuker calls this "graph history interaction" (or game history
>interaction). When you have no repetition (yet), one side might have tried hard
>from the current position down, to avoid repetition. With another path reaching
>this same position, it might have been easier to avoid repetition.
>
>I just did a small experiment. For draw scores in the HT, I return "worthless"
>(meaning the move can be used for move ordering, but not for cutoff). I changed
>stalemate score to 1. With these changes in the following position, I believe it
>is basically the same as your REP3 idea (I think all draw scores come from
>stalemate or repetition).
>
>In the following position white (Yace) just captured on g7 an threw away a win.
>With my original code, big fail lows very fast and draw score in 30 seconds (I
>do lots of extensions here - it is very deep, to see repetition). With my
>experimental setup, still -7 score after 5 minutes, and I believe, no draw score
>in days.
>
>[D] 7k/6R1/6R1/1r5P/6K1/8/8/8 b - - 0 55
>
>BTW. Current version with current hardware and not too fast time control could
>avoid xg7.
>

Yeah, I understand.

Keep in mind that this position is an unfair test. If you randomly sprinkled
0.00s into the hash table, you'd improve your performance :)

But yes, it might be necessary to do something incorrect to avoid a huge penalty
..

Vas

>Perhaps even a position to try the no progress ideas (and more things, like
>stalemate detection in qsearch).
>
>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.