Author: Robert Hyatt
Date: 09:23:15 01/27/05
Go up one level in this thread
On January 27, 2005 at 04:38:04, Dr. Axel Steinhage wrote: >On January 26, 2005 at 12:59:42, Robert Hyatt wrote: > >>On January 26, 2005 at 08:50:03, Dr. Axel Steinhage wrote: > >>Your case of "fail high" seems to be terribly expensive. Doubling the size of >>the tree at a minimum, because to search the second move after you have a >>fail-high is pure overhead. DB did this as well, but they did do a search to a >>significantly reduced depth, rather than a normal search. Hsu called this "FH >>singular" (fail-high singular). I implemented it exactly as he spelled it out, > >Thanks for your comments! Just wanted to comment on this reply from you (above): >My "fail high" is not expensife, because I also go on searching with reduced >depth (I think I wrote that I use a reduction factor of R=2). OK, but even that is a huge cost, as where you normally did a single move search of size W^D (less alpha beta reduction of course) you now do W^D + N * W^(D-2) which blows the tree way up. It generally costs a ply in the Cray Blitz testing I did in 93-94... But the program seemed to play better. But that was with null move R=1, not recursively applied. In Crafty, it seemed to be highly inconsistent with null move R=2-3... >Maybe I did not make myself clear enough. I think the main difference between my >algorithm and the others I have seen so far is, that I NEVER touch a move twice >and I don't even have to generate all moves most of the time. What Hsu et Al did >was to FIRST find the best move and THEN test whether it is singular. What most >people do today is FIRST do a complete search (although at reduced depth) to >find a singular move and then search the whole branch again with the singular >move having higher depth, right? Yes, but remember that Hsu's approach is _far_ more accurate. At PV nodes he _really_ identifies singular moves. The "el-cheapo" solution only identifies moves that appear to be singular to a reduced depth search. But what if things only get difficult at the full search depth? You don't notice the singularity and overlook that which you were hoping to find... Also speaking for myself and Bruce only, for the "el-cheapo" we didn't search _all_ moves to reduced depth. We searched only a few, because at an "ALL" node, singularity makes no sense and searching ALL nodes to reduced depth is just wasting time. Our approach reduces ALL node overhead, but at the same time means we can fail to find "the" singular move at a CUT node, if we don't somehow get it near the top of the move list to fall within the set of moves we are going to test... > This also means to touch this branch twice. >What I do, however, is only to GO ON searching (with reduced depth!) after a >fail high. So no RESEARCH but a CONTINUATION of the search. This seems costly, >but it may not be! Most of the time the next move I search (after the fail high) >is already within the Singular window (or a fail high again). Nothing wrong with that, that is exactly how Hsu implemented the FH-singular test, and is the same way I did it in CB, except we always re-searched to D+1 if the singular test was passed, which I think is important, otherwise your last iteration (arguably the most important one) will note singular moves but won't extend them to see what effect they produce. >Plus, I have many >conditions where I don't have to go on searching anyway. >It seems that the test for singularity produces nearly no overhead. Only the >actual extension. But as you stated: this may already be too much overhead. I >can believe, that SE is somehow orthogonal to Nullmove. I will go on testing. >I did not do complete testing so far. I only checked the solution times for a >set of test positions. But that does not mean anything for the practical game >later on. I will keep you up to date on my findings, if you like. > >Thanks, Axel Certainly, I'm sure everyone is interested. My observations to date have been that SE helps in tactical situations, but when you play a real game, and in non-tactical situations you lose a ply of search overall, you make mistakes of a different sort by not seeing positionally deep enough... IE I could never get a SE implementation that would beat my non-SE version in heads-up competition on equal hardware. The margin of victory for the non-SE version was approximately what would be produced by just playing against the same version on hardware 1/3 as fast to remove a ply of search that way instead..
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.