|
04-17-2006, 01:46 PM
| #1 |
| Registered User Join Date: Aug 2002 Location: Hermosa Beach, CA
Posts: 446
| NegaScout
__________________ The crows maintain that a single crow could destroy the heavens. Doubtless this is so. But it proves nothing against the heavens, for the heavens signify simply: the impossibility of crows. |
| IfYouSaySo is offline |  |
|
04-17-2006, 02:55 PM
| #2 |
| Crazy Fool  Join Date: Jan 2003 Location: Canada
Posts: 2,588
| It looks similar to alpha-beta because they are both MiniMax algorithms. NegaScout claims superiority because it explores less nodes in the case where strong moves are searched first. As wikipedia notes though, NegaScout is actually worse than alpha-beta if the search order is randomized. They are both optimizations of the MiniMax algorithm. Disclaimer: ive never even heard of NegaScout before, my explanation is simply an interpretation of wikipedia's article.
__________________ jeff.bagu.org - Terrain rendering and other random stuff |
| Perspective is offline | |
|
04-17-2006, 04:02 PM
| #3 |
| Registered User Join Date: Aug 2002 Location: Hermosa Beach, CA
Posts: 446
| 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;
__________________ The crows maintain that a single crow could destroy the heavens. Doubtless this is so. But it proves nothing against the heavens, for the heavens signify simply: the impossibility of crows. |
| IfYouSaySo is offline | |
|
04-17-2006, 07:16 PM
| #4 |
| Registered User Join Date: Aug 2002 Location: Hermosa Beach, CA
Posts: 446
| I found my answer...it turns out that NegaScout is also known as Principal Variation Search: http://www.seanet.com/~brucemo/topics/pvs.htm
__________________ The crows maintain that a single crow could destroy the heavens. Doubtless this is so. But it proves nothing against the heavens, for the heavens signify simply: the impossibility of crows. |
| IfYouSaySo is offline | |
 |
| Thread Tools | |
| Display Modes | |
|
Linear Mode
