16
\$\begingroup\$

It's the ending of another well played chess game. You're the white player, and you still have a rook and your king. Your opponent only has his king left.

Since you're white, it's your turn. Create a program to play this chess match. Its output can be a sequence of moves, a gif animation, ASCII art or whatever you like.

It seems quite obvious, but I'll state it explicitly: you have to win the game (in a finite number of moves). It's always possible to win from this position. DO NOT LOSE THAT ROOK. DO NOT STALEMATE.

Your program may or may not accept a human input for the starting position and for each black move (you can safely assume this is a legal position, i.e. the kings are not touching each other). If it doesn't, a random starting position and random movements for the black king will suffice.

Score

Your score will be length in byte of your code + bonus. Any language is allowed, lowest score wins.

Bonus

-50 if your program allows both a human defined starting position and a random one. Humans can enter it via stdin, file, GUI...

-100 if your program allows both a human and a random player to move the black king

+12345 if you rely on an external chess solver or a built-in chess library

Good luck!

Update!

Extra rule: The match must be played until checkmate. Black does not resign, doesn't jump outside the chessboard and doesn't get kidnapped by aliens.

Hint

You can probably get help from this question on chess.se.

\$\endgroup\$
  • 2
    \$\begingroup\$ Does the 50 move draw rule apply? \$\endgroup\$ – Comintern Feb 27 '14 at 0:35
  • 1
    \$\begingroup\$ @Victor I've had a couple of goes, but it hasn't worked out yet. Brute force is obviously too slow, alpha-beta too because the landscape of position ratings is quite flat; and tends to get stuck in a loop. Retrograde analysis would work but very slow up-front. My next attempt will use Bratko's algorithm for KRK, which I've avoided because it's a pile of special cases, not great for golf. \$\endgroup\$ – bazzargh Mar 6 '14 at 23:33
  • 1
    \$\begingroup\$ @victor I'm looking at this too. This is interesting precisely because it simple to define and difficult to do. In turn the program will not be short, so the code-golf tag made it seem doubly hard. If my program works you'll see it soon. \$\endgroup\$ – Level River St Mar 7 '14 at 0:35
  • 1
    \$\begingroup\$ @Victor the problem was not about trying to be optimal, any attempt to pick a 'best' move without considering game history led to loops. Need to test game terminates from every position. Bratko+variants arent optimal but provably terminate. Trying retrograde analysis just now (ie build endgame table), looks promising and actually is optimal, which is nice. Also turns out reasonably short. \$\endgroup\$ – bazzargh Mar 7 '14 at 1:17
  • 2
    \$\begingroup\$ If anyone needs inspiration (or is just curious), you can find a 1433 character complete chess engine at home.hccnet.nl/h.g.muller/umax1_6.c \$\endgroup\$ – Comintern Mar 7 '14 at 17:42
11
+50
\$\begingroup\$

Haskell 1463-100=1363

Just getting an answer in. This finds the solution the retrograde way, working back from checkmate to the position we're in. It differs from the description of retrograde analysis on chessprogramming - instead of starting with an initial set and expanding it with backwards moves until no squares moved to haven't been seen, it starts with all unused squares and reduces that set by trying forward moves. This is going to be less time-efficient than the traditional way, but the memory usage exploded for me when I tried it.

Compile with ghc -O2 for acceptable performance for the endgame table calculation; play is instant after the first move. Supply white king, rook, black king squares as arguments. For a move, it just wants a square, and will pick one for you if you press return. Example session:

$ time  printf "\n\n\n\n\n\n\n\n"|./rook8 e1 a1 e8
("e1","a7","e8")[d8]?
("d2","a7","d8")[c8]?
("d2","h7","c8")[b8]?
("c3","h7","b8")[a8]?
("b4","h7","a8")[b8]?
("c5","h7","b8")[a8]?
("b6","h7","a8")[b8]?
("b6","h8","b8") mate

real    0m8.885s
user    0m8.817s
sys 0m0.067s

Code:

import System.Environment
import qualified Data.Set as S
sp=S.partition
sf=S.fromList
fl=['a'..'h']
rk=[0..7]
lf=filter
m=map
ln=notElem
lh=head
pl=putStrLn
pa[a,b]=(lh[i|(i,x)<-zip[0..]fl,a==x],read[b]-1)
pr(r,c)=fl!!r:show(c+1)
t f(w,r,b)=(f w,f r,f b)
km(a,b)=[(c,d)|c<-[a-1..a+1],d<-[b-1..b+1],0<=c,c<=7,0<=d,d<=7]
vd (w,r,b)=b`ln`km w&&w/=r&&b/=w&&b/=r
vw p@(_,r,b)=vd p&&r`ln`km b&&(ck p||[]/=bm p)
vb p=vd p&&(not.ck)p
rm (w@(c,d),(j,k),b@(u,x))=[(w,(j,z),b)|z<-rk,z/=k,j/=c||(k<d&&z<d)||(d<k&&d<z),j/=u||(k<x&&z<x)||(x<k&&x<z)]
kw(w,r,b)=m(\q->(q,r,b))$km w
xb(w,r,_)b=(w,r,b)
wm p=lf(\q->q/=p&&vw q)$rm p++(m(t f)$rm$t f p)++kw p
bm p@(_,_,b)=lf(\q->q/=p&&vb q)$m(xb p)$km b
c1((c,d),(j,k),(u,x))=j==u&&(c/=j||(k<x&&d<k)||(k>x&&d>k))
ck p=c1 p||(c1$t f p)
mt p=ck p&&[]==bm p
h(x,y)=(7-x,y)
v=f.h.f
f(x,y)=(y,x)
n p@((c,d),_,_)|c>3=n$t h p|d>3=n$t v p|c>d=n$t f p|True=p
ap=[((c,d),(j,k),(u,x))|c<-[0..3],d<-[c..3],j<-rk,k<-rk,u<-rk,x<-rk]
fr s p=S.member(n p)s
eg p=ef(sp mt$sf$lf vw ap)(sf$lf vb ap)
ps w mv b0=sp(\r->any(fr b0)$mv r)w
ef(b0,b1)w=let(w1,w2)=ps w wm b0 in(w1,b0):(if S.null w2 then[]else ef(f$ps b1 bm w2)w2)
lu((w1,b0):xs)p=if fr w1 p then lh$lf(fr b0)$wm p else lu xs p
th(_,_,b)=b
cd tb q=do{let{p=lu tb q};putStr$show$t pr p;if mt p then do{pl" mate";return()}else do{let{b1=pr$th$lh$bm p};pl("["++b1++"]?");mv<-getLine;cd tb$xb p (pa$if""==mv then b1 else mv)}}
main=do{p1<-getArgs;let{p2=m pa p1;p=(p2!!0,p2!!1,p2!!2)};cd(eg p)p}

Edited: Fixed code to remember endgame table and use arguments, so much less painful to test repeatedly.

\$\endgroup\$
  • 2
    \$\begingroup\$ haskell code with side effects? how could you, heretic! :p \$\endgroup\$ – Einacio Mar 7 '14 at 16:24
  • \$\begingroup\$ finally a serious one! \$\endgroup\$ – izabera Mar 7 '14 at 17:12
  • \$\begingroup\$ that puzzle was evil @izabera! \$\endgroup\$ – bazzargh Mar 7 '14 at 17:16
  • \$\begingroup\$ Nice! Much better than the attempt I was working on. I was trying to just improve the El Ajedrecista enough to ensure 50 move mates, but as far as an algorithm goes it's really bad. \$\endgroup\$ – Comintern Mar 7 '14 at 17:40
  • \$\begingroup\$ A lot of the sucky performance comes from me not memoizing the endgame table (y). This is really obvious in that the second move isn't fast when we've already considered the whole endgame. I am off to the pub this evening but if I get the chance tomorrow I'll make this less terrible. \$\endgroup\$ – bazzargh Mar 7 '14 at 18:00
7
\$\begingroup\$

C, Currently 2552 noncomment nonwhitespace characters

The count indicates to me that I could golf it down below 2552 total chars, but given there is already a smaller answer (which will be tough to beat) I will consider that carefully before bothering to do it. It's true there's about 200 chars for displaying the board and another 200 each for checking user input of both start position and move (which i need for testing, but could eliminate.)

No game tree here, just hardcoded algorithm, so it moves instantly.

Start positions are entered as row (1-8) column (1-8) numbered from top right and the program works on the same scheme. So if you turned your screen 90 degrees anticlockwise, it would follow the standard Correspondence Chess numeric square notation. Positions where the black king is already in check are rejected as illegal.

Black moves are entered as a number from 0 to 7, with 0 being a move to the north, 1 to the northeast and so on in a clockwise sense.

It doesn't follow the commonly known algorithm that exclusively uses the rook under the protection of the white king to restrict the black king. The rook only restricts the black king in a vertical sense (and will run away horizontally if chased.) The white king restricts the black king in horizontal movement. This means the two white pieces do not get in each others' way.

I seem to have ironed out most of the bugs and possible infinite loops, it's running pretty well now. I will play with it again tomorrow and see if there is anything else that needs fixing.

#include "stdafx.h"
#include "stdlib.h"
#include "string.h"

int b[2], w[2], r[2], n[2],s,t,i,nomate;
int v[2][8] = { {-1,-1,0,1,1,1,0,-1}, {0,1,1,1,0,-1,-1,-1} };
int u[5] = { 0, 1, -1, 2, -2 };
char empty[82] = "        \n--------\n--------\n--------\n--------\n--------\n--------\n--------\n--------\n";
char board[82];

int distance(int p[2], int q[2]){
    return __max(abs(p[0]-q[0]),abs(p[1]-q[1]));
}

int sign(int n){
    return (n>0)-(0>n); 
}

// from parameters p for white king and q for rook, determines if rook is/will be safe
int rsafe(int p[2],int q[2]){
    return  distance(p, q)<2 | distance(q,b)>1;
}

void umove(){
    t=0;
    while (t != 100){
        printf("Enter number 0 to 7 \n");
        scanf_s("%d", &t); t %= 8;
        n[0] = b[0] + v[0][t];
        n[1] = b[1] + v[1][t];
        if (distance(w, n) < 2 | (n[0] == r[0] & (n[1]-w[1])*(r[1]-w[1])>0) 
            | ((n[1] == r[1]) & (n[0]-w[0])*(r[0]-w[0])>0) | n[0] % 9 == 0 | n[1] % 9 == 0)
            printf("illegal move");
        else{ b[0] = n[0]; b[1] = n[1]; t = 100; };
    }
}

void imove(){
    t=0;
    // mate if possible
    if (distance(b, w) == 2 & b[0] == w[0] & (b[1] == 1 | b[1] == 8) & r[0]!=w[0]){
        n[0] = r[0]; n[1] = b[1];
        if (rsafe(w, n)){
            r[1] = n[1]; 
            printf("R to %d %d mate!\n", r[0], r[1]);
            nomate=0;
            return;
        }
    }

    //avoid stalemate
    if ((b[0] == 1 | b[0] == 8) & (b[1] == 1 | b[1] == 8) & abs(b[0] - r[0]) < 2 & abs(b[0]-w[0])<2){
        r[0] = b[0]==1? 3:6;
        printf("R to %d %d \n", r[0], r[1]);
        return;
    }

    // dont let the rook be captured. 
    if(!rsafe(w,r)) 
    {
        if (w[0] == r[0]) r[1] = w[1] + sign(r[1]-w[1]);
        else r[1] = r[1]>3? 2:7;
        printf("R to %d %d \n", r[0], r[1]);
        return;
    }

    // if there's a gap between the kings and the rook, move rook towards them. we only want to do this when kings on same side of rook, and not if the black king is already on last row.
    if (abs(w[0]-r[0])>1 & abs(b[0] - r[0]) > 1 & (b[0]-r[0])*(w[0]-r[0])>0 & b[0]!=1 & b[0]!=8){
        n[0] = r[0] + sign(b[0] - r[0]); n[1] = r[1];
        if (rsafe(w, n)) r[0] = n[0]; 
        else r[1] = r[1]>3? 2:7;
        printf("R to %d %d \n", r[0], r[1]);
        return;

    }
    // if kings are far apart, or if they not on the same row (except if b 1 row from r and w 2 rows from r), move king
    if ((w[0]-r[0])!=2*(b[0]-r[0]) | abs(b[0]-w[0])>1 | distance(w,b)>2){
        for (i = 0; i<8; i++) if (v[0][i] == sign(b[0] - w[0]) & v[1][i] == sign(b[1] - w[1])) t = i;
        s = 1 - 2 * (w[0]>3 ^ w[1] > 3);
        for (i = 0; i < 5; i++){
            n[0] = w[0] + v[0][(t + s*u[i] + 8) % 8];
            n[1] = w[1] + v[1][(t + s*u[i] + 8) % 8] *(1-2*(abs(w[0]-b[0])==2));
            if (distance (n,b)>1 & distance(n, r)>0 & rsafe(n,r) & n[0]%9!=0 & n[1]%9!=0
                & !(n[0]==r[0] & (w[0]-r[0])*(b[0]-r[0])>0)) i = 5;
        }
        if (i == 6) {
            w[0] = n[0]; w[1] = n[1]; printf("K to %d %d \n", w[0], w[1]); return;
        }
    }

    //if nothing else to do, perform a waiting move with the rook. Black is forced to move his king.
    t = r[1]>3? -1:1;
    for (i = 1; i < 5; i++){
        n[0] = r[0]; n[1] = r[1] + t*i;
        if (rsafe(w, n)){ r[1] = n[1]; i=5; }
    }
    printf("R to %d %d \n", r[0], r[1]);
}

int _tmain(){

    do{ 
        t=0;
        printf("enter the row and col of the black king ");
        scanf_s("%d%d", &b[0], &b[1]);
        printf("enter the row and col of the white king ");
        scanf_s("%d%d", &w[0], &w[1]);
        printf("enter the row and col of the rook");
        scanf_s("%d%d", &r[0], &r[1]);
        for (i = 0; i < 2; i++) if (b[i]<1 | b[i]>8 | w[i]<1 | w[i]>8 | w[i]<1 | w[i]>8)t=1;
        if (distance(b,w)<2)t+=2;
        if ((b[0] == r[0] & (b[1]-w[1])*(r[1]-w[1])>0) | ((b[1] == r[1]) & (b[0]-w[0])*(r[0]-w[0])>0)) t+=4;
        printf("error code (0 if OK) %d \n",t);
    } while(t);

    nomate=1;
    while (nomate){
        imove();
        strncpy_s(board, empty, 82);
        board[b[0] * 9 + b[1] - 1] = 'B'; board[w[0] * 9 + w[1] - 1] = 'W'; board[r[0] * 9 + r[1] - 1] = 'R'; printf("%s", board);      
        if(nomate)umove();
    }
    getchar(); getchar();

}

Here's a typical finish (mate can sometimes occur anywhere on the right or left edge of the board.)

enter image description here

\$\endgroup\$
6
\$\begingroup\$

Bash, 18 (or -32?)

Okay, this is a joke answer. Since Black is a good chess player, and Black knows that White is also a good chess player, he decides that the only sensible thing to do is:

echo Black resigns

This results in white winning, which meets the specification.

Technically you can enter the current positions as arguments too, the program just ignores them, so arguably this can qualify for the -50 bonus.

\$\endgroup\$
  • \$\begingroup\$ Funny, but I updated the rules. Playing until checkmate is now mandatory. \$\endgroup\$ – izabera Feb 26 '14 at 20:24
  • 1
    \$\begingroup\$ Btw the original question clearly states that your program may allow a human or a random player for black, and yours is not random. \$\endgroup\$ – izabera Feb 26 '14 at 20:27
  • 2
    \$\begingroup\$ Using standard notation, you could output 1-0 which is a bit shorter. \$\endgroup\$ – daniero Feb 26 '14 at 20:44
  • 1
    \$\begingroup\$ @Comintern well actual when losing optimal usually means lasting out the longest. \$\endgroup\$ – PyRulez Mar 2 '14 at 2:48
  • \$\begingroup\$ @PyRulez according to wikipedia, "Either player may resign at any time and their opponent wins the game." Plus, this is just a joke answer, don't take it so seriously. \$\endgroup\$ – ace_HongKongIndependence Mar 2 '14 at 9:09

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.