Доска Tic Tac Toe альфа-бета MiniMaxfor 4x4 (JavaScript) - PullRequest
Новая
       73

Доска Tic Tac Toe альфа-бета MiniMaxfor 4x4 (JavaScript)

0 голосов
/ 07 июня 2018

Я реализовал JavaScript с применением минимакс альфа-бета.Он хорошо работает с доской 3х3, но когда я меняю доску на 4х4 или выше, программа, кажется, зависает.

ОБНОВЛЕНИЕ: Программа неэффективна, когда количество доступных ходов превышает 10

Вот минимаксная функция альфа-бета: 

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 за победу компьютера

Спасибо за помощь

1 Ответ

0 голосов
/ 08 июня 2018

Я успешно построил игру под названием Othello (это почти как игры GO), и это то же самое, что вы делаете, но мой основной язык - Java (и вы используете JavaScript).Итак, я покажу свой pseudocode для вас (потому что я не знаю 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

Затем вам нужна функция типа findBestMove(), чтобы вернуть лучшую следующую позицию для 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;
...