Author: Robert Hyatt
Date: 08:38:01 08/21/02
Go up one level in this thread
On August 21, 2002 at 00:54:29, Russell Reagan wrote: >On August 21, 2002 at 00:18:40, Robert Hyatt wrote: > >>On August 20, 2002 at 22:44:28, Russell Reagan wrote: >> >>>On August 20, 2002 at 21:52:05, Robert Hyatt wrote: >>> >>>>That's backward. A hash hit near the root saves a _huge_ amount of work. >>>>Just think how big the sub-tree is one ply away from the root, compared to >>>>the sub-tree one ply away from a tip position... >>> >>>His concern was that a false hash hit near the root would cause a blunder. If >>>you didn't probe for the first (say) 2 plies, you'd still get that same result >>>from the hash hit you got at ply 3, right? Maybe I'm not thinking about it >>>correctly, but as far as I can tell, the only *extra* work you're doing here is >>>a 2 ply search, which is nothing. Unless I'm missing something (which wouldn't >>>be the first time...) >>> >>>Russell >> >> >>You are doing a (say) 12 ply search. If you probe at ply=2 you might get a >>false hit, or not. But if you get a hit of any kind, you stop that branch at >>ply=2 and avoid a 11 ply search. >> >>That is a _lot_ of work to avoid... > >What's the difference if you spend 0.001 seconds searching the first ply and >then get a 10 ply hit instead? If you get a hash hit at ply=2, you do _zero_ work. If you don't get a hash hit, you have to do a full 11-ply search there and that is not free... > You aren't gaining an extra ply, since the 11th >ply was the first ply that you spent basically zero time searching. Even if you >searched 8 ply and got a 3 ply hit, you're still saving a _lot_ compared to the >amount of searching you did to get to the 8th ply, right? Maybe, but I want to avoid doing _any_ searching. Remember, a hash probe takes microseconds. A search from the same position can take seconds or minutes. > >I could say the same thing about null move. You are doing a 12 ply search, and >you do a few million "shallow" searches to test your null moves. I could sit >here and make it sound like null move is a piece of trash because its going to >use a _lot_ of work to do a few million shallower searches. You of course know >that's not the case, but to someone who was new to computer chess, you can say >things like this and make them believe it. > >In this case, I'm the guy you could make believe it, so I'm wondering what (if >anything) is the drawback to NOT probing at ply 1 to avoid a (probably) fatal >blunder if you get a false hash hit. 1 in 1,225 is a lot better chances of >surviving the false hit than 1 in 35. If you increase it to no probing in the >first three plies (still nothing in comparison to the full search), your chance >of blundering from the false hit go to 1 in 42,875 (all using 35 legal moves per >ply). > >It seems to be that as long as you didn't probe in the first couple of plies, it >is highly unlikely that you will suffer any consequences. If you're probing at >the first ply, your chances are 1 in about 35 that a false hit will be fatal. I don't believe this is true. For any search tree, there are "critical nodes" that must be handled correctly. An error at any of them will have consequences that affect the accuracy of the search. The question is, what is the ratio of critical nodes to non-critical nodes? I don't (yet) have a good feel for this. It is apparently a lot lower than I thought since 1 error every 1K nodes didn't harm anything in the tests I ran. It doesn't really matter where the error happens, at ply=2 or ply=20, if the node is critical to the root score results... All you do by not probing at ply=2 is hurt search efficiency, and it isn't clear that you help reduce the probability of error at all by doing that... > >Maybe I'm missing something as far as the statistical analysis goes. I never was >very good with statistics. I guess the other possibility is that the actual >probability that you will suffer on the first ply false hit is >(1/35)*(probability of a false hit)? In that case, your odds are much better at >ply 1. > >Hmm...you're the one with the PhD. Maybe you can figure this out :) > >Russell
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.