Author: Matthew Hull
Date: 10:17:23 01/27/05
Go up one level in this thread
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? > >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.