Дерево Реализация в MinMax с альфа-бета отсечение

Question

Я хочу реализовать AI (искусственный интеллект) для шашек-как игра

я написал методы последующей:

-The метод

public List<Move> allMoves(){ 
     ... 
    } 

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

-The метода

public int apply(Move m){ 
     ... 
} 

применять ходы на доске и возвращает 1, если какая-то пешка был убит

-The метод

public void undo(){ 
    ... 
} 

восстановить прежний статус совета.

Это игры с нулевой суммой, поэтому AI shoud максимизирует пешки цвета игрока и сводит к минимуму пешки противника.

Для этого лучше всего использовать min-max с обрезкой альфа-бета. Это имеет последующего псевдокод

function alphabeta(node, depth, α, β, maximizingPlayer) 

      if depth = 0 or node is a terminal node 
       return the heuristic value of node 
      if maximizingPlayer 
       v := -∞ 
       for each child of node 
        v := max(v, alphabeta(child, depth - 1, α, β, FALSE)) 
        α := max(α, v) 
        if β ≤ α 
         break (* β cut-off *) 
       return v 
      else 
       v := ∞ 
       for each child of node 
        v := min(v, alphabeta(child, depth - 1, α, β, TRUE)) 
        β := min(β, v) 
        if β ≤ α 
         break (* α cut-off *) 
       return v 

    (* Initial call *) 
    alphabeta(origin, depth, -∞, +∞, TRUE) 

Но я не понял, как адаптировать это к моей проблеме. Кто-нибудь может мне помочь?

EDIT

У меня есть этот MinMax, но без обрезки

private Integer minimax(Board board, Integer depth, Color current, Boolean maximizingPlayer) { 
    Integer bestValue; 
    if (0 == depth) 
     return ((current == selfColor) ? 1 : -1) * this.evaluateBoard(board, current); 

    Integer val; 
    if (maximizingPlayer) { 
     bestValue = -INF; 
     for (Move m : board.getPossibleMoves(current)) { 
      board.apply(m); 
      val = minimax(board, depth - 1, current, Boolean.FALSE); 
      bestValue = Math.max(bestValue, val); 
      board.revert(m); 
     } 
     return bestValue; 
    } else { 
     bestValue = INF; 
     for (Move m : board.getPossibleMoves(current)) { 
      board.apply(m); 
      val = minimax(board, depth - 1, current, Boolean.TRUE); 
      bestValue = Math.min(bestValue, val); 
      board.revert(m); 
     } 
     return bestValue; 
    } 
} 

the evaluate function 

private Integer evaluateBoard(Board board, Color player) { 
    return board.pawns(player) - board.pawns(player.other()); 
} 

Как изменить, чтобы получить альфа-бета отсечение?

Answer 1

Это какой-то псевдокод для программы по альфа-бета-версии, которую я написал в прошлом. Ну, шашки или шахматы - нет большой разницы в этой части:

Const White  =  1; 
     Black  =  -1; 

     MaxInteger = 32767; 
     MinInteger = -32768; 

    Function AlphaBeta (Color, Alpha, Beta, 
          Depth, MaxDepth : Integer) : Integer; 
    var Value : Integer; 

    begin 
    if Depth = MaxDepth then 
     AlphaBeta := EvaluatePosition (Color) 

    end else 
    begin 
     GenerateMoves(Color, MoveList); 

     For Each Move in MoveList do 
     begin 
      MoveForward (Move); 

       Value := AlphaBeta (-Color, Beta, Alpha, 
              Depth +1, MaxDepth); 

       if Color = White then 
        if Value > Alpha then Alpha := Value; 

       if Color = Black then 
        if Value < Alpha then Alpha := Value; 

      MoveBack (Move); 

       if Color = White then 
        if Alpha >= Beta then Return Alpha; 

       if Color = Black then 
        if Alpha <= Beta then Return Alpha; 
     end; 

     AlphaBeta := Alpha; 
    end; 
    end; 

Только GenerateMoves, EvaluatePosition и MoveForward/Back специфичны. Вы можете найти полный код here. Это не супер оптимизирован, потому что пытался сделать его читаемым как можно

добавил: так удалить current, как это на самом деле не требуется. Добавить два параметра для окна поиска и добавить обрезку:

private Integer minimax(Board board, Integer depth, Boolean maximizingPlayer, 
         Integer maxPlayerBestVal, Integer minPlayerBestVal) { 
    Integer bestValue; 
    if (0 == depth) 
     return this.evaluateBoard(board); 

    Integer val; 
    if (maximizingPlayer) { 
     bestValue = -INF; 
     // current never changed in your case; so you better use the bool 
     for (Move m : board.getPossibleMoves(maximizingPlayer))) { 
      board.apply(m); 
      val = minimax(board, depth - 1, Boolean.FALSE, 
          minPlayerBestVal, maxPlayerBestVal); // swap here 
      bestValue = Math.max(bestValue, val); 
      board.revert(m); 
      if (bestValue >= minPlayerBestVal) // too good for the minPlayer 
       return bestValue;    // so cut here (pruning) 
     } 
     return bestValue; 

Наконец, вы должны вызвать алгоритм с развернутым окном:

minimax(board, 3, true, Integer.MinInt, Integer.MaxInt); 

... то есть его макс.игроки начинают с наихудшими возможными значениями (Integer.MinInt)