ChessUSA.com TalkChess.com
Hosted by Your Move Chess & Games
 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

Singular extension
Post new topic    TalkChess.com Forum Index -> Computer Chess Club: Programming and Technical Discussions Flat
View previous topic :: View next topic  
Author Message
H.G.Muller



Joined: 10 Mar 2006
Posts: 22012
Location: Amsterdam

PostPost subject: Singular extension    Posted: Fri Jul 17, 2015 9:15 pm Reply to topic Reply with quote

When I was making my mini-Shogi opening book, analyzing all positions along the opening lines to high depth, I noticed there is a staggering number of positions where there is only a single playable move, and every deviation causes a score drop > 1.00. Having 6 or 8 such half-moves in a row is not uncommon, and usually the score from analyzing the start position of such a sequence is substantially different from a similar-depth analysis at the end.

So I realized my search must be all wrong. Or at least sub-optimal. When in a PV node at ply level n it spends a lot of time proving that all moves but the best are worse than a certain score, while this perceived best move might be doomed to lead to a very poor position, actually making it fail low compared to some of the moves that are now rejected, and in any case would require those other moves proven bad compared to a much more tight bound, making the refutation trees used on earlier iterations often inadequate.

When conducting the search of good opening lines by hand, I quickly learned first to follow moves with a promising score for as long they were forced (as seen by multi-PV). Then at least I got a more or less reliable score I could use for testing the side branches against.

In an automated search, a singular extension should do this. I have never used one in any of my engines, though. After some thinking, the following algorithm seems reasonable to me:

At some remaining depth, say 7, rather than searching the non-PV move in PV nodes with the null window at the PV-move score (i.e. regular PVS), I search them with an offsetted null window, bestScore - 90. If any of them fails high, it gets re-searched with the normal PVS null-window, and the remaining moves will also be searched as regular PVS. (I.e., the offset is reset from the initial 90 to 0.) If after searching all moves the offset is still 90, I know the PV move was singular.

In that case, I want to re-search the PV move with an extension (i.e. at 8 ply). For the search window there are two cases:
(1) The original alpha for the node was less than 90 below (non-extended) PV-move score. In that case I keep using the normal search window. If the extended search does not fail low, the score was still above that of all other moves, and I am done. If it fails low, the entire node fails low (as the other moves already failed lower), and I am done as well.
(2) The original alpha was more than 90 below the PV-move score. Now I up alpha to bestScore-90 for the extended PV-move search. If the search does not fail low, the PV move remains best, and I am done. However, if it fails low, one of the other moves might now be best. And I have no idea of the true score of any of the moves. (But I don't want to continue piling extension on extension in the designated PV branch to push the score below the original alpha, which might actually be -INFINITY, when other moves might already be better.)

So basically the whole search has to be attempted again, first searching the PV move non-extended with the original alpha as lower window bound, which will now profit from hash hits of the extended search as far as pushing the score below the old bestScore-90 concerns, but is going to work harder for the opponent to see if he can push the score deeper down towards the original alpha, or even beyond it. (Of course if the returned upper bound from the previous extended fail low of the PV move was already below the original alpha, we can discard the PV move right away, and can continue like normal PVS with a null window at the original alpha for the other moves.) If this again provides a score above alpha, it becomes the new bestScore for the re-search, and we repeat the whole circus. This might again prove that the lowered score of the extended PV-move search is singular, after which the extended re-search of it will again follow, and, by the time it reaches the tips of that branch might have to extend even deeper if more singular moves follow. Of course the PV move might now not be singular, because of the score drop it suffered from extension, or might not even be best. In which case another move now becomes PV move, and will then undergo the same procedure of singularity testing and extension.

Does that sound about like how it should be done?
Back to top
View user's profile Send private message Visit poster's website
Display posts from previous:   
Subject Author Date/Time
Singular extension H.G.Muller Fri Jul 17, 2015 9:15 pm
      Re: Singular extension Marcel van Kervinck Fri Jul 17, 2015 9:50 pm
      Re: Singular extension Robert Hyatt Fri Jul 17, 2015 9:52 pm
            Re: Singular extension Alvaro Cardoso Mon Jul 27, 2015 7:03 pm
                  Re: Singular extension Eelco de Groot Tue Jul 28, 2015 3:33 am
      Re: Singular extension Henk van den Belt Fri Jul 17, 2015 10:02 pm
      Re: Singular extension Eelco de Groot Fri Jul 17, 2015 10:34 pm
      Re: Singular extension H.G.Muller Sat Jul 18, 2015 9:56 am
            Re: Singular extension Dennis Sceviour Mon Oct 26, 2015 3:19 pm
                  Re: Singular extension H.G.Muller Mon Oct 26, 2015 3:46 pm
                        Re: Singular extension Dennis Sceviour Mon Oct 26, 2015 4:25 pm
                              Re: Singular extension H.G.Muller Tue Oct 27, 2015 8:58 am
                                    Re: Singular extension Dennis Sceviour Tue Oct 27, 2015 2:19 pm
                                          Re: Singular extension H.G.Muller Tue Oct 27, 2015 2:28 pm
                                    Re: Singular extension Robert Hyatt Tue Oct 27, 2015 6:05 pm
                                          Re: Singular extension H.G.Muller Tue Oct 27, 2015 6:31 pm
                                                Re: Singular extension Peter Österlund Tue Oct 27, 2015 7:44 pm
                                                      Re: Singular extension Lucas Braesch Sat Oct 31, 2015 11:26 am
                                                            Re: Singular extension Robert Hyatt Sun Nov 01, 2015 3:48 pm
                                          Re: Singular extension Alvaro Cardoso Fri Oct 30, 2015 12:30 am
                  Re: Singular extension Eelco de Groot Mon Oct 26, 2015 5:03 pm
                        Re: Singular extension Dennis Sceviour Mon Oct 26, 2015 6:47 pm
                  Re: Singular extension Robert Hyatt Mon Oct 26, 2015 6:57 pm
                        Re: Singular extension Dennis Sceviour Mon Oct 26, 2015 7:26 pm
                              Re: Singular extension Robert Hyatt Mon Oct 26, 2015 9:44 pm
                        Re: Singular extension Steve Maughan Fri Oct 30, 2015 3:09 pm
                              Re: Singular extension Dennis Sceviour Fri Oct 30, 2015 5:26 pm
      Re: Singular extension J. Wesley Cleveland Fri Oct 30, 2015 4:50 am
            Re: Singular extension H.G.Muller Fri Oct 30, 2015 11:18 am
                  Re: Singular extension daniel jose Fri Oct 30, 2015 2:21 pm
Post new topic    TalkChess.com Forum Index -> Computer Chess Club: Programming and Technical Discussions

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum




Powered by phpBB © 2001, 2005 phpBB Group
Enhanced with Moby Threads