Alpha Beta Pruning Optimization

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 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 a = (ArrayList) moves.clone();
a.add(true);
int level = 0; // Level is how far down it would go

if (moves.size() = 14 && 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 wil

Cloning vs copy-constructors

ArrayList moves = (ArrayList) 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 list = new ArrayList<>();
// instead of
// ArrayList list = new ArrayList();

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

Boolean comparison and ternary conditions

In your Player class:

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

public float prun(int level, ArrayList 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 moves, boolean maxNode) {
    // ...
    return al > alpha;
}

public float prun(int level, List 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.

StackExchange Code Review Q#119124, answer score: 2