井字游戏脚趾α-βMiniMaxfor 4x4板（JavaScript）

Question

我已经使用alpha-beta-minimax实现了JavaScript。它适用于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（）返回：

• 0代表不平不赢
• 1换领带
• 2代表玩家获胜
• 3代表电脑获胜

谢谢你的帮助

Answer 1

我已经成功地构建了一个名为Otherlo的游戏（它几乎像GO游戏），它和您正在做的一样，但我的主要语言是Java（您正在使用JavaScript）。因此，我将为您展示我的伪代码（因为我不懂JavaScript）。我希望它能在这种情况下帮助您：

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

然后，您需要像findBestMobile（）这样的函数来返回计算机的最佳下一个位置：

  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;