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

Question

我已经实现 JavaScript 应用 alpha-beta minimax。它适用于 3x3 板，但是当我将板更改为 4x4 或更高时，程序似乎挂起。

更新： 当可用移动超过 10 个时，程序效率不高

这是 alpha-beta minimax 函数：

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 表示不平局或不赢
1 平手
2 表示玩家获胜
3 计算机获胜

感谢您的帮助

Answer 1

我已经成功构建了一个名为 Othello 的游戏（它几乎就像 GO 游戏）并且它与您正在做的相同，但我的主要语言是 Java（并且您正在使用 JavaScript）。所以，我会为你展示我的pseudocode（因为我不知道Java脚本）。希望对您有所帮助：

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

然后，你需要一个像 findBestMove() 这样的函数来 return 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;

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

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

javascript

minimax

alpha-beta-pruning