I created the minimax, pvs and alpha-beta algorithms and compared their results using a random tree to traverse. This tree has [2,10] children for each parent with a total depth of 10. Each leaf node has a random value of [0,10].
When i run the tree traversal minimax algorithm the resulting value is usually 2 or 3. This is odd to me as i would have guess it would have given 5 or maybe 4 or 6, but it's always 2 or 3. This is minimax algorithm it should give the max of the min ect which is confusing why it seems to be giving almost the min of the whole tree, fyi i start the algorithms as the maximizing player.
This is the results:
Alpha Beta: 2.0, time: 10.606461 milli seconds
PVS: 2.0, time: 41.119652 milli seconds
Minimax: 2.0, time: 184.492937 milli seconds
This is the source code, excluding the Timer class as that's not relevent to my question.
import testing.utilities.data.Timer;
import java.util.ArrayList;
import java.util.List;
import java.util.Objects;
import java.util.Random;
public class MinimaxAlphaBetaTest {
public static void main(String[] args) {
Node parent = new Node(0.);
int depth = 10;
createTree(parent,depth);
Timer t = new Timer().start();
double ab = alphabeta(parent,depth+1,Double.NEGATIVE_INFINITY,Double.POSITIVE_INFINITY,true);
t.stop();
System.out.println("Alpha Beta: "+ab+", time: "+t.getTime());
t = new Timer().start();
double pv = pvs(parent,depth+1,Double.NEGATIVE_INFINITY,Double.POSITIVE_INFINITY,1);
t.stop();
System.out.println("PVS: "+pv+", time: "+t.getTime());
t = new Timer().start();
double mm = minimax(parent,depth+1,true);
t.stop();
System.out.println("Minimax: "+mm+", time: "+t.getTime());
}
public static void createTree(Node n, int depth){
if(depth == 0) {
n.getChildren().add(new Node((double) randBetween(0, 10)));
return;
}
for (int i = 0; i < randBetween(2,10); i++) {
Node nn = new Node(0.);
n.getChildren().add(nn);
createTree(nn,depth-1);
}
}
private static Random r; // pseudo-random number generator
private static long seed; // pseudo-random number generator seed
// static initializer
static {
// this is how the seed was set in Java 1.4
seed = System.currentTimeMillis();
r = new Random(seed);
}
public static int randBetween(int min, int max){
return r.nextInt(max-min+1)+min;
}
public static double pvs(Node node, int depth, double alpha, double beta, int color){
if(depth == 0 || node.getChildren().isEmpty())
return color*node.getValue();
int i = 0;
double score;
for(Node child : node.getChildren()){
if(i++==0)
score = -pvs(child,depth-1,-beta,-alpha,-color);
else {
score = -pvs(child,depth-1,-alpha-1,-alpha,-color);
if(alpha<score || score<beta)
score = -pvs(child,depth-1,-beta,-score,-color);
}
alpha = Math.max(alpha,score);
if(alpha>=beta)
break;
}
return alpha;
}
public static double alphabeta(Node node, int depth, double alpha, double beta, boolean maximizingPlayer){
if(depth == 0 || node.getChildren().isEmpty())
return node.getValue();
double v = maximizingPlayer ? Double.NEGATIVE_INFINITY : Double.POSITIVE_INFINITY;
for(Node child : node.getChildren()){
if(maximizingPlayer) {
v = Math.max(v, alphabeta(child, depth - 1, alpha, beta, false));
alpha = Math.max(alpha, v);
}else {
v = Math.min(v, alphabeta(child, depth - 1, alpha, beta, true));
beta = Math.min(beta, v);
}
if(beta <= alpha)
break;
}
return v;
}
public static double minimax(Node node, int depth, boolean maximizingPlayer){
if(depth == 0 || node.getChildren().isEmpty())
return node.getValue();
double v = maximizingPlayer ? Double.NEGATIVE_INFINITY : Double.POSITIVE_INFINITY;
for(Node child : node.getChildren()){
if(maximizingPlayer)
v = Math.max(v,minimax(child,depth-1,false));
else
v = Math.min(v,minimax(child,depth-1,true));
}
return v;
}
static class Node{
List<Node> children = new ArrayList<>();
double value;
public Node(double value) {
this.value = value;
}
public List<Node> getChildren() {
return children;
}
public double getValue() {
return value;
}
public void setValue(double value) {
this.value = value;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Node node = (Node) o;
return Double.compare(node.value, value) == 0;
}
@Override
public int hashCode() {
return Objects.hash(value);
}
}
}
Thanks to Jiri Tousek comment it makes sense now, when run with a depth of an odd number gives a number usually higher than 5 and an even number usually lower than 5, like 11 for instance it produces the following results:
Alpha Beta: 7.0, time: 39.697701 milli seconds
PVS: 7.0, time: 216.849568 milli seconds
Minimax: 7.0, time: 998.207216 milli seconds
Running it further with odd numbers, it looks like at depth 3 the results are from what i've seen (5,6,7,8,9,10), depth 5 the results are from what i've seen (7,8,9), depth 7 the results are from what i've seen 7 or 8, depth 9 the results from what i've seen are 8, and depth 11 i've seen 7 and 8
Whereas even numbers produce {2,4,(2,3,4,5,6)},{6,8,10,(2,3)}
So when running the algorithm and look for results, should it matter who's turn it is?
IE if it's the maximizer's turn then go an odd depth down and if it's the minimzer's turn go an even depth down, any depth produce the ideal move?
Since you're starting with maximum (at the very top) and going 10 levels down, you're gonna choose the minimums at the deepest level.
Since you're choosing minimum of the [2-10] numbers there (not an average), you cannot expect it to be roughly 5 - it will most often be lower. In fact, a chance that the minimum of 6 numbers in range [0-10] will be 5 or higher is roughly (1/2)^6 ~ 1.5%.
The operations then alternate. I'm not able to compute any good probabilities there, but intuitively the effect should be about neutral.
It might help to look at what happens after one alternation of min then max. Let's go with 6 children per node (to make it simple). As already stated, the chance that a result of the "min" phase will be 5 or higher is roughly (1/2)^6. For the "max" phase to result in a number 5 or higher, it's enough for any child to be 5 or higher. There are 6 children, so the chance is about 1 - (1 - (1/2)^6)^6 ~ 9%.
This is already much lower than the initial 50% chance of a 5+ number at the very bottom. Another iteration would then result in 1 - (1 - (0.09)^6)^6 ~ 3e-6 probability of a 5+ number.