Problem
I’m working on a program that is supposed to use alpha beta pruning to find the best move for a game. The game is basically a binary tree of degree of 40 and each node will have a different float value. The moves are only true or false. The goal is to score a positive score at the end. The professor gave us the Main and the Tree class and all I have to do is the Player. The opponent class is just a class I made that would randomly play true or false just to test my code. I have implemented the class but I’m not sure if it is working properly since I do get negative scores on some play through with the random opponent I made. If someone could look at this and see if my logic for the alpha beta pruning part is correct, it would be really helpful.
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));
}
}
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=564715140;
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];
}
}
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, beta;
alpha = Float.NEGATIVE_INFINITY;
beta = Float.POSITIVE_INFINITY;
ArrayList<Boolean> a = new ArrayList<Boolean>();
a = (ArrayList<Boolean>) moves.clone();
float al;
a.add(true);
int level = 10; // It will look ahead 10 nodes
if (moves.size() >= 30) // If we're at move 30
level = 39 - moves.size();
alpha = Math.max(alpha, prun(level, a, maxNode, alpha, beta));
a.remove(a.size()-1);
al = alpha;
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) {
//System.out.println(m.size());
return t.value(m);
}
ArrayList<Boolean> moves = new ArrayList<Boolean>();
moves = (ArrayList<Boolean>) m.clone();
ArrayList<Boolean> moves1 = new ArrayList<Boolean>();
moves = (ArrayList<Boolean>) m.clone();
float score;
// child arraylist is the possible moves for the 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);
if (level > 0) {
if (maxNode) {
for (ArrayList c : child) {
score = prun(level-1, c, !maxNode, a, b);
if (score > a) a = score;
if (a >= b) break;
}
return a;
}
else {
for (ArrayList c : child) {
score = prun(level-1, c, !maxNode, a, b);
if (score < b) b = score;
if (a >= b) break;
}
return b;
}
}
return 0;
}
}
Opponent:
import java.util.ArrayList;
public class Opponent {
private Tree t;
public Opponent(Tree t) {
this.t = t;
}
// maxNode = true is player, false is opponent
// WHEN ALPHA <= BETA CURRENT NODE IS WORTHLESS
public boolean play(ArrayList<Boolean> moves, boolean maxNode) {
int i = (int)(Math.random() * 10) + 1;
if (i % 2 == 0) return false;
else return true;
}
}
Solution
Useless variable assignment
ArrayList<Boolean> a = new ArrayList<Boolean>();
a = (ArrayList<Boolean>) moves.clone();
ArrayList<Boolean> moves = new ArrayList<Boolean>();
moves = (ArrayList<Boolean>) m.clone();
ArrayList<Boolean> moves1 = new ArrayList<Boolean>();
moves = (ArrayList<Boolean>) m.clone();
You put a new ArrayList inside variable a, only to be replaced with the result of clone().
ArrayList<Boolean> a = (ArrayList<Boolean>) moves.clone();
Use interfaces instead of abstract classes
ArrayList<Boolean> a = new ArrayList<Boolean>();
a = (ArrayList<Boolean>) moves.clone();
By using interfaces instead of abstract classes, you restrict yourself to a certain type. This prevents yourself later changing the type to for example a LinkedList, this will hinder yourself when testing performance
List<Boolean> a = (List<Boolean>) moves.clone();
Repeated calculation
score = prun(level-1, c, !maxNode, a, b);
The only place where the level variable is used in the recursion. Yet it is called multiple times, and java needs to subtract it by 1 every time. By doing the subtraction at the top of the method, you can speed it up and reduce the line length.
At the top of the method, change to:
if (level <= 0) {
//System.out.println(m.size());
return t.value(m);
}
level--;
Default values of class ignored
public long randomSeed=564715140;
You define a field with a default value, this default value is overridden in every constructor, making it only confusing for the reader to check where this default value is used, only to discover it isn’t used.
public long randomSeed;
Bad formatting
public final int TOTALNODES=2097152;
public final float EPSILON=0.00001f;
public final float distribution=10.0f;
public long randomSeed=564715140;
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; }
}
The formatting in the above piece of code makes it hard to read because it’s too compact, putting spaces around operators like =, +, && and all the others makes it less compact, and by that harder to follow.
(I read you said you cannot change this, but sometimes professors also need critic, 🙂 )
Don’t declare variables before they are used
float alpha, beta;
float al;
Possible bug:
ArrayList<Boolean> moves = new ArrayList<Boolean>();
moves = (ArrayList<Boolean>) m.clone();
ArrayList<Boolean> moves1 = new ArrayList<Boolean>();
moves = (ArrayList<Boolean>) m.clone();
You assign moves 2 times the result of clone, if you followed above steps you would properly already seen this, but if you didn’t, shouldn’t the lowest assignment be moves1 instead of moves.