C++

Forum

 
Implement Negascout with stack

notamonopoly (2)
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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
 
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.
notamonopoly (2)
Topic archived. No new replies allowed.