Markian Hlynka

Home * People * Markian Hlynka

Markian Hlynka

Markian Hlynka,
a Canadian computer scientist and systems analyst at University of Alberta. Along with Jonathan Schaeffer et al., Markian Hlynka researched and published on search enhancements and temporal difference learning.

Pre-Search

Abstract

This paper introduces the idea of pre-searching a position — searching it before αβ determines that it needs to be searched. Consider the case where an iteration of αβ search comes across a position p that needs to be searched to depth d1, and the transposition table reveals that p will likely need to be searched later in that iteration to depth d2 greater than d1. Pre-searching involves speculatively searching p to depth d2, even though it has not been demonstrated that search to this depth is needed. If the gamble is successful, then additional accuracy is introduced to the search (using a result with extra search depth d2 − d1). While any search extension scheme is not without some risk, empirical results indicate that the impact on the αβ search tree size is small, but the additional accuracy that is introduced improves program performance. 

Pseudo Code

// Assumptions:
// * search depth counts down to 0 (leaf node)
// * IDDepth is the iterative deepening search depth
// * searches are to a fixed depth
int AlphaBeta( state, depth, alpha, beta, presearch ) {
  if( TerminalNode( state ) || depth == 0 )
    return( Evaluate( state ) );

  save_alpha = alpha;
  save_beta = beta;
  tt_found = TTLook( state, &tt_depth, &tt_value, &tt_bound, &tt_iteration );

  if( tt_found == TRUE && tt_depth >= depth ) {
    if( tt_bound == LOWER ) alpha = MAX( alpha, tt_score );
    if( tt_bound == UPPER ) beta = MIN( beta, tt_score );
    if( tt_bound == ACCURATE ) alpha = beta = tt_bound;
    if( alpha >= beta ) return( alpha );
  }
  // Check for pre-search conditions
  if( tt_found && // node is in TT
      tt_iteration != IDDepth && // not updated this iteration
      // Check that entry has deeper search needs
      tt_depth + ( IDDepth - tt_iteration) >= depth ) {
    // Found a shallow node
    new_depth = tt_depth + ( IDDepth - tt_iteration );
    if( presearchFilter( newdepth, depth, tt_depth, tt_iteration, presearch ) ) {
      presearch = true;
      depth = new_depth;
    }
  }
  score = -INFINITY;
  num_moves = Generate( state, moves[] );
  for( i = 1; i <= num_moves; i++ ) {
    result = -AlphaBeta( state.moves[i], depth-1, -beta, -alpha, presearch );
    score = MAX( score, result );
    alpha = MAX( alpha, score );
    if( alpha >= beta )
      break;
  }
  // Normal TT update, but need to also save IDDepth
  TTUpdate( state, score, save_alpha, save_beta, depth, IDDepth );
  return( score );
}


bool presearchFilter( new_depth, depth, tt_depth, tt_iteration, presearch ) {
  // Do not allow a pre-search in a pre-search
  if( presearch ) return( false);

  // Ensure that we are searching deeper
  if( new_depth <= depth ) return( false );

  // Limit the amount of the search extension
  if( new_depth - depth > Risk ) return( false );

  // Prefer deep nodes close to the root
  if( tt_iteration - tt_depth > NearRoot ) return( false );

  // Prefer shallow nodes that are not close to the leaves
  if( depth < NearLeaf ) return( false );

  // Pre-search
  return( true );
}

Fotos

10th Computer Olympiad, Go 9x9, Taipei 2005, Shih-Chieh Huang and Markian Hlynka operating
Go Intellect and NeuroGo, Fredrik Niemelä watching

Selected Publications

• Jonathan Schaeffer, Markian Hlynka, Vili Jussila (2001). Temporal Difference Learning Applied to a High-Performance Game-Playing Program. CGW@IJCAI 2001
• Markian Hlynka, Jonathan Schaeffer (2004). Pre-Searching. ICGA Journal, Vol. 27, No. 4, pdf
• Markian Hlynka, Jonathan Schaeffer (2005). Automatic Generation of Search Engines. Advances in Computer Games 11

External Links

• Markian Hlynka Full Circle | Information Services and Technology UoA (Wayback Machine, July 2018)

References

Up one level