recursively creating a tree

Question

I am trying to recursively populate a tree, but my code is only only fill out one depth length, and then quiting. i.e. each node only has one child. Is there something am failing to take in to consideration?

public static void populate(Node n, int depth, String player){
    System.out.println("Depth: " + depth);
    if(player.equalsIgnoreCase("X"))
        player = "O";
    else
        player = "X";
    int j = 0;
    System.out.println("empty spots: " + ((Board)n.getData()).noOfEmpty());
    for(int i=0; i<((Board)n.getData()).noOfEmpty(); i++){
        if(((Board)n.getData()).getSquare(j).equalsIgnoreCase("X")
                || ((Board)n.getData()).getSquare(j).equalsIgnoreCase("O"))
            j++;
        else{
            Board tmp = new Board(((Board)n.getData()), j, player);
            Node newNode = new Node(tmp);
            tree.insert(n, newNode);
            populate(newNode, depth-1, player);
        }
    }
}

P.S. and i check the noOfEmpty() return value, which should determine the number of children a node should have.

edit:@eznme the complete code as requested:

public class MinMax {

    protected static Tree tree;


    public static void createTree(Board b){
        tree = new Tree();
        tree.setRoot(new Node(b));
        populate(tree.getRoot(), 5, "X");
        //System.out.println("printing tree");
        //tree.print(1);
    }

    public static void populate(Node n, int depth, String player){
        System.out.println("Depth: " + depth);
        if(player.equalsIgnoreCase("X"))
            player = "O";
        else
            player = "X";
        int j = 0;
        System.out.println("empty spots: " + ((Board)n.getData()).noOfEmpty());
        for(int i=0; i<((Board)n.getData()).noOfEmpty(); i++){
            if(((Board)n.getData()).getSquare(j).equalsIgnoreCase("X")
                    || ((Board)n.getData()).getSquare(j).equalsIgnoreCase("O"))
                j++;
            else{
                Board tmp = new Board(((Board)n.getData()), j, player);
                Node newNode = new Node(tmp);
                tree.insert(n, newNode);
                populate(newNode, depth-1, player);
            }
        }
    }
}

import java.util.ArrayList;

/**
*
* @author Greg
*/
public class Node {

    protected Object data;
    protected int score; //fields to be used by the MaxMin class
    protected ArrayList<Node> children;

    //constructors
    public Node(){
        children = new ArrayList(0);
        data = null;
    }
    public Node(Object obj){
        children = new ArrayList(0);
        data = obj;
    }


    public void setChild(Node n){
        //EFFECT: set the ith child to node t
        children.add(n);
    }
    public void setChildren(Node[] t){
        //EFFECT: copy the array t, into the array children, effectively
        // setting all the chidern of this node simultaneouly
        int l = children.size();
        for(int i=0; i<t.length; i++){
            children.add(l, t[i]);
        }
    }
    public void setData(Object obj){
        //EFFECT: set the date of this node to obj, and also set the number of
        //  children this node has
        data = obj;
    }
    public Node getChild(int i){
        //EFFECT: returns the child at index i
        return children.get(i);
    }

    public int noOfChildren(){
        //EFFECT: return the length of this node
            return children.size();
    }

    public Object getData(){
        //EFFECT: returns the data of this node
        return data;
    }

    @Override
    public String toString(){
        //EFFECT: returns the string form of this node
        return "" + data.toString() + "\nwith " + noOfChildren()+ "\n";
    }

    public boolean isLeaf(){
        if(children.size()==0)
            return true;
        return false;
    }


    public void setScore(int scr){
        score = scr;
    }

    public int getScore(){
            return score;
    }
}

public class Tree {

    private Node root;

    public Tree(){
        setRoot(null);
    }

    public Tree(Node n){
        setRoot(n);
    }

    public Tree(Object obj){
        setRoot(new Node(obj));
    }

    protected Node getRoot(){
        return root;
    }

    protected void setRoot(Node n){
        root = n;
    }

    public boolean isEmpty(){
        return getRoot() == null;
    }

    public Object getData(){
        if(!isEmpty())
            return getRoot().getData();
        return null;
    }

    public Object getChild(int i){
        return root.getChild(i);
    }

    public void setData(Object obj){
        if(!isEmpty())
            getRoot().setData(obj);
    }

    public void insert(Node p,Node c){
        if(p != null)
            p.setChild(c);
    }

    public void print(int mode){
        if(mode == 1) pretrav();
        else if(mode == 2) postrav();
        else
            System.out.println("yeah... mode 1 or 2...nothing else, try agn");
    }

    public void pretrav(){
        pretrav(getRoot());
    }

    protected void pretrav(Node t){
        if(t == null)
            return;
        System.out.println(t.getData()+" \n");
            for(int i=0; i<t.noOfChildren(); i++)
                pretrav(t.getChild(i));
    }

    public void postrav(){
        postrav(getRoot());
    }

    protected void postrav(Node t){
        if(t == null)
            return;
        System.out.print(t.getData()+" ");
            for(int i=0; i<t.noOfChildren(); i++)
                pretrav(t.getChild(i));
        System.out.print(t.getData()+" ");
    }
}

public class Board {

    boolean isFull = false;         // a check to see if the board is full
    String[] grid = new String[9];  //an array represting the 9 square on a board
    int hV;
    String MIN, MAX;

    public Board(){
        for(int i=0; i<grid.length;i++)
            grid[i] = Integer.toString(i);
        hV = heuristicValue(this);
    }

    public Board(Board b, int x, String player){
        this.grid = b.getBoard();
        if(!(grid[x].equalsIgnoreCase("X")|| grid[x].equalsIgnoreCase("X")))
            grid[x] = player;
    }

    public boolean setSquare(String player, int position){
        /*
        EFFECT:set a square on the board to either a X or a O, debending on the player
        PRECON: square (x,y) is empty
        POATCON: square (x,y) has player 'symbol'
        */

        boolean isValidPlay = false;
        try{
            //as a sanity
            Integer.parseInt(grid[position]);
            grid[position] = player;
            isValidPlay = true;

        }catch(NumberFormatException e){
            System.out.println("positon " + position + "is already occupied");
        }
        return isValidPlay;
    }

    public boolean endGame(){
        /*
        * EFFECT: check to see if the game have been won or drawn
        */
        if(ticTacToe(0,1,2)){
            //System.out.println("Player " + grid[0] + " wins");
            return true;
        }
        else if(ticTacToe(3,4,5)){
            //System.out.println("Player " + grid[3] + " wins");
            return true;
        }
        else if(ticTacToe(6,7,8)){
            //System.out.println("Player " + grid[6] + " wins");
            return true;
        }
        else if(ticTacToe(0,4,8)){
            //System.out.println("Player " + grid[0]+ " wins");
            return true;
        }
        else if(ticTacToe(0,3,6)){
            //System.out.println("Player " + grid[0]+ " wins");
            return true;
        }
        else if(ticTacToe(1,4,7)){
            //System.out.println("Player " + grid[1] + " wins");
            return true;
        }
        else if(ticTacToe(2,5,8)){
            //System.out.println("Player " + grid[2] + " wins");
            return true;
        }else if(ticTacToe(2,4,6)){
            //System.out.println("Player " + grid[2] + " wins");
            return true;
        }
        else
            return isDrawn();
    }

    public boolean ticTacToe(int x, int y, int z){
        /*
        * check is x, y and z has the same value
        */
        try{
            Integer.parseInt(grid[x]);
            return false;
        }catch(NumberFormatException e){
        if( grid[x].equals(grid[y])
                && grid[x].equals(grid[z]))
            return true;
        else
            return false;
        }
    }

    public String getSquare(int i){
        return grid[i];
    }

    @Override
    public String toString(){
        String msg = "";
        for(int i=0; i<grid.length; i++){
            msg = msg + grid[i] + " ";
            if(i==2 || i==5)
                msg = msg+ "\n";
        }
        return msg;
    }

    public boolean isDrawn(){
        /*
        * check to see if there are any 'free' spaces on the board, if there are any
        * return false, else return true
        */
        for(int i=0; i<grid.length; i++){
        try{
            Integer.parseInt(grid[i]);
            return false;
            }catch(NumberFormatException e){
            }
        }
        System.out.println("Game drawn");
        return true;
    }

    public String[] getBoard(){
        return grid;
    }

    public int noOfEmpty(){
        //EFFECT: returns the number of empty squares
        int count = 0;
        for(int i=0; i<grid.length; i++)
            if (!(grid[i].equalsIgnoreCase("X") || grid[i].equalsIgnoreCase("O")))
                count++;
        return count;
    }

    public int heuristicValue(Board b){
        String MAX = "X", MIN = "O";
        /*
        * calculate a value that will be used as a heuristic function
        * the function works for ever X in a row WITHOUT O: 1 point,
        * for two X in a row WITHOUT a O: 5 points
        * and 3 X in a row: 100 points
        */
        //System.out.println("Computing heuristic");
        //System.out.println("Computing horizontals");
        int hCount = 0;
        //sum up the horizontals
        for(int i=0; i<9; i=i+3){
            int tmpMAX = playerCount(b, MAX,i,i+1,i+2);
            int tmpMIN = playerCount(b, MIN,i,i+1,i+2);
            //System.out.println(tmpMAX);
            //System.out.println(tmpMIN);
            if(tmpMIN > 0){
                //System.out.println("Min was zero");
            }
            else if(tmpMAX==1){
                //System.out.println("has one");
                hCount = hCount + 1;
            }
            else if(tmpMAX==2){
                //System.out.println("was tw0");
                hCount = hCount + 5;
            }
            else if(tmpMAX==3){
                //System.out.println("full 100");
                hCount = hCount + 100;
            }
        }
        //System.out.println("Computing verticals");
        //sum up the verticals
        for(int i=0; i<3; i++){
            int tmpMAX = playerCount(b, MAX,i,i+3,i+6);
            int tmpMIN = playerCount(b, MIN,i,i+3,i+6);
            if(tmpMIN > 0){}
            else if(tmpMAX==1){
                hCount = hCount +1;
            }
            else if(tmpMAX==2){
                hCount = hCount + 5;
            }
            else if(tmpMAX==3){
                hCount = hCount + 100;
            }
        }
        //System.out.println("Computing diagonals");
        //sum up diagonals
        if(playerCount(b, MIN,0,4,8)==0){

            if(playerCount(b, MAX,0,4,8)==1){
                hCount = hCount + 1;
            }
            if(playerCount(b, MAX,0,4,8)==2)
                hCount = hCount + 5;
            if(playerCount(b, MAX,0,4,8)==3)
                hCount = hCount + 100;
        }
        if(playerCount(b, MIN,2,4,6)==0){

            if(playerCount(b, MAX,2,4,6)==1){
                hCount = hCount + 1;
            }
            if(playerCount(b, MAX,2,4,6)==2)
                hCount = hCount + 5;
            if(playerCount(b, MAX,2,4,6)==3)
                hCount = hCount + 100;
        }
        //System.out.println("Computing completed");
        int hV = hCount;
        return hV;
    }

    int playerCount(Board b, String player, int x, int y, int z){
        int count = 0;
        if(b.getSquare(x).equals(player))
            count = count + 1;
        if(b.getSquare(y).equals(player))
            count = count + 1;
        if(b.getSquare(z).equals(player))
            count = count + 1;
        //System.out.println("playerCount; " + count);
        return count;
    }
}

import java.io.*;

import java.io.IOException;

public class Main {

public static void main(String[] args) throws IOException{
    BufferedReader  reader = new BufferedReader(new
                                            InputStreamReader(System.in));
    Board thisGame = new Board();
    System.out.println("Start \n" + thisGame.toString());
    MinMax.createTree(thisGame);
    System.exit(0);
}

}

Solution 1

So here is what I would do in your case (minimax tic-tac-toe):

Terminology:

• Height of a node: Distance from this node to it's further leaf.
• Depth of a node: Distance from the root of the tree, to this node.

You have to keep trying all cases until: the board is full OR one player won. So, your tree's height is numberOfCells + 1. If we simplify the problem and don't worry about symmetric duplicates: Each node will have numberOfcells - nodeDepth childs.

public static void main(String[] args){
    Tree t = new Tree();
    int nbCells = 9;
    t.setRoot(buildTree(new Board(nbCells), 0, -1));
}

public static Node buildTree(Board b, int player, int positionToPlay){
    if(player != 0){
        b.setCellAt(positionToPlay, player);
    }
    Node n = new Node(b, b.nbEmptyCells());

    int j = 0;
    for(int i = 0; i < b.nbCells(); i++){
        if(b.getCellAt(i) == 0)
            n.setChildAt(j++, buildTree(new Board(b), changePlayer(player), i));
    }

return n;
}

public static int changePlayer(int p){
    switch(p){
    case 0:
        return 1;
    case 1:
        return 2;
    case 2:
        return 1;
    default:
        return 0;
    }
}

Node class:

public class Node {
    private Board board;
    private Node[] childs;

    public Node(Board b, int nbChilds){
        this.board = new Board(b);
        this.childs = new Node[nbChilds];
    }

    public Node getChildAt(int i){
        return childs[i];
    }

    public int nbChilds(){
        return childs.length;
    }

    public void setChildAt(int i, Node n){
        this.childs[i] = n;
    }

    public Board getBoard(){
        return this.board;
    }

Solution 2

In order to recursively build a n-ary tree, I would do this:

public static void populate(Node n, int height){
    if(height = 0){
        n = new Node();  
    }else{
        n = new Node();
        for(int i = 0; i < n.nbChilds(); i++){
            populate(n.getChildAt(i), height - 1);
        }
    }
}

I hope it helps.

Order of nodes creation with this algo (on a binary tree):

              1
      2                9
  3       6        10     13
4  5    7   8    11  12 14  15

Comments

[Bernd Elkemann]

please post complete code so we can compile and run it

[cubearth]

will try to, but it is big, the complete code involve 4 classes; Node, Tree, Board and MinMax

[cubearth]

and there is a main class, but that just calls the createTree() method in MinMax

[cubearth]

just to clarify, you are suggesting that I allow node to deal with the creation of it's children?

[nbarraille]

@cubearth: With recursion, each node n is responsible of building its own subtree, yes. I really don't see how you could make a recursive solution where it is not the case (but I'd be happy to read it if you find one). Is it a problem in your case?

[cubearth]

if each node create it own children, am assuming that these children are created when the node is created, wouldnt cause all possible state to be created when i called the first node, as each child will also created it's own children?

[nbarraille]

@cubearth What do you mean by "all possible state". With this, the whole tree will be populated at the same time (I edited my post to show you the specific order in which the nodes will be created), when you call populate(rootNode, treeHeight). If you only want to populate two levels, you can just call populate(rootNode, 2), and if you want to continue populate a tree that is already started, you can call populate() on any node you want. But I think it would be a good idea to explain a little what it is you want to do (it looks like a tic-tac-toe to me but I find it weird to use a tree).

[cubearth]

It is tic tac toe, am trying to solve it using a minimax algorithm. so am basical, trying to create the tree so that i can then get the min max values of each node.

[cubearth]

I really think the problem is with my node class, do you know where i can get a node skeleton class to implement. Cause i have been fighting over this code for too long. I tried having the node class create it's own children, but now am getting a stack overflow error. :(

[nbarraille]

@cubearth I edited my answer with a Node class, that's all you need. Note the keypoint though: this.board = new Board(b); and not this.board = b. You don't want to reuse the same instance of board, but to create another one (so modifying a Node's board won't modify its parent's)

[cubearth]

ok, let me try to implement it and I'll let you know how it goes

[cubearth]

hey thanks man, I got it to produce a tree, Now am off to implement minimax ^___^

[nbarraille]

@cubearth Cool. Let me know if you run into any more problems, I'm interested in this problem.

[cubearth]

As is started with the minimax implementation, i notice i didnt need trees, just a understanding of tree/nodes, so thanks again. However I encountered a lil snag. I posted as another question here [link] (stackoverflow.com/questions/5237307/…)

[Andrei]

if(height = 0) should be if(height == 0)