function v = tttOptimal
%solve tic-tac-toe for optimal players

v = zeros(3,3,3,3,3,3,3,3,3); %indices: 1 for blank, 2 for X, 3 for O; entries: 1 for X win, -1 for O win, 0 for tie
win = [1 2 3;4 5 6;7 8 9;1 4 7;2 5 8;3 6 9;1 5 9;3 5 7]; %all winning combinations

for ply=9:-1:0 %moves taken: work inductively backward
    xmoves=ceil(ply/2); %moves taken by X
    omoves=floor(ply/2); %moves taken by O
    for a=1:3, for b=1:3, for c=1:3, for d=1:3, for e=1:3, for f=1:3, for g=1:3, for h=1:3, for i=1:3 %loop through all states
        s = [a b c d e f g h i]; %vector representation of state
        if sum(s==2)==xmoves && sum(s==3)==omoves %only consider states with appropriate numbers of moves
            if xmoves==omoves %X's turn
                v(a,b,c,d,e,f,g,h,i) = -1;
                if max(sum(s(win)==3,2)) < 3 %O hasn't won; otherwise leave v = -1 and move on
                    for x=1:9 %loop possible moves for X
                        if s(x)==1 %this square open
                            snew = s; snew(x) = 2; %new state from X moving at x
                            vnew = v(snew*(3.^(0:8))'-9840); %value of new state (using vector unrolling of v)
                            v(a,b,c,d,e,f,g,h,i) = max(v(a,b,c,d,e,f,g,h,i),vnew); %value of current state is max over possible next states
                        end
                    end
                end
            elseif ply==9 %board is full
                if max(sum(s(win)==2,2))==3 %X won
                    v(a,b,c,d,e,f,g,h,i) = 1;
                elseif max(sum(s(win)==3,2))==3 %O won
                    v(a,b,c,d,e,f,g,h,i) = -1;
                else %tie
                    v(a,b,c,d,e,f,g,h,i) = 0;
                end
            else %O's turn
                v(a,b,c,d,e,f,g,h,i) = 1;
                if max(sum(s(win)==2,2)) < 3 %X hasn't won; otherwise leave v = 1 and move on
                    for o=1:9 %loop possible moves for O
                        if s(o)==1 %this square open
                            snew = s; snew(o) = 3; %new state from O moving at o
                            vnew = v(snew*(3.^(0:8))'-9840); %value of new state (using vector unrolling of v)
                            v(a,b,c,d,e,f,g,h,i) = min(v(a,b,c,d,e,f,g,h,i),vnew); %value of current state is min over possible next states
                        end
                    end
                end
            end
        end
    end,end,end,end,end,end,end,end,end
end