Traduzimos para você um artigo de Lauri Hartikka sobre a criação da IA mais simples para o xadrez. Foi redigido em 2017, mas os princípios básicos permaneceram os mesmos. Todos os arquivos que Lori usou também estão disponíveis.
Inteligência artificial simples que pode jogar xadrez pode ser criada com base em quatro conceitos:
- 1. Movendo-se;
- 2. Avaliação do conselho;
- 3. Minimax ;
- 4. Recorte alfa alfa . Em cada estágio do trabalho com o algoritmo, um deles será usado, isso melhorará gradualmente os recursos de jogo da IA.
A Skillbox recomenda: O Curso Online Aplicado do Python Data Analyst .
Lembramos que: para todos os leitores de "Habr" - um desconto de 10.000 rublos ao se inscrever em qualquer curso Skillbox usando o código promocional "Habr".
O código-fonte pronto pode ser encontrado no
GitHub .
Etapa 1. Visualização de um tabuleiro de xadrez com a geração de movimentos
Neste ponto, usaremos as bibliotecas
chess.js para gerar movimentos e
chessboard.js para renderizar o tabuleiro de xadrez. A biblioteca, responsável pela geração de jogadas, permite aplicar todas as regras do xadrez, para que possamos calcular cada ação para um arranjo específico de peças.
Quando você clicar na imagem, ela será aberta em resolução total.
Trabalhar com essas bibliotecas permite que você se concentre na tarefa principal - pesquisando e criando um algoritmo que permite encontrar a jogada ideal. Iniciamos o trabalho escrevendo uma função que retorna um movimento aleatório de uma lista de todos os possíveis.
var calculateBestMove =function(game) {
Apesar do fato de o algoritmo não ser um jogador de xadrez ideal, isso será suficiente para a maioria dos jogadores de seu nível.
O preto se move aleatoriamente. (
fonte e jogo online )
Etapa 2. Avaliação da Posição
Agora vamos descobrir qual lado tem a vantagem nesta ou naquela posição. A maneira mais fácil é calcular a força relativa das peças no tabuleiro, isso pode ser feito usando a tabela.
Usando a função de avaliação, temos a oportunidade de criar um algoritmo que seleciona o movimento com a classificação máxima.
var calculateBestMove = function (game) { var newGameMoves = game.ugly_moves(); var bestMove = null;
Em princípio, o nível é o mesmo, mas o algoritmo já pode assumir a figura de outra pessoa quando existe essa oportunidade.
As pretas tiveram a oportunidade de pegar peças brancas. (Fontes e jogo estão
aqui ).
Etapa 3. Árvore de pesquisa com minimax
Depois disso, criamos uma árvore de pesquisa. Agora o programa pode escolher a melhor opção. Isso é feito usando o algoritmo minimax.
Aqui, uma árvore recursiva com a exibição de todos os movimentos possíveis é analisada até uma determinada profundidade. A posição é estimada pelas folhas da nossa árvore.
Em seguida, retornamos o valor mínimo ou máximo do filho ao nó pai. Tudo depende de qual lado está calculando mal atualmente. Em outras palavras, o resultado é maximizado ou minimizado em cada nível.
Aqui, b2-c3 é a melhor jogada para as brancas, pois ele garante que o jogador chegue à posição com uma pontuação de -50.
var minimax = function (depth, game, isMaximisingPlayer) { if (depth === 0) { return -evaluateBoard(game.board()); } var newGameMoves = game.ugly_moves(); if (isMaximisingPlayer) { var bestMove = -9999; for (var i = 0; i < newGameMoves.length; i++) { game.ugly_move(newGameMoves[i]); bestMove = Math.max(bestMove, minimax(depth - 1, game, !isMaximisingPlayer)); game.undo(); } return bestMove; } else { var bestMove = 9999; for (var i = 0; i < newGameMoves.length; i++) { game.ugly_move(newGameMoves[i]); bestMove = Math.min(bestMove, minimax(depth - 1, game, !isMaximisingPlayer)); game.undo(); } return bestMove; } };
Com o algoritmo minimax, nossa IA já começou a entender as táticas básicas do xadrez.
Minimax com profundidade de 2 (Fontes e o jogo
aqui )
Vale ressaltar que a eficiência do algoritmo minimax aumenta com a profundidade da pesquisa. O próximo passo é responsável por isso.
Estágio 4. Clipe Beta Beta
Este é um método de otimização de algoritmo minimax que possibilita ignorar algumas ramificações na árvore de pesquisa. E isso permite aumentar a profundidade da pesquisa, gastando a mesma quantidade de recursos.
O recorte alfa beta é baseado em uma situação em que podemos parar de avaliar uma ramificação específica, se for constatado que uma nova ação levará a uma situação pior do que a que vimos ao avaliar a anterior.
A otimização não afeta o resultado do minimax, mas tudo começa a funcionar mais rapidamente.
Esse algoritmo é muito mais eficiente se você verificar primeiro os caminhos que levam a boas jogadas.
A imagem mostra movimentos desnecessários ao usar o recorte alfa beta.
Como você pode ver, com o recorte alfa-beta, o minimax é otimizado e muito significativamente.
O número de posições que você deseja avaliar no caso de uma pesquisa com profundidade de 4 e a posição inicial, mostrada acima. (fonte e jogo estão disponíveis
aqui )
Etapa 5. Função de avaliação aprimorada
A função de avaliação inicial é bastante simples, porque simplesmente conta os pontos das peças no tabuleiro. Para otimizar, você pode levar em consideração a posição das figuras. Por exemplo, se você colocar o cavalo no centro do tabuleiro, ele se tornará mais caro - o leque de movimentos disponíveis para esta peça se expandirá.
Neste ponto, trabalharemos com uma versão ligeiramente modificada das tabelas quadradas originalmente descritas no
wiki de programação de xadrez .
E agora nosso algoritmo já está jogando muito bem, é claro, comparado ao jogador médio.
Fontes e jogos estão disponíveis
aqui.Conclusão
A vantagem do algoritmo proposto é que ele não comete erros muito estúpidos. Obviamente, a estratégia aqui dificilmente pode ser considerada perfeita, mas mesmo assim.
A implementação do nosso algoritmo é de apenas 200 linhas de código, portanto os princípios básicos são bastante simples. A versão final do programa pode ser <a href= target
github.com/lhartikk/simple-chess-ai'> vista no GitHub.
Outros módulos podem ser adicionados ao algoritmo, incluindo:
Mais sobre algoritmos de xadrez podem ser encontrados no
Wiki de programação de xadrez .
A Skillbox recomenda: