Alpha Beta Pruning Optimization

Question

I made a class that would do alpha beta pruning on a binary tree of 40 degree. However there is a time limit on a single move of 30 seconds. I am to play against my professor and his opponent class. I tried going down 6 levels but I would lose. I tried going down 7 levels and I was taking too long. Is there a way to make my code run faster? If possible can you also check my logic for the alpha beta pruning part and see if I missed anything causing it to run longer than it should. I will include all classes but I only need help with the Player class since that is the only one I'm working on. Everything else is given by the professor. I want it to run faster so I can go deeper down the tree so I have an advantage and win the game. The game is won if I end up with a positive number.

Player:

import java.util.ArrayList;

public class Player {

    private Tree t;

    public Player(Tree t) {
        this.t = t;
    }

    // play will take in the moves and the player (in this case the maximizer)
    // and return the best possible move
    public boolean play(ArrayList<Boolean> moves, boolean maxNode) {
        float alpha = Float.NEGATIVE_INFINITY;
        float beta = Float.POSITIVE_INFINITY;
        // a will be the two possible moves that this node can take
        ArrayList<Boolean> a = (ArrayList<Boolean>) moves.clone();
        a.add(true);
        int level = 0; // Level is how far down it would go

        if (moves.size() < 14) {
            level = 19 - moves.size();
        } else if (moves.size() >= 14 && moves.size() < 34) {
            level = 6;
        } else if (moves.size() >= 34) {
            level = 39 - moves.size();
        }
        //System.out.println(moves.size() + "     " + level);
        alpha = Math.max(alpha, prun(level, a, maxNode, alpha, beta));
        a.remove(a.size() - 1);
        float al;
        al = alpha;
        alpha = Float.NEGATIVE_INFINITY;
        a.add(false);
        alpha = Math.max(alpha, prun(level, a, maxNode, alpha, beta));
        if (al > alpha) {
            return true;
        } else {
            return false;
        }
    }

    // prun is a recursive function that will determine alpha and beta
    public float prun(int level, ArrayList<Boolean> m, boolean maxNode, float a, float b) {
        if (level <= 0) {
            return t.value(m);
        }
        level--;
        ArrayList<Boolean> moves = (ArrayList<Boolean>) m.clone();
        ArrayList<Boolean> moves1 = (ArrayList<Boolean>) m.clone();
        // Child is all possible moves for a node.
        ArrayList<ArrayList<Boolean>> child = new ArrayList<ArrayList<Boolean>>();
        child.add(moves);
        child.add(moves1);
        child.get(0).add(true);
        child.get(1).add(false);
        float score;
        for (ArrayList c : child) {
            score = prun(level, c, !maxNode, a, b);
            if (maxNode) {
                if (score > a) {
                    a = score;
                }
            } else if (!maxNode) {
                if (score < b) {
                    b = score;
                }
            }
            if (a >= b) {
                break;
            }
        }
        if (maxNode) {
            return a;
        } else {
            return b;
        }
    }
}

Tree:

import java.util.ArrayList;
import java.util.Random;

public class Tree {
    public final int TOTALNODES=2097152;
    public final float EPSILON=0.00001f;
    public final float distribution=10.0f;

    public long randomSeed=0L;
    public float[] topTree=new float[TOTALNODES];
    private Random r=new Random();
    public long height=40;

    public Tree(long rs) {
        randomSeed=rs;
        r.setSeed(randomSeed);
        topTree[0]=topTree[1]=0.0f;
        int current=2; int levelNodes=2; float factor=1.0f;
        while (current<TOTALNODES) {
            for (int i=0; i<levelNodes; i++) {
                int parent=current/2;
                float sign=0.0f;
                if (r.nextBoolean()&&r.nextBoolean())
                    if (topTree[parent]>EPSILON) sign=1.0f; else sign=-1.0f;
                else if (topTree[parent]>EPSILON) sign=-1.0f; else sign=1.0f;
                float offset=((Math.abs(topTree[parent])<EPSILON)?(r.nextFloat()*2.0f*distribution-distribution):(r.nextFloat()*distribution*factor*sign));
                topTree[current]=topTree[parent]+offset;
                current++; }
            levelNodes*=2; factor*=0.9f; }
    }

    public float value(ArrayList<Boolean> moves) {
        // low and high will both be values between 0 and 2^21-1=TOTALNODES.
        // The depth will be the number of bits examined, starting with the low order bit of the low int.
        // A depth of 0 will indicate the root.
        int position=1;
        for (int i=0; i<Math.min(20, moves.size()); i++) {
            if (moves.get(i).booleanValue()) position=position*2+1; else position*=2; }
        if (moves.size()<=20) return topTree[position];
        r.setSeed(randomSeed+position);

        float[] bottomTree=new float[TOTALNODES];
        bottomTree[0]=bottomTree[1]=topTree[position];
        int current=2; int levelNodes=2; float factor=0.12157665459056928801f;
        while (current<TOTALNODES) {
            for (int i=0; i<levelNodes; i++) {
                int parent=current/2;
                float sign=0.0f;
                if (r.nextBoolean()&&r.nextBoolean())
                    if (bottomTree[parent]>EPSILON) sign=1.0f; else sign=-1.0f;
                else if (bottomTree[parent]>EPSILON) sign=-1.0f; else sign=1.0f;
                float offset=((Math.abs(bottomTree[parent])<EPSILON)?(r.nextFloat()*2.0f*distribution-distribution):(r.nextFloat()*distribution*factor*sign));
                bottomTree[current]=bottomTree[parent]+offset;
                current++; }
            levelNodes*=2; factor*=0.9f; }

        position=1;
        for (int i=20; i<moves.size(); i++) {
            if (moves.get(i).booleanValue()) position=position*2+1; else position*=2; }
        return bottomTree[position];
    }
}

Main:

import java.util.ArrayList;

public class Main {


    public static void main(String[] args) {
        final long randomSeed=564715140;

        Tree t=new Tree(randomSeed);
        ArrayList<Boolean> moves=new ArrayList<Boolean>();

        Player player=new Player(t);
        Opponent other=new Opponent(t);
        int turn=0;
        for (int i=0; i<t.height; i++) {
            long before=System.currentTimeMillis();
            boolean maxNode=(turn==0);
            Boolean newMove=((maxNode)?player.play(moves, maxNode):other.play(moves, maxNode));
            if (newMove==null) throw new RuntimeException("No decision made.");
            moves.add(newMove);
            long after=System.currentTimeMillis();
            if ((after-before)>30000) {
                if (maxNode) System.out.println("The maximizer took too long: "+(after-before));
                else System.out.println("The minimizer took too long: "+(after-before));
                System.exit(0); }
            System.out.println("Time: "+(after-before));
            turn=1-turn;
        }
        System.out.println("Final score: "+t.value(moves));
    }

}

Opponent: (This would be the professor's class which I don't have so I just have it return random)

import java.util.ArrayList;

public class Opponent {
    private Tree t;

    public Opponent(Tree t) {
        this.t = t;
    }
    // play will take in the moves and the player (in this case the maximizer)
    // and return the best possible move
    public boolean play(ArrayList<Boolean> moves, boolean maxNode) {
        int rand = (int)(Math.random() * 10) + 1;
        return (rand%2 == 0);
    }
}

Answer 1

Cloning vs copy-constructors

ArrayList<Boolean> moves = (ArrayList<Boolean>) m.clone();

Instead of clone()-ing, you should be using the constructor ArrayList(Collection) to create new List instances backed by the same elements as the original. This is safe for adding or removing elements on the newly created instances.

Interfaces over implementations

Interface types such as List is recommended over the implementing types, i.e. ArrayList, because the users of the variable should only need to use the methods provided by the List API without having to understand the underlying implementation. This is also known as loose coupling. Additionally, since Java 7, you can use generic type inference to save you some keystrokes:

List<AVeryLongType> list = new ArrayList<>();
// instead of
// ArrayList<AVeryLongType> list = new ArrayList<AVeryLongType>();

// instead of ArrayList<T>
public static void methodName(List<T> list) {
    // ...
}

Boolean comparison and ternary conditions

In your Player class:

public boolean play(ArrayList<Boolean> moves, boolean maxNode) {
    // ...
    if (al > alpha) {
        return true;
    } else {
        return false;
    }
}

public float prun(int level, ArrayList<Boolean> m, boolean maxNode, float a, float b) {
    // ...
    if (maxNode) {
        return a;
    } else {
        return b;
    }
}

You can also consider using the direct boolean comparison and ternary operators to simplify the expressions here:

public boolean play(List<Boolean> moves, boolean maxNode) {
    // ...
    return al > alpha;
}

public float prun(int level, List<Boolean> m, boolean maxNode, float a, float b) {
    // ...
    return maxNode ? a : b;
}

Code formatting styles

Your Player class's code formatting is the conventional kind, which a seasoned Java developer should be able to understand easily, and that is weirdly different from your Tree and Main classes. You should either make the Player class 'look' more like the rest for consistency, or make the code formatting of the other two more conventional.