function playconnectfour
%% performs a game of connect four (or a more general connect game)
%%
%% nrow= number of rows in the game board
%% ncol= number of columns in the game board
%% cnum= number of items needed to connect to win (cnum=4 for connect four)
%%
%% a game state is represented as an nrow by ncol matrix.  player 1's game
%%    pieces are 1s in the board, and player -1's game pieces are -1s in
%%    the game board.  an empty space is represented by a 0.
%%
nrow= 6;   % number of rows of the game board
ncol=7;    % number of colums of the game board
cnum=4;     % number in a row that wins the game (cnum=4 for connect four)

ptime=.1;  % number of seconds to pause after every move

gamestate=zeros(nrow,ncol); % instantiate the gamestate to an empty board
close all; figure; hold on;  % close all figures, create a new figure
displaygame(gamestate);  % plot current game state

while gameover(gamestate,cnum)==0   % someone has not yet won
    p1move= randomplayer(gamestate,1);  % playerone makes one move
    %p1move= blockplayer(gamestate,1,cnum);  % playerone makes one move
    if ~moveislegal(gamestate,p1move)  %then playerone made illegal move
        warning('Player One made an illegal move!');
    end
    gamestate=p1move; %update the game state with the new move
    displaygame(gamestate);  % plot the new game state
    winhappened=gameover(gamestate,cnum); % check if player1 wins
    if winhappened==1
        fprintf('Player One (Red) Wins!\r');
        title('Player One (Red) Wins!');
    else %player 1 did not win, so player 2 now moves
        pause(ptime);
        %p2move= randomplayer(gamestate,-1);  % playertwo makes one move
        p2move= blockplayer(gamestate,-1,cnum);  % playertwo makes one move
        if ~moveislegal(gamestate,p2move)  %then plyrtwo made illegal move
            warning('Player Two made an illegal move!');
        end
        gamestate=p2move;
        displaygame(gamestate);  % plot the new game state
        pause(ptime);
        
        winhappened=gameover(gamestate,cnum); % check if player2 wins
        if winhappened==1
            fprintf('Player Two (Blue) Wins!\r');
            title('Player Two (Blue) Wins!');
        end
    end
    
end

%if the above while loop exits then it is possible no one wins
winhappened=gameover(gamestate,cnum); % check if no one wins
if winhappened==2
    fprintf('Tie!  No One Wins!\r');
    title('Tie!  No One Wins!');
end



end

function out=legalmoves(gamestate)
%% outputs an nrow by ncol matrix with 1's in current locations for legal
%% moves, and 0's in other locations

tokens=abs(gamestate);  % game state
up1shift= tokens(2:end,:);  % delete top row of tokens
up1shift(end+1,:)=1;  % make the last row of up1shift equal to 1

out = (up1shift ~= tokens);
end

function out=moveislegal(prevgamestate,nextgamestate)
%% checks if a legal move has been made, starting with prevgamestate,
%%  and ending with nextgamestate
%%
%% out=1 if the move is legal, and out=0 otherwise.

newplace= (prevgamestate~= nextgamestate); %location of new move(s)
numprev=sum(prevgamestate~=0); %number of previous game tokens
numcur=sum(nextgamestate~=0); %number of current game tokens
if numcur-numprev~=1 % then a single move was not made
    out=0;
elseif abs(nextgamestate(newplace))~=1  % not (1 or -1) was used as a move
    out=0;
else  % then a legal move was made
    out=1;
end

end

function out=gameover(gamestate,cnum)
%% checks if the current gamestate has a winning player or not
%%   also check if the game has ended in a draw
%%
%% out=1 if there is a winner
%% out=2 if a draw as occurred
%% out=0 otherwise
%%
%% winloc = location of the winning move

% by default, out=0,
out=0;

%%%% first, check if a horizonal connect made a win
tempgamestate=gamestate;
rshift=tempgamestate;
for i=1:cnum-1  % sum up cnum horizontal shifts of the game state to left
    tempgamestate=matshift(tempgamestate,'le');
    rshift=rshift+tempgamestate;
end
if  sum(sum(rshift==cnum))>=1  % then player 1 wins
    out=1;
    winloc=find(rshift==cnum); winloc=winloc(1);  % pick first win location
    plotwin(gamestate,winloc,'le',cnum);   % plot the winning move
end
if  sum(sum(rshift==-cnum))>=1  % then player 2 wins
    out=1;
    winloc=find(rshift==-cnum); winloc=winloc(1); % pick first win location
    plotwin(gamestate,winloc,'le',cnum);   % plot the winning move
end

%%%% next, check if a vertical connect made a win
tempgamestate=gamestate;
ushift=tempgamestate;
for i=1:cnum-1 % sum up cnum vertical shifts of the game state upwards
    tempgamestate=matshift(tempgamestate,'up');
    ushift=ushift+tempgamestate;
end
if  sum(sum(ushift==cnum))>=1  % then player 1 wins
    out=1;
    winloc=find(ushift==cnum);  winloc=winloc(1);  % could be > 1 win
    plotwin(gamestate,winloc,'up',cnum);   % plot the winning move
end
if  sum(sum(ushift==-cnum))>=1  % then player 2 wins
    out=1;
    winloc=find(ushift==-cnum);  winloc=winloc(1);  % could be > 1 win
    plotwin(gamestate,winloc,'up',cnum);   % plot the winning move
end

%%%% check if a right diagonal connect made a win
tempgamestate=gamestate;
u1shift=tempgamestate;
for i=1:cnum-1  % sum up cnum diagonal right shifts of the game state
    tempgamestate=matshift(tempgamestate,'up');
    tempgamestate=matshift(tempgamestate,'ri');
    u1shift=u1shift+tempgamestate;
end
if  sum(sum(u1shift==cnum))>=1  % then player 1 wins
    out=1;
    winloc=find(u1shift==cnum); winloc=winloc(1);  % could be > 1 win
    plotwin(gamestate,winloc,'dr',cnum);   % plot the winning move
end
if  sum(sum(u1shift==-cnum))>=1  % then player 2 wins
    out=1;
    winloc=find(u1shift==-cnum); winloc=winloc(1);  % could be > 1 win
    plotwin(gamestate,winloc,'dr',cnum);   % plot the winning move
end

%%%% finally, check if a leftdiagonal connect made a win
tempgamestate=gamestate;
u1shift=tempgamestate;
for i=1:cnum-1  % sum up cnum diagonal left shifts of the game state
    tempgamestate=matshift(tempgamestate,'up');
    tempgamestate=matshift(tempgamestate,'le');
    u1shift=u1shift+tempgamestate;
end
if  sum(sum(u1shift==cnum))>=1  % then player 1 wins
    out=1;
    winloc=find(u1shift==cnum); winloc=winloc(1);  % could be > 1 win
    plotwin(gamestate,winloc,'dl',cnum);   % plot the winning move
end
if  sum(sum(u1shift==-cnum))>=1  % then player 2 wins
    out=1;
    winloc=find(u1shift==-cnum); winloc=winloc(1);  % could be > 1 win
    plotwin(gamestate,winloc,'dl',cnum);   % plot the winning move
end

%%%% one final check: if no one has won, and the game board is full
%%%%    then declare a draw
if sum(sum(gamestate==0))==0  && out==0
    out=2;  %declare a draw has occurred
end

end

function out=matshift(inmat,direction)
%% shifts the matrix inmat by one in the given direction, by zero padding
%% direction='le' denotes the matrix is shifted to the left
%% direction='ri' denotes the matrix is shifted to the right
%% direction='up' denotes the matrix is shifted upwards

[nrow,ncol]=size(inmat);
if direction=='le'  % shift left
    out=[inmat,zeros(nrow,1)];  % add a column of zeros on right
    out= out(:,2:end);  % delete left column
elseif direction=='ri'  % shift right
    out=[zeros(nrow,1),inmat];  % add a column of zeros on left
    out= out(:,1:end-1);  % delete right column
elseif direction=='up'  %shift up
    out=[inmat; zeros(1,ncol)];  % add a column of zeros on bottom
    out= out(2:end,:);  % delete top row
end

end

function outstate=randomplayer(instate,pm1)
%% performs a random move among all available moves
%%
%% instate is the current game state, and outstate is the new game state
%% after one person makes a move
%%
%% pm1=1 if the program moves as player 1
%% pm1=-1 if the program moves as player -1

moveplaces=legalmoves(instate);  % places to move your piece
nummoves=sum(sum(moveplaces));   % number of possible moves to make
if nummoves==0  % then no move can be made
    outstate=instate;
else  % then at least one move can be made
    moveindices= find(moveplaces);  % array indices for legal moves
    randommove= ceil(nummoves*rand);  % make a random move
    randmoveindex=moveindices(randommove); %vector index of the chosen move
    instate(randmoveindex)=pm1;  % change the game state according to pm1
    outstate=instate; %the move has been made, so output the new game state
end

end

function displaygame(gamestate)
%% make a plot of the current gamestate
[nrow,ncol]=size(gamestate);
xvals=ones(nrow,1)*(1:ncol);  % x-values to plot
yvals=(nrow:-1:1)'*ones(1,ncol);  % y-values to plot

player1tokens= (gamestate==1);   % positions of player 1's game tokens
player2tokens= (gamestate==-1);  % positions of player -1's game tokens
plot(xvals(player1tokens),yvals(player1tokens),'r.','MarkerSize',60); %red
plot(xvals(player2tokens),yvals(player2tokens),'b.','MarkerSize',60); %blue
axis([1/2,ncol+1/2,1/2,nrow+1/2]);
end

function plotwin(gamestate,winloc,direction,cnum)
%% the input gamestate has displayed a winning game position
%% this function plots the winning connection of game tokens
%% gamestate = the current (winning) game state
%% winloc= the "starting" location of the winning connection of tokens
%% direction= the direction of the winning connection of tokens
%%    'le' denotes a horizontal win, 'up' denotes a vertical win
%%    'dr' denotes a diagonal right win,  'dl' denotes a diagonal left win,

[nrow,ncol]=size(gamestate);
xvals=ones(nrow,1)*(1:ncol); % x-values to plot
yvals=(nrow:-1:1)'*ones(1,ncol); % y-values to plot
if direction=='le'  % horizontal win occurred
    xstart=xvals(winloc);  % starting x-value of the horizontal win
    ystart=yvals(winloc);  % starting y-value of the horizontal win
    plot(xstart:1:xstart+cnum-1,ystart*ones(1,cnum),'k');
elseif direction=='up'  % vertical win occurred
    xstart=xvals(winloc); % starting x-value of the vertical win
    ystart=yvals(winloc); % starting y-value of the vertical win
    plot(xstart*ones(1,cnum),ystart:-1:ystart-cnum+1,'k');
elseif direction=='dl'  %diagonal left win occurred
    xstart=xvals(winloc); % starting x-value
    ystart=yvals(winloc); % starting y-value
    plot(xstart:1:xstart+cnum-1,ystart:-1:ystart-cnum+1,'k');
elseif direction=='dr'  %diagonal right win occurred
    xstart=xvals(winloc); % starting x-value 
    ystart=yvals(winloc); % starting y-value 
    plot(xstart:-1:xstart-cnum+1,ystart:-1:ystart-cnum+1,'k');
end

end



function outstate=blockplayer(gamestate,pm1,cnum)
%% chooses a game move among all avilable moves that blocks the best
%%   connection of the opponent, if possible.
%%
%% instate is the current game state, and outstate is the new game state
%% after one person makes a move
%%
%% pm1=1 if the program moves as player 1
%% pm1=-1 if the program moves as player -1


moveplaces=legalmoves(gamestate);  % places to move your piece
nummoves=sum(sum(moveplaces));   % number of possible moves to make
if nummoves==0  % then no move can be made
    outstate=gamestate;
else  % then at least one move can be made
    moveindices= find(moveplaces);  % array indices for legal moves
    
    j=cnum-1; % first, look for opponent's connection of length j=cnum-1
              % continue decreasing j until the longest connection is
              % found.  if no length 2 connect is found, just move randomly
    blockmove=[];
    while j>1 && isempty(blockmove)
        %%%% first, check for length of horizontal connections
        tempgamestate=gamestate;
        lshift=tempgamestate;
        for i=1:j  % sum up j horizontal shifts of the game state to left
            tempgamestate=matshift(tempgamestate,'le');
            lshift=lshift+tempgamestate;
        end

        if  sum(sum(lshift(moveindices)==-j*pm1))>=1  % then have length j conn 
            blockmove=find(lshift(moveindices)==-j*pm1);
            blockmove=blockmove(1);  % pick first blocking move index
        end
        
        tempgamestate=gamestate;
        rshift=tempgamestate;
        for i=1:j  % sum up j horizontal shifts of the game state to right
            tempgamestate=matshift(tempgamestate,'ri');
            rshift=rshift+tempgamestate;
        end

        if  sum(sum(rshift(moveindices)==-j*pm1))>=1  % have length j conn 
            blockmove=find(rshift(moveindices)==-j*pm1);
            blockmove=blockmove(1);  % pick first blocking move index
        end

        %%%% next, check for length of vertical connections
        tempgamestate=gamestate;
        ushift=tempgamestate;
        for i=1:j  % sum up j horizontal shifts of the game state to left
            tempgamestate=matshift(tempgamestate,'up');
            ushift=ushift+tempgamestate;
        end
        if  sum(sum(ushift(moveindices)==-j*pm1))>=1  % then have length j conn
            blockmove=find(ushift(moveindices)==-j*pm1);
            blockmove=blockmove(1);  % pick first blocking move index
        end
        
        
        %%%% next, check for diagonal right connections of length j
        tempgamestate=gamestate;
        u1shift=tempgamestate;
        for i=1:j  % sum up j horizontal shifts of the game state to left
            tempgamestate=matshift(tempgamestate,'up');
            tempgamestate=matshift(tempgamestate,'ri');
            u1shift=u1shift+tempgamestate;
        end
        if  sum(sum(u1shift(moveindices)==-j*pm1))>=1  % then have length j conn
            blockmove=find(u1shift(moveindices)==-j*pm1);
            blockmove=blockmove(1);  % pick first blocking move index
        end
        
         %%%% finally, check for diagonal left connections of length j
        tempgamestate=gamestate;
        u2shift=tempgamestate;
        for i=1:j  % sum up j horizontal shifts of the game state to left
            tempgamestate=matshift(tempgamestate,'up');
            tempgamestate=matshift(tempgamestate,'le');
            u2shift=u2shift+tempgamestate;
        end
        if  sum(sum(u2shift(moveindices)==-j*pm1))>=1  % then have length j conn
            blockmove=find(u2shift(moveindices)==-j*pm1);
            blockmove=blockmove(1);  % pick first blocking move index
        end
        
        %decrease j by one
        j=j-1;  
    end
    
    %% if j>1, then we found a good blocking move.
    %% if j=1, then we found no good blocking moves.  so just move randomly
    if j>1
        gamestate(moveindices(blockmove))=pm1;
        outstate=gamestate;
    else %j=1
        randommove= ceil(nummoves*rand);  % make a random move
        randmoveindex=moveindices(randommove); %vector index of the chosen move
        gamestate(randmoveindex)=pm1;  % change the game state according to pm1
        outstate=gamestate; %the move has been made, so output the new game state
    end
    
end

end