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