rei + torre vs rei

16

É o fim de outro jogo de xadrez bem jogado. Você é o jogador branco e ainda tem uma torre e seu rei. Seu oponente só tem o rei dele.

Desde que você é branco, é a sua vez. Crie um programa para jogar esta partida de xadrez. Sua saída pode ser uma sequência de movimentos, uma animação gif, arte ASCII ou o que você quiser.

Parece bastante óbvio, mas vou dizer explicitamente: você precisa vencer o jogo (em um número finito de jogadas). Sempre é possível ganhar desta posição. NÃO PERCA ESSE ROOK. NÃO ESTALEMOS.

Seu programa pode ou não aceitar uma entrada humana para a posição inicial e para cada movimento preto (você pode assumir com segurança que esta é uma posição legal, ou seja, os reis não estão se tocando). Caso contrário, uma posição inicial aleatória e movimentos aleatórios para o rei preto serão suficientes.

Ponto

Sua pontuação terá o comprimento em bytes do seu código + bônus. Qualquer idioma é permitido, a pontuação mais baixa vence.

Bônus

-50 se o seu programa permitir uma posição inicial definida pelo homem e uma posição aleatória. Os humanos podem acessá-lo via stdin, arquivo, GUI ...

-100 se o seu programa permitir que um jogador humano e um jogador aleatório movam o rei preto

+12345 se você contar com um solucionador de xadrez externo ou uma biblioteca de xadrez embutida

Boa sorte!

Atualizar!

Regra extra: a partida deve ser disputada até o xeque-mate. O preto não renuncia, não pula para fora do tabuleiro de xadrez e não é sequestrado por alienígenas.

Sugestão

Provavelmente você pode obter ajuda com essa pergunta no chess.se .

izabera
fonte
2
A regra de 50 movimentos se aplica?
Comintern
11
@ Victor Eu tive algumas tentativas, mas ainda não deu certo. A força bruta é obviamente muito lenta, alfa-beta também porque o cenário das classificações de posição é bastante plano; e tende a ficar preso em um loop. A análise retrógrada funcionaria, mas muito lentamente no início. Minha próxima tentativa usará o algoritmo de Bratko para o KRK, que evitei porque é uma pilha de casos especiais, não muito boa para o golfe.
bazzargh
11
@ victor Também estou vendo isso. Isso é interessante justamente porque é simples de definir e difícil de fazer. Por sua vez, o programa não será curto, então a tag code-golf fez com que parecesse duplamente difícil. Se meu programa funcionar, você o verá em breve.
Nível River St
11
@ Victor, o problema não era tentar ser o ideal, qualquer tentativa de escolher uma 'melhor' jogada sem considerar o histórico do jogo levava a loops. Precisa testar o jogo termina em todas as posições. As variantes Bratko + não são ótimas, mas comprovadamente terminam. Tentar a análise retrógrada agora (por exemplo, criar tabela de final de jogo) parece promissor e, na verdade, é ideal, o que é bom. Também acaba razoavelmente curto.
bazzargh
2
Se alguém precisar de inspiração (ou é apenas curioso), você pode encontrar um mecanismo de xadrez completo de 1433 caracteres em home.hccnet.nl/hgmuller/umax1_6.c
Comintern

Respostas:

11

Haskell 1463-100 = 1363

Apenas obtendo uma resposta. Isso encontra a solução da maneira retrógrada, retornando do xeque-mate à posição em que estamos. Difere da descrição da análise retrógrada na programação de xadrez - em vez de começar com um conjunto inicial e expandi-lo com movimentos para trás até que nenhum quadrado movido não seja visto, ele começa com todos os quadrados não utilizados e reduz esse conjunto, tentando avançar. Isso será menos eficiente em termos de tempo do que a maneira tradicional, mas o uso de memória explodiu para mim quando eu tentei.

Compile com ghc -O2desempenho aceitável para o cálculo da tabela de final de jogo; o jogo é instantâneo após o primeiro movimento. Forneça rei branco, torre, quadrados pretos de rei como argumentos. Por um movimento, ele só quer um quadrado e escolherá um para você se você pressionar retornar. Sessão de exemplo:

$ 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

Código:

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}

Editado: código corrigido para lembrar a tabela de final de jogo e usar argumentos, muito menos doloroso para testar repetidamente.

bazzargh
fonte
2
código haskell com efeitos colaterais? como você pôde, herege! : p
Einacio
finalmente sério!
Izabera 7/03
esse quebra-cabeça era mau @izabera!
precisa saber é o seguinte
Agradável! Muito melhor do que a tentativa em que estava trabalhando. Eu estava tentando apenas melhorar o El Ajedrecista o suficiente para garantir 50 posicionamentos, mas, no que diz respeito a um algoritmo, é muito ruim.
Comintern
Muito do desempenho ruim vem de mim, não memorizando a tabela de fim de jogo ( y). Isso é realmente óbvio, pois o segundo passo não é rápido quando já consideramos o final do jogo. Estou indo ao pub hoje à noite, mas se tiver a chance amanhã, tornarei isso menos terrível.
precisa saber é
7

C, atualmente 2552 caracteres não-espaço em branco que não são comentários

A contagem indica para mim que eu poderia jogar abaixo de 2552 caracteres totais, mas, como já existe uma resposta menor (que será difícil de bater), considerarei isso cuidadosamente antes de me preocupar em fazê-lo. É verdade que existem cerca de 200 caracteres para exibir o quadro e outros 200 para verificar a entrada do usuário tanto na posição inicial quanto na movimentação (o que eu preciso para testar, mas poderia eliminar).

Nenhuma árvore de jogo aqui, apenas algoritmo codificado, então ele se move instantaneamente.

As posições iniciais são inseridas como a linha (1-8) da coluna (1-8) numerada no canto superior direito e o programa funciona no mesmo esquema. Portanto, se você girar a tela 90 graus no sentido anti-horário, seguirá a notação quadrada numérica padrão do xadrez por correspondência. Posições em que o rei preto já está sob controle são rejeitadas como ilegais.

Os movimentos pretos são inseridos como um número de 0 a 7, com 0 sendo um movimento para o norte, 1 para o nordeste e assim por diante no sentido horário.

Não segue o algoritmo comumente conhecido que usa exclusivamente a torre sob a proteção do rei branco para restringir o rei preto. A torre apenas restringe o rei preto no sentido vertical (e foge horizontalmente se for perseguida.) O rei branco restringe o rei preto em movimento horizontal. Isso significa que as duas peças brancas não se interpõem.

Eu pareço ter resolvido a maioria dos bugs e possíveis loops infinitos, está funcionando muito bem agora. Amanhã vou jogar novamente e ver se há mais alguma coisa que precise ser consertada.

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

}

Aqui está um acabamento típico (às vezes, o posicionamento pode ocorrer em qualquer lugar na borda direita ou esquerda do quadro.)

insira a descrição da imagem aqui

Level River St
fonte
6

Bash, 18 (ou -32?)

Ok, esta é uma resposta de brincadeira. Como as pretas são um bom jogador de xadrez, e as pretas sabem que as brancas também são um bom jogador de xadrez, ele decide que a única coisa sensata a fazer é:

echo Black resigns

Isso resulta em vitórias em branco, que atendem às especificações.

Tecnicamente, você pode inserir as posições atuais como argumentos também, o programa as ignora, portanto, sem dúvida, isso pode se qualificar para o bônus de -50.

user12205
fonte
Engraçado, mas eu atualizei as regras. Jogar até xeque-mate agora é obrigatório.
izabera
11
Entre a pergunta original afirma claramente que seu programa pode permitir que um jogador humano ou aleatório use preto, e o seu não é aleatório.
Izabera
2
Usando a notação padrão, você pode produzir 1-0um pouco mais curto.
Daniero
11
@ Interntern bem real quando perder ótimo geralmente significa durar mais tempo.
PyRulez #
@PyRulez de acordo com a wikipedia , "Qualquer jogador pode se demitir a qualquer momento e seu oponente vence o jogo." Além disso, esta é apenas uma resposta de brincadeira, não leve tão a sério.
user12205