11
\$\begingroup\$

The program plays white.

Example stdin:

8 ║♜ ♞ ♝ ♛ ♚ ♝ ♞ ♜
7 ║♟ ♟ ♟ ♟ … ♟ ♟ ♟
6 ║… … … … … … … …
5 ║… … … … ♟ … … …
4 ║… … … … … … … …
3 ║… … ♘ … … … … …
2 ║♙ ♙ ♙ ♙ ♙ ♙ ♙ ♙
1 ║♖ … ♗ ♕ ♔ ♗ ♘ ♖
——╚═══════════════
—— a b c d e f g h

Example stdout:

8 ║♜ ♞ ♝ ♛ ♚ ♝ ♞ ♜
7 ║♟ ♟ ♟ ♟ … ♟ ♟ ♟
6 ║… … … … … … … …
5 ║… … … … ♟ … … …
4 ║… … … … ♙ … … …
3 ║… … ♘ … … … … …
2 ║♙ ♙ ♙ ♙ … ♙ ♙ ♙
1 ║♖ … ♗ ♕ ♔ ♗ ♘ ♖
——╚═══════════════
—— a b c d e f g h

Any valid move is ok. "En passant" and castling are ignored. It is ok to show error messages or print nothing if there is no valid move.

The answer with the most votes wins.

\$\endgroup\$
  • \$\begingroup\$ I mean a standard error message caused by failure of some built-in function of the language. So that's ok? — Is it mandatory that the program can do any legal move? Perhaps castling and pawn special moves should be made optional with some bonus? \$\endgroup\$ – ceased to turn counterclockwis Jan 21 '12 at 15:12
  • 2
    \$\begingroup\$ @leftaroundabout: Whenever you can castle, you can just move the rook instead, so you can skip the logic for that at least. \$\endgroup\$ – hammar Jan 21 '12 at 15:15
  • 2
    \$\begingroup\$ ... and thinking about it some more, the "en passant" move requires information about what previous moves has been made, which cannot be inferred from just the positions of the pieces, so I guess it might be safe to drop that. However, whether the double first move is available can be inferred from the rank of the pawn, so you might want to include that. \$\endgroup\$ – hammar Jan 21 '12 at 18:41
  • \$\begingroup\$ @hammar: you're right, I hadn't thought about that. The double move is also not important, except for one case: when you can go two steps you can also go one, so it only becomes important when you're in check and the double-move is the only move that covers the king. Also, even when you don't need to be able to use every move, you still need to consider that black can answer with any possibility. \$\endgroup\$ – ceased to turn counterclockwis Jan 21 '12 at 19:14
  • 9
    \$\begingroup\$ Is resigning counted as a legal move? :) \$\endgroup\$ – gnibbler Jan 22 '12 at 13:19
16
\$\begingroup\$

I'm not complaining about upvotes, but to be fair... my solution here isn't actually all that great. Ugoren's is better, apart from lacking unicode support. Be sure to look at all the answers before voting, if you've come across this question only now!
Anyway.

Haskell, 893 888 904 952 (without castling)

862 (without pawn double-moves)

(You didn't specify if this is supposed to be code golf, but it seems to me it should)

χ=w⋈b;w="♙♢♤♔♕♖♗♘";b="♟♦♠♚♛♜♝♞"
μ=t⤀ζ++((\(x,y)->(x,-y))⤀)⤀μ;q c|((_,m):_)<-((==c).fst)☂(χ⋎μ)=m
t(x:y:l)=(d x,d y):t l;t _=[];d c=fromEnum c-78
ζ=["NM","NL","MMOM","MMMNMONMNOOMONOO",σ⋈δ,σ,δ,"MLOLPMPOOPMPLOLM"]
σ=l>>=(\c->'N':c:c:"N");δ=[l⋎l,reverse l⋎l]>>=(>>=(\(l,r)->[l,r]))
l="GHIJKLMOPQRSTU"
α c|c∊"♢♤"='♙'|c∊"♦♠"='♟'|c∊χ=c;π('♙':_)=6;π _=1
(⋎)=zip;(⤀)=map;(∊)=elem;(✄)=splitAt;(☂)=filter;(⋈)=(++)
φ r@(x,y)p a
 |x>7=φ(0,y+1)p a
 |y>7=[]
 |c<-a✠r=(c⌥r)p a y⋈φ(x+1,y)p a
(c⌥r)p a y
 |c==p!!0=(a☈r)c χ++const(y==π p)☂(a☈r)(p!!1)χ++(a☈r)(p!!2)('…':w)
 |c∊p=(a☈r)c χ
 |True=[]
a✠(x,y)=a!!y!!(x*2);o(x,y)=x>=0&&x<8&&y>=0&&y<8
(n➴a)(x,y)|(u,m:d)<-y✄a,(l,_:r)<-(x*2)✄m=u⋈(l⋈(n:r):d)
(a☈r@(x,y))c b=(α c➴('…'➴a)r)⤀((\r->o r&&not((a✠r)∊b))☂((\(ξ,υ)->(x+ξ,y+υ))⤀q c))
main=interact$unlines.uncurry((⋈).zipWith((⋈).(:" ║"))['8','7'..]
 .head.((all(any('♔'∊)).φ(0,0)b)☂).φ(0,0)w.(drop 3⤀)).(8✄).lines

When you have GHC installed (for instance as part of the Haskell platform) you can do just

$ runhaskell def0.hs < examplechessboard.txt
8 ║♜ ♞ ♝ ♛ ♚ ♝ ♞ ♜
7 ║♟ ♟ ♟ ♟ … ♟ ♟ ♟
6 ║… … … … … … … …
5 ║… ♘ … … ♟ … … …
4 ║… … … … … … … …
3 ║… … … … … … … …
2 ║♙ ♙ ♙ ♙ ♙ ♙ ♙ ♙
1 ║♖ … ♗ ♕ ♔ ♗ ♘ ♖
——╚═══════════════
—— a b c d e f g h
\$\endgroup\$
  • \$\begingroup\$ Now this is crazy :) I will check it out :) \$\endgroup\$ – Hristo Hristov Jan 21 '12 at 20:37
  • \$\begingroup\$ Any idea how to test this awesomeness? Ideone.com can not handle it... \$\endgroup\$ – Hristo Hristov Jan 21 '12 at 20:53
  • \$\begingroup\$ @HristoHristov: strange it doesn't work on Ideone. Probably has to do with the non-ASCII characters. \$\endgroup\$ – ceased to turn counterclockwis Jan 21 '12 at 21:10
  • \$\begingroup\$ yes, this is the problem with ideone \$\endgroup\$ – Hristo Hristov Jan 21 '12 at 21:12
  • 14
    \$\begingroup\$ Congratulations, you've managed to make Haskell look like APL. :-) \$\endgroup\$ – Ilmari Karonen Jan 22 '12 at 15:54
11
\$\begingroup\$

C, 734 672 640 characters

Characters counted without removable whitespace.
The file format I used is not as requested, but simplified ASCII.
I need to add Unicode character support, it would cost some characets.

char*r=" kpnbrq  KPNBRQ $ ,&)$wxy()879()8(6:GI(",B[256],*b=B,i;
e(x,d,m,V,c,r,n,p){
    for(r=0,p=b[x];m/++r;){
        n=x+d*r;
        if(p==2+8*(d<0)||n&136||!(b[n]?r=8,8^p^b[n]^8&&c&65^64:c&65^65)
            ? r=m,0
            : V?v(n,x):b[n]==1)
            return b[x]=0,b[n]=p%8-2||n/16%7?p:p+4;
    }
    return d>0&&e(x,-d,m,V,c);
}
d(x,v,m,i)char*m;{
    return(i=*m-40)?e(x,i%64,b[x]%8-2?b[x]&4?7:1:(x/16-1)%5|i%2?1:2,v,i)||d(x,v,m+1):0;
}
v(t,f){
    bcopy(B,b+=128,128);
    b[t]=b[f];b[f]=0;
    i=a(1,63);
    b=B;
    return!i;
}
a(c,n){
    return b[i=n*2-n%8]&&b[i]/8==c&&d(i,!c,r+r[b[i]%8+15]-10)||n--&&a(c,n);
}
main(){
    for(;gets(b);b+=8)for(;*b;b++)*b=strchr(r,*b)-r;b=B;
    for(i=64*!a(0,63);i<64;i++%8-7||puts(""))putchar(r[b[i*2-i%8]]);
}

Input/output file format:
Must be exactly 8 lines of exactly 8 characters. pnbrqk are used for white pieces, PNBRQK for black pieces, spaces for spaces:

RNBQKBNR
PPPP PPP

 n  P


pppppppp
r bqkbnr

The logic is quite simple:
For each possible move of each white piece, try each possible move of each black piece.
If no black move captures the white king, the white move is valid.

The board is maintained as char[256], treated as a 16x16 matrix, where only the top-left 8x8 is used. Positions and movement vectors are kept in 8-bit integers (x:4,y:4). The extra bit allows using simple arithmetic (new_pos = old_pos + steps*direction), with easy detection of the board edge (&0x88 does the magic). r[] encodes three things:

  1. The first 15 bytes map internal piece codes (K=1,P=2,N=3,B=4,R=5,Q=6) to letters.
  2. The next 6 bytes map internal piece codes to offsets in the last part (K and Q are the same, B is their tail).
  3. The last 16 bytes encode the movement of all pieces, as '('+vector.

Functions:

  1. main reads the board, converts letters to internal code, calls a to find white moves, prints the board.
  2. arecursively loops over the 64 squares. For each piece of the right color (parameter c), it finds the movement rule for the piece and calls d.
  3. d recursively loops over the encoded movement rule, which is a list of vectors, calling e for each one. It gives e the original position, the vector and the range limit (7 for pieces above B, 2 for second rank pawns, 1 otherwise).
  4. e tests all movements along a vector. If the move is possible (i.e. pawns move forward, within board, not blocked, pawn capture diagonally), checks one of two things. For white moves, runs v to validate the move. For black moves, checks if the white king is captured. If true, the move is played on the board.
  5. v validates a white move. It copies the board aside, executes the move to test, and calls a again, to look for black moves.
\$\endgroup\$
  • \$\begingroup\$ At last, a solution with proper compressed encoding of the possible moves! And it's nicely fast. Don't you think you could add a Unicode wrapper and still be shorter than my code? \$\endgroup\$ – ceased to turn counterclockwis Feb 8 '12 at 18:08
  • \$\begingroup\$ @leftaroundabout, I guess I can. The main problem is that I'm working in a Linux command line, where you can't see Unicode, so debugging it would be annoying. I also have a version that saves about 40 more bytes (I'll update soon), so I have lots of chars to work with. \$\endgroup\$ – ugoren Feb 8 '12 at 19:14
  • \$\begingroup\$ @ugoren: Surely any half-way modern Linux distribution supports UTF-8 out of the box? \$\endgroup\$ – han Feb 25 '12 at 9:29
  • \$\begingroup\$ @han, I'm working on Windows and connect to Linux by SSH, and Unicode doesn't work. I can write to a file and open in in Windows, but it just isn't interesting any more. \$\endgroup\$ – ugoren Feb 25 '12 at 12:38
  • \$\begingroup\$ Will this compile with gcc? I'm using Geany for Windows with MinGW and it will compile with a bunch of errors and warnings but it will not build/run.eg:C:\Users\xxx\AppData\Local\Temp\ccpBG9zy.o:codegolfchess.c:(.text+0x2d8): undefined reference to `bcopy' collect2: ld returned 1 exit status \$\endgroup\$ – rpd Nov 8 '12 at 19:11
5
\$\begingroup\$

Python 2.6, 886 - 1425 characters

My initial version (in the revisions) came in at 886 characters but did not satisfy the spec completely (it did not check for avoiding checkmate ; it didn't even consider the possible moves of the black pieces).

Now it does (and I've fixed several bugs in the original). Alas this comes with a cost in characters: 1425 for now, but there should still be little room for improvement. This version should be a lot more solid in handling edge cases then the previous one.

#-*-coding:utf8-*-
import sys;e=enumerate
B,W=["♟","♜","♞","♝","♛","♚"],["♙","♖","♘","♗","♕","♔"]
R={"♙":[11,42],"♖":[28],"♘":[31],"♗":[8],"♕":[8,28],"♔":[1,21]}
def F(w):return sum([[(i,j)for j,p in e(o)if p==w]for i,o in e(Z)],[])
def G(x,y):
 P=Z[x][y];D=P in W;L=[]
 for o in R[P]if D else R[unichr(ord(P.decode('utf8'))-6).encode('utf8')]:
  r,k="%02d"%o        
  for g,h in[[(-1,-1),(1,1),(-1,1),(1,-1)],[[(1,-1),(1,1)],[(-1,-1),(-1,1)]][D],[(-1,0),(1,0),(0,-1),(0,1)],[(-2,-1),(-2,1),(-1,-2),(-1,2),(1,-2),(1,2),(2,-1),(2,1)],[(-1,0)]][int(r)]:
   J=0
   for i in range(int(k)):
    T=x+(i+1)*g;U=y+(i+1)*h
    if T<0 or T>7 or U<0 or U>7:break
    M=Z[T][U]
    if not J:L.append((T,U,P,M))
    else:break
    if r in"02"and(M in W+B):
     J=1
     if not((D and M in B)or(not D and M in W)):L.pop()
    elif(r=="1"and not((D and M in B)or(not D and M in W)))or(r=="4"and((i==1 and x!=6)or M!="…")):L.pop()
 return L  
Z=[[y for y in l[5:].split()]for l in sys.stdin.readlines()[:-2]]
Q=[]
for p in R:
 for i,j in F(p):
  for M,L,c,_ in G(i,j):
   O=Z[M][L];Z[i][j]="…";Z[M][L]=c;E=[];map(E.extend,map(F,B))
   if not any(any(1 for _,_,_,I in G(v,h)if I==["♔","♚"][c in B])for v,h in E):Q.append((i,j,M,L,c))
   Z[i][j]=c;Z[M][L]=O
(x,y,X,Y,p)=Q[0];Z[x][y]="…";Z[X][Y]=p
for i,h in e(Z):print`8-i`+' ║'+' '.join(h)
print"——╚"+"═"*16+"\n—— a b c d e f g h"

Example input and output:

# INPUT

8 ║♜ ♞ ♝ … ♚ ♝ ♞ ♜
7 ║♟ ♟ ♟ ♟ … ♟ ♟ ♟
6 ║… … … … … … … …
5 ║… … … … ♟ … … …
4 ║… … … … … … ♙ ♛
3 ║… … … … … ♙ … …
2 ║♙ ♙ ♙ ♙ ♙ … ♙ …
1 ║♖ ♘ ♗ ♕ ♔ ♗ ♘ ♖
——╚═══════════════
—— a b c d e f g h
# OUTPUT

8 ║♜ ♞ ♝ … ♚ ♝ ♞ ♜
7 ║♟ ♟ ♟ ♟ … ♟ ♟ ♟
6 ║… … … … … … … …
5 ║… … … … ♟ … … …
4 ║… … … … … … ♙ ♛
3 ║… … … … … ♙ ♙ …
2 ║♙ ♙ ♙ ♙ ♙ … … …
1 ║♖ ♘ ♗ ♕ ♔ ♗ ♘ ♖
——╚════════════════
—— a b c d e f g h
\$\endgroup\$
  • \$\begingroup\$ It's 886 bytes, but only 854 chars. (My program has over 1kB, thanks to the many non-ASCII operators!) — Are you going to add checking for taking the king yet? \$\endgroup\$ – ceased to turn counterclockwis Feb 8 '12 at 17:58
  • \$\begingroup\$ @leftaroundabout: I've added the king checks (which forces me to also account for possible moves of black, and adds a lot of characters...). Oh well, this version should be more solid around edge cases (as far as I tested). \$\endgroup\$ – ChristopheD Feb 15 '12 at 23:31

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.