Um guia passo-a-passo para construir uma simples IA de xadrez

Vamos explorar alguns conceitos básicos que nos ajudarão a criar uma AI simples de xadrez:

  • mover-geração
  • avaliação do conselho
  • minimax
  • e poda alfa beta.

Em cada etapa, melhoraremos nosso algoritmo com uma dessas técnicas de programação de xadrez testadas pelo tempo. Vou demonstrar como cada um afeta o estilo de jogo do algoritmo.

Você pode ver o algoritmo AI final aqui no GitHub .

Etapa 1: Mova a visualização da geração e da placa

Usaremos a biblioteca chess.js para geração de movimento e o chessboard.js para visualizar a placa. A biblioteca de geração de movimentos basicamente implementa todas as regras do xadrez. Com base nisso, podemos calcular todos os movimentos legais para um determinado estado de tabuleiro.

Uma visualização da função de geração de movimento. A posição inicial é usada como entrada e a saída é todos os movimentos possíveis daquela posição.

O uso dessas bibliotecas nos ajudará a se concentrar apenas na tarefa mais interessante: criar o algoritmo que encontra o melhor movimento.

Vamos começar criando uma função que apenas retorna um movimento aleatório de todos os movimentos possíveis:

Embora este algoritmo não seja um jogador de xadrez muito sólido, é um bom ponto de partida, já que podemos jogar contra ele:

O preto joga movimentos aleatórios. Jogável em https://jsfiddle.net/lhartikk/m14epfwb/ 4

Etapa 2: avaliação de posição

Agora vamos tentar entender qual lado é mais forte em uma determinada posição. A maneira mais simples de conseguir isso é contar a força relativa das peças no tabuleiro usando a seguinte tabela:

Com a função de avaliação, podemos criar um algoritmo que escolhe o movimento que fornece a avaliação mais alta:

A única melhoria tangível é que o nosso algoritmo irá agora capturar uma peça se puder.

O preto joga com o auxílio da função de avaliação simples. Jogável em https://jsfiddle.net/lhartikk/m5q6fgtb/1/

Etapa 3: pesquisar árvore usando Minimax

Em seguida, vamos criar uma árvore de pesquisa 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 a uma dada profundidade, e a posição é avaliada nas “folhas” finais da árvore.

Depois disso, retornamos o menor ou o maior valor do filho para o nó pai, dependendo se é um branco ou preto para ser movido. (Ou seja, tentamos minimizar ou maximizar o resultado em cada nível.)

Uma visualização do algoritmo minimax em uma posição artificial. O melhor movimento para o branco é b2-c3 , porque podemos garantir que podemos chegar a uma posição em que a avaliação é -50

Com o minimax no lugar, nosso algoritmo está começando a entender algumas táticas básicas do xadrez:

Minimax com nível de profundidade 2. Jogável em: https://jsfiddle.net/k96eoq0q/1/

A eficácia do algoritmo minimax é fortemente baseada na profundidade de pesquisa que podemos alcançar. Isso é algo que vamos melhorar na etapa seguinte.

Etapa 4: Poda Alfa-beta

A remoção de alfa-beta é um método de otimização para o algoritmo minimax que nos permite desconsiderar algumas ramificações na árvore de busca. Isso nos ajuda a avaliar a árvore de busca minimax muito mais profundamente, usando 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 leve a uma situação pior do que um movimento descoberto anteriormente.

A poda alfa-beta não influencia o resultado do algoritmo minimax – só o torna mais rápido.

O algoritmo alfa-beta também é mais eficiente se acontecer de visitar primeiro os caminhos que levam a bons movimentos.

As posições que não precisamos explorar se a remoção de alfa-beta for usada e a árvore for visitada na ordem descrita.

Com o alpha-beta, obtemos um aumento significativo no algoritmo minimax, como mostra o exemplo a seguir:

O número de posições necessárias para avaliar se queremos realizar uma pesquisa com profundidade de 4 e a posição “raiz” é a que é mostrada.

Siga este link para experimentar a versão melhorada alpha-beta da IA ??do xadrez.

Etapa 5: Função de avaliação aprimorada

A função de avaliação inicial é bastante ingênua, pois contamos apenas o material encontrado no quadro. Para melhorar isso, adicionamos à avaliação um fator que leva em conta a posição das peças. Por exemplo, um cavaleiro no centro do tabuleiro é melhor (porque tem mais opções e é, portanto, mais ativo) do que um cavaleiro na borda do tabuleiro.

Usaremos uma versão ligeiramente ajustada das tabelas de peças quadradas originalmente descritas no wiki de programação de xadrez .

As tabelas visualizadas de peça quadrada visualizadas. Podemos diminuir ou aumentar a avaliação, dependendo da localização da peça.

Com a seguinte melhoria, começamos a obter um algoritmo que joga um xadrez “decente”, pelo menos do ponto de vista de um jogador casual:

Avaliação aprimorada e poda de alfa-beta com profundidade de pesquisa de 3. Reproduzível em https://jsfiddle.net/q76uzxwe/1/

Conclusões

A força de um simples algoritmo de jogar xadrez é que ele não comete erros estúpidos. Dito isto, ainda falta compreensão estratégica.

Com os métodos que introduzi aqui, conseguimos programar um algoritmo de jogo de xadrez que pode jogar xadrez básico. A “parte AI” (exclusão de geração de movimento) do algoritmo final é de apenas 200 linhas de código, o que significa que os conceitos básicos são bastante simples de implementar. Você pode conferir se a versão final está no GitHub .

Algumas outras melhorias que poderíamos fazer no algoritmo seriam, por exemplo:

Se você quiser aprender mais, confira o wiki de programação de xadrez . É um recurso útil para explorar além desses conceitos básicos que apresentei aqui.

Obrigado pela leitura!

Deixe uma resposta

O seu endereço de e-mail não será publicado. Campos obrigatórios são marcados com *