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 

A search enhancement?
Post new topic    TalkChess.com Forum Index -> Computer Chess Club: Programming and Technical Discussions Flat
View previous topic :: View next topic  
Author Message
Daniel Homan



Joined: 28 Dec 2011
Posts: 109
Location: United States
PostPost subject: A search enhancement?    Posted: Mon Apr 30, 2012 12:18 pm Reply to topic Reply with quote
I've been testing an idea for pruning or aborting a search in the middle of the movelist on a given node. I am not sure if this is a new idea... In fact, it is so simple, I would be surprised if it is new. A quick search of the chess progamming wiki shows a similar idea, "uncertainty cutoffs", which is more precise about when to terminate a node. The idea I tested makes no use of uncertainty and simply makes the decision of whether to abort based on position in the movelist.

The idea applies to nodes where we have searched a significant fraction of the moves already, so there is high probability the node will fail low. At this point, we simply abort the search and return alpha rather than continue trying the rest of the moves.

This seems quite drastic, and I expected it to be one of the many ideas that fail miserably, but I was pleasantly surprised that it seemed to be worth about +20 to +30 elo....

Code:

Rank Name                  Elo    +    - games score oppo. draws
   1 GNU Chess 6.0.1       100   10   10  3000   61%    19   18%
   2 Arasan 14.0 (1 cpu)    57   10   10  3000   55%    19   21%
   3 Crafty-21.6            56   10   10  3000   55%    19   22%
   4 EXchess v2012_04_29    31    8    8  5000   50%    33   23%
   5 EXchess v2012_04_28    24    8    8  5000   49%    33   24%
   6 DoubleCheck 2.7        20   10   10  3000   50%    19   18%
   7 EXchess vref            0    8    8  5000   46%    33   24%
   8 EXchess v6.10         -66   10   10  3000   37%    19   40%


EXchess vref is the current best version of my engine without this idea implemented. v2012_04_28 and v2012_04_29 have less and more agressive implementations of the idea respectively. The other engines are my current test opponents. The test games here are very fast (6s + 0.1s per move per side). The error bars here are 2 sigma (95% confidence).

The implementation is absolutely straight forward... essentially we wait until we get to the part of the movelist where we would normally be testing for LMR and pruning (after all good captures and killer moves), and we simply check what fraction of the moves have been played... if that fraction is larger than a certain amount, abort the search.

v2012_04_28 applies this with the equivalent of the following pseudo-code...

Code:

// Search Abort Test
if(depth < 5
   && !first_move_searched
   && !pos.check            // we are not in check
   && !next->pos.check      // current move doesn't cause check
   && move.score < 2000000  // move scored below good captures & killers
   && alpha == beta - 1     // zero-window node
   && alpha > -MATE/2       // not during a MATE resolution
   && 100*mcount > (100-10*(5-depth))*total_moves))
{
  clean-up and abort search by returning alpha
}


v2012_04_29 applies it in the same way but at depth < 7 using

Code:

if(100*mcount > (100-10*(7-depth))*total_moves))
 


which is quite a bit more agressive.

It is surprising to me that this works as well as it seems to... especially the more agressive version. Other than the two versions above, I've made no serious attempt to tune this up or try variations on the conditions, so it is possible there is more gain here to be had. Does anyone have experience with this type of idea? My best guesses for its apparent success are...

(1) Something about my implementation of LMR or pruning is not optimal, so this idea exploits some of the potential gain there.

(2) It somehow is covering up a bug in my engine

(3) It is actually an enhancement.

- Dan
Back to top
View user's profile Send private message
Display posts from previous:   
Subject Author Date/Time
A search enhancement? Daniel Homan Mon Apr 30, 2012 12:18 pm
      Re: A search enhancement? F. Bluemers Mon Apr 30, 2012 12:25 pm
      Re: A search enhancement? Ronald de Man Mon Apr 30, 2012 1:57 pm
            Re: A search enhancement? Lucas Braesch Mon Apr 30, 2012 2:06 pm
            Re: A search enhancement? Jon Dart Mon Apr 30, 2012 2:46 pm
            Re: A search enhancement? Daniel Homan Mon Apr 30, 2012 8:01 pm
                  Re: A search enhancement? Jon Dart Tue May 01, 2012 12:24 am
                  Re: A search enhancement? Ferdinand Mosca Tue May 01, 2012 5:47 am
                        Re: A search enhancement? Vincent Diepeveen Tue May 01, 2012 12:01 pm
                              Re: A search enhancement? Daniel Homan Tue May 01, 2012 8:45 pm
      Re: A search enhancement? Joona Kiiski Mon Apr 30, 2012 2:35 pm
      Re: A search enhancement? -- Update Daniel Homan Sat May 05, 2012 10:44 am
            Re: A search enhancement? -- Update Jon Dart Sat May 05, 2012 11:32 pm
            Re: A search enhancement? -- Update Joona Kiiski Sun May 06, 2012 4:22 pm
                  Re: A search enhancement? -- Update Uri Blass Sun May 06, 2012 8:12 pm
                        Re: A search enhancement? -- Update Joona Kiiski Mon May 07, 2012 7:41 am
                              Re: A search enhancement? -- Update Uri Blass Mon May 07, 2012 8:31 am
            Re: A search enhancement? -- Update F. Bluemers Mon May 07, 2012 5:14 pm
                  Re: A search enhancement? -- Update Matthew R. Brades Tue May 08, 2012 2:56 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