Szachy - Znajdź wszystkie legalne ruchy (oprócz roszady i en passant)

19

Napisz najkrótszy kod, który oblicza wszystkie możliwe (legalne) ruchy bieżącego gracza z danego ciągu FEN. Co to jest łańcuch FEN? (Wikipedia)

  • Najkrótszy kod wygrywa, język nie ma znaczenia.
  • Ruchy wyjściowe muszą być zgodne z regułami ruchu szachowego, z wyjątkiem promocji en passant , castling i pionków.
  • Zignoruj ​​czek, mat i impas, króla nie można też schwytać.

Można ustawić wyjść inaczej, jak chcesz (na przykład: A2-A4, A2A4, a2a4, a2->a4...)

Przypadki testowe:

# WEJŚCIE 1:

rnbqkbnr / ppppppppp / 8/8/8/8 / PPPPPPPP / RNBQKBNR w KQkq - 0 1
# WYJŚCIE 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
# WEJŚCIE 2

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

# WYJŚCIE 2

A1-B1, A1-C1, A2-A3, A2-A4, B2-B3, B2-B4, H1-H2, H1-G1, H1-G2
golffzz
źródło
tutaj też wyglądają tablice wejściowe przypadków testowych: i.stack.imgur.com/qlbH4.png
golffzz
1
@ugoren, zastanowiłem się nad tym, ale wyliczenie wszystkich możliwych ruchów potencjalnie eliminuje niektóre skróty. Nie jestem jednak pewien, dlaczego en passant nie jest wymagany: częścią FEN jest to, że zawiera wystarczającą ilość informacji, aby umożliwić en passant.
Peter Taylor
@PeterTaylor Napisałem to tylko po to, by zredukować pracę. Zastanawiam się, dlaczego nikt nie interesuje się tym golfem :)
golffzz
1
@ Golffzz nie powinien być twoją wersją testową 2 7k / 8/8/8/8/8 / PP6 / Q1q4K w - - 0 1 zamiast 6pk / 6pp / 8/8/8 / p7 / PP4pp / Q2p2pK w - - 0 1 (który między innymi wydaje się mieć pionki na końcowych poziomach)?
Penguino

Odpowiedzi:

8

C - 391 bajtów

Pobiera dane wejściowe jako argumenty wiersza poleceń i wypisuje na standardowe pole z kwadratami oznaczonymi od 0 do 63.

OK, miałem kilka minut, więc próbowałem usunąć wszystkie bity związane z wykryciem czeku. Myślę, że teraz nie jest to zbyt wydajne ...

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 bajtowa wersja z wykrywaniem kontroli

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;}
feersum
źródło
To zdumiewające, ale nie odpowiada na pytanie: „Ignoruj ​​czek, mat i impas, króla też nie można schwytać”.
edc65
@ edc65 Nie zgadzam się z twoją interpretacją tych niestety niespójnych instrukcji. Mówi: „Ruchy wyjściowe muszą być zgodne z regułami ruchu szachowego, z wyjątkiem awansu en passant, castling i pionka”. Przejście do czeku nie pojawia się na pogrubionej liście reguł do zignorowania. Traktuję trzeci punkt jako notatkę, że nie musisz wykrywać tych sytuacji i w żaden sposób odzwierciedlać ich w wynikach (np. Konwencja pisania „+” po sprawdzeniu). Również drugi przypadek testowy 2 był poprawny, jak napisano, biorąc pod uwagę, że jeden ignoruje promocję pionka, jak określono (ale nie daje wglądu w czek).
feersum
Drugi przypadek testowy (dane wejściowe) był nieprawidłowy, posiadając czarny pionek o randze 8 i różny od obrazu opublikowanego jako komentarz przez OP ( also here is how test case input boards look like). Biorąc pod uwagę pozycję na obrazie, oryginalny wynik testu wypadł poprawnie zgodnie z regułami.
edc65
2
Och, świetnie, prawdziwa specyfikacja jest w komentarzach? Ugh, co za kiepskie pytanie.
feersum
1
Wyraźny zwycięzca
edc65
2

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);}
znaczniki
źródło
2

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)

Wcięcie dwoma spacjami to znak tab, który oszczędza 5 bajtów.

Przyszło mi do głowy, że prawdopodobnie uda ci się ocenić rozsądne ruchy do przyzwoitej warstwy i utrzymać ją poniżej 1024 bajtów :) Zacząłem przeglądać inne pytania , ale wydaje się, że nie ma pytania o silnik szachowy codegolf ...

Wola
źródło
2
Gratulacje dla wskrzeszenia tego pytania! (Myślę, że mogę umieścić bounty na to, by zobaczyć, co się dzieje.) Twoja odpowiedź jest dobry wygląd, ale strzela B1C3i H2H3w pierwszym przykładzie przedstawionym w pytaniu.
piskliwy ossifrage
Przepraszam, nie H2H3, miałem na myśli G1H3- innymi słowy, twoi biali rycerze skręcają w lewo.
piskliwy ossifrage
Będzie musiał poczekać, aż będę na komputerze, ale jest to łatwy błąd i widzę wiele sposobów na jego skrócenie. Mam nadzieję, że są inne wpisy.
Czy
@squeamishossifrage naprawiono :)
Czy
1

Python 638 637 (482?) Bajtów

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 ")

Uwaga: po def O(y):pojawieniu się nowej linii i znaku tabulacji wcześniejif

Uwaga: za pomocą modułu zlib można uzyskać prawidłowy kod źródłowy Python o wielkości 482 bajtów, po prostu kompresując prawdziwe źródło:

#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╚У")
6502
źródło
1

JavaScript (E6) 481 492 550

Edytuj Naprawiono paskudny błąd w ruchu rycerza. Dużo pracy, aby bajt się nie zmienił.

(Nie licząc początkowych spacji i znaków nowej linii dla zachowania czytelności)

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

Mniej golfa

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
)

Przetestuj w konsoli FireFox / FireBug

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

Wynik

B3B4 A2A3 A2A4 A1B2 A1C3 A1D4 A1E5 A1F6 A1G7 A1H8 A1B1 A1C1 H1G1 H1H2 H1G2
edc65
źródło
1

JAVA 631 599 594

Naprawiono błąd w wersji 599 bajtów (dziękuję Jackowi za zwrócenie na to uwagi!) I skróciłem kod do 594 bajtów.

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);}}}

Kompiluj: javac F.java
Uruchom: Dane java F 6pk/6pp/8/8/8/p7/PP4pp/Q2p2pK w - - 0 1
wyjściowe:B2B3 B2B4 B2A3 A1B1 A1C1 A1D1 H1H2 H1G1 H1G2

Bob Genom
źródło
Bo 3Q4/p4r1k/P4pp1/4P3/5n2/3P4/4BbbP/RN3KN1 w - - 0 0nie widzę ruchów, F1F2czy F1G2król jest w stanie uchwycić?
Jack
Dziękujemy za zwrócenie na to uwagi. Masz rację. Ta opublikowana wersja jest zbyt zoptymalizowana :(
Bob Genom
Więc muszę wrócić do mojego rozwiązania o długości 631 bajtów.
Bob Genom
573 bajtów
pułapcatcat