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 

SEE on non-capture moves in main search
Post new topic    TalkChess.com Forum Index -> Computer Chess Club: Programming and Technical Discussions Flat
View previous topic :: View next topic  
Author Message
Robert Hyatt



Joined: 27 Feb 2006
Posts: 15816
Location: Birmingham, AL
PostPost subject: Re: SEE on non-capture moves in main search    Posted: Thu Mar 29, 2007 9:35 pm Reply to topic Reply with quote
Tord Romstad wrote:
bob wrote:
I think the problem is this: with things like hash moves, good captures, killers, etc, by the time you have tried all of those, either you have already failed high, or you are never going to fail high at this position.


Perhaps, but if it were as simple as this, wouldn't the use of history counters also be worthless for move ordering?


Not sure. I don't use history counters any longer. Smile

The effect was never very large for me, and over the past couple of years, it became a pretty-much break-even thing, so I took it out.

Quote:


With regard to SEE and move ordering, my intuition disagrees with my experience. This is what I have found:

  • For captures, it is best to search the winning and equal captures before the losing captures, and to prune losing captures in the quiescence search. This makes perfect sense. However, among the winning and equal captures, MVV/LVA move ordering performs better than SEE move ordering, which is counter-intuitive to me. After some thought, I think I have an explanation: If there there is a winning capture in the position, this winning capture will usually still be available after the exchange of some more valuable piece. Exchanging strong pieces before capturing the hanging piece reduces the subtree size, because both sides will have fewer legal moves after the exchange (on average).


I have never seen that kind of result with MVV/LVA vs SEE. You can find old discussions on this topic on r.g.c.c back in the early 90's. I ran a bunch of tests and even distributed a version of Crafty where one could choose between SEE and MVV/LVA for q-search move ordering, and others ran lots of tests as well. The net outcome was that SEE produced a tree roughly 10% smaller over a large test set. But when SEE was augmented with the "cull losing captures in q-search idea" then the difference went up dramatically, reducing the size of the tree by 50% (after that original 10% reduction). Numerically, if MVV/LVA searched a tree of size 100,000,000 nodes, SEE would search 90,000,000 nodes. But if SEE was used to eliminate losing q-search captures completely, the tree size was reduced to 45,000,000 nodes.

I've _never_ seen MVV/LVA out-perform SEE, except for the occasional pathological case (atypical).


Quote:



  • For the non-capturing moves after the hash move and killers, history move ordering performs better than no move ordering, as expected. But trying to refine this by using SEE values does not work. I have tried to sort the moves into two groups, first searching non-captures with SEE value zero ordered by history scores, and then searching losing non-captures by their SEE values. This performs slightly worse than simplistic history move ordering for all moves. I have no idea why.
  • Searching the losing captures after the non-captures is slightly better than searching them before the non-captures. This is not entirely unexpected, but intuitively I would expect that searching the losing non-captures after the losing captures (i.e. first the hash move, then winning and equal captures, then killers, then non-losing non-captures, then losing captures, and finally losing non-captures) would perform better still. Surprisingly, this is not the case.



    • Are you searching tactical positions? If so, losing captures before non-captures would make sense. Otherwise, to me, it does not at all.


    Quote:

    It is very frustrating that I haven't found a way to use SEE to improve the ordering of non-captures, because calling the SEE for every move doesn't slow me down noticably. Perhaps I can find some other way to use the SEE values (pruning or reduction decisions, maybe).

    Tord
    Back to top
    View user's profile Send private message
    Display posts from previous:   
    Subject Author Date/Time
    SEE on non-capture moves in main search Gary Wed Mar 28, 2007 11:25 pm
          Re: SEE on non-capture moves in main search Robert Hyatt Thu Mar 29, 2007 1:17 am
                Re: SEE on non-capture moves in main search Tord Romstad Thu Mar 29, 2007 10:03 am
                      Re: SEE on non-capture moves in main search ed Thu Mar 29, 2007 1:34 pm
                            Re: SEE on non-capture moves in main search Sam Hamilton Fri Mar 30, 2007 12:07 am
                            Re: SEE on non-capture moves in main search Tord Romstad Fri Mar 30, 2007 11:46 am
                      Re: SEE on non-capture moves in main search Robert Hyatt Thu Mar 29, 2007 9:35 pm
                            Re: SEE on non-capture moves in main search H.G.Muller Thu Mar 29, 2007 10:27 pm
                                  Re: SEE on non-capture moves in main search Robert Hyatt Fri Mar 30, 2007 12:05 am
                                        Re: SEE on non-capture moves in main search H.G.Muller Fri Mar 30, 2007 6:50 am
                                              Re: SEE on non-capture moves in main search Robert Hyatt Fri Mar 30, 2007 9:27 pm
                                                    Re: SEE on non-capture moves in main search Tord Romstad Fri Mar 30, 2007 10:29 pm
                                                          Re: SEE on non-capture moves in main search Robert Hyatt Sun Apr 01, 2007 1:51 am
                                                                Re: SEE on non-capture moves in main search Tord Romstad Sun Apr 01, 2007 7:54 am
                                                                      Re: SEE on non-capture moves in main search Robert Hyatt Mon Apr 02, 2007 1:57 am
                                                                Re: SEE on non-capture moves in main search H.G.Muller Sun Apr 01, 2007 10:22 am
                                                                      Re: SEE on non-capture moves in main search Robert Hyatt Mon Apr 02, 2007 2:05 am
                                                                            Re: SEE on non-capture moves in main search H.G.Muller Mon Apr 02, 2007 12:31 pm
                                                                                  Re: SEE on non-capture moves in main search Robert Hyatt Mon Apr 02, 2007 3:56 pm
                                                                                        Re: SEE on non-capture moves in main search Steven Edwards Mon Apr 02, 2007 4:44 pm
                                                                                              Re: SEE on non-capture moves in main search H.G.Muller Mon Apr 02, 2007 4:59 pm
                                                                                              Re: SEE on non-capture moves in main search Robert Hyatt Mon Apr 02, 2007 6:44 pm
                                                                                              Re: SEE on non-capture moves in main search Robert Hyatt Mon Apr 02, 2007 6:40 pm
                                                                                        Re: SEE on non-capture moves in main search H.G.Muller Mon Apr 02, 2007 4:53 pm
                                                    Re: SEE on non-capture moves in main search H.G.Muller Sat Mar 31, 2007 8:38 am
                                                          Re: SEE on non-capture moves in main search Robert Hyatt Sun Apr 01, 2007 1:59 am
                                                                Re: SEE on non-capture moves in main search Tord Romstad Sun Apr 01, 2007 7:58 am
                                                                      Re: SEE on non-capture moves in main search Robert Hyatt Mon Apr 02, 2007 3:57 pm
                                                                      Re: SEE on non-capture moves in main search Peter Fendrich Mon Apr 02, 2007 5:19 pm
                                                                            Re: SEE on non-capture moves in main search Robert Hyatt Mon Apr 02, 2007 6:46 pm
                                                                            Re: SEE on non-capture moves in main search Tord Romstad Mon Apr 02, 2007 6:51 pm
                                                                                  Re: SEE on non-capture moves in main search Peter Fendrich Mon Apr 02, 2007 7:53 pm
                                                                                        Re: SEE on non-capture moves in main search H.G.Muller Mon Apr 02, 2007 9:01 pm
                                                                                              Re: SEE on non-capture moves in main search Peter Fendrich Mon Apr 02, 2007 9:30 pm
                                                                                              Re: SEE on non-capture moves in main search H.G.Muller Tue Apr 03, 2007 8:46 am
                                                                                              Re: SEE on non-capture moves in main search Peter Fendrich Tue Apr 03, 2007 10:29 am
                                                                                              Re: SEE on non-capture moves in main search Robert Hyatt Tue Apr 03, 2007 9:23 pm
                                                                                              Re: SEE on non-capture moves in main search Tord Romstad Wed Apr 04, 2007 2:38 pm
                                                                                              Re: SEE on non-capture moves in main search Peter Fendrich Wed Apr 04, 2007 7:49 pm
                                                                                              Re: SEE on non-capture moves in main search Tony Tue Apr 03, 2007 10:54 am
                                                                                              Re: SEE on non-capture moves in main search Robert Hyatt Tue Apr 03, 2007 9:24 pm
                                                                                              Re: SEE on non-capture moves in main search H.G.Muller Tue Apr 03, 2007 9:29 pm
                                        Re: SEE on non-capture moves in main search Tord Romstad Fri Mar 30, 2007 11:40 am
                                  Re: SEE on non-capture moves in main search Tord Romstad Fri Mar 30, 2007 11:54 am
                                        Re: SEE on non-capture moves in main search H.G.Muller Fri Mar 30, 2007 1:28 pm
                                              Re: SEE on non-capture moves in main search H.G.Muller Fri Mar 30, 2007 4:41 pm
                            Re: SEE on non-capture moves in main search Tord Romstad Fri Mar 30, 2007 11:30 am
                                  Re: SEE on non-capture moves in main search Uri Blass Fri Mar 30, 2007 11:50 am
                                        Re: SEE on non-capture moves in main search Tord Romstad Fri Mar 30, 2007 10:32 pm
                                  Re: SEE on non-capture moves in main search H.G.Muller Fri Mar 30, 2007 12:16 pm
                                  Re: SEE on non-capture moves in main search Robert Hyatt Fri Mar 30, 2007 9:32 pm
                                        Re: SEE on non-capture moves in main search Tord Romstad Fri Mar 30, 2007 10:00 pm
          Re: SEE on non-capture moves in main search Mark Lefler Thu Mar 29, 2007 6:30 am
          Re: SEE on non-capture moves in main search H.G.Muller Thu Mar 29, 2007 9:28 am
                Re: SEE on non-capture moves in main search Tord Romstad Thu Mar 29, 2007 10:13 am
                      Re: SEE on non-capture moves in main search H.G.Muller Thu Mar 29, 2007 12:03 pm
                            Re: SEE on non-capture moves in main search Tord Romstad Thu Mar 29, 2007 12:39 pm
                                  Re: SEE on non-capture moves in main search H.G.Muller Thu Mar 29, 2007 2:15 pm
                                        Re: SEE on non-capture moves in main search Zach Wegner Thu Mar 29, 2007 9:10 pm
                      Re: SEE on non-capture moves in main search Steven Edwards Thu Mar 29, 2007 2:18 pm
                      Re: SEE on non-capture moves in main search Rob Sun Apr 01, 2007 6:01 pm
          Re: SEE on non-capture moves in main search Gary Sun Apr 01, 2007 8:26 am
          Re: SEE on non-capture moves in main search Markoff Thu Apr 05, 2007 11:25 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