king + rook vs king

Question

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.

Answer 1

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.

Answer 2

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