Artigo original: A step-by-step guide to building a simple chess AI
Escrito por: Lauri Hartikka
Vamos examinar alguns conceitos básicos que nos ajudarão a criar uma IA de xadrez simples:
- geração de movimentos
- avaliação do tabuleiro
- minimax
- e poda alfa-beta.
Em cada passo, melhoraremos nosso algoritmo com uma dessas técnicas comprovadas de programação de xadrez. Demonstrarei como cada uma delas afeta o estilo de jogo do algoritmo.
Você pode ver o algoritmo final da IA aqui no GitHub.
Passo 1: geração de movimentos e visualização do tabuleiro
Usaremos a biblioteca chess.js para a geração de movimentos e a chessboard.js para a visualização do tabuleiro. A biblioteca de geração de movimentos, basicamente, implementa todas as regras do xadrez. Com base nisso, podemos calcular todos os movimentos legais em um determinado estado do tabuleiro.
Usar essas bibliotecas nos ajudará a nos concentrarmos apenas na tarefa mais interessante: criar o algoritmo que encontra o melhor movimento.
Começaremos criando uma função que apenas retorna um movimento aleatório a partir de todos os movimentos possíveis:
Embora esse algoritmo não seja um jogador de xadrez dos melhores, ele é um bom ponto de partida, pois já podemos, de fato, jogar contra ele:
Passo 2 : avaliação da posição
Agora, tentaremos entender que lado é o mais forte em determinada posição. O modo mais simples de se conseguir isso é contar a força relativa das peças no tabuleiro usando a tabela a seguir:
Com a função de avaliação, conseguimos criar um algoritmo que escolhe o movimento que dá a avaliação mais alta:
A única melhoria clara é o fato de, agora, nosso algoritmo procurar capturar uma peça sempre que puder.
Passo 3: árvore de busca usando o minimax
Em seguida, vamos criar uma árvore de busca a partir da qual o algoritmo pode escolher o melhor movimento. Isso é feito usando o algoritmo minimax.
Neste algoritmo, a árvore recursiva de todos os movimentos possíveis é explorada até uma determinada profundidade. A posição é avaliada nas "folhas" mais extremas (finais) da árvore.
Depois disso, retornamos o valor menor ou maior do nó pai, dependendo de ser um movimento das brancas ou das pretas (ou seja, tentamos minimizar ou maximizar o resultado em cada nível).
Com o minimax atuando, nosso algoritmo começa a entender algumas táticas básicas do xadrez:
A eficácia do algoritmo minimax é em grande parte baseada na profundidade da busca que podemos atingir. Isso é algo que melhoraremos no próximo passo.
Passo 4: poda alfa-beta
A poda alfa-beta é um método de otimização que nos permite desconsiderar alguns dos ramos da árvore de busca. Isso nos ajuda a avaliar a árvore de busca minimax com muito mais profundidade, embora usemos os mesmos recursos.
A poda alfa-beta é baseada na situação em que podemos parar de avaliar uma parte da árvore de busca se encontrarmos um movimento que leva a uma situação pior em comparação com um movimento descoberto anteriormente.
A poda alfa-beta não influencia o resultado do algoritmo minimax — ela só o torna mais rápido.
O algoritmo alfa-beta também fica mais eficiente se visitamos primeiro aqueles caminhos que levam a bons movimentos.
Com a poda alfa-beta, obtemos uma melhoria significativa no algoritmo minimax, conforme vemos no exemplo a seguir:
Siga este link se quiser testar a versão melhorada da IA de xadrez com a poda alfa-beta.
Passo 5: função de avaliação melhorada
A função de avaliação inicial é bem ingênua, pois avaliamos apenas o material encontrado no tabuleiro. Para melhorá-la, adicionamos à avaliação um fator que leva em consideração a posição das peças. Por exemplo, um cavalo no centro do tabuleiro é melhor (por ter mais opções e, portanto, ser mais ativo) do que um cavalo em um dos cantos do tabuleiro.
Usaremos uma versão levemente ajustada das tabelas peça-posição descritas originariamente na chess-programming-wiki (site em inglês).
Com essa melhoria, começamos a ter um algoritmo que joga xadrez relativamente bem, ao menos do ponto de vista de um jogador amador:
Conclusões
A força de um algoritmo de jogo de xadrez simples é o fato de não cometer erros idiotas. Dito isso, saiba que ele ainda não tem o entendimento estratégico.
Com os métodos que apresentei aqui, conseguimos programar um algoritmo para jogar xadrez que pode jogar um xadrez básico. A "parte da IA" (excluindo a geração de movimentos) do algoritmo final é de apenas 200 linhas de código, o que significa que os conceitos são bastante simples de se implementar. Confira a versão final no GitHub.
Outras melhorias podem ser feitas no algoritmo (textos em inglês), por exemplo:
- ordenação dos movimentos
- geração de movimentos mais rápida
- e avaliação específica de final de jogo.
Se quiser aprender mais, confira a chess programming wiki (site em inglês). É um recurso muito útil para explorar que vai além dos conceitos básicos apresentados aqui.
Obrigado pela leitura!