Author: Vincent Diepeveen
Date: 04:48:14 01/28/05
Go up one level in this thread
On January 28, 2005 at 04:33:50, Vasik Rajlich wrote: >On January 27, 2005 at 19:56:58, Vincent Diepeveen wrote: > >>On January 27, 2005 at 13:12:09, Vasik Rajlich wrote: >> >>>On January 27, 2005 at 11:16:22, Vincent Diepeveen wrote: >>> >>>>On January 27, 2005 at 04:35:46, Vasik Rajlich wrote: >>>> >>>>>On January 26, 2005 at 08:50:03, Dr. Axel Steinhage wrote: >>>>> >>>>>>Hi all, >>>>>> >>>>>>I registered to this forum just a week ago. However I have quite some experience >>>>>>in Chess-Programming although I always did it for myself only. In the late 80ies >>>>>>I wrote an Assembler Program for Z80 which was on the same level as Colossus4 at >>>>>>that time. Then I stopped programming for more than a decade. One year ago I >>>>>>restarted with a new Engine in ANSI C. I named it "Astimate" and concerning the >>>>>>limited time I can invest in that hobby, I think I am quite far already. I am >>>>>>very proud on the fact that I never ever looked into someone elses code but >>>>>>wanted to discover everything on my own. Being a scientist by education, I read >>>>>>the important publications though! Doing that, I learned a lot about Singular >>>>>>Extensions, starting out from the first paper of the DeepBlue team up to the >>>>>>various comments by Bob and others here in the forum. >>>>>>It seemed to me that so far SE is still a "nice idea" only. The problem seems to >>>>>>be with the efficient implementation. So I sat down for quite some time and >>>>>>tried to come up with an algorithm that works well in practice. Now, I think, I >>>>>>have found one. I made some tests and so far it looks very good as it finds >>>>>>lotsa combinations earlier without adding a lot overhead. Before going into more >>>>>>testing, I would like to hear the programming-gurus' opinion about the idea. So >>>>>>please give your comments. The algorithm works as follows: >>>>>> >>>>>>I do a normal Search (Soft NegaScout, PVS, Aspiration, Verified Nullmove (R=3), >>>>>>Hashtables, Killer, ...) and keep track of the best and the second best move >>>>>>when testing out all possible moves. When the best and the second best differ by >>>>>>a given margin S, I define the move as singular. So far, this is well known. But >>>>>>now come two innovations: >>>>>>1. in case of a fail high, the best move may be singular but I don't know it >>>>>>because I have cut off before searching all moves. This, I prevent as follows: >>>>>>In case of a fail high, I look if the second best move is within the S window. >>>>>>If so, I cut off cuz the best move cannot be singular. If not, I go on searching >>>>>>(although I could cut off already!) with reduced depth (R=2). I do this until I >>>>>>have searched all moves or until I have a second best move within S (or another >>>>>>fail high, of course). If all the other moves are outside the S window, I define >>>>>>the move singular. >>>>>>2. If I found a move to be singular, I do NOT do a research. Instead, I store >>>>>>this information in the Hashtable and prevent this hash-entry from being >>>>>>overwritten in the future. In the next depth-iteration, I know from the >>>>>>Hash-Entry then already upfront that this move might be singular and extend its >>>>>>max depth. Of course, I don't do the singularity search on the move I have >>>>>>already classified singular. >>>>>> >>>>>>Because of the reduced depth singularity-search after cutoff and omitting the >>>>>>research, there is practically no overhead other than the extension itself. >>>>>>Of course, this algorithm is "cheapo SE" as it might miss quite a lot of >>>>>>Singular moves: first, the reduced depth might not discover a singularity. >>>>>>second, the "second best" value may be wrong, as it might also only be a >>>>>>boundary (have to analyse that). Finally, the information that a move is >>>>>>singular stems from the last depth iteration. However, in the current depth >>>>>>iteration, the move may not be singular anymore. >>>>>> >>>>>>Despite of these drawbacks, the algorithm turned out to work quite well on some >>>>>>test positions with my engine. Before pdoing more tests, however, I would rather >>>>>>like to hear what you think about my idea. >>>>>> >>>>>>Axel >>>>> >>>>>I doubt it makes any real difference. Basically you're doing R==3 instead of >>>>>R==2, and skipping an intial R==2 search of the first move which is useful >>>>>anyway as an IID search. >>>>> >>>>>Note also that all the fancy changes to the hash tables usually change your >>>>>engine level by at most 1 rating point, you could safely skip that part. >>>>> >>>>>My problem with SE is that I don't see a top engine from 2008 (let's say) using >>>>>it. It's always nice to see some shot in X ply instead of X+3 ply, but you won't >>>>>see those shots in the really important games. >>>>>Vas >>>> >>>>I'm very sure at least 1 top engine in 2008 will be using it. However most >>>>likely that won't be Diep. Please keep in mind that SE are excellent form of >>>>extensions to compensate dubious forward pruning near the leafs. >>>> >>>>More interesting question is whether in 2008 people will be using multicut. >>>> >>>>The reason why multicut is more interesting than SE is because multicut REDUCES >>>>the branching factor. SE doesn't :) >>>> >>>>It gets Diep a deeper search (0.5 ply or so), tactical it seems to work, but >>>>positional i have my doubts. And the deeper you search the more dubious it gets. >>>> >>>>Stefan Meyer-Kahlen like a real profi obviously doesn't want to discuss them >>>>with me. >>>> >>>>So that's why it's good now to ask this publicly. When i analyze with shredder >>>>7.04 versus shredder8 i can't avoid getting the impression that somehow S8 is >>>>using them. S8 is missing so much more positional than S7.04 that it can only an >>>>algorithm like this explaining it. >>>> >>>>What are your thoughts there? >>>> >>>>Vincent >>> >>>Shredder 8 is definitely not using SE - in fact, it's doing something quite the >>>opposite. Try setting up a position where there is a forcing piece sac at the >>>root, then clear the hash table and set up the position one move later, right >>>after the piece sac, and see how much fewer ply you need for the second search. >>>It's usually >1 ply difference, and I've never seen a 0-ply difference. Junior >>>also shows this behavior. >>> >>>BTW I don't like the probcut idea for chess. Too often the eval just needs a >>>certain amount of search - for example, a manoever Nf3-g1-e2-c3-d5. It looks bad >> >>probcut != multicut >> >>Probcut type ideas are IMHO nonsense. >> >>Multicut more interesting as it requires more than 1 fail high. >> > >So what is multicut? > >BTW Fabien is using the probcut idea in Fruit 2.0 - maybe it's worth a try. I >also agree though, it doesn't sound right. If a program searches inefficient, everything seems to work to get it more efficient. For multicut see online paper from Bjornsson/Marsland (there is an umlaut at the first o from Bjornsson, so it might be more clever to search for the name marsland at altavista.com) Note i have the paper on real paper in an ICGA book. The advantage of being a member of ICGA is you never miss anything. >Vas > >>>until the end. Of course it's a question of statistics - one thing is for sure, >>>search is a really strange thing. >>> >>>Vas
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.