function ttt_play(S,V)
% ttt_play(S,V) 
%
% plays Tic-Tac-Toe, permiting optimal autoplay for any move. The cell array S
% and contains the states that can be reached at each stage and is
% computed using 
%    S=ttt_states(0);
% and the cell array V contains the cost-to-go and is computed using:
%    V=ttt_value(S);

    %% Initialize state
    x=S{1};
    ttt_drawboard(x);

    for k=1:9
        if rem(k,2)==1
            %% player X (minimizer) plays at odd stages
            fprintf('stage %d: X plays\n',k);
            % compute all next states
            [newS,won,invalid]=ttt_addX(x);
            % convert states to indices in S{k+1}
            [exists,newSndx]=ismember(newS,S{k+1});
            % compute all possible values
            newV=zeros(size(newS),'int8');
            newV(exists)=V{k+1}(newSndx(exists));
            newV(won)=-1; 
            newV(invalid)=Inf;              % penalize invalid actions (+inf for minimizer)
            [~,autoslot]=min(newV);
        else
            %% player O (maximizer) plays at even stages
            fprintf('stage %d: O plays\n',k);
            % compute all next states
            [newS,won,invalid]=ttt_addO(x); 
            % convert states to indices in S{k+1}
            [exists,newSndx]=ismember(newS,S{k+1});
            % compute all possible values
            newV=zeros(size(newS),'int8');
            newV(exists)=V{k+1}(newSndx(exists));
            newV(won)=1;
            newV(invalid)=-Inf;             % penalize invalid actions (-inf for maximizer)
            [~,autoslot]=max(newV);
        end

        % get action from player
        while (1)
            slot=input('select slot [1:9] or 0 for optimal autoplay: ');
            if length(slot)==1 && ismember(slot,1:9) && ~invalid(slot)
                % manual play
                break;
            elseif length(slot)==1 && slot==0
                slot=autoslot;
                break;
            else
                fprintf('  invalid input, try again\n\t');
            end
        end

        x=newS(slot);
        ttt_drawboard(x);
        
        if won(slot)
            if rem(k,2)==1
                fprintf('X won!\n');
            else
                fprintf('O won!\n');
            end
            return
        else
            if newV(slot)>0
                fprintf('  O will win!\n');
            end
            if newV(slot)<0
                fprintf('  X will win!\n');
            end
        end
    end
    fprintf('draw\n');
end


