Author: Gerd Isenberg
Date: 14:23:14 01/26/05
Go up one level in this thread
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 Hi Axel, welcome and thank you for sharing your ideas! Making a few hash entries more resistant against overwrites sounds fine. Doubling the costs for 90-99% first cuts sounds a bit expensive - but of course you may benefit in further iterations from resistant hash hits of those nodes tagged as singular. As mentioned already by Bob, while finishing the last iteration, you did a lot of dual multicuts to detect a few new singular cuts with full depth, but without further extend to "profit" from the detection. What about a final iteration with no further (or some centi-plies) depth increment - just "solving" the new detected singular extensions? Have you considered "Multi-Cut pruning in Game-Tree Search" by Yngvi Björnsson and Tony Marsland? http://www.cs.ualberta.ca/~yngvi/Papers/tcs2001.pdf Cheers, Gerd
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.