Как улучшить производительность Minimax для Chess.js? - PullRequest
Новая
       31

Как улучшить производительность Minimax для Chess.js?

0 голосов
/ 27 мая 2018


Я пытаюсь написать шахматный движок, используя Chess.js и Chessboard.js, используя алгоритм Minimax с отсечкой альфа-бета.Проблема заключается в том, что алгоритму требуется очень много времени для выполнения всех оценок и принятия решения о перемещении, даже с depth=3.Как я могу ускорить производительность?

Ниже приводится моя минимаксная реализация: 

var minimax = function (depth, game, alpha, beta, isAIplaying) {

  // end branch: simply evaluate and return the current score of the board
  if (depth === 0) {
    return evaluateBoard(game);
  }

  // list of all the possible moves in current status
  var newGameMoves = game.moves();
  if (isAIplaying) {
      var bestMove = -9999;
      for (var i = 0; i < newGameMoves.length; i++) {
          game.move(newGameMoves[i]);
          bestMove = Math.max(bestMove, minimax(depth - 1, game, !isAIplaying));
          game.undo();
          alpha = Math.max(alpha, bestMove);
          if (beta <= alpha) {
            return bestMove;
          }
      }
      return bestMove;
  } else {
      var bestMove = 9999;
      for (var i = 0; i < newGameMoves.length; i++) {
          game.move(newGameMoves[i]);
          bestMove = Math.min(bestMove, minimax(depth - 1, game, !isAIplaying));
          game.undo();
          beta = Math.min(beta, bestMove);
          if (beta <= alpha) {
           return bestMove;
          }
      }
      return bestMove;
  }
};

Функция вызывается в следующем коде, где черные должны решить, какой ход следует предпринять.: 

var possibleMoves = game.moves(); 

// game over
if (possibleMoves.length === 0) 
  return;

var best_score = -9999;
var bestMoveFound;

for(var i=0; i<possibleMoves.length; ++i){
  game.move(possibleMoves[i]); // make one possible move

   // minimax: take the current status of the game
  // it is not Black's turn
  var score = minimax(3, game, -10000, 10000, false);

  // if I get a better score then I store it
  if(score >= best_score){
    best_score = score;
    bestMoveFound = i;
  }

  // undo move
  game.undo();
}

// make the best move (update both the game and the board on the screen)
game.move(possibleMoves[bestMoveFound]);
board.position(game.fen());

Где следующая функция оценки: 

var evaluateBoard = function(current_game) {
    var status = current_game.fen();

    var score = 0;

    // calculate score for the current situation
    var fen_idx = 0;
    var piece = status[fen_idx];
    while(piece != ' '){
      switch(piece){
        case 'p': score += pawn; break;
        case 'n': score += knight; break;
        case 'b': score += bishop; break;
        case 'r': score += tower; break;
        case 'q': score += queen; break;
        case 'k': score += king; break;
        case 'P': score -= pawn; break;
        case 'N': score -= knight; break;
        case 'B': score -= bishop; break;
        case 'R': score -= tower; break;
        case 'Q': score -= queen; break;
        case 'K': score -= king; break;
        default: break;
      }

      ++fen_idx;
      piece = status[fen_idx];
    }

    return score;
};

pawn, bishop, остальные - простые константы, а p обозначает черную пешку, тогда как P обозначает белый.Есть ли у вас идеи по увеличению производительности?

1 Ответ

0 голосов
/ 09 июля 2018

Идея оценки FEN-String выглядит быстро, но ваша программа должна рассчитывать FEN-String для каждого выхода из дерева игры.Это действительно медленно, потому что он должен сканировать доску о каждой фигуре, а также о каждом пустом квадрате доски в цикле по 64 клеткам.Вы не должны этого делать, но держите цифры на доске в списке для расчета аналога вашего исходного кода.

Было бы даже лучше иметь сумму всех миров и только добавлять или вычитать значение,если кусок взят или заменить на доске.Таким образом, у вас нет вычисления в вашей функции оценки, и ваш движок будет намного быстрее.По моему опыту, вы должны достичь глубины 7 за <2 секунды, если ваша функция оценки - это только сравнение значений кусков двух сторон. </p>

...