Author: Vasik Rajlich
Date: 13:56:26 01/27/05
Go up one level in this thread
On January 27, 2005 at 13:17:23, Matthew Hull 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. > > >Are there no free engines that show this behavior also. Don't they all? > > Actually - on second thought, yes, simple futility pruning would do this too. So I guess it's possible Shredder is doing SE (or something similar) with big futility pruning. So let me say it differently: I strongly suspect that the top engines are doing something anti-SE, that is, favoring (statistically) good moves over forcing moves, whereas SE favors forcing moves over good moves. Just an impression ... Vas > >> >>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 >>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.