Implement Negascout Algorithm with stack
- by Dan
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.
