To koniec kolejnej dobrze rozgrywanej gry w szachy. Jesteś białym graczem i nadal masz wieżę i swojego króla. Twój przeciwnik ma tylko króla.

Ponieważ jesteś biały, twoja kolej. Utwórz program, aby zagrać w ten mecz w szachy. Jego rezultatem może być sekwencja ruchów, animacja gif, grafika ASCII lub cokolwiek zechcesz.

Wydaje się to dość oczywiste, ale stwierdzę to wprost: musisz wygrać grę (skończoną liczbą ruchów). Z tej pozycji zawsze można wygrać. NIE UTRACAJ TEGO ROOK. NIE STALEMATE.

Twój program może, ale nie musi, przyjmować ludzkie dane wejściowe dla pozycji początkowej i każdego czarnego ruchu (możesz bezpiecznie założyć, że jest to legalna pozycja, tzn. Królowie się nie dotykają). Jeśli nie, wystarczy losowa pozycja początkowa i losowe ruchy czarnego króla.

Wynik

Twój wynik będzie długości bajtu kodu + bonus. Dowolny język jest dozwolony, wygrywa najniższy wynik.

Premia

-50, jeśli twój program dopuszcza zarówno pozycję początkową zdefiniowaną przez człowieka, jak i losową. Ludzie mogą wejść do niego przez stdin, plik, GUI ...

-100, jeśli twój program pozwala zarówno ludzkiemu, jak i losowemu graczowi przenieść czarnego króla

+12345, jeśli polegasz na zewnętrznym rozwiązaniu szachowym lub wbudowanej bibliotece szachowej

Powodzenia!

Aktualizacja!

Dodatkowa zasada: mecz musi zostać rozegrany do mata. Czarny nie rezygnuje, nie wyskakuje z szachownicy i nie zostaje porwany przez kosmitów.

Wskazówka

Prawdopodobnie możesz uzyskać pomoc z tego pytania na stronie chess.se .

Haskell 1463–100 = 1363

Po prostu otrzymuję odpowiedź. Znajduje to rozwiązanie w sposób wsteczny, wracając od szacha do pozycji, w której się znajdujemy. Różni się to od opisu analizy wstecznej w programowaniu szachowym - zamiast zaczynać od zestawu początkowego i rozszerzać go o ruchy wstecz dopóki nie zostaną wyświetlone żadne przesunięte kwadraty, zaczyna się od wszystkich nieużywanych kwadratów i zmniejsza ten zestaw, próbując wykonać ruchy do przodu. Będzie to mniej czasochłonne niż tradycyjny sposób, ale użycie pamięci eksplodowało, gdy próbowałem.

Skompiluj z ghc -O2dla akceptowalnej wydajności do obliczeń tabeli końcowej; gra jest natychmiastowa po pierwszym ruchu. Zaopatruj białego króla, wieżę, czarne kwadraty króla jako argumenty. Dla ruchu chce tylko kwadratu i wybierze dla ciebie, jeśli naciśniesz return. Przykładowa sesja:

$ 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

Kod:

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}

Edytowano: Naprawiono kod zapamiętujący tabelę gier końcowych i używający argumentów, więc o wiele mniej bolesne było powtarzanie testów.

C, obecnie 2552 niekomentowanych znaków spoza białej przestrzeni

Liczenie wskazuje mi, że mógłbym zagrać w golfa poniżej 2552 znaków, ale biorąc pod uwagę, że jest już mniejsza odpowiedź (która będzie trudna do pokonania), zastanowię się nad tym ostrożnie, zanim się tym zajmę. To prawda, że ​​jest około 200 znaków do wyświetlania tablicy, a kolejne 200 do sprawdzania danych wprowadzanych przez użytkownika zarówno pozycji początkowej, jak i ruchu (które potrzebuję do przetestowania, ale mogę je wyeliminować).

Nie ma tu drzewa gry, tylko zakodowany algorytm, więc porusza się natychmiast.

Pozycje początkowe są wprowadzane jako wiersz (1-8) kolumna (1-8) ponumerowana od prawej górnej części, a program działa na tym samym schemacie. Jeśli więc obrócisz ekran o 90 stopni w kierunku przeciwnym do ruchu wskazówek zegara, będzie on zgodny ze standardową notacją kwadratową w szachach korespondencyjnych. Pozycje, w których czarny król jest już pod kontrolą, są odrzucane jako nielegalne.

Czarne ruchy są wprowadzane jako liczby od 0 do 7, przy czym 0 oznacza ruch na północ, 1 na północny wschód i tak dalej, zgodnie z ruchem wskazówek zegara.

Nie postępuje zgodnie z powszechnie znanym algorytmem, który wykorzystuje wieżę wyłącznie pod ochroną białego króla, aby ograniczyć czarnego króla. Wież ogranicza czarnego króla tylko w sensie pionowym (i ucieknie poziomo, jeśli zostanie ścigany). Biały król ogranicza czarnego króla w ruchu poziomym. Oznacza to, że dwa białe elementy nie wchodzą sobie w drogę.

Wydaje mi się, że usunąłem większość błędów i możliwych nieskończonych pętli, teraz działa całkiem dobrze. Zagram jutro ponownie i zobaczę, czy jest coś jeszcze, co wymaga naprawy.

#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();

}

Oto typowe wykończenie (kolega może czasem wystąpić w dowolnym miejscu po prawej lub lewej krawędzi planszy).

Bash, 18 (lub -32?)

Dobra, to żartobliwa odpowiedź. Ponieważ czarny jest dobrym szachistą, a czarny wie, że biały jest również dobrym szachistą, postanawia, że ​​jedyną rozsądną rzeczą jest:

echo Black resigns

Skutkuje to białym zwycięstwem, które spełnia specyfikację.

Technicznie możesz wprowadzić bieżące pozycje jako argumenty, program po prostu je ignoruje, więc prawdopodobnie kwalifikuje się to do premii -50.