[output]=create_sub_tree(current_state,player,i,m,n)

%Copywrite Abhilash Harpale (c) 2009.

%This function generates the tree for the game of chomp.
%The conventions are :
%-1 signifies creating a node .
%-2 signifies creating a sister node.
%-3 signifies moving up to the parent node.
%below every -1 and -2 the move played to reach that node is given.
%Below -3 there is inf by default.
%At a perticular node the first number signifies its shortest distance from
%the starting node.
%The second number signifies the player who has to play the next move(0.5
%for player 1 and 1.5 for player 2).
%If the node is a leaf then the second number signifies the payoff for
%player 1 (1,-1,0).



function [output]=create_sub_tree(current_state,player,i,m,n)

if(size(current_state,2)==1)
    if(player==0.5)
        n=-1;
    end
    if(player==1.5)
        n=1;
    end
    output=[i;n];
else
    s=0;
    tree=[i;player];
    for j=current_state
        if (j~=((m*n)-n+1))
            s=s+1;
         if(s==1)
            tree=[tree [-1;j]];
            tree=[tree create_sub_tree(next(current_state,j,m,n),flip(player),i+1,m,n)];
         else
            tree=[tree [-2;j]];
            tree=[tree create_sub_tree(next(current_state,j,m,n),flip(player),i+1,m,n)];
         end
        end
    end
    tree=[tree [-3;inf]];
    output=tree;
end
end