c++algorithmartificial-intelligencealpha-beta-pruningcoderef

C++ 4 In a row AlphaBeta algorithm is not very smart


I'm making an AI controlled alpha-beta algorithm for a school project, but my algorithm is very inconsistent. Sometimes it blocks all my moves successfully, and sometimes it just ignores my 3 in a row as seen here. How could this happen and how can I resolve the issue?

int alphaBeta(const State board, int alpha, int beta, const Player player, int depth)
{
    //Max player = Player::O
    //Min player = Player::X

    std::vector<Move> possibleMoves = getMoves(board);

    if(eval(board)==Player::X){return 9999-depth;}      //Player X wins
    else if(eval(board)==Player::O){return -9999+depth;}    //Player O wins
    else if(possibleMoves.size()==0){return 0;}     //Tie
    else{   //Zoek verder
        depth++;
        State nextBoard = board;
        int result;

        if(player==Player::O){
            for (Move move: possibleMoves) {
                nextBoard = doMove(nextBoard, move);
                result = alphaBeta(nextBoard, alpha, beta, Player::X, depth);
                if (result > alpha){    
                    alpha = result; 
                    if (depth == 1){
                                    choice = move; //The actual move he will do
                    }
                }
                else if (alpha >= beta){ 
                    return alpha; 
                }
            }
            return alpha;
        }

        else{
            for (Move move: possibleMoves) {
                nextBoard = doMove(nextBoard, move);
                result = alphaBeta(nextBoard, alpha, beta, Player::O, depth);
                if (result < beta){ 
                    beta = result;
                    if (depth == 1){
                                    choice = move;
                    }
                }
                else if (beta <= alpha){ 
                    return beta;
                }
            }
            return beta;
        }
    }
}

Solution

  • You're repeatedly modifying nextBoard, adding (possibly illegal) moves to it:

    nextBoard = doMove(nextBoard, move);
    

    but you should try each move in turn on the original board:

    State nextBoard = doMove(board, move);
    

    (Disclaimer: there may be other issues, as well.)