Author: J. Wesley Cleveland
Date: 20:52:03 06/04/01
Go up one level in this thread
On June 04, 2001 at 23:13:33, Robert Hyatt wrote:
>On June 04, 2001 at 17:00:10, J. Wesley Cleveland wrote:
>
>>On June 01, 2001 at 13:59:11, J. Wesley Cleveland wrote:
>>I have been thinking about fail high's and fail low's. If you have a fail high,
>>and you have used a significant portion of the time available for this move (>
>>25% ?), you should just make the move without further searching, as you will not
>>have time to resolve the fail high and investigate other moves anyway.
>>
>>Fail low's are a different problem. When you get a fail low, what you know is
>>that the current move has an upper bound at ply n of the ply n-1 value - window
>>while all other moves have an upper bound at ply n-1 of the ply n-1 value. It
>>seems it might be better to search some of the other moves before re-searching
>>this one.
>>
>>This leads to a crafty question. In search.c, if all the values are < alpha (a
>>fail low), the value returned is alpha and not MAX(values). Why is this ?
>
>
>Why does it matter? The value you get back is totally useless. Because
>everything cut off low on the alpha value.
Is not the value you get back an upper bound for that subtree ? If you return
and save that value in the hash table, if you later get a fail low closer to the
root, you may not need to re-search this subtree.
>
>
>
>>
>>>On May 31, 2001 at 10:44:18, Robert Hyatt wrote:
>>>
>>>>On May 31, 2001 at 08:56:33, Gian-Carlo Pascutto wrote:
>>>>
>>>>>On May 30, 2001 at 15:14:46, Robert Hyatt wrote:
>>>>>
>>>>>>3. When I fail high, I just relax
>>>>>>beta to +infinity, rather than the tiered approach I used in Cray Blitz. If
>>>>>>there are lots of mates here, that are not forced, the program still has to
>>>>>>search them all out as with +infinity, you get zero beta cutoffs at positions
>>>>>>where white is to move, until you establish a better beta value after a lot
>>>>>>of searching.
>>>>>
>>>>>Silly question...why don't you do it in Crafty? It's not like it's
>>>>>hard to code, and it gives real benefits.
>>>>>
>>>>>I use the CB approach after you once described it here or on rgcc and
>>>>>it's saved my ass a dozen times...
>>>>>
>>>>>--
>>>>>GCP
>>>>
>>>>
>>>>That is actually a good question. I guess I have simply not stopped to think
>>>>about it, but it was obviously a reasonable idea. Harry had this one ugly
>>>>position that at depth=12 would fail high, but we could not get a score back
>>>>from ever. We discovered that the problem was that if we relaxed beta to +inf,
>>>>about 90% of the positions were mates. Very deep mates. But not forced. When
>>>>we put in the tiered fail-high, the problem went away. It has been on my to-do
>>>>list for years, but I simply haven't gotten to it...
>>>
>>>It appears to be trivial to do. I put the following code in iterate.c
>>>
>>> int failinc[4] = {150, 350, 1000, MATE};
>>> int failhi = 0;
>>> root_beta += failinc[failhi++];
>>> if (root_beta> MATE+1)
>>> root_beta=MATE+1;
>>>
>>>and it speeded up the result on this problem about 100 fold. It certainly needs
>>>more testing and tweaking, but definitely seems worth looking at. Here are snips
>>>from the log files.
>>>
>>>before the change
>>>
>>> 13 31.70 3.39 1. Rxh7 Kxh7 2. Rh2+ Kg8 3. Qh4 Bxf6
>>> 4. exf6 Kf8 5. Qh8+ Qg8 6. Rh7 g5 7.
>>> f7 Qxh8 8. Rxh8+ Kxf7 9. Rxc8 g4 10.
>>> Kf2 Kf6
>>> 13-> 40.06 3.39 1. Rxh7 Kxh7 2. Rh2+ Kg8 3. Qh4 Bxf6
>>> 4. exf6 Kf8 5. Qh8+ Qg8 6. Rh7 g5 7.
>>> f7 Qxh8 8. Rxh8+ Kxf7 9. Rxc8 g4 10.
>>> Kf2 Kf6
>>> 14 48.98 ++ 1. Rxh7!!
>>> 14 121:42 4.01 1. Rxh7 Kxh7 2. Rh2+ Kg8 3. Qh4 Bxf6
>>> 4. exf6 Kf8 5. Qh8+ Qg8 6. f7 Qxh8
>>> 7. Rxh8+ Kxf7 8. Rxc8 Kg7 9. Kg2 g5
>>> 10. Bxg5 Rxb2+ 11. Kg3 e5
>>> 14-> 122:06 4.01 1. Rxh7 Kxh7 2. Rh2+ Kg8 3. Qh4 Bxf6
>>> 4. exf6 Kf8 5. Qh8+ Qg8 6. f7 Qxh8
>>> 7. Rxh8+ Kxf7 8. Rxc8 Kg7 9. Kg2 g5
>>> 10. Bxg5 Rxb2+ 11. Kg3 e5
>>>
>>>after
>>>
>>> 13 29.80 3.39 1. Rxh7 Kxh7 2. Rh2+ Kg8 3. Qh4 Bxf6
>>> 4. exf6 Kf8 5. Qh8+ Qg8 6. Rh7 g5 7.
>>> f7 Qxh8 8. Rxh8+ Kxf7 9. Rxc8 g4 10.
>>> Kf2 Kf6
>>> 13-> 37.29 3.39 1. Rxh7 Kxh7 2. Rh2+ Kg8 3. Qh4 Bxf6
>>> 4. exf6 Kf8 5. Qh8+ Qg8 6. Rh7 g5 7.
>>> f7 Qxh8 8. Rxh8+ Kxf7 9. Rxc8 g4 10.
>>> Kf2 Kf6
>>> 14 45.65 ++ 1. Rxh7!!
>>> 14 1:26 4.01 1. Rxh7 Kxh7 2. Rh2+ Kg8 3. Qh4 Bxf6
>>> 4. exf6 Kf8 5. Qh8+ Qg8 6. f7 Qxh8
>>> 7. Rxh8+ Kxf7 8. Rxc8 Kg7 9. Kh2 g5
>>> 10. Bxg5 Rxb2+ 11. Kg3 e5
>>> 14-> 1:54 4.01 1. Rxh7 Kxh7 2. Rh2+ Kg8 3. Qh4 Bxf6
>>> 4. exf6 Kf8 5. Qh8+ Qg8 6. f7 Qxh8
>>> 7. Rxh8+ Kxf7 8. Rxc8 Kg7 9. Kh2 g5
>>> 10. Bxg5 Rxb2+ 11. Kg3 e5
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.