Há alguns anos comecei a escrever uma engine de xadrez. Já contei essa história aqui no blog. Parei e continuei várias vezes. Mas resumidamente, comecei o desenvolvimento, cheguei no ponto do programa realizar movimentos com uma inteligência mínima, mas muito longe de me ganhar (na verdade, ele não conseguiria aplicar xeque-mate a menos que ele fosse extremamente óbvio, mas fazia um meio jogo com algum sentido). Parei o desenvolvimento, iniciei uma faculdade e xadrez computacional virou tema do meu trabalho de conclusão de curso.
Nesta sequência de postagens eu vou mostrar o passo a passo da construção de uma engine. Vou começar do zero 🙂 É um hobby que pretendo retomar de maneira estruturada e com algum método. O objetivo é conseguir ser vencido pelo programa.
Funcionalidades
Um programa de computador capaz de jogar xadrez pode ser tão simples quanto possível, ou tão robusto quanto necessário. Algumas funcionalidades são essenciais. A maneira como o tabuleiro é representado, como a posição vai ser avaliada e como o programa vai interagir com um ser humano são algumas das necessidades mais imediatas.
Ela será escrita em linguagem Kotlin para rodar na plataforma java e vai se chamar ANKOBACHEN (Another Kotlin Based Chess Engine).
Listo a seguir algumas das funcionalidades que vou considerar o trabalho que pretendo fazer.
Representação do tabuleiro e das peças
A representação do tabuleiro e das peças é uma parte fundamental no desenvolvimento de uma engine de xadrez. Diferentes métodos de representação têm implicações diretas na eficiência e eficácia da geração de movimentos, avaliação de posições e execução de algoritmos de busca.
A presentação que será usada é a de bitboards, amplamente utilizada nas mais diversas engines por aí. Essa representação usa 64 bits (um para cada casa do tabuleiro) para representar a presença de peças, com diferentes bitboards para diferentes tipos de peças. Apesar de ser um pouco mais complicada de entender e implementar, tem a vantagem de ser extremamente eficiente para operações bit a bit e paralelização. Permite rápidas operações de geração e avaliação de movimentos.
Geração de movimentos
A geração de movimentos é um componente crucial em uma engine de xadrez, responsável por criar todas as possíveis jogadas legais a partir de uma posição dada no tabuleiro. Este processo envolve considerar as regras do xadrez para cada tipo de peça e garantir que os movimentos gerados sejam válidos.
A geração de movimentos está totalmente atrelada à forma como o tabuleiro está representado e precisa ser capaz de indicar movimentos de captura, xeque, xeque-mate, roque, en passant, etc. É a patir dos movimentos gerados que a função de busca consegue percorrer todas as possibilidades e avaliar os pontenciais movimentos candatos.
Função de avaliação
A função de avaliação é, basicamente, um algoritmo que determina o quão boa é uma posição, uma disposição das peças em um determinado momento. Para um computador saber qual é o melhor movimento a se fazer, na teoria, basta calcular todos os movimentos possíveis até chegar em uma posição de xeque-mate. Mas isso não é possível, são mais possibilidades que o número de átomos em todo universo. Com essa limitação, o computado calcula possibilidades até onde é possível dentro dos limites computacionais e de tempo.
Como não é possível enxergar até o xeque-mate, o computador avalia uma posição em termos de vantagem para peças pretas ou brancas. De maneira simples, se um lado tiver um bispo a mais, isso pode ser usado como fator determinante para avaliar que o jogador com esse bispo a mais está melhor. Na prática, existem centase de pequenos fatores que determinam se um jogador está em vantagem, alguns desses fatores são naturalmente aplicados por jogadores humanos durante uma partida.
Uma rede neural também pode ser usada como função de avaliação de uma posição de xadrez. Particularmente, sou fascinado por esse método porque não precisamos programar cada uma das características que determinam a qualidade de uma posição. A rede neural, durante o treinamento, simplesmente aprende essas coisas. No entanto, realizar esse treinamento é computacionalmente muito caro. A rede precisa ser treinada com milhões de partidas, posições e o máximo de diversidade possível para que o máximo de características sejam aprendidas.
Pare o software que vou construir, aplicarei ambos os métodos de avaliação. Treinar a rede a ponto de ficar boa para me vencer talvez não seja factível (lembrando que “me vencer” não significa que eu seja bom, mas que nem pra isso um único computador seja capaz de alcançar em tempo razoável).
Algoritmos de busca
Os algoritmos de busca são componentes muito importantes em uma engine de xadrez, permitindo que ela explore as possíveis sequências de movimentos para encontrar o melhor lance. Os algoritmos de busca ajudam a engine a avaliar milhões de posições em um curto período de tempo, aplicando diversas técnicas para otimizar o processo de tomada de decisão.
É necessário uma sinergia entre algoritmo de busca e função de avaliação. Como a quantidade de movimentos possíveis é muito grande, a busca precisa focar no que é potencialmente mais importante e é papel do algoritmo de busca tomar esse tipo de decisão.
A engine de xadrez que pretendo implementar pode usar algoritmos mais simples. Implementar boas soluções é algo bastante complicado do ponto de vista da lógica de programação. Essa é uma etapa que vai ser revisitada e melhorada gradualmente.
FEN – Forsyth-Edwards Notation
FEN é uma notação para descrever posições específicas no xadrez. É amplamente usada para registrar estados de tabuleiro em jogos de xadrez e para reiniciar jogos a partir de posições específicas. Uma engine deve ser capaz de ler e escreve posições a partir da FEN para os mais diversos fim. Durante o desenvolvimento, isso é bastante útil para os testes.
A FEN descreve a posição das peças, o lado que tem a vez de jogar a partir da posição descrita, os movimentos de roque que estão disponíveis, en passant e contadores de movimento.
Exemplo de FEN para a posição inicial do xadrez.
rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1Mais informações sobre a FEN: https://www.chessprogramming.org/Forsyth-Edwards_Notation
PGN – Portable Game Notation
PGN é um formato de arquivo utilizado para armazenar e compartilhar partidas com todos seus movimentos de forma legível e padronizada. É amplamente usado em bases de dados de xadrez, programas de análise, sites e publicações de xadrez. A notação PGN inclui informações detalhadas sobre a partida, como os jogadores, data, local e movimentos jogados, facilitando a leitura e a análise por humanos e máquinas. É um formato cuja implementação de leitura e escrita é simples em uma computador, além de ser legível para humanos.
Logo, é muito importante uma engine ser capaz de ler e escrever partidas de xadrez em formato PGN. Isso também serve submeter partidas à engine e testar se ela fará os movimentos que são esperados a fim de testar o poder de jogo.
Exemplo de PGN com a partida entre Bobby Fischer e Boris Spassky pelo campeonato mundial de 1972.
[Event "Spassky - Fischer World Championship Match"]
[Site "Reykjavik ISL"]
[Date "1972.07.23"]
[EventDate "?"]
[Round "6"]
[Result "1-0"]
[White "Robert James Fischer"]
[Black "Boris Spassky"]
[ECO "D59"]
[WhiteElo "?"]
[BlackElo "?"]
[PlyCount "81"]
1. c4 e6 2. Nf3 d5 3. d4 Nf6 4. Nc3 Be7 5. Bg5 O-O 6. e3 h6
7. Bh4 b6 8. cxd5 Nxd5 9. Bxe7 Qxe7 10. Nxd5 exd5 11. Rc1 Be6
12. Qa4 c5 13. Qa3 Rc8 14. Bb5 a6 15. dxc5 bxc5 16. O-O Ra7
17. Be2 Nd7 18. Nd4 Qf8 19. Nxe6 fxe6 20. e4 d4 21. f4 Qe7
22. e5 Rb8 23. Bc4 Kh8 24. Qh3 Nf8 25. b3 a5 26. f5 exf5
27. Rxf5 Nh7 28. Rcf1 Qd8 29. Qg3 Re7 30. h4 Rbb7 31. e6 Rbc7
32. Qe5 Qe8 33. a4 Qd8 34. R1f2 Qe8 35. R2f3 Qd8 36. Bd3 Qe8
37. Qe4 Nf6 38. Rxf6 gxf6 39. Rxf6 Kg8 40. Bc4 Kh8 41. Qf4 1-0Um pouco mais sobre PGN (especificação, regras, sintaxe, etc): http://www.saremba.de/chessgml/standards/pgn/pgn-complete.htm
Base de abertuas
Uma base de aberturas é um recurso essencial no xadrez que compila uma ampla coleção de sequências de movimentos iniciais usadas em partidas. Essas sequências são baseadas tanto na teoria quanto na prática histórica de jogos, incluindo partidas de mestres e grandes mestres. A base de aberturas é utilizada por jogadores de todos os níveis para estudar e memorizar aberturas eficazes, preparando-se melhor para partidas competitivas.
Depois de algum tempo, mesmo os jogados mais iniciantes, percebem que iniciar o jogo fazendo alguns movimentos é bastante ruim. Esse conhecimento pode ser utilizado para evitar que o computador realize cálculos em cima de movimentos que são sabidamente ruins. Mesmo que a engine que pretendo construir seja muito mais um hobby que um objetivo competitivo, ainda assim é válido usar uma base de abertuas.
Existem bases de abertuas na internet com os mais diversos tamanhos, alguams até pagas, usadas por jogadores profissionais de elite. O xadrez jogado em altíssimo nível tem um pouco de decoreba.
Um pouco mais sobre abertuas: https://pt.wikipedia.org/wiki/Abertura_(xadrez)
Endgame tablebases
Da mesma forma que existem bases para o início de jogo, também há para o fim. Para qualquer posição com até 7 peças no tabuleiro, o xadrez já foi resolvido. Isto é, a sequência de movimentos que leva ao resultado já está catalogada. São quase 500 trilhões de posições.
Assim, é importante uma engine conseguir ler uma base de finais. Mas programar o computador conseguir vencer um final de partida também deve ser muito divertido. Dessa forma, ambas as funcionalidades estaram implementadas.
Para navegar e testar posições usando a base de finais Syzygy: https://syzygy-tables.info/
Integração com Lichess
Lichess é uma das plataformas de xadrez online mais populares e amplamente utilizadas no mundo. Foi fundada por Thibault Duplessis em 2010, gratuita e de código aberto, oferecendo uma ampla gama de recursos para jogadores de todos os níveis, desde iniciantes até grandes mestres.
Além de todos os recursos para jogo, a plataforma oferece APIs para integração. Dessa forma, é possível uma engine rodando em qualquer lugar integrar com o site e alguém jogar com ela (possivelmente eu).
Site do Lichess: https://lichess.org/
Base de dados com as partidas jogadas no Lichess (quase 6 bilhões): https://database.lichess.org/
UCI – Universal Chess Interface
O UCI é um protocolo amplamente utilizado para permitir a comunicação entre engines de xadrez e interfaces de usuário. Desenvolvido por Stefan Meyer-Kahlen, criador a engine Shredder, o UCI se tornou um padrão de fato na comunidade de xadrez, proporcionando uma forma consistente e eficiente de integrar diferentes engines de xadrez com várias interfaces gráficas e ferramentas de análise. Também pode ser usado como menismo para que duas engines joguem entre si.
Com tudo isso, para que uma engine possa ser usada em diferentes programas de análise, implementar protocolo UCI é essencial.
Link para download da especificação do UCI: https://www.shredderchess.com/chess-features/uci-universal-chess-interface.html
Mais informações sobre o UCI: https://www.chessprogramming.org/UCI
Conclusão
É isso! Se você se interessa por xadrez computacional, penso que estas postagens podem ser um ótimo ponto de partida para iniciar uma implementação de um programa de computador capaz de jogar xadrez.
Todas as postagens da série ANKOBACHEN
- Construindo uma engine de xadrez # Parte 1: ANKOBACHEN – Definições
- Construíndo uma engine de xadrez # Parte 2: Um parser de FEN escrito em Kotlin
Abraços!
