Author: Vasik Rajlich
Date: 10:12:09 01/27/05
Go up one level in this thread
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 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.01 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.