output=solve_tree(tree)

%Copywrite Abhilash Harpale (c) 2009.

%This function decodes the tree to find the maximum payoff for player 1 at every
%node .The player who has to play the next move is specified in the third
%row(1 for player 1 and 2 for player 2).The forth row specifies which of
%the nodes is a leaf(1 if it is a leaf 0 otherwise).

function output=solve_tree(tree)
output=tree;
temp=tree;
while(output(2,1)~=1 && output(2,1)~=-1 && output(2,1)~=0)
    [r c]=find(temp==-1);
     c=c.*(r==1);
     clear r;
     for i=c'
         if (i~=0)
             flag=0;
             j=1;
             z=0;
             while(temp(1,i+j)~=-3)
                 if(temp(1,i+j)~=0)
                    if(mod(j-z,2)==1 && ~(temp(1,i+j)>0 && (temp(2,i+j)==-1 || temp(2,i+j)==1)))
                        flag=flag+1;
                    end
                    if(mod(j-z,2)==0 && ~(temp(1,i+j)==-2))
                        flag=flag+1;
                    end
                 else
                     z=z+1;
                 end
                 j=j+1;
             end
             
             if(flag==0)
                 node_scores=[];
                 for k=1:j
                     if(temp(1,i+k)>0)
                         node_scores=[node_scores temp(2,i+k)];
                     end
                 end
                 if(temp(2,i-1)==0.5)
                     output(2,i-1)=max(node_scores);
                     temp(2,i-1)=max(node_scores);
                 else
                     output(2,i-1)=min(node_scores);
                     temp(2,i-1)=min(node_scores);
                 end
                 temp(1:2,i:(i+j))=0;
             end
         end
     end
end
output(3,:)=1*(tree(2,:)==0.5)+2*(tree(2,:)==1.5);
output(4,:)=(tree(1,:)>0).*((tree(2,:)==1)+(tree(2,:)==0)+(tree(2,:)==-1));
end