Implement Negascout Algorithm with stack

Question

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;
int adaptiveBeta = beta;

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.

Answer 1

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;
   int adaptiveBeta;
   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;

Assign Initial Values to the first item in the stack:

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.adaptiveBeta = currentSnapshot.beta;

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.alpha = -currentSnapshot.adaptiveBeta;
    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;
}