function S=ttt_states(S0)
% S=ttt_states(S0)
%
% Computes the set of all *non-terminal* states that may arise in a
% Tic-Tac-Toe game, starting from the initial state S0. Typically
% S0=0, which corresponds to the empty board.
%
%% Game state representation
%
% Each state is represented by an integer with 9x2 = 18 bit of the form
%     (a91 a90) (a81 a80) (a71 a70) (a61 a60) (a51 a50) (a41 a40) (a31 a30) (a21 a20) (a11 a10)
% where each pair of bits 
%     (aX1 aX0) representes the state of the X-th square of the
%     Tic-tac-Toe board as follows:
%       00 - empty slot
%       01 - X
%       10 - O
%       11 - invalid state
% The board slots are numbered as follows
%
%    1st | 2nd | 3rd
%   -----+-----+-----
%    4th | 5th | 6th
%   -----+-----+-----
%    7th | 8th | 9th
%
%
%% Set of states representation
% S = cell array with 9 elements, each is an vector that enumerates
%     all *non-terminal* states for stage  k:
%          k = 1,3,5,7,9 - states just before X plays
%          k = 2,4,6,8   - states just before O plays
%          k = 10        - states after X plays last
    
    t0=clock();
    
    K=9;
    S=cell(K+1,1);
    S{1}=S0;
    for k=1:K
        if rem(k,2)==1
            %% player X (minimizer) plays at odd stages
            fprintf('stage %d: X plays',k);
            [newS,won,invalid]=ttt_addX(S{k}); % compute all next states
        else
            %% player O (minimizer) plays at even stages
            fprintf('stage %d: O plays',k);
            [newS,won,invalid]=ttt_addO(S{k}); % compute all next states
        end
        % stack all states in a column vector
        newS=reshape(newS,[],1);            
        won=reshape(won,[],1);
        invalid=reshape(invalid,[],1);
        % store (unique) list of states for which the game continues
        S{k+1}=unique(newS(~invalid & ~won)); 
        fprintf('# of non-terminal states = %5d\n',length(S{k}));
    end
   
    fprintf('done in %f.6 sec\n',etime(clock(),t0));
end
