[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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

A few of comments below:

From: Evan Daniel <evanbd@xxxxxxxxxxxxxxxxx>

Reply-To: evand@xxxxxxxxxxxxxxxxx, computer-go <computer-go@xxxxxxxxxxxxxxxxx>
To: computer-go <computer-go@xxxxxxxxxxxxxxxxx>
Subject: [computer-go] alpha-beta + graph history question
Date: Thu, 17 Mar 2005 01:32:32 -0500

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);
It's not overly important, but this is kind of an unusual way of expressing the alpha beta algorithm.
More normal is something like this:

moveScore = -alphabeta(-beta, -alpha, depth -1)

so depth starts at D (depth of current iteration) counts down to zero, and the score is always relative to the side to move (positive means better for side to move). Obviously your depth is counting up to D, but how about your scores?

    if (child.score > score) {
      score = child.score;
      score_type = EXACT_SCORE;
in here don't you want to set alpha = child.score? Otherwise you aren't narrowing the AB window.

    }

    if (score > beta) {

this should be >=


      store_transposition_table();
      score_type = BETA_CUTOFF;
      return score;
    }

    if (score > alpha) {
      assert child.score_type == EXACT_SCORE;
    }
this assert seems OK to me, but then it is easy to make a mistake with this stuff :-)

cheers,
Peter

  }

  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/

_________________________________________________________________
Check out news, entertainment and more @  http://xtra.co.nz/broadband

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