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 

Transposition table based pruning idea
Post new topic    TalkChess.com Forum Index -> Computer Chess Club: Programming and Technical Discussions Flat
View previous topic :: View next topic  
Author Message
J Donald



Joined: 24 Oct 2012
Posts: 247

PostPost subject: Transposition table based pruning idea    Posted: Mon Dec 25, 2017 10:05 pm Reply to topic Reply with quote

Hi all,

Merry Christmas!

I was wondering if anyone has tried a scheme like the following in a fail-soft environment:

If:
- trans_depth == depth -1, not in pv, and trans_score is far below alpha or far above beta (with the correct bound of course), then return trans_value instead of searching the position.

While this seems fairly sound as long as the margin is large enough, that by itself is obviously not sufficient as it would simply cause the engine to skip alternate depths when searching these lines which are far from the alpha/beta window.

So, to avoid this problem, if trans_depth == depth -2 (i.e. the next ply):
- we search the position at depth-1 while deactivating the tt-based pruning
- if the result of the search is unexpected (i.e. cut node doesn't cut or all node produces a beta cutoff), then we note the best move from the depth-1 search for move ordering and then search to full depth. Otherwise, we return the depth-1 score.

This way we also avoid searching the full depth unless absolutely necessary.

I'm getting a promising +8 elo in self-play after 6000 games (more games needed of course), so I was wondering if anyone has tried something like this? Or are there any potential problems?

Psuedo-code:

Code:

if (SearchCurrent[ThreadId]->trans_pruning){ // this is a flag to enable/disable the pruning scheme
    if (trans_depth+1 == depth){

   trans_value = value_from_trans(trans_value,height);         

   if ((TRANS_IS_LOWER(trans_flags) && trans_value >= beta + margin) || (TRANS_IS_UPPER(trans_flags) && trans_value <= alpha - margin))
      return trans_value;
   } else if (trans_depth+2 == depth){

   trans_value = value_from_trans(trans_value,height);
                     
         // if last time we returned early from trans (HACK: alpha & beta may have changed)
   if ((TRANS_IS_LOWER(trans_flags) && trans_value >= beta + margin) || (TRANS_IS_UPPER(trans_flags) && trans_value <= alpha - margin)) { //
                     
      // we do a new search at depth-1
      SearchCurrent[ThreadId]->trans_pruning = false;
      value = full_search(board,alpha,beta,depth-1,height,new_pv,node_type,false,ThreadId);
      SearchCurrent[ThreadId]->trans_pruning = true;
                               
      // if the search returns the expected value / cutoff, we return its value. if not, go on to full depth search
      if (node_type == NodeCut && value >= beta)
          return value;
      if (node_type == NodeAll && value <= alpha)
          return value;
                                  
      // use info from previous depth-1 search   
      trans_move = new_pv[0];
     }
   }
}
Back to top
View user's profile Send private message
Display posts from previous:   
Subject Author Date/Time
Transposition table based pruning idea J Donald Mon Dec 25, 2017 10:05 pm
      Re: Transposition table based pruning idea J Donald Mon Dec 25, 2017 10:07 pm
      Re: Transposition table based pruning idea Mark Lefler Mon Jan 01, 2018 5:38 am
            Re: Transposition table based pruning idea J Donald Mon Jan 01, 2018 7:06 am
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