Dedicado a todos que agora assistem à aclamada série de TV "The Queen's Gambit". Mais termos de xadrez em nossa nova tradução.
Neste artigo, tentaremos entender como os motores de xadrez funcionam ao portar o motor de xadrez sunfish para o Go. Sunfish é notável por sua simplicidade e tamanho pequeno, mas ainda é capaz de jogar um jogo de xadrez decente. Go, por outro lado, é conhecido como uma linguagem de programação simples e legível, então espero que juntos eles formem um ótimo par.
Para criar um mecanismo de xadrez, você primeiro precisa decidir sobre três pontos importantes:
- Como representar o tabuleiro de xadrez (células, peças, movimentos permitidos)?
- Como você avalia o conselho (quem tem mais chances de ganhar)?
- Como encontrar o movimento ideal?
Os trechos de código nesta postagem são simplificados e contêm apenas as partes mais importantes. Você pode encontrar o código completo do motor em github.com/zserge/carnatus (carnatus é o nome latino para robalo, espécie Sebastes carnatus).
Células e formas
É importante encontrar uma representação conveniente do tabuleiro que não ocupe muito espaço, já que milhares de variações do tabuleiro serão armazenadas na memória durante a busca pelo movimento ideal.
Normalmente, um tabuleiro é um conjunto de células. Vamos adicionar preenchimento ao redor do tabuleiro 8x8 padrão para que as peças inválidas caiam nesta área. Isso nos permitirá evitar a verificação de limites e simplificar muito o código.
Estaremos usando uma matriz linear. A maior distância que uma peça de xadrez pode se mover é o movimento de um cavalo de 2 casas. Claro, outras peças deslizantes podem se mover por longas distâncias, mas tais movimentos serão avaliados sequencialmente conforme cada quadrado é cruzado, o que significa que os limites do tabuleiro serão detectados antes que uma peça possa ir além deles.
Portanto, precisamos de um espaço de duas células ao longo das bordas do tabuleiro. Poderíamos criar um tabuleiro 12x12, mas como o estamos representando como uma matriz de linha, precisamos de um tabuleiro 12x10 porque o quadrado de recuo mais à direita na linha anterior pode ser usado como o quadrado de recuo mais à esquerda na próxima linha (× = recuo):
×××××××××× ×××××××××× ×........× ×........× ×........× ×........× ×........× ×........× ×........× ×........× ×××××××××× ××××××××××
Em nossa notação, “a1” seria semelhante a 9 × 10 + 1 = 91 e “a8” seria semelhante a “2 × 10 + 1” = 21.
Cada célula na matriz do tabuleiro representaria uma peça de xadrez, uma casa vazia ou uma zona de recuo. poderia ter usado constantes numéricas para esses valores, mas para simplificar a depuração, usamos caracteres legíveis por humanos. Letras maiúsculas e minúsculas denotam formas, espaços denotam zonas de recuo e pontos denotam células vazias:
| | RNBQKBNR | PPPPPPPP | ........ | ........ | ........ | <- ........ | ........ | ........ | pppppppp | rnbkqbnr | | |
Decodificação de abreviações
R — rook —
N — knight —
B — bishop —
Q — queen —
K — king —
N — knight —
B — bishop —
Q — queen —
K — king —
Finalmente, podemos começar a escrever o código:
type Piece byte
func (p Piece) Value() int { ... }
func (p Piece) Ours() bool { ... }
func (p Piece) Flip() Piece { ... }
type Board [120]piece
func (b Board) Flip() Board { ... }
type Square int
func (s Square) Flip() Square { ... }
As formas têm um certo valor. Esses valores são necessários para avaliar as posições no conselho e entender quem está ganhando. Normalmente, um peão = 100, um cavalo = 280, um bispo = 320, uma torre = 479, uma rainha = 929 e um rei é tão valioso que vence 8 rainhas (peões transformados em rainhas) em conjunto com pares de cavalos, bispos e torres. Se tivermos toda essa riqueza, mas perdermos o rei, a contagem ainda mostrará que vamos perder.
Cada tipo tem um método Flip () que retorna o mesmo valor após virar o tabuleiro antes que o oponente se mova. Para formas, ele muda o caso do símbolo de forma. Nas casas, ele retorna 119 casas (contando a partir da outra extremidade do tabuleiro). Quanto ao tabuleiro, ele copia todas as peças das casas na ordem inversa, mudando sua caixa.
Gerador de curso
Portanto, já temos os blocos de construção para o motor e agora podemos pensar nas posições do jogo. Posição é um tabuleiro com peças e estados adicionais no jogo, como um quadrado de passagem, um quadrado errante e possibilidades de roque. Se quiséssemos simplificar o jogo, poderíamos reutilizar o tipo de tabuleiro, mas criaremos um tipo de posição separado para movimentos e avaliação de tabuleiro.
O que é um movimento? Esta é uma combinação de duas células - a célula na qual a peça estava localizada antes da movimentação e a célula onde a peça se moveu. A posição é um tabuleiro de xadrez com pontuação, regras de roque para cada jogador e casas de passagem / errantes. Ambos os tipos também possuem um método Flip () para os movimentos do oponente.
type Move struct {
from Square
to Square
}
func (m Move) Flip() Move { ... }
type Position struct {
board Board //
score int // — ,
wc [2]bool //
bc [2]bool //
ep Square // ,
kp Square // ,
}
func (p Position) Flip() Position { ... }
Agora podemos escrever o primeiro grande método - o gerador de movimentos permitidos. Só nos preocupamos com as peças brancas, pois para jogar com as pretas vamos virar o tabuleiro e mover as brancas novamente.
Para gerar todos os movimentos válidos, precisamos:
- faça uma lista de todos os movimentos de uma etapa em cada direção para cada peça;
- faça o mesmo para todas as células, ignorando as peças não brancas;
- designe um movimento em todas as direções possíveis para cada peça branca;
- se o comprimento do movimento de uma peça não for limitado (torre, bispo, rainha), continue a movê-la até que um obstáculo seja encontrado no caminho: uma peça do oponente ou recuo atrás da borda do tabuleiro.
Este é um código simplificado que não leva em consideração a captura e o roque. Você pode encontrar a implementação completa no Github , não é muito diferente.
Para tornar a aritmética de direção mais legível, usaremos as constantes de direção N / E / S / W:
const N, E, S, W = -10, 1, 10, -1
var directions = map[Piece][]Square{
'P': {N, N + N, N + W, N + E},
'N': {N + N + E, E + N + E, E + S + E, S + S + E, S + S + W, W + S + W, W + N + W, N + N + W},
'B': {N + E, S + E, S + W, N + W},
'R': {N, E, S, W},
'Q': {N, E, S, W, N + E, S + E, S + W, N + W},
'K': {N, E, S, W, N + E, S + E, S + W, N + W},
}
func (pos Position) Moves() (moves []Move) {
for index, p := range pos.board {
if !p.ours() {
continue
}
i := Square(index)
for _, d := range directions[p] {
for j := i + d; ; j = j + d {
q := pos.board[j]
if q == ' ' || (q != '.' && q.ours()) {
break
}
if p == 'P' {
if (d == N || d == N+N) && q != '.' {
break
}
if d == N+N && (i < A1+N || pos.board[i+N] != '.') {
break
}
}
moves = append(moves, Move{from: i, to: j})
if p == 'P' || p == 'N' || p == 'K' || (q != ' ' && q != '.' && !q.ours()) {
break
}
}
}
}
return moves
}
Essas são todas as regras do jogo de xadrez que precisamos considerar para fazer movimentos válidos. A próxima etapa é aplicar um movimento à posição para criar uma nova posição de jogo. Sem levar em consideração a captura durante a rota, a promoção do peão e o roque, o método seria parecido com este:
func (pos Position) Move(m Move) (np Position) {
np = pos
np.board[m.to] = pos.board[m.from]
np.board[m.from] = '.'
return np.Flip()
}
Ele simplesmente move a peça, marca a célula na qual ela estava vazia e vira o tabuleiro. A implementação completa do método pode ser encontrada no Github , ele lida com todos os movimentos especiais de peão e rei corretamente.
Nesta fase, você pode jogar xadrez "homem contra homem", controlando o processo e realizando apenas jogadas legais. Ou você pode criar um mecanismo de xadrez primitivo que faz movimentos aleatórios até perder.
Mas como entendemos que estamos perdendo?
Avaliação da placa
Os pontos são concedidos para cada posição no tabuleiro. Inicialmente, o placar é zero, já que os dois jogadores começam em igualdade de condições. Depois de completar um movimento, a pontuação muda dependendo de quais peças foram capturadas e como as peças mudaram de posição no tabuleiro.
No caso mais simples, podemos contar as peças do tabuleiro e somar seu valor (menos as peças do adversário). Tal cálculo mostrará se o rei foi declarado xeque e xeque-mate. Mas este é um sistema de avaliação muito fraco.
Uma abordagem muito mais precisa e surpreendentemente simples são as tabelas de proporção forma-para-quadrado ( PST- Mesas de peça-quadrada). Para cada peça, é criada uma mesa do mesmo tamanho de um tabuleiro de xadrez, onde um valor correspondente é atribuído a cada casa. Esses valores são empíricos, então eu apenas os tirei do motor Sunfish.
Na verdade, os mecanismos de xadrez mais avançados atualizam os PSTs durante o jogo porque o valor das peças muda (ou seja, os peões se tornam mais valiosos no final do jogo). Mas teremos um motor simples.
Para avaliar a posição após a mudança, precisamos:
- determinar a classificação da posição atual,
- subtraia o valor da peça que está sendo movida,
- adicione um novo valor de figura de acordo com a tabela PTS,
- adicione o valor da peça capturada, se houver.
Além disso, precisamos ajustar na tabela PST o valor da torre durante o roque e o valor do peão durante a promoção ou captura no passe. Mas aqui não vamos considerar isso:
var pst = map[Piece][120]int{
'P': { ... },
'N': { ... },
'B': { ... },
'R': { ... },
'Q': { ... },
'K': { .... },
}
func (pos Position) value(m Move) int {
i, j := m.from, m.to
p, q := Piece(pos.board[i]), Piece(pos.board[j])
// PST-
score := pst[p][j] - pst[p][i]
if q != '.' && q != ' ' && !q.ours() {
// PST-
score += pst[q.Flip()][j.Flip()]
}
return score
}
Agora podemos fazer um motor um pouco mais avançado que escolherá o melhor movimento possível, ao invés de qualquer um dos válidos.
Mas os mecanismos de xadrez reais fazem análises mais profundas e iteram os ramos dos movimentos possíveis de cada lado para encontrar o melhor movimento possível a longo prazo.
Algoritmo de busca
O algoritmo de busca mais comum nos motores de xadrez é mais simples - busca em profundidade, que começa na raiz e desce até um determinado limite de profundidade, repetindo todos os movimentos possíveis antes de retornar. Para cada posição do curso, o valor é calculado usando um algoritmo minimax (minimax) c poda alfa-beta (poda alfa-beta ).
Minimax é uma regra usada para minimizar possíveis perdas no pior cenário: o jogador considera todas as melhores jogadas do adversário e escolhe tal jogada para que a melhor estratégia do adversário traga o máximo de pontos possível.
Um algoritmo minimax simples seria muito lento para o xadrez e exigiria a repetição de muitos movimentos para encontrar um bom.
A poda alfa-beta é usada para acelerar o algoritmo minimax removendo nós que não valem a pena considerar. O recorte alfa-beta é baseado na seguinte lógica: Imagine que você está jogando xadrez e descobre uma jogada muito boa A. Você continua olhando para o tabuleiro e encontra uma jogada ainda melhor B. Mas então você analisa a situação mais profundamente e entende que se você escolher no movimento B, o inimigo declarará xeque e xeque-mate para você em alguns movimentos. Agora você descartará B e não perderá tempo analisando outras combinações possíveis após B.
Os recortes de minimax e alfa-beta são importantes para entender como o mecanismo de xadrez funciona. O mecanismo Sunfish usa um algoritmo de pesquisa MDF (f) aprimorado , que também é uma variante do algoritmo minimax combinado com recorte.
Em nosso mecanismo, aumentaremos gradualmente a profundidade da pesquisa e chamaremos o algoritmo MDF (f) para encontrar os limites inferior e superior do resultado ideal. O algoritmo MDF (f) usará uma iteração de recorte alfa-beta com um cache de transposição.
O dinheiro de transposição é um cache onde, para cada posição no tabuleiro, memorizamos a profundidade, contamos e movemos que nos levaram a essa posição. Então, ao considerar uma nova posição, ela é primeiro verificada na tabela de transposição.
Não vou postar o código do algoritmo de pesquisa aqui, pois são apenas algumas linhas de pesquisa recursiva, mas você sempre pode encontrar o código-fonte completo do mecanismo de xadrez no GitHub .
Qual é o próximo?
Se você está interessado em motores de xadrez simples, eu recomendo jogar com Sunfish. A propósito, Sunfish é baseado no motor Micromax e vem com uma ótima documentação do autor, que definitivamente vale a pena ler.
Para nosso mecanismo em Go, adicionei uma pequena implementação do protocolo UCI para que ele possa ser usado com a IU do PyChess. Provavelmente, ele ainda tem muitos bugs e muito potencial para melhorias, mas foi um caminho interessante: da ideia de desenvolver um mecanismo de xadrez até um programa de xadrez de computador pronto para funcionar.
Sim, ele é fraco, mas joga xadrez de verdade!
Espero que tenha gostado deste artigo. Você pode me seguir em Github , Twitter ou inscreva-se via rss .