function V=ttt_value(S)
% V=ttt_value(S) 
%
% computes the cost-to-go for the Tic-Tac-Toe game. The cell array S
% and contains the states that can be reached at each stage and is
% computed using 
%    S=ttt_states(0);
%
%% Value function representation
% V    = cell array with 9 elements, each elements is an vector that
%        enumerates the cost-to-go for all possible states at stage
%        k, which are enumerated in S{k}:
%          k = 1,3,5,7,9 - cost-to-go (after) minimizer placex X optimally
%          k = 2,4,6,8   - cost-to-go (after) maximizer placex O optimally
%
%        For consistency with the (simultaneous play) model in the
%        book, we encoded an alternate plays game as a simultaneous
%        play game in which one of the players cannot do any move at
%        each stage.
%        
%        Each entry of each V{k} can have 3 values
%          0    - draw
%          -1   - X wins
%          +1   - O wins
%          +Inf - invalid move for X (minimzer)
%          -Inf - invalid move for O (maximizer)
%        (since V{k} is of type int8, +Inf and -Inf are actually finite integers)
%
    
    t0=clock();

    % Initialize value function
    K=9;
    V=cell(K+1,1);
    V{K+1}=zeros(size(S{K+1}),'int8');
    for k=K:-1:1
        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(S{k});
            % 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)
            V{k}=min(newV,[],2); % pick best for minimizer
        else
            %% player O (maximizer) plays at even stages
            fprintf('stage %d: O plays\n',k);
            % compute all next states
            [newS,won,invalid]=ttt_addO(S{k}); 
            % 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)
            V{k}=max(newV,[],2); % pick best for maximizer
        end % if rem...
    end % for k=...
    fprintf('done in %f.6 sec\n',etime(clock(),t0));
    fprintf('Value of game = V{1}(1) = %d\n',V{1}(1));
end
       
