Sou um entusiasta do xadrez e programador. Recentemente, decidi começar a fazer um mecanismo de xadrez usando meus conhecimentos de xadrez e programação. Então aqui está a minha pergunta:
Qual linguagem (eu estou familiarizado com Java, C ++ e Python) e metodologia devo adaptar ao escrever um mecanismo de xadrez?
Um pouco de orientação seria muito apreciado.
Editar:
Então eu decidi fazê-lo em JavaScript. Eu baixo essa interface do Xadrez do github e agora estou pronto! Meu primeiro passo seria escrever movimentos legais para isso. Então, alguém pode me apontar na direção certa? (Eu sou novo no jQuery, mas tenho muita experiência em programação).
PS: Não estou tentando criar um mecanismo muito eficiente (sei que é muito difícil), só quero me familiarizar com o processo e aprender algumas novas técnicas ao longo do caminho.
fonte
Respostas:
Jogador de xadrez com classificação 2072 aqui. Eu criei este site em JavaScript puro durante um fim de semana. Não é um mecanismo de xadrez (eu o projetei para criar posições de abertura divertidas como uma espécie de mecanismo perverso do Chess960), mas é um ponto de partida. O código fonte está aqui .
Existem muitas complicações envolvidas na criação de uma placa funcional. Esses incluem:
Todos os mecanismos de xadrez funcionam olhando para todos (possivelmente um subconjunto heuristicamente determinado) dos movimentos legais em uma posição e avaliando os números para representar seus valores relativos, fazendo esses movimentos e fazendo recursivamente o mesmo para as posições resultantes. Seus problemas gêmeos aqui são
Tudo isso além de projetar o algoritmo em primeiro lugar, com informações disponíveis em abundância.
Quanto a qual idioma usar (embora eu ache que você já tenha decidido o JavaScript), acho que depende mais do seu objetivo do que qualquer outra coisa. Eu queria fazer o meu online (e melhorar o JavaScript), então o JavaScript foi a minha escolha. Qualquer linguagem de programação orientada a objetos o fará.
Depois de se sentir confortável com o que está fazendo, os seguintes recursos provavelmente serão realmente úteis:
Boa sorte!
fonte
O problema com o "programa de xadrez" como conceito é que existem muitas peças que podem absorver muito tempo e não necessariamente interessam a você no momento. Você pode passar anos trabalhando apenas em gráficos, ou em uma pesquisa alfa-beta ou em uma visualização para ajudar a desenvolver o mecanismo de pesquisa, ou ... bem, existem muitas peças.
Eu recomendo encontrar um programa de xadrez de código aberto (deve haver muitos) e começar a melhorar as partes que mais lhe interessam. Você pode eventualmente substituir o programa inteiro, uma função de cada vez, ou aprender o suficiente e estar motivado para jogá-lo fora e criar seu próprio programa a partir do zero. De qualquer forma, a chave é iniciar a "luz" e aprender as cordas antes de tentar arquitetar um programa inteiro.
fonte
Se você está familiarizado com as regras do xadrez, um bom ponto de partida sobre técnicas básicas é http://www.frayn.net/beowulf/theory.html Uma extensa coleção de materiais e links que você pode encontrar aqui: http: // chessprogramming .wikispaces.com / E terceiro: aprenda com o código de outras pessoas. Dê uma olhada nas fontes de Crafty . É o principal mecanismo de código aberto. Muito importante será pensar nos casos de teste, para ver se você faz melhorias: Comece por exemplo com algumas posições simples e fáceis de final de jogo com 3 ou 4 figuras.
fonte
Como mencionado, não há nada terrivelmente difícil em construir um mecanismo de xadrez. Talvez você deva se concentrar em como deseja usar e (potencialmente) implantar esse aplicativo, pois isso provavelmente determinará sua escolha de idioma.
Se este é apenas um exercício divertido, convém codificá-lo em Javascript e implantá-lo como uma página da web. Se você nunca quiser transformá-lo em um jogo de xadrez experiente, pelo menos outros poderão jogar com ele e seu código-fonte.
Se você deseja aprender uma tecnologia específica ao mesmo tempo, digamos WPF, essa pode ser uma boa maneira de matar dois coelhos com uma cajadada só. O MVVM pode ser um exagero para este aplicativo, mas você aprenderá pelo menos.
Se você deseja segmentar dispositivos Android, o Java seria uma boa escolha. Da mesma forma, Objective-C para dispositivos iOS.
Longo e curto, a escolha do idioma não existe no vácuo.
fonte
Suponho que você já conheça o conceito de Min-Max, árvores e poda, heurística e outras noções básicas e o que escrevo aqui são apenas alguns detalhes que podem ter sido subestimados.
Na companhia de um amigo, escrevi nosso próprio mecanismo de xadrez algumas vezes atrás. Compartilho algumas questões e idéias que tivemos e espero que você as ache úteis.
Como nós dois éramos programadores de Java, nossa linguagem transformou-se em Java e começamos com uma abordagem orientada a objetos. Peças eram objetos, tabuleiro era objeto, arquivos e fileiras (linhas e colunas na literatura de xadrez) eram objetos. E isso estava errado. A sobrecarga era enorme e o programa estava lutando para ir além de 2 movimentos (4 dobras) na árvore de pesquisa.
Assim, com algumas pesquisas, acabamos com uma idéia brilhante (embora não a nossa!): Representar peças e tabuleiro como números inteiros longos (64 bits). Isso faz sentido porque um tabuleiro de xadrez tem 64 quadrados. O resto foram operações um pouco sábias (rodando muito perto da CPU = extremamente rápido). Por exemplo, considere um número inteiro binário de 64 bits no qual os que estão apresentando os quadrados no quadro que sua peça pode atacar. Agora, se você executar um "AND" lógico entre dois números como esse, um resultado diferente de zero indicará que você tem um quadrado com atacantes. Existem várias maneiras de apresentar o tabuleiro e as peças de xadrez:
Então você precisa e abrir o banco de dados. A abertura do xadrez é de alguma forma resolvida e é altamente recomendável ter um livro de abertura. Nesse caso, você tem muito tempo extra em jogos de blitz.
Fizemos isso, mas ainda estávamos longe de ser bons:
Então o que fizemos então foi usar o tempo morto (se é um mecanismo humano versus computador).
E ainda estávamos longe de 12 dobras. Com mais estudos, descobrimos alguns truques! Por exemplo, foi sugerido pular uma dobra da árvore e começar da seguinte (como se não houvesse oponente). A idéia é que, se um movimento é extremamente idiota, por que perder tempo e ver quais são as respostas dos oponentes a esse movimento? No entanto, um bom mecanismo deve ser capaz de distinguir entre movimento idiota e sacrifício da rainha genial.
Eu e meu amigo, nesse estado, ainda éramos ruins: / O que poderíamos fazer - e parcialmente fizemos - foi salvar as posições calculadas. Se você calcular uma posição, salve-a para o futuro! O mesmo vale para loops na árvore de pesquisa. O objetivo era salvar / recuperar de forma eficiente:
e finalmente:
Esse problema é extremamente caro, tanto no tempo como na memória da CPU. É muito importante escrever seu código com muita eficiência. Lembre-se de que estamos falando do fator de ramificação 35. Isso significa que um "se" inútil em algum lugar da sua heurística pode se transformar em um
3.3792205e+18"se" inútil em algum lugar profundo da sua árvore de pesquisa.A programação de xadrez é um desafio muito muito interessante e é o momento de colocar seus recursos de programação em um teste sério. Há mais alguns pontos que posso sugerir, mas tenho certeza que você os descobrirá por si mesmo. Há muitos outros pontos que eu não sei, mas você pode encontrá-los na internet!
Boa sorte e divirta-se!
ps Eu não conheço javascript muito bem, mas algo está me dizendo a base da dificuldade do problema, talvez, considerando tudo o que o C ++ possa oferecer, seria melhor descartar o javascript e fazê-lo em C ++.
fonte
De acordo com sua edição, você está pronto para definir movimentos "legais".
Existem duas maneiras de descrever jogadas no xadrez. Notação descritiva e notação algébrica . O que você provavelmente quer é uma função que tome a peça, a posição inicial e a posição final como parâmetros. por exemplo. O Knight de QN1 a QB2 é inválido, mas o Knight de QN1 a Q2 é válido. Pensando nisso, a notação algébrica pode ser mais simples devido à capacidade de calcular facilmente o posicionamento 'relativo'.
Para garantir que você esteja escrevendo a quantidade mínima de código necessária, eu começaria escrevendo testes para essa função primeiro . Se você estiver usando notação algébrica, provavelmente não precisará de um teste por peça / início / fim. Faça com que cada teste funcione e refatore a duplicação antes de passar para o próximo 'movimento'. Seu código terminará mais limpo.
Depois de cobrir suficientemente os movimentos legais e ilegais de cada peça, eu começaria a adicionar testes para outras variáveis (como mover um rei para as condições de 'check' e 'mate').
Eu recomendo o qunit para testes de unidade e o jasmim para testes comportamentais em JavaScript.
fonte
Na verdade, eu escrevi um mecanismo de xadrez. Prepare-se para um deleite e um pesadelo. Quando meus amigos e eu fizemos isso, foi em um concurso de programação cronometrada e a linguagem que decidimos seguir era o Java. Eu sinto que Java ou C é sua melhor escolha, mas vejo que você decidiu usar o Javascript. Eu realmente não posso bater porque não estou familiarizado com isso.
O principal problema aqui será que existem tantos cenários de movimento / vitória em cada peça que você precisa levar em consideração, por isso recomendo que você escreva todas essas situações possíveis para cada peça antes de começar a codificar. Se pular sem planejar, esse projeto divertido será uma tarefa repetitiva. Mas essa é realmente a principal coisa. Apenas planeje fora do código primeiro e verifique se você obtém todos os cenários de uma peça de cada vez.
Boa sorte
fonte
Para a parte de decisões do jogador do computador, não posso recomendar o suficiente o livro "Inteligência Artificial: Uma Abordagem Moderna" (site do livro http://aima.cs.berkeley.edu/ ). Dependendo do seu conhecimento em matemática (a teoria dos grafos ajuda), pode ser um pouco alto, mas é escrito da maneira mais simples possível, e contém uma visão geral (e alguma profundidade) das técnicas para faça programas decidirem coisas.
Ele indicará coisas para você, como declarar uma meta (por exemplo, xeque-mate ou nulo), avaliar a proximidade de um determinado estado (layout da placa) com essa meta, como gerar os diferentes estados possíveis a partir do atual e como atravessar o que é um imenso espaço problemático.
Uma coisa que pode ajudar na criação de um algoritmo de IA é descobrir como decidir qual jogada jogar a seguir, como se você tivesse todo o tempo do mundo, começando em uma situação muito próxima a um jogo ganho. Você o otimiza para encontrar uma solução em um período de tempo razoável (horas) e, em seguida, encontra maneiras de escolher um caminho vencedor, mesmo que ainda não tenha explorado todos os resultados, para poder realmente interromper o "pensamento" para um turno vale a pena.
Somente então eu procuraria otimizar a representação para acelerar os cálculos individuais, como o uso de números inteiros longos, conforme sugerido. Não importa a rapidez com que você possa fazer uma comparação única, se a maneira como percorrer o espaço do problema não tiver uma boa heurística, levará anos para isso.
fonte
Você pode realmente ir da maneira que quiser, mas estes são meus pensamentos sobre o assunto:
Eu usaria Java, pois isso permite que você seja de alto nível e tenha bibliotecas de interface do usuário (AWT, Swing) à sua disposição direta. Você pode usar uma abordagem orientada a objetos para modelar o tabuleiro e as peças de xadrez. Outros objetos podem substituir o histórico e a pontuação dos movimentos. Até os jogadores podem ser objetos e, no futuro, você poderá estender sua
Playerclasse para fornecer um reprodutor de computador inteligente e artificial.Você pode dar uma olhada no MVC (Model-View-Controller) pois é uma abordagem muito boa nesse caso para vincular seus objetos de modelo (modelo de domínio) à interface do usuário (visualização) e permitir que o usuário manipule o modelo (através do controlador).
Você também pode aplicar o desenvolvimento orientado a teste , que não apenas garante que todos os métodos se comportem da maneira que você espera, mas também obriga a escrever um código modular testável.
fonte
As próprias regras do xadrez são bastante simples. Você só precisa criar uma matriz (matriz bidimensional) para o quadro e encontrar uma maneira de codificar os conceitos das peças, as regras de movimento de cada peça, a validação de que um movimento é legal e as condições que sinalizam o fim do jogo. Nada de particularmente difícil nisso. Você deve usar qualquer idioma com o qual esteja mais familiarizado.
Agora, se você quiser criar uma IA de xadrez que assuma o papel de um dos jogadores, é aí que as coisas ficam complicadas. Mas, novamente, a escolha do idioma não é o maior problema aqui; é entender os princípios de IA envolvidos. Esse será um fator muito mais importante.
(Dito isso, esse tipo de tomada de decisão pode ser extremamente intensivo em termos de computação, e você provavelmente desejará usar algo que compila o código nativo em vez de uma linguagem de script. E o C ++ é uma escolha muito ruim, não porque não esteja bem. - adequado a esse problema, mas simplesmente porque é uma linguagem muito ruim em geral, e tentar implementar coisas complexas é uma boa maneira de codificar todos os tipos de dores de cabeça para você.)
fonte