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

[Evan Daniel <evanbd@xxxxxxxxx>]

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;
    }

    if (score > beta) {
      store_transposition_table();
      score_type = BETA_CUTOFF;
      return score;
    }
    
    if (score > alpha) {
      assert child.score_type == EXACT_SCORE;
    }
  }

  store_transposition_table();
  return score;


(It's a bit more complicated, but I think that's the relevant bit.)

Now, the question is:  is the assert at the bottom of the loop a valid
assertion to make?  On very rare occasion, it triggers, but I haven't
been able to track down why or under what conditions exactly.  So does
that represent a bug buried in my code somewhere, or are there real
cases where it isn't true in properly coded alpha-beta searches?

Thanks in advance,

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