Um passo-a-passo para a construção de um simples xadrez AI

por Lauri Hartikka

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

mover-geração
avaliação da diretoria
minimax
alfa e beta de poda.

a cada passo, vamos melhorar o nosso algoritmo com uma destas técnicas de programação de xadrez testadas no tempo. Vou demonstrar como cada um afecta o estilo de jogo do algoritmo.

pode ver o algoritmo de IA final aqui no GitHub.

Passo 1: Geração de movimento e visualização de tabuleiro

usaremos o xadrez.js library for move generation, and chessboard.js por visualizar o quadro. A biblioteca move generation basicamente implementa todas as regras do xadrez. Com base nisto, podemos calcular todos os movimentos legais para um determinado estado do Conselho.

a visualization of the move generation function. A posição inicial é usada como entrada e a saída são todos os movimentos possíveis a partir dessa posição.

usando estas bibliotecas nos ajudará a focar apenas na tarefa mais interessante: criar o algoritmo que encontra a melhor jogada.

vamos começar por criar uma função que retorna apenas um move aleatório de todos os movimentos possíveis:

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

Preto desempenha jogadas aleatórias. Playable on https://jsfiddle.net/lhartikk/m14epfwb/4

Step 2 : Avaliação da posição

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

Com a função de avaliação, somos capazes de criar um algoritmo que escolhe o movimento que dá a mais alta avaliação:

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

Black joga com a ajuda da função de avaliação Simples. Jogável em https://jsfiddle.net/lhartikk/m5q6fgtb/1/

Passo 3: árvore de Busca usando Minimax

em seguida vamos criar uma árvore de busca a partir do qual o algoritmo pode escolher a melhor jogada. Isto é feito usando o algoritmo Minimax.

neste algoritmo, a árvore recursiva de todos os movimentos possíveis é explorada para uma dada profundidade, e a posição é avaliada nas “folhas” finais da árvore.

Depois disso, devolvemos o menor ou o maior valor da criança para o nó pai, dependendo se é um branco ou preto para mover. (Isto é, tentamos minimizar ou maximizar o resultado em cada nível.)

a visualization of the minimax algorithm in an artificial position. A melhor jogada para o branco é b2-c3, porque nós garantimos que nós podemos chegar a uma posição onde a avaliação é de -50

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

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

A eficácia do algoritmo minimax é fortemente baseada na profundidade da pesquisa podemos alcançar. Isto é algo que vamos melhorar no passo seguinte.

Passo 4: Poda alfa-beta

poda alfa-beta é um método de otimização para o algoritmo minimax que nos permite ignorar alguns ramos 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 leva a uma situação pior do que um movimento previamente descoberto.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 por acaso visitarmos primeiro os caminhos que levam a bons movimentos.

as posições que não precisamos explorar se a poda alfa-beta é usada e a árvore é visitada na ordem descrita.

com alfa-beta, obtemos um impulso significativo para o algoritmo de minimax, como é mostrado no exemplo a seguir:

O número de posições que são necessários para avaliar se o que se pretende realizar uma pesquisa com profundidade de 4 e a posição “tônica” é o que é mostrado.

Follow this link to try the alpha-beta improved version of the chess AI.

Passo 5: Função de avaliação melhorada

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

usaremos uma versão ligeiramente ajustada das tabelas de peças quadradas que são originalmente descritas no chess-programming-wiki.

the visualized piece-square tables visualized. Podemos diminuir ou aumentar a avaliação, dependendo da localização da peça.

Com as seguintes melhorias, nós começamos a obter um algoritmo que interpreta algumas “decente” de xadrez, pelo menos do ponto de vista de um jogador casual:

Melhor avaliação de alfa e beta de poda com a pesquisa, a profundidade de 3. Jogável em https://jsfiddle.net/q76uzxwe/1/

Conclusões

A força de até mesmo um simples xadrez algoritmo é que ele não faz erros estúpidos. Dito isto, falta-lhe ainda compreensão estratégica.com os métodos que introduzi aqui, conseguimos programar um algoritmo de xadrez que pode jogar xadrez básico. A “parte AI” (excluindo a geração de movimento) do algoritmo final é apenas 200 linhas de código, significando que os conceitos básicos são bastante simples de implementar. Você pode verificar a versão final está no GitHub.

algumas melhorias adicionais que poderíamos fazer ao algoritmo seriam, por exemplo:

move-ordering
geração mais rápida de movimento
e avaliação específica do jogo final.

KGSAU