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

[Don Dailey <drd@xxxxxxx>]

Evan,

If this actually represents your code, you are losing a lot of cutoffs
due to the " if (score > beta)" test.  That should be "if (score >=
beta)"

Basically, you can take a cutoff here because this line is "futile",
improving or even EQUALING beta is enough to cause the opponent to shy
away from the parent node.  In the equal case the opponent can achieve
beta in another line, so there is no point is seeing if he can achieve
it in this line.

Normally, you would also update alpha locally if the child.score is
above alpha and pass this new information towards the leaf nodes.

The score returned from a search can be below alpha, above alpha or in
between.  So I'm not sure that assertion makes sense.

If the score returned is between alpha and beta, it is an exact score.
If it is EQUAL or less than alpha it is not exact and if it is greater
than or equal to beta, it is a lower bound (the true score is at least
the returned score but could be higher.)

In my program I label my nodes upperbound and lowerbound, it is easier
to think of that way for me.  I still use alpha and beta in the search
function call however.

If the child.score is greater than the best score found so far you
update it.  This is correct but you do not need to do the following tests
in the case where it isn't,  you should just proceed to the next move.
That might even trigger the assertion.    I'm in a big hurry so I
can't study the code further,  but I'm a bit unsure if the assertion
is correct or not,   I believe off-hand that it is wrong but I could
be wrong.

- Don



   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/

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