19
\$\begingroup\$

Write the shortest code that calculates all possible (legal) moves of current player from a given FEN string. What is FEN string? (Wikipedia)

  • Shortest code wins, language doesn't matter.
  • Output moves must obey chess rules of movement except en passant, castling, and pawn promotion.
  • Ignore check, checkmate, and stalemate, king cannot be captured situations too.

You can set outputs differently as you want (for example: A2-A4, A2A4, a2a4, a2->a4...)

Test cases:

# INPUT 1:

rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1
# OUTPUT 1

A2-A4, A2-A3, B2-B4, B2-B3, C2-C4, C2-C3, D2-D4, D2-D3, E2-E4, E2-E3,
F2-F4, F2-F3, G2-G4, G2-G3, H2-H4, H2-H3, B1-A3, B1-C3, G1-F3, G1-H3
# INPUT 2

7k/8/8/8/8/8/PP6/Q1q4K w - - 0 1

# OUTPUT 2

A1-B1, A1-C1, A2-A3, A2-A4, B2-B3, B2-B4, H1-H2, H1-G1, H1-G2
\$\endgroup\$
  • \$\begingroup\$ also here is how test case input boards look like: i.stack.imgur.com/qlbH4.png \$\endgroup\$ – golffzz Mar 7 '13 at 3:39
  • 1
    \$\begingroup\$ possible duplicate of Play a valid chess move, given a board on stdin \$\endgroup\$ – ugoren Mar 7 '13 at 13:56
  • 1
    \$\begingroup\$ @ugoren, I considered that, but enumerating all possible moves potentially eliminates some shortcuts. I'm not sure, though, why en passant isn't required: part of the point of FEN is that it includes enough information to make en passant possible. \$\endgroup\$ – Peter Taylor Mar 7 '13 at 14:09
  • \$\begingroup\$ @PeterTaylor I wrote that just to reduce the work. I wonder why no one interested in this golf :) \$\endgroup\$ – golffzz Mar 8 '13 at 21:12
  • 1
    \$\begingroup\$ @golffzz shouldn't your test case input 2 be 7k/8/8/8/8/8/PP6/Q1q4K w - - 0 1 instead of 6pk/6pp/8/8/8/p7/PP4pp/Q2p2pK w - - 0 1 (which among other things, seems to have pawns on the end ranks)? \$\endgroup\$ – Penguino Sep 9 '14 at 21:38
8
+150
\$\begingroup\$

C - 391 bytes

Takes input as command line arguments and prints to stdout with the squares labeled from 0 to 63.

OK, I had a few minutes so I tried to delete all the bits relating to the detection of check. I think it is now not very efficient though...

O(x,y){return((x&7)-(y&7))/5;}
B[64],*b=B,J=32,M,L,x,*X,N;
main(int c,char**V){
for(;x=*V[1]++;c=J&2**V[2])
x>56?*b++=x:x>47?b+=x-48:0;
for(;b-->B;)
for(M=-1,N=*b%J^16,*V=strchr("bGInFJOQrAHkAGHIqAGHIpGHIx",*b|J);*b&&*b&J^c&&(M=M<0?*++*V%J:-M,**V<96);)
for(x=b-B,L=N?9^*b&8:1+(x/8==1+c/6);L--*!(O(x,x+M)|O(x>>3,x+M>>3));L=!*X|~*X&J^c&&N|(!*X^M&1&&M<0^!c)?printf("%d-%d ",b-B,x),L*!*X:0)
X=B+(x+=M);}

478 byte check-detecting version

O(x,y){return((x&7)-(y&7))/5;}
B[64],*b=B,c,I,J=32;
main(int C,char**V){
int*D,M,L,t,x,*X,N;
for(;b-B<64;C=c=J&2**V[2])
(t=*V[1]++)>56?*b++=t:t>47?b+=t-48:0;
for(D=b;D-->B;)
for(M=-1,N=*D%J^16,*V=strchr("bGInFJOQrAHkAGHIqAGHIpGHIx",*D|J);*D&&*D&J^C&&(M=M<0?*++*V%J:-M,**V<96);)
for(x=D-B,L=N?9^*D&8:1+(x/8==1+C/6);L--*!(O(x,x+M)|O(x>>3,x+M>>3));L=!*X|~*X&J^C&&N|(!*X^M&1&&M<0^!C)?c^C?I|=*X%J==11:(*X=*D,*D=I=0,main(C^J,V+1),*D=*X,I||printf("%d-%d ",D-B,x)),L*!(*X=t):0)
X=B+(x+=M),t=*X;}
\$\endgroup\$
  • \$\begingroup\$ This is amazing, but does not correspond to the question: "Ignore check, checkmate, and stalemate, king cannot be captured situations too." \$\endgroup\$ – edc65 Oct 13 '14 at 14:58
  • \$\begingroup\$ @edc65 I don't agree with your interpretation of these unfortunately incoherent instructions. It says "Output moves must obey chess rules of movement except en passant, castling, and pawn promotion." Moving into check does not appear in the bolded list of rules to ignore. I take the third bullet point as a note that you do not need to detect these situations and reflect them in any way in the output (e.g. the convention of writing '+' after a check). Also, the second test case 2 was correct as originally written, given one ignores pawn promotion as specified (but gives no insight on check). \$\endgroup\$ – feersum Oct 14 '14 at 6:07
  • \$\begingroup\$ The second test case (input) was invalid having a black pawn on rank 8, and different from the image posted as a comment by OP (also here is how test case input boards look like). Given the position in the image, the original test case output was correct according to the rules. \$\endgroup\$ – edc65 Oct 14 '14 at 6:19
  • 2
    \$\begingroup\$ Oh great, the real spec is in the comments? Ugh, what a poor question. \$\endgroup\$ – feersum Oct 14 '14 at 6:41
  • 1
    \$\begingroup\$ The clear winner \$\endgroup\$ – edc65 Oct 16 '14 at 19:39
2
\$\begingroup\$

Java 1455

String q(String f){int[][]b=new int[8][8];int i=0,j=0,k,l,m,n,c;HashSet<String>h=new HashSet<String>();while((c=f.charAt(i))>32){if(c>48&c<57)j+=c-49;if(c==47)j--;if(c>56)b[j%8][j/8]=c;i++;j++;}boolean w=f.charAt(++i)>99;for(i=0;i<8;i++)for(j=0;j<8;j++)if((c=b[i][j])<91?w&c>0:!w){switch(c%32){case 14:for(k=0;k<8;k++){l=(k/4+1)*(k%2*2-1)+i;m=(2-k/4)*(k%4/2*2-1)+j;if(b(l,m)&&(w&b[l][m]%91<40|!w&b[l][m]<91))h.add(h(i,j,l,m));}break;case 11:for(k=0;k<8;k++){l=i+(k==4?1:k/3-1);m=j+(k==4?1:k%3-1);if(b(l,m)&&(w&b[l][m]%91<40|!w&b[l][m]<91))h.add(h(i,j,l,m));}break;case 17:for(k=0;k<8;k++){for(n=1;n<9;n++){l=i+n*(k==4?1:k/3-1);m=j+n*(k==4?1:k%3-1);if(b(l,m)){c=b[l][m];if(w&c%91<40|!w&c<91)h.add(h(i,j,l,m));if(c>0)break;}else break;}}break;case 2:for(k=0;k<4;k++){for(n=1;n<9;n++){l=i+n*(k/2*2-1);m=j+n*(k%2*2-1);if(b(l,m)){c=b[l][m];if(w&c%91<40|!w&c<91)h.add(h(i,j,l,m));if(c>0)break;}else break;}}break;case 18:for(k=0;k<4;k++){for(n=1;n<9;n++){l=i+n*(k/2*(k%2*2-1));m=j+n*((1-k/2)*(k%2*-2+1));if(b(l,m)){c=b[l][m];if(w&c%91<40|!w&c<91)h.add(h(i,j,l,m));if(c>0)break;}else break;}}break;default:m=w?-1:1;if(b[i][j+m]<1){h.add(h(i,j,i,j+m));if(b[i][j+2*m]<1&j==(w?6:1))h.add(h(i,j,i,j+2*m));}for(l=-1;i+l<8&i+l>=0&l<2;l+=2){c=b[i+l][j+m];if(c>0&(c<91?!w:w))h.add(h(i,j,i+l,j+m));}}}return h.toString();}boolean b(int l,int m){return m>=0&m<8&l>=0&l<8;}String h(int i,int j,int l,int m){return""+g(i)+(8-j)+g(l)+(8-m);}char g(int i){return(char)(i+65);}
\$\endgroup\$
2
\$\begingroup\$

Python 553 649 678

b,Q=raw_input(),range;R=Q(8);D="w"in b
for i in Q(9):b=b.replace(`i`,"_"*i)
if D:b=b.swapcase()
def X(h,v,c):
 h+=x;v+=y
 if c and h|v in R and"a">b[v*9+h]:print chr(65+x)+`8-y`+chr(65+h)+`8-v`;return"_"==b[v*9+h]
for y in R:
 for x in R:
  z=y*9+x;p=b[z];N=p=="n";j=[p in"qrk"]*4+[p in"qbk"]*4
  if"p"==p:j[D]=k=(1,-1)[D];X(1,k,b[z+10*k]<"_");X(-1,k,b[z+8*k]<"_")
  for i in Q(1,(2,(y==(1,6)[D])+2,8)["kp".find(p)]):
   for k in R:j[k]=X((0,0,-i,i,-i,i,-i,i)[k],(i,-i,0,0,-i,-i,i,i)[k],j[k])
  for v,h in((2,1),(1,2)):X(v,h,N);X(-v,-h,N);X(-v,h,N);X(v,-h,N)

Two-space indent is tab char, which saves 5 bytes.

It occurs to me that you can likely make it evaluate reasonable moves to a decent ply and keep it under 1024 bytes :) I started looking through other questions, but there doesn't seem to be a codegolf chess engine question...

\$\endgroup\$
  • 2
    \$\begingroup\$ Well done for resurrecting this question! (I think I might put a bounty on it just to see what happens.) Your answer is looking good, but it misses B1C3 and H2H3 in the first example shown in the question. \$\endgroup\$ – squeamish ossifrage Oct 10 '14 at 15:22
  • \$\begingroup\$ Sorry,not H2H3, I meant G1H3 — in other words, your white knights are only turning left. \$\endgroup\$ – squeamish ossifrage Oct 10 '14 at 15:39
  • \$\begingroup\$ It'll have to wait until I am on a pc, but this is an easy bug and I can see lots of ways to shorten it too. Hope there are other entries. \$\endgroup\$ – Will Oct 10 '14 at 20:38
  • \$\begingroup\$ @squeamishossifrage fixed :) \$\endgroup\$ – Will Oct 11 '14 at 7:12
1
\$\begingroup\$

Python 638 637 (482?) bytes

exec"""p=raw_input()
for x in"12345678":p=p.replace(x,"~"*int(x))
b=map(ord,"#"*21+p[:71].replace("/","##")+"#"*21)
d,e=-10,126
if not"w"in p:b,d=[x^32*(64<x<e)for x in b],10
B=[-9,9,-11,11]
R=[-1,1,-d,d]
Q=B+R
c=Zx:chr(96+x%10)+chr(58-x/10)
for x,p in enumerate(b):
 def O(y):
    if 111<b[y]:print c(x)+c(y)
 s=ZL:[O(x+X)for X in L];m=ZL,z=x:L&(O(z+L[0]),m(L,z+L[0])if e==b[z+L[0]]else m(L[1:]))
 if p==80:e==b[x+d]&(O(x+d)or e==b[x+d*2]&35==b[x-d*2]&O(x+d*2)),111<b[x+d-1]<e&O(x+d-1),111<b[x+d+1]<e&O(x+d+1)
 p==75&s(Q),p==78&s([-12,12,-8,8,-21,21,-19,19]),p==82&m(R),p==66&m(B),p==81&m(Q)""".replace("Z","lambda ").replace("&"," and ")

Note: after def O(y): there is a newline and a tab char before if

Note: by using zlib module it's possible to get a valid Python source code of 482 bytes by simply compressing the real source:

#encoding=koi8-r
import zlib
exec zlib.decompress("x°MRKkЦ0>╞~┘Pы Eё╜Е4▌Ц█.9Br*1зБ┤B╠#°■╙=Лoъ╠M⌡│╬г0█\\pcл⌡╝x9╣ЧМф9^:Х╘e:·=м⌠Eй2oЭ╞нЫsQ9─ЩeсS{ЦAR ╕ПЭруюь4жрГыBшОhЖхпy`B▌╬ 58ёt:NхИHшк█╫ЁSK}VBmРПgOyР╢\n+'╬Z║╔▒╣иу√═╢╜-ы#G╙├з▓²Yк=╘л!dуkг≈┴?u$dOФ╘\n▐HфАюВ9]Шж╦╝╦9^┼▄пзИ√ Э│mi╜WeЧa3ъА╗╢бae┘.║WsьdЫ√Ы<ТВэГзьъ
ЙПiB╤≥П-Ъ■⌡<╡▌Б┬1╚3╕лGjщЫЙ(з╧н,>$Eш⌠FыdmШ<x,Р╔Mc;≥м╒2DLc!`Л≥рvЕFCИЪtyв%Н║╞╤≤O╝|'═┤)B|н*┘T╛▐рKпK;╔Я╓АШ&  бУ╗j└;│И╬Ж╝Щ\\4e]P&НРeZ╢5┼ДГt╚У")
\$\endgroup\$
1
\$\begingroup\$

JavaScript (E6) 481 492 550

Edit Fixed a nasty bug in knight moving. A lot of work to keep the byte count the same.

(Not counting leading spaces and newlines kept for readability)

B=f=>
  [for(c of(o=b='',f=f.split(w=' '))[0])b+=-c?w.repeat(c):c<'0'?z=10:c]+
  [...b].map((c,p)=>
    (K=d=>(d=b[p+d])==w?0:d>'a'?m:d>'A'?-m:9)(0)-1||(
      t='pPkKnNrRQqBb'.search(c),
      O=d=>K(d)<1?o+=w+P(p)+P(p+d):0,
      S=(d,s=0)=>O(d*++s)&&!K(d*s)&&S(d,s),
      //o+='\n'+P(p)+' '+c, // Uncomment to display pieces list
      t<2?[for(i of[~(s=t<1?z:-z),1-s])~K(i)||O(i)]+!K(s)&&O(s)&&(p/z|0)==t*5+1&!K(s+=s)&&O(s)
      :t<6?[for(i of t<4?[1,9,z,11]:[12,8,21,19])O(i)+O(-i)]
      :[for(i of[t>7&&9,t>7&&11,t<z,t<z&&z])S(i)+S(-i)]
    )
  ,m=f[1]<'w'?1:-1,
  //console.log(','+([...b]+',').replace(/1,0/g,'\n')), // Uncomment to display chessboard
  P=p=>'ABCDEFGH'[p%z]+(9+~p/z|0))&&o

Less Golfed

B=f=>(
  o=b='',[for(c of f)b+=-c?'.'.repeat(c):c],
  m=(w=b[72]=='w')?1:2,n=3-m,
  t=0,
  P=p=>'ABCDEFGH'[p%9]+(9+~p/9|0),
  b=b.slice(0,71),
  // console.log(b.replace(/\//g,'\n')), // Uncomment to display chessboard

  [...b].map((c,p)=>{
    r=p/9|0
    K=k=>(k=b[k])=='.'?0:k>'a'?m:k>'A'?n:9
    J=d=>K(p+d)<2,
    O=d=>J(d)?o+=' '+P(p)+P(p+d):0,
    S=(s,d)=>O(d*++s)&&!K(p+d*s)?S(s,d):0;

    if(K(p)==2){
      // o+='\n'+P(p)+ ' '+c; // Uncomment to display pieces list
      if (c=='P')
      {
        (f=!K(p-9))&&O(-9),
        f&r==6&&!K(p-18)&&O(-18),
        [for(i of[10,8])K(p-i)==1&&O(-i)]
      }
      else if (c=='p')
      {
        (f=!K(p+9))&&O(+9),
        f&r==1&&!K(p+18)&&O(+18),
        [for(i of[10,8])K(p+i)==1&&O(+i)]
      }
      else if (c=='K' |c=='k')
        [for(i of[1,8,9,10])O(i)+O(-i)]
      else if (c=='N' | c=='n')
        [for(i of[11,7,19,17])O(i)+O(-i)]
      else 
      {
        if (c!='r' & c!='R')
          [for(i of[10,8])S(0,i)+S(0,-i)]
        if (c!='b' & c!='B')
          [for(i of[9,1])S(0,i)+S(0,-i)]
      }
    }     
  }),
  o
)

Test in FireFox/FireBug console

B("7k/8/8/8/8/1P6/P7/Q1q4K w - - 0 1")

Output

B3B4 A2A3 A2A4 A1B2 A1C3 A1D4 A1E5 A1F6 A1G7 A1H8 A1B1 A1C1 H1G1 H1H2 H1G2
\$\endgroup\$
1
\$\begingroup\$

JAVA 631 599 594

Fixed a bug in the 599-bytes version (thank you Jack for pointing this out!) and shortened the code to 594-bytes.

class F{
public static void main(String[]A){int p=0,i=8,u,v,d,z[]={0,1,-1,2,1,0,1};String f=A[0],S[]="p,n,rqk,bqk,aA,PNBRQK,aAPNBRQK".split(",");
for(;i>0;)f=f.replace(""+i,"a"+(--i==0?"":i));
for(;p<448;p++)
for(int k=p%7,w=A[1].equals("w")?32:0,c=f.charAt(p/7%8+p/56*9),a=z[k],b=k==4?2:1,q=0;S[(k/2-1|k-1)/2].indexOf(c+w)>=0&&q++<(k<3?1:4);i=a,a=b,b=-i){
for(i=1,d=97;d==97&&((u=p/7%8+i*a)|(v=p/56+i*b*(1-w/16)))>=0&&(u|v)<8&&i<(k>4?(c=='K'||c=='k')?2:9:(k<1&&p/56==w/6+1?3:2))&&S[61/(61^(k*k-2))+5].indexOf((d=f.charAt(u+9*v))-w)>=0;i++)System.out.printf("%c%d%c%d ",65+p/7%8,8-p/56,65+u,8-v);}}}

Compile: javac F.java
Run: java F 6pk/6pp/8/8/8/p7/PP4pp/Q2p2pK w - - 0 1
Output: B2B3 B2B4 B2A3 A1B1 A1C1 A1D1 H1H2 H1G1 H1G2

\$\endgroup\$
  • \$\begingroup\$ For 3Q4/p4r1k/P4pp1/4P3/5n2/3P4/4BbbP/RN3KN1 w - - 0 0 I'm not seeing moves F1F2 or F1G2 is the king able to capture? \$\endgroup\$ – Jack Feb 3 '17 at 18:07
  • \$\begingroup\$ Thank you for pointing this out. You are right. This published version is over optimized :( \$\endgroup\$ – Bob Genom Feb 24 '17 at 11:47
  • \$\begingroup\$ So I have to fall back to my 631 byte long solution. \$\endgroup\$ – Bob Genom Feb 24 '17 at 12:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.