Recursive population of tree
Question
I've been attempting to create and populate a tree in java, and then use the minimax algorithm to find the best course for an AI.
Recursive function to generate tree:
public void gen(Node n, int depth){
if(depth == 6){
n = new Node();
n.depth = height;
}
else{
n = new Node();
n.depth = depth;
gen(n.e1, depth+1);
gen(n.e2, depth+1);
gen(n.e3, depth+1);
gen(n.p1, depth+1);
gen(n.p2, depth+1);
gen(n.p3, depth+1);
}
}
Function to populate tree with values:
public void score(Node node, char a){
//Assigning scores to states to find utility value
//Changing state strings to reflect current state of nodes and phase
if(node!=null && node.depth!=6){
if(node.depth%2==1){
//Player's turn
node.state = node.state.substring(0, node.depth))+a+node.state.substring((node.depth+2));
score(node.e1, 'a');
score(node.e2, 'b');
score(node.e3, 'a');
score(node.p1, 'b');
score(node.p2, 'a');
score(node.p3, 'b');
}
else if(node.depth%2==0){
//AI's turn
node.state = node.state.substring(0,(node.depth+4))+a+node.state.substring((node.depth+6));
score(node.e1, 'a');
score(node.e2, 'b');
score(node.e3, 'a');
score(node.p1, 'b');
score(node.p2, 'a');
score(node.p3, 'b');
}
}
}
Test function to see if everything worked, by printing the contents:
public void printTree(Node node){
if(node!=null){
System.out.println(node.depth + " " + node.state);
printTree(node.e1);
printTree(node.e2);
printTree(node.e3);
printTree(node.p1);
printTree(node.p2);
printTree(node.p3);
}
}
And, the node class itself:
final class Node
{
public String state = "BCXXXCXXX";
//utility value
public int score;
public int oscore;
public int utility;
public int min;
public int max;
public int depth;
Node p1;
Node p2;
Node p3;
Node e1;
Node e2;
Node e3;
public Node()
{
}
}
I run the print function, and it prints 1 BxXXCXXX Which I expected for the first node. I called it with an empty node, and depth of 1. Why isn't it generating (or printing) the rest of the tree, down to depth 6?
Although I think this is possibly unrelated, this code will eventually be used in an Android game.
Solution
Java passes Node
by value, so your assignment n = new Node();
has no effect. Your gen
function should return the node it creates, instead of taking one as a parameter.
public Node gen(int depth){
Node n = new Node();
if (depth == 6){
n.depth = height;
} else {
n.depth = depth;
n.e1 = gen(depth+1);
n.e2 = gen(depth+1);
n.e3 = gen(depth+1);
n.p1 = gen(depth+1);
n.p2 = gen(depth+1);
n.p3 = gen(depth+1);
}
return n;
}