Java - Alpha beta обрезка для минимаксной реализации

Question

Я пытаюсь создать AI-плеер для игры, используя минимаксный алгоритм с альфа-бета-обрезкой. У меня возникли проблемы с его правильной реализацией. У меня есть 2 функции для работы, один для оценки текущего состояния моей платы для данного игрока (который возвращает некоторый балл) getBoardScore, а другой - для возврата всех возможных состояний платы, созданных каждым возможным движением (из заданного состояния платы для данный игрок) getPossibleBoards.

Мой ИИ совершает переход, первоначально вызывая альфа-Бета, передавая ему текущее состояние платы. Затем он устанавливает новое состояние платы из переменной «bestBoard», которая была рекурсивно изменена функцией alphaBeta. Вот мой код для моей функции Alphabeta:

static int MAX = -1; 
static int MIN = 1; 
Board node; 
Board bestBoard; 

public int alphaBeta(Board node, int depth, int alpha, int beta, int player) { 

    if (depth == 0 || node.gameFinished()) { 
     return node.getBoardScore(player); 
    } 

    ArrayList<Board> childNodes = node.getPossibleBoards(player); //All valid moves from current the board state 
    if (player == MAX) { 
     for (Board currentBoard: childNodes) { 
      int result = alphaBeta(currentBoard, depth-1, alpha, beta, -player);  
      if (alpha < result) { 
       alpha = result; 
        bestBoard = currentBoard; 
      } 
      if (beta <= alpha) { 
       break; //alpha cut-off        
      } 
     }      
    return alpha; 
    } 
    else { 
     for (Board currentBoard: childNodes) { 
      int result = alphaBeta(currentBoard, depth-1, alpha, beta, -player); 
      if (beta > result) { 
       beta = result; 
        bestBoard = currentBoard; 
      } 
      if (beta <= alpha) { 
        break; //alpha cut-off 
      }        
     } 
     return beta; 
    } 
} 

Моя проблема заключается в том, что это просто установив свою переменную bestBoard к последней доске состояние смотрел на (а не оптимальной). Кажется, я не могу понять, где я должен устанавливать свою самую лучшую переменную (или если у меня должно быть какое-то условие, прежде чем я ее установлю). Может ли кто-нибудь указать мне в правильном направлении? Спасибо

Answer 1

Я думаю, проблема в том, что вам нужно сохранить bestBoard, только если вы находитесь в первом слое поиска.