关于java：如何实现高效的Alpha-Beta剪枝游戏搜索树？

    public Best chooseMove(boolean side, int prevScore, int alpha, int beta){
    Best myBest = new Best();
    Best reply;

    if (prevScore == COMPUTER_WIN || prevScore == HUMAN_WIN || prevScore == DRAW){
        myBest.score = prevScore;
        return myBest;
    }

    if (side == COMPUTER){
        myBest.score = alpha;
    }else{
        myBest.score = beta;
    }
    Log.d(TAG,"Alpha:" + alpha +" Beta:" + beta +" prevScore:" + prevScore);
    Move[] moveList = myBest.move.getAllLegalMoves(board);
    for (Move m : moveList){
        String choice;
        if (side == HUMAN){
            choice = playerChoice;
        }else if (side == COMPUTER && playerChoice.equals("X")){
            choice ="O";
        }else{
            choice ="X";
        }
        Log.d(TAG,"Current Move: column-" + m.getColumn() +" row-" + m.getRow());
        int p = makeMove(m, choice, side);
        reply = chooseMove(!side, p, alpha, beta);
        undoMove(m);
        if ((side == COMPUTER) && (reply.score > myBest.score)){
            myBest.move = m;
            myBest.score = reply.score;
            alpha = reply.score;
        }else if((side == HUMAN) && (reply.score < myBest.score)){
            myBest.move = m;
            myBest.score = reply.score;
            beta = reply.score;
        }//end of if-else statement
        if (alpha >= beta) return myBest;
    }//end of for loop
    return myBest;
}

    public Move[] getAllLegalMoves(String[][] grid){
    //I’m unsure whether this method really belongs in this class or in the grid class, though, either way it shouldn’t matter.
    items = 0;
    moveList = null;
    Move move = new Move();

    for (int i = 0; i < 3; i++){
        for(int j = 0; j < 3; j++){
            Log.d(TAG,"At Column:" + i +" At Row:" + j);
            if(grid[i][j] == null || grid[i][j].equals("")){
                Log.d(TAG,"Is Empty");
                items++;
                if(moveList == null || moveList.length < items){
                    resize();
                }//end of second if statement
                move.setRow(j);
                move.setColumn(i);
                moveList[items – 1] = move;
            }//end of first if statement
        }//end of second loop
    }//end of first loop
    for (int k = 0; k < moveList.length; k++){
        Log.d(TAG,"Count:" + k +" Column:" + moveList[k].getColumn() +" Row:" + moveList[k].getRow());
    }
    return moveList;
}

private void resize(){
    Move[] b = new Move[items];
    for (int i = 0; i < items – 1; i++){
        b[i] = moveList[i];
    }
    moveList = b;
}

function alphabeta(node, depth, α, β, Player)        
    if  depth = 0 or node is a terminal node
        return score
    if  Player = MaxPlayer
        for each child of node
            α := max(α, alphabeta(child, depth–1, α, β, not(Player) ))    
            if β ≤ α
                break                             (* Beta cut–off *)
        return α
    else
        for each child of node
            β := min(β, alphabeta(child, depth–1, α, β, not(Player) ))    
            if β ≤ α
                break                             (* Alpha cut–off *)
        return β

import java.math.BigDecimal;

public class Board {

    /**
     * -1: opponent
     * 0: empty
     * 1: player
     */
    int[][] cells = new int[3][3];

    /**
     * the best move calculated by eval(), or -1 if no more moves are possible
     */
    int bestX, bestY;

    int winner() {
        // row
        for (int y = 0; y < 3; y++) {
            if (cells[0][y] == cells[1][y] && cells[1][y] == cells[2][y]) {
                if (cells[0][y] != 0) {
                    return cells[0][y];
                }
            }
        }

        // column
        for (int x = 0; x < 3; x++) {
            if (cells[x][0] == cells[x][1] && cells[x][1] == cells[x][2]) {
                if (cells[x][0] != 0) {
                    return cells[x][0];
                }
            }
        }

        // 1st diagonal
        if (cells[0][0] == cells[1][1] && cells[1][1] == cells[2][2]) {
            if (cells[0][0] != 0) {
                return cells[0][0];
            }
        }

        // 2nd diagonal
        if (cells[2][0] == cells[1][1] && cells[1][1] == cells[0][2]) {
            if (cells[2][0] != 0) {
                return cells[2][0];
            }
        }

        return 0; // nobody has won
    }

    /**
     * @return 1 if side wins, 0 for a draw, -1 if opponent wins
     */
    int eval(int side) {
        int winner = winner();
        if (winner != 0) {
            return side * winner;
        } else {
            int bestX = –1;
            int bestY = –1;
            int bestValue = Integer.MIN_VALUE;
        loop:
            for (int y = 0; y < 3; y++) {
                for (int x = 0; x < 3; x++) {
                    if (cells[x][y] == 0) {
                        cells[x][y] = side;
                        int value = –eval(–side);
                        cells[x][y] = 0;

                        if (value > bestValue) {
                            bestValue = value;
                            bestX = x;
                            bestY = y;
                            if (bestValue == 1) {
                                // it won’t get any better, we might as well stop thinking
                                break loop;
                            }
                        }
                    }
                }
            }
            this.bestX = bestX;
            this.bestY = bestY;
            if (bestValue == Integer.MIN_VALUE) {
                // there were no moves left, it must be a draw!
                return 0;
            } else {
                return bestValue;
            }
        }
    }

    void move(int side) {
        eval(side);
        if (bestX == –1) {
            return;
        }
        cells[bestX][bestY] = side;
        System.out.println(this);

        int w = winner();
        if (w != 0) {
            System.out.println("Game over!");
        } else {
            move(–side);
        }
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        char[] c = {‘O’, ‘ ‘, ‘X’};
        for (int y = 0; y < 3; y++) {
            for (int x = 0; x < 3; x++) {
                sb.append(c[cells[x][y] + 1]);
            }
            sb.append(‘/
‘);
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        long start = System.nanoTime();
        Board b = new Board();
        b.move(1);
        long end = System.nanoTime();
        System.out.println(new BigDecimal(end – start).movePointLeft(9));
    }
}