[computer-go] AlphaBeta

[Don Dailey]

On Sun, 2006-09-24 at 15:20 -0700, Phil G wrote:
> I have a question that I could use some help on. In an typical
> AlphaBeta search (sample code below), how do you actually return the
> best move found by the search? I see how the best move's evaulation is
> returned, but not the move itself. 

Hi Phil,

The code doesn't show that.  One way is to pass it as a pointer to the
function like so:

   int AlphaBeta( int depth, int alpha, int beta, mv_t *mv );

If you do this,  you might as well consider *mv as an array and get a
principal variation recursively, then you might want to rename the
variable to *pv.

Here is a modification that will return a principal variation.  When you
call the search it will return an array of moves,   the best move is
pv[0] and the best line of play continues  pv[1], pv[2], etc.

I didn't check the code for errors,  use at your own risk!  It's not
quite real code anyway.   Be sure that pv is large enough when you first
call it to do a search.  

int AlphaBeta(int depth, int alpha, int beta, mv_t *pv)
{
  mv_t   vpv[MAX_PV_LEN];            // "variation pv" from sub-search
  int    best_score -INF;

  pv[0] = PV_END;   // a value that indicates the end of a PV.

  if (depth == 0)
    return Evaluate();
 
  GenerateLegalMoves();
 
  while (MovesLeft()) {
 
    cmv = current_move;

    MakeNextMove();
    
    val = -AlphaBeta(depth - 1, -beta, -alpha, vpv);
    
    UnmakeMove();

    if (val > best) {
      best_score  = val;
      pv[0] = cmv;
      memcpy( pv+1, vpv, sizeof(mv_t) * (MAX_PV_LEN - 1) );
      pv[ MAX_PV_LEN - 1 ] = PV_END;   // don't allow overflow
    }
    
    if (val >= beta)
      return beta;
    
    if (val > alpha)
      alpha = val;
  }
  
  return alpha;
}
 





 
> int AlphaBeta(int depth, int alpha, int beta)
> {
> 
>     if (depth == 0)
> 
>         return Evaluate();
> 
>     GenerateLegalMoves();
> 
>     while (MovesLeft()) {
> 
>         MakeNextMove();
> 
>         val = -AlphaBeta(depth - 1, -beta, -alpha);
> 
>         UnmakeMove();
> 
>         if (val >= beta)
> 
>             return beta;
> 
>         if (val > alpha)
> 
>             alpha = val;
> 
>     }
> 
>     return alpha;
> 
> }
> 
>  
> 
> Thanks in advance,
> 
>  
> 
> Phil
> 
>  
> 
> 
> _______________________________________________
> computer-go mailing list
> computer-go at computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/