# Implement Negascout Algorithm with stack

I'm not familiar with how these stack exchange accounts work so if this is double posting I apologize. I asked the same thing on stackoverflow.

I have added an AI routine to a game I am working on using the Negascout algorithm.

It works great, but when I set a higher maximum depth it can take a few seconds to complete. The problem is it blocks the main thread, and the framework I am using does not have a way to deal with multi-threading properly across platforms.

So I am trying to change this routine from recursively calling itself, to just managing a stack (vector) so that I can progress through the routine at a controlled pace and not lock up the application while the AI is thinking.

I am getting hung up on the second recursive call in the loop. It relies on a returned value from the first call, so I don't know how to add these to a stack.

My Working c++ Recursive Code:

``````MoveScore abNegascout(vector<vector<char> > &board, int ply,
int alpha, int beta, char piece) {
if (ply==mMaxPly) {
return MoveScore(evaluation.evaluateBoard(board, piece, oppPiece));
}

int currentScore;
int bestScore = -INFINITY;
MoveCoord bestMove;

vector<MoveCoord> moveList =
evaluation.genPriorityMoves(board, piece,
findValidMove(board, piece, false));

if (moveList.empty()) {
return MoveScore(bestScore);
}

bestMove = moveList[0];

for(int i=0;i<moveList.size();i++) {
MoveCoord move = moveList[i];

vector<vector<char> > newBoard;
newBoard.insert( newBoard.end(), board.begin(), board.end() );
effectMove(newBoard, piece, move.getRow(), move.getCol());

// First Call ******
MoveScore current = abNegascout(newBoard, ply+1, -adaptiveBeta,
-max(alpha,bestScore), oppPiece);

currentScore = - current.getScore();

if (currentScore>bestScore){
if (adaptiveBeta == beta || ply>=(mMaxPly-2)){
bestScore = currentScore;
bestMove = move;
}else {
// Second Call ******
current = abNegascout(newBoard, ply+1, -beta,
-currentScore, oppPiece);
bestScore = - current.getScore();
bestMove = move;
}

if(bestScore>=beta){
return MoveScore(bestMove,bestScore);
}
adaptiveBeta = max(alpha, bestScore) + 1;
}
}
return MoveScore(bestMove,bestScore);
}
``````

If someone can please help by explaining how to get this to work with a simple stack. Example code would be much appreciated. While c++ would be perfect, any language that demonstrates how would be great.

Thank You.

-
How to ask questions the smart way: describe the goal, not the step. What you're really asking is "how can I run the negascout algorithm without chewing up all the available resources?" You can modify a recursive routine to make it progress at a controlled pace too, and keep it recursive, you know. – doppelgreener Sep 18 '12 at 23:15
@Jonathan, I am intrigued. Would you be able to explain how to keep it recursive and be able to control the pace? I am using the cocos2d-x framework so I don't really have full control over the main game loop without altering the framework, which I would like to avoid. – Dan Sep 19 '12 at 1:24
Byte56, I didn't know if the two sites were connected as when I searched for the post I made on stackoverflow here, it did not show up, so I assumed it was separate. I've voted for the other one to be deleted. – Dan Sep 19 '12 at 1:28

So I finally managed to convert my AI routine using this fantastic article which explains everything in detail. The only thing that wasn't covered and which I had trouble with was how to deal with the fact that my nested recursive statements were in a loop that was created on each recursive step. I got around that by breaking each stage of code into a separate method and re-assigning the stage number to 1, in this case, which would iterate to the next item in the list.

It works great. Through testing it appears to generate the identical results that I had before. What I've done is call the main method (abNegascoutwithStack) on each tick of the game loop to processes a part of the stack until the stack is empty or until n milleseconds have passed and then wait for the next game tick.

I have not noticed it running any slower and the benefit of being able to completely control the routine is great. A truly cross-platform solution that does not require multi-threading.

This was a lot of work for me so I hope that I can save someone else the time/energy/headaches by sharing my code here. It's not perfect but it works. I have only included the parts of code relevant to Negascout, not my entire game.

The 'stack' struct

``````struct SnapShotStruct {
vector<vector<char> > board;
int ply;
int alpha;
int beta;
char piece;

char oppPiece;
int currentScore;
int bestScore;
MoveCoord bestMove;
vector<MoveCoord> moveList;
int moveListIndex;
MoveCoord move;
vector<vector<char> > newBoard;
MoveScore current;
int stackID;
int stage;
};

int uniqueStackID;
float lastAiRun;
SnapShotStruct currentSnapshot;

stack<SnapShotStruct> snapshotStack;
MoveScore retVal;
``````

``````currentSnapshot.board = board;
currentSnapshot.ply = 0;
currentSnapshot.alpha = -INFINITY;
currentSnapshot.beta = INFINITY;
currentSnapshot.piece = piece;
currentSnapshot.stage=0;

snapshotStack.push(currentSnapshot);
uniqueStackID = 0;
``````

Then from your gameloop make calls as needed

abNegascoutwithStack:

``````void abNegascoutwithStack(){
currentSnapshot=snapshotStack.top();
snapshotStack.pop();

switch(currentSnapshot.stage) {
case 0:
if (abNegascout0()) {
return;
}
case 1:
if (abNegascout1()) {
return;
}
case 2:
if (abNegascout2()) {
return;
}
case 3:
if (abNegascout3()) {
return;
}
case 4:
if (abNegascout4()) {
return;
}
break;
}
}
``````

abNegascout0:

``````bool abNegascout0() {
currentSnapshot.stackID = uniqueStackID;
uniqueStackID++;

currentSnapshot.oppPiece = (currentSnapshot.piece == sBLACK_PIECE) ? sWHITE_PIECE : sBLACK_PIECE;

if (currentSnapshot.ply==mMaxPly){
retVal = MoveScore(evaluation.evaluateBoard(currentSnapshot.board, currentSnapshot.piece, currentSnapshot.oppPiece));
return true;
}

currentSnapshot.currentScore = 0;
currentSnapshot.bestScore = -INFINITY;

currentSnapshot.moveListIndex = -1;
currentSnapshot.moveList = evaluation.genPriorityMoves(currentSnapshot.board, currentSnapshot.piece, findValidMove(currentSnapshot.board, currentSnapshot.piece, false));

if (currentSnapshot.moveList.empty()) {
retVal = MoveScore(currentSnapshot.bestScore);
return true;
}

currentSnapshot.bestMove = currentSnapshot.moveList[0];
return false;
}
``````

abNegascout1:

``````bool abNegascout1() {
currentSnapshot.moveListIndex++;
if (currentSnapshot.moveListIndex < currentSnapshot.moveList.size()) {
currentSnapshot.move = currentSnapshot.moveList[currentSnapshot.moveListIndex];
currentSnapshot.newBoard.clear();
currentSnapshot.newBoard.insert( currentSnapshot.newBoard.end(), currentSnapshot.board.begin(), currentSnapshot.board.end() );

effectMove(currentSnapshot.newBoard, currentSnapshot.piece, currentSnapshot.move.getRow(), currentSnapshot.move.getCol());

currentSnapshot.stage = 2;
snapshotStack.push(currentSnapshot);

SnapShotStruct newSnapshot;
newSnapshot.board = currentSnapshot.newBoard;
newSnapshot.ply = currentSnapshot.ply+1;
newSnapshot.beta = - max(currentSnapshot.alpha,currentSnapshot.bestScore);
newSnapshot.piece = currentSnapshot.oppPiece;

newSnapshot.stage=0;
snapshotStack.push(newSnapshot);
return true;
}
retVal = MoveScore(currentSnapshot.bestMove,currentSnapshot.bestScore);
return true;
}
``````

abNegascout2:

``````bool abNegascout2() {
currentSnapshot.current = retVal;
currentSnapshot.currentScore = - currentSnapshot.current.getScore();

if (currentSnapshot.currentScore > currentSnapshot.bestScore){
if (currentSnapshot.adaptiveBeta == currentSnapshot.beta || currentSnapshot.ply>=(mMaxPly-2)){
currentSnapshot.bestScore = currentSnapshot.currentScore;
currentSnapshot.bestMove = currentSnapshot.move;
return false;
} else {
currentSnapshot.stage = 3;
snapshotStack.push(currentSnapshot);

SnapShotStruct newSnapshot;
newSnapshot.board = currentSnapshot.newBoard;
newSnapshot.ply = currentSnapshot.ply+1;
newSnapshot.alpha = -currentSnapshot.beta;
newSnapshot.beta = -currentSnapshot.currentScore;
newSnapshot.piece = currentSnapshot.oppPiece;

newSnapshot.stage=0;
snapshotStack.push(newSnapshot);
return true;
}
}

currentSnapshot.stage = 1;
snapshotStack.push(currentSnapshot);
return true;
}
``````

abNegascout3:

``````bool abNegascout3() {
if (currentSnapshot.stage != 3) {
return false;
}
currentSnapshot.current = retVal;
currentSnapshot.bestScore = - currentSnapshot.current.getScore();
currentSnapshot.bestMove = currentSnapshot.move;

return false;
}
``````

abNegascout4:

``````bool abNegascout4() {
if(currentSnapshot.bestScore>=currentSnapshot.beta){
retVal = MoveScore(currentSnapshot.bestMove,currentSnapshot.bestScore);
return true;
}
currentSnapshot.adaptiveBeta = max(currentSnapshot.alpha, currentSnapshot.bestScore) + 1;

currentSnapshot.stage = 1;
snapshotStack.push(currentSnapshot);
return true;
}
``````
-
If you found the solution to your own question, then mark this as the answer as soon as you can. If its not the answer then edit your question with the new info and remove this answer or you won't get anyone to look at it. Its a Q&A format, not a forum board format. – Daniel Carlsson Sep 23 '12 at 21:39