Tic Tac Toe alpha-beta MiniMaxfor 4x4 board (JavaScript)

Question

I have implement JavaScript applying alpha-beta minimax. It works well with 3x3 board, but when I change the board to 4x4 or higher, the program seems to hang.

UPDATE: The program is not efficient when available moves are more than 10

Here is the alpha-beta minimax function:

function AlphaBetaMinMax(game_board, depth, alpha, beta) {
    if (CheckForWinner(game_board) === 1 || CheckForWinner(game_board) === 2 ||
        CheckForWinner(game_board) === 3)
        return GameScore(game_board, depth);

    depth += 1;

    var availableMoves = GetAvailableMoves(game_board);

    var move, result, possible_game;
    if (active_turn === "COM") {

        for (var i = 0; i < availableMoves.length; i++) {
            move = availableMoves[i];
            possible_game = GetNewState(move, game_board);
            result = AlphaBetaMinMax(possible_game, depth, alpha, beta);
            game_board = UndoMove(game_board, move);
            if (result > alpha) {
                alpha = result;
                if (depth == 1)
                    choice = move;
            } else if (alpha >= beta) {
                return alpha;
            }
        }
        return alpha;
    } else {
        for (var i = 0; i < availableMoves.length; i++) {
            move = availableMoves[i];
            possible_game = GetNewState(move, game_board);
            result = AlphaBetaMinMax(possible_game, depth, alpha, beta);
            game_board = UndoMove(game_board, move);
            if (result < beta) {
                beta = result;
                if (depth == 1)
                    choice = move;
            } else if (beta <= alpha) {
                return beta;
            }
        }
        return beta;
    }
}

function GameScore(game_board, depth) {
    var score = CheckForWinner(game_board);
    var t = (board_size + 1);
    if (score === 1)
        return 0;
    else if (score === 2)
        return depth - t;
    else if (score === 3)
        return t - depth;
}

function UndoMove(game_board, move) {
    game_board[move] = UNOCCUPIED;
    ChangeTurn();
    return game_board;
}

function GetNewState(move, game_board) {
    var piece = ChangeTurn();
    game_board[move] = piece;
    return game_board;
}

function ChangeTurn() {
    var piece;
    if (active_turn === "COM") {
        piece = 'X';
        active_turn = "PLAYER";
    } else {
        piece = 'O';
        active_turn = "COM";
    }
    return piece;
}

function GetAvailableMoves(game_board) {
    var AvailableMoves = new Array();
    for (var i = 0; i < board_size; i++) {
        if (game_board[i] === UNOCCUPIED) {
            AvailableMoves.push(i);
        }
    }
    return AvailableMoves;
}

CheckForWinner() returns:

• 0 for not a tie or not a win
• 1 for a tie
• 2 for Player win
• 3 for Computer win

Thanks for your help

Answer 1

I have successful built a game named Othello (It's almost like GO games) and it same what you are doing but my main language is Java (and you are using JavaScript). So, I will show my pseudocode for you (because I don't know JavaScript). I hope it can help you in this case:

function minimax(turn, max_depth ,depth, alpha, beta):
    if isFinishState() or depth==max_depth :
       return value of the node

    if turn == "computer" :
        best = -INFINITY 
        turn = "Human"
        for each move in available moves :
           possible_game = GetNewState(move, game_board); 
           value = minimax(turn, depth+1,max_depth, alpha, beta)
           //insert some code to undo if you have changed the game board
           best = max( best, value) 
           alpha = max( alpha, best)
           if beta <= alpha:
              break
         return best
    else : //human turn
        best = +INFINITY 
        turn = "Computer"
        for each move in available_moves:
           possible_game = GetNewState(move, game_board);
           value = minimax(turn, depth+1, max_depth, alpha, beta)
           //insert some code to undo if you have changed the game board
           best = min( best, value) 
           beta = min( beta, best)
           if beta <= alpha:
              break
        return best

Then, you need a function like findBestMove() to return the best next position for computer:

  int findBestMove(int max_depth) :
    alpha = -9999999; //-INFINITY 
    beta  = 9999999; //+INFINITY 
    choice = null;
    best =-9999999;//-INFINITY 
   for each move in available_moves:

                possible_game = GetNewState(move, game_board);
                moveVal = minimax("computer", 0, max_depth, alpha, beta);
                if (best < moveVal):
                    best = moveVal;
                    choice = move;

                //insert code here to undo game_board
    return choice;