Yeah, I sort of understood as much, I was basically wondering the inner workings of how the optimization produces a better result.
For example, the following is basically the code given on Wiki (I changed it so that it makes more c++ sense). And I put ifdefs around the place where the code is different. And I'm trying to figure out exactly what that means...besides "this is some hocus pocus that performs better than alphabeta but only in certain circomstances." As an example of the kind of description I'm hoping for, check this link for an AlphaBeta description:
http://www.seanet.com/~brucemo/topics/alphabeta.htm
And, in case you're wondering, I'm going to implement NegaScout, for my ConnectFour game, and I'm running on the assumption that it won't work correctly the first time. And if my implementation is just me copying code, I'll probably never figure out the real problem...
Code:
/* Compute minimax value of position p */
NegaScout ( GameState& gs, int depth, int alpha, int beta ) {
if (gs.EndState() || depth == 0) {
return gs.Evaluate();
}
list<moves_t> themoves;
gs.GenerateMoves(themoves);
for (list<moves_t>::iterator itr = themoves.begin();
itr != themoves.end(); itr++) {
MakeMove(gs);
int temp = -NegaScout ( gs, depth - 1, -beta, -alpha )
# if NEGASCOUT
if ( alpha > temp && temp > beta) && not_first_child(*itr))
alpha = -NegaScout ( gs, depth -1, -beta, -temp );
UnMakeMove(gs);
// these lines look very similar to alpha beta code ...
if (temp > alpha) alpha = temp; // this is done after the next line in AlphaBeta!
if (alpha >= beta)
return alpha; // alpha beta returns beta here!
beta = alpha + 1; // this is not done in alphabeta!
# elif ALPHABETA
UnMakeMove(gs);
if (temp >= beta) return beta;
if (temp > alpha) alpha = temp;
# endif
}
return alpha;