Tree Implementation in MinMax with Alpha-Beta Pruning

Question

I want to implement an AI (Artificial Intelligence) for a checkers-like game

I have written the follow methods:

-the method

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

that returns me the list of all valid moves sorted by weight, where the weight is calculated according the kind of moves and the position

-the method

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

to apply the moves to board and returns 1 if some pawn has been killed

-the method

public void undo(){
     ...
}

to restore the previous status of the board.

This is a zero-sum games so the AI shoud maximize pawns of the player color and minimize the pawns of the opponent.

For this the best way seems using min-max with alpha-beta pruning. This has the follow Pseudo-Code

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)

But I haven't understood how to adapt this to my problem.' Someone could help me?

EDIT

I have this MinMax but is without pruning

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());
}

How to edit to obtain alpha beta pruning?

Answer 1

This is some pseudo code for an alpha beta chess program I wrote in the past. Well, checkers or chess - there is no big difference in this part:

  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;

Only GenerateMoves, EvaluatePosition and MoveForward/Back are specific. You can find the complete code here. It's not super optimized because tried to make it as readable as possible

added: so remove current, as it is not really required. Add two parameters for the search window and add the pruning:

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;

Finally you need to call the algorithm with a maximized window:

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

... meaning its the max. players turn who starts with the worst values possible (Integer.MinInt)