population récursive d'arbre
Question
Je suis tenté de créer et remplir un arbre en Java, puis utilisez l'algorithme minimax pour trouver le meilleur pour une IA.
fonction récursive pour générer l'arbre:
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);
}
}
Fonction pour alimenter l'arbre avec des valeurs:
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');
}
}
}
fonction de test pour voir si tout a fonctionné, en imprimant le contenu:
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);
}
}
Et, la classe de nœud lui-même:
Noeud de classe finale
{
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()
{
}
}
Je lance la fonction d'impression, et il imprime 1 BxXXCXXX Ce que je m'y attendais pour le premier noeud. Je l'ai appelé avec un noeud vide, et la profondeur de 1. Pourquoi est-il pas générer (ou l'impression), le reste de l'arbre, jusqu'à la profondeur 6?
Bien que je pense que cela est peut-être sans rapport, ce code sera finalement utilisé dans un jeu Android.
La solution
Java passe Node
par valeur, de sorte que votre n = new Node();
d'affectation n'a pas d'effet. Votre fonction gen
doit retourner le nœud qu'il crée, au lieu de prendre un comme paramètre.
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;
}