Как я могу go о реализации таблицы транспонирования в минимаксном алгоритме? - PullRequest
Новая
       3

Как я могу go о реализации таблицы транспонирования в минимаксном алгоритме?

1 голос
/ 18 января 2020

Я сейчас нахожусь в процессе создания простого шахматного движка, проблема в том, что даже с простой функцией оценки и с учетом глубины 2 двигателю требуется около 15 секунд, чтобы сделать ход. Я хочу улучшить производительность движка с помощью таблицы транспонирования, поэтому я попытался реализовать таблицу транспонирования самостоятельно, но прирост производительности не наблюдался. Что может быть не так с моей реализацией, и как я могу это исправить?

Вот код: 

function alphaBeta(node, depth, alpha, beta, maximisingPlayer){
  if(depth === 0 || isTerminalNode(node)){
    if(isTerminalNode(node)){
      if(isCheckmate(blackPieces, node)){
        return 900;
      } else {
        return -900;
      }
    } else {
      let zorbistKeyValue = evaluateBoardZorbistKeyCode(node);
      let storedMoveItem = storedMoves[zorbistKeyValue];
      if(storedMoveItem != undefined){
        return storedMoveItem;
      } else {
        let evaluation = evaluateBoard(node);
        storedMoves[zorbistKeyValue] = evaluation;
        return evaluation;
      }
    }
  }
  maximisingPlayer ? player = whitePieces : player = blackPieces;
  availableSpots = availableValidSpots(node, player);
  if(maximisingPlayer){
    value = -Infinity;
    for(availableSpot = 0; availableSpot < availableSpots.length; availableSpot++){
      child = availableSpots[availableSpot].node;
      value = Math.max(value, alphaBeta(child, depth - 1, alpha, beta, false));
      alpha = Math.max(alpha, value);
      if(alpha >= beta){
        break;      
      }
    }
    return value;
  } else {
    value = Infinity;
    for(availableSpot = 0; availableSpot < availableSpots.length; availableSpot++){
      child = availableSpots[availableSpot].node;
      value = Math.min(value, alphaBeta(child, depth - 1, alpha, beta, true));
      beta = Math.min(beta, value);
      if(alpha >= beta){
        break;
      }     
    }
    return value;
  }
}

function findBestMove(board, player){
  player == blackPieces ? isMaximisingPlayer = false : isMaximisingPlayer = true;
  let availSpots = availableValidSpots(board, player);
  if(isMaximisingPlayer){
    let bestScore = -Infinity;
    for(availSpot = 0; availSpot < availSpots.length; availSpot++){
      let value = alphaBeta(availSpots[availSpot].node, 2, -Infinity, Infinity, true);
      if(value > bestScore){
        bestScore = value;
        bestMove = availSpots[availSpot];
      }
    }
  } else {
    let bestScore = Infinity;
    for(availSpot = 0; availSpot < availSpots.length; availSpot++){
      let value = alphaBeta(availSpots[availSpot].node, 2, -Infinity, Infinity, false);
      if(value < bestScore){
        bestScore = value;
        bestMove = availSpots[availSpot];
      }
    }
  }
  return bestMove;
}
...