Re: [computer-go] alpha-beta + graph history question

[Richard Delorme <abulmo@xxxxxxxxxxxxxxxx>]

Evan Daniel a écrit :

> In my go program (GoFigure), I use a global alpha-beta search with
> transpostion table.  The transposition table is rotationally
> invariant, and maintained across invocations of the program, which
> results in walking of the game tree in ways that seem good at
> demonstrating subtle problems with my code and my understanding of
> alpha-beta search.
>
> My alpha-beta function (simplified) looks something like this:
>
> alphabeta(int alpha, int beta, int depth) {
>  check_transposition_table();
>  get_moves();
>  score_type = ALPHA_CUTOFF;
>  for (int i = 0; i < children.length; i++) {
>    children[i].alphabeta(beta, alpha, depth + 1);
>    if (child.score > score) {
>      score = child.score;
>      score_type = EXACT_SCORE;
>    }
The above is correct only if 'score' initial value is 'alpha' (or 
greater); otherwise, it is possible to have a 'score' value lower than 
'alpha', ie an alpha cutoff and not an exact score. Maybe a better code is :
  if (child.score > score) {
    score = child.score;
    if (score > alpha) {
      alpha = score;
      score_type = EXACT_SCORE;
    }
  }

>    if (score > beta) {
>      store_transposition_table();
>      score_type = BETA_CUTOFF;
>      return score;
>    }
As said by others, the beta cutoff is obtained if (score >= beta). If 
some performance efficiency is needed, it may be interesting to nest 
this comparison inside the above one.

>    
>    if (score > alpha) {
>      assert child.score_type == EXACT_SCORE;
>    }
I think the assertion may fail depending on the 'score' initial value.

By the way, I don't think that storing a score and a score_type flag is 
very efficient. I prefer two score bounds instead. Inside the 
transposition storage function, I am using something like :
if (score > score_lower_bound && score > alpha) score_lower_bound = score;
if (score < score_upper_bound && score < beta) score_upper_bound = score;
This method is not more complicated than the score_type flag one, but 
contains more information and allows extra cutoff to be produced when a 
transposed position is found.

--
Richard
_______________________________________________
computer-go mailing list
computer-go@xxxxxxxxxxxxxxxxx
http://www.computer-go.org/mailman/listinfo/computer-go/