function [pList state] = PossibleMoves(B,noCheck)
% generates a list of all possible moves given the board object, B
%
% m used throughout as a temporary storage variable for different functions
%
% The noCheck input is used to indicate that we wish to ignore move
% restrictions associated with check, typically done for speed. If noCheck
% equals 1, state will always be returned as 'play'.
%
% movement data: [r0 c0 r1 c0 flag]
% flag can take the following values:
% >0: indicates a promotion (supercedes all other flags)
% 0: move to an empty square
% -1: en passant
% -2: castle
% -3: indicates a piece is protecting itself
% -4: a capture
%
% %%% code for ChessPiece, v1.1 2012, ZCD %%%
%
%% movement and effect types initialization
% track different move types
pMoves = zeros(200,5); % moves
pMi = 1; % counters
pCaptures = zeros(200,5); % captures
pCi = 1;
pImmobile = zeros(50,3); % immobilized pieces
pIi = 1;
pProtect = zeros(50,3); % protected pieces
pPi = 1;
if nargin==1
noCheck = 0;
end
%% obtain all possible moves w/o regard for checks
% a matrix of all colour values for the current board configuration
cmap1 = reshape([B.top.colour],size(B.top));
% only check possible moves starting from squares occupied by pieces
[ixRow ixCol] = find(cmap1<0 | cmap1>0);
% loop to check all pieces for their possible moves
for ii=1:length(ixRow)
% only cycle through squares with pieces on them:
i=ixRow(ii);
j=ixCol(ii);
% only check this piece if its owner has moving rights
if B.top(i,j).colour==B.info.turn
% proceed to check all effects of this piece on legal moves
if iscell(B.top(i,j).move)
for k=1:length(B.top(i,j).move)
% get the available squares for this piece
m = B.top(i,j).move{k}([i j],B);
% add those squares to pMoves
if ~isempty(m)
% put in the squares
inputSize = size(m,1);
pMoves(pMi:pMi+inputSize-1,:) = [repmat([i j],[inputSize 1]) m];
pMi = pMi + inputSize; % increment the counter
end
end
end
if iscell(B.top(i,j).capture)
for k=1:length(B.top(i,j).capture)
m = B.top(i,j).capture{k}([i j],B);
if ~isempty(m)
inputSize = size(m,1);
pCaptures(pCi:pCi+inputSize-1,:) = [repmat([i j],[inputSize 1]) m];
pCi = pCi + inputSize; % increment the counter
end
end
end
if iscell(B.top(i,j).init)
for k=1:length(B.top(i,j).init)
m = B.top(i,j).init{k}([i j],B);
if ~isempty(m)
% mark en passant with -1 in the flag column
if strcmp(B.top(i,j).type,'guard')
% hack - for each move, if it can be done regularly
% without the initial move, do not mark it,
% otherwise mark it
for ip=1:size(m,1)
if ~any(all(pMoves(:,3:4)==repmat(m(ip,1:2),[size(pMoves,1) 1]),2))
m(ip,end)=-1;
end
end
end
inputSize = size(m,1);
pMoves(pMi:pMi+inputSize-1,:) = [repmat([i j],[inputSize 1]) m];
pMi = pMi + inputSize; % increment the counter
end
end
end
if B.top(i,j).castle==1 && B.top(i,j).royal==1
% check for legality of castling
% locations of royal and major casteling pieces on the to-move
% side
yR=i; xR=j;
ixM = find([B.top.castle]==1 & [B.top.royal]==0 & [B.top.colour]==B.info.turn);
[yM xM] = ind2sub(size(B.top),ixM);
% once for each combination of royal piece and major piece
% with castle rights
for im = 1:length(ixM)
% castle rules:
% 1) royal and major are on the same rank
% 2) there are no pieces between the royal and major
% 3) the royal does not land on a piece after a castle
% 4) check restrictions (enforced in the check loop)
canCastle = 1;
% rule 1
if yM(im)~=i
canCastle = 0;
end
% rule 3
if xM(im)<xR
cf=xM(im)+1:xR-1; % squares that must have no pieces
adj=-2;
else
cf=xR+1:xM(im)-1;
adj=2;
end
if ~( strcmp(B.top(i,j+adj).type,'empty') || all([i j+adj]==[yM(im) xM(im)]) )
% if the landing square is empty OR the landing square
% is occupied by the castling major piece, allow castling
canCastle = 0;
end
% rule 2
if all(strcmp({B.top(yR,cf).type},'empty')) && canCastle
pMoves(pMi,:) = [yR xR yM(im) xM(im) -2];
pMi = pMi+1;
end
end
end
end
% special features require checking all pieces, not just the side to move
if ~isempty(B.top(i,j).name)
% check for immobilized squares
if iscell(B.top(i,j).immobile)
% note the squares that are frozen
for k=1:length(B.top(i,j).immobile)
m = B.top(i,j).immobile{k}([i j],B);
if ~isempty(m)
inputSize = size(m,1);
pImmobile(pIi:pIi+inputSize-1,:) = m;
pIi = pIi + inputSize; % increment the counter
end
end
end
% check for protected squares
if iscell(B.top(i,j).protect)
% note the squares that are protected
for k=1:length(B.top(i,j).protect)
m = B.top(i,j).protect{k}([i j],B);
if ~isempty(m)
inputSize = size(m,1);
pProtect(pPi:pPi+inputSize-1,:) = m;
pPi = pPi + inputSize; % increment the counter
end
end
end
end
end % end squares loop
% get rid of all excess zeros from moves
pMoves(pMi:end,:)=[];
pCaptures(pCi:end,:)=[];
pImmobile(pIi:end,:)=[];
pProtect(pPi:end,:)=[];
% === combine captures and moves ===
% format: [x0 y0 x1 y1 pflag; ...]
pList = unique([pMoves; pCaptures],'rows');
% = Examine special cases (pieces with protection or immobilization) =
% Pieces moving FROM immobile squares is illegal
ix = zeros(size(pList,1),1);
for i2=1:size(pImmobile,1)
% mark each time we find an immobilized square
ix = ix + all(repmat(pImmobile(i2,1:2),[size(pList,1) 1])==pList(:,1:2),2);
end
% eliminate these moves as possibilities
pList(ix>0,:) = [];
% Pieces moving TO protected squares is illegal (unless its a castle)
ix = zeros(size(pList,1),1);
for i2=1:size(pProtect,1)
% if the square being protected is itself a piece with protection
% capability (and the piece isn't protecting itself) do not allow it
%if isnan(B.top(pProtect(i2,1),pProtect(i2,1)).protect)
% mark each time we find a protected square
ix = ix + all(repmat(pProtect(i2,1:2),[size(pList,1) 1])==pList(:,3:4),2) & pList(:,end)~=-2;
%end
end
% eliminate these moves as possibilities
pList(ix>0,:) = [];
%% introduce legality of checks
if ~noCheck
% check all psuedo moves for check
ix = ones(1,size(pList,1));
for pm=1:size(pList,1)
% make the ith pseudomove
pseudoB = MakeMove(pList(pm,1:2),pList(pm,3:4),B,pList(pm,5));
% if this is a castling move
if pList(pm,5)==-2
% note which squares must not be "in check" for castle to be
% permitted
if pList(pm,2)<pList(pm,4), cf2=1; else cf2=-1; end
% original square k was on and square the king passed through (and
% square where k landed, but he is already there now in pseudoB)
ixC = [pList(pm,1:2) pList(pm,3) pList(pm,2)+cf2];
pseudoB.top(ixC(1),ixC(2)) = NewPiece('king',-pseudoB.info.turn);
pseudoB.top(ixC(3),ixC(4)) = NewPiece('king',-pseudoB.info.turn);
end
% rebuild immobilizing squares after pseudomove
[imobRow imobCol] = ind2sub(size(pseudoB.top),find(cellfun(@iscell,{pseudoB.top.immobile})));
ixI = zeros(1,3);
for ii=1:length(imobRow)
i=imobRow(ii); j=imobCol(ii);
% note the squares that are frozen
for k=1:length(pseudoB.top(i,j).immobile)
ixI = [ixI; pseudoB.top(i,j).immobile{k}([i j],pseudoB)];
end
end
% rebuild protected squares after pseudomove
[protRow protCol] = ind2sub(size(pseudoB.top),find(cellfun(@iscell,{pseudoB.top.protect})));
ixP = zeros(1,3);
for ii=1:length(protRow)
i=protRow(ii); j=protCol(ii);
% note the protected squares
for k=1:length(pseudoB.top(i,j).protect)
ixP = [ixP; pseudoB.top(i,j).protect{k}([i j],pseudoB)];
end
end
% get the royal piece positions of the previously moving side
[x y] = ind2sub(size(pseudoB.top),find([pseudoB.top.royal] & ...
[pseudoB.top.colour]==-pseudoB.info.turn));
rlocs = [x' y'];
% remove all protected squares because capture is not allowed
ixr = zeros(size(rlocs,1),1);
for i2=1:size(ixP,1)
% mark each time we find a protected square
ixr = ixr + all(repmat(ixP(i2,1:2),[size(rlocs,1) 1])==rlocs,2);
end
rlocs(ixr>0,:) = [];
% only check possible moves starting from squares occupied by pieces
cmap2 = reshape([pseudoB.top.colour],size(B.top));
[ixRow2 ixCol2] = find(cmap2<0 | cmap2>0);
for ii=1:length(ixRow2)
% only cycle through squares with pieces on them:
i=ixRow2(ii);
j=ixCol2(ii);
% check all capture possibilities on the royal squares
if pseudoB.top(i,j).colour==pseudoB.info.turn && ~any(all(repmat([i j],[size(ixI,1) 1])==ixI(:,1:2),2))
mi=1;
chCaps = zeros(100,3);
if iscell(pseudoB.top(i,j).capture) % non-capturing pieces exist
for k = 1:length(pseudoB.top(i,j).capture)
m = pseudoB.top(i,j).capture{k}([i j],pseudoB);
if ~isempty(m)
inputSize = size(m,1);
chCaps(mi:mi+inputSize-1,:) = m;
mi = mi+inputSize;
end
end
end
% lets also check initial move possibilities (which could be
% royal captures)
if iscell(pseudoB.top(i,j).init)
for k = 1:length(pseudoB.top(i,j).init)
m = pseudoB.top(i,j).init{k}([i j],pseudoB);
if ~isempty(m)
inputSize = size(m,1);
chCaps(mi:mi+inputSize-1,:) = m;
mi = mi+inputSize;
end
end
end
% if a capture is possible...
if mi>1
chCaps(mi:end,:)=[];
for k=1:size(rlocs,1)
if any(all(chCaps(:,1:2)==repmat(rlocs(k,:),[size(chCaps,1) 1]),2))
% note moves that result in check
ix(pm) = 0;
break;
end
end
end
end
if ix(pm)==0; break; end % no need to look farther at this move
end % end loop for this move
end
% === remove the all ix (illegal due to check) moves ===
pList = pList(ix==1,:);
%% check victory conditions
% draw by repitition?
if B.info.draw50>5
% check if there are 3 position repeats
numReps = sum(all(strcmp(repmat(B.info.hist(end,:),[size(B.info.hist,1) 1]),B.info.hist),2));
if numReps == 3
state = '1/2-1/2, draw by repitition';
return;
end
end
% 50 moves draw?
if B.info.draw50==100
state = '1/2-1/2, draw by 50 moves';
return;
end
% check for checkmate and stalemate when there are no legal moves
if isempty(pList)
% get the royal piece positions of the previously moving side
[x y] = ind2sub(size(B.top),find([B.top.royal] & ...
[B.top.colour]==B.info.turn));
rlocs = [x' y']; % and remove all protected squares because capture is not allowed
% remove all protected squares because capture is not allowed
ixr = zeros(size(rlocs,1),1);
for i2=1:size(pProtect,1)
% mark each time we find a protected square
ixr = ixr + all(repmat(pProtect(i2,1:2),[size(rlocs,1) 1])==rlocs,2);
end
rlocs(ixr>0,:) = [];
% make sure we aren't referencing empty arrays
if isempty(pImmobile), pImmobile=zeros(1,3); end
% assume stalemate unless check is found
mflag = 0;
for i=1:size(B.top,1)
for j=1:size(B.top,2)
% look at pieces that are to move next AND that are not immobile
if B.top(i,j).colour==-B.info.turn && ...
~any(all(repmat([i j],[size(pImmobile,1) 1])==pImmobile(:,1:2),2))
% get captures for this pieces
m = [];
for k = 1:length(B.top(i,j).capture)
if iscell(B.top(i,j).capture) % non-capturing pieces exist
m = [m; B.top(i,j).capture{k}([i j],B)];
end
end
for k = 1:length(B.top(i,j).init) % in case a piece makes an initial capture on the royal piece
if iscell(B.top(i,j).init)
m = [m; B.top(i,j).init{k}([i j],B)];
end
end
% if this piece can make captures (not empty) test to see if
% any are royal captures
if ~isempty(m)
for ii=1:size(rlocs,1)
for jj=1:size(m,1)
if all(rlocs(ii,:)==m(jj,1:2))
% this is a checkmate condition, stop searching
mflag = 1;
end
end
end
end
end
if mflag; break; end
end
if mflag; break; end
end
% final game outcome
if mflag
if B.info.turn==1
state = '0-1, White checkmated';
else
state = '1-0, Black checkmated';
end
else
state = '1/2-1/2, Stalemate';
end
else
state = 'play';
end
else
% when checks are not considered
% check to see if royal pieces are on the board
state = 'play';
% if there are no royal pieces on the board for this side, consider it
% a null (this is useful for computer evaluations, because the
% computer may capture royal pieces during move consideration)
[x y] = ind2sub(size(B.top),find([B.top.royal] & ...
[B.top.colour]==B.info.turn));
rlocs = [x' y'];
if isempty(rlocs)
state = '0-0, No royals';
pList = zeros(0,5);
end
end
