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.