Como o motor funciona

Duas partes: busca e avaliação

Um motor de xadrez são dois programas trabalhando juntos. A busca olha à frente: “se eu jogar isto, eles podem responder aquilo, aí eu jogo isto…”. A avaliação olha para uma única posição, sem mover nada, e dá a ela um número: quem está melhor, e por quanto.

Uma precisa da outra. Quanto mais profunda a busca, menos importa uma avaliação fraca; quanto melhor a avaliação, menos profundidade é necessária. Como a avaliação roda em cada ponta de cada linha — centenas de milhares de vezes por segundo —, ela tem que ser ao mesmo tempo boa e muito rápida.

A busca

O motor pensa um nível mais fundo de cada vez (aprofundamento iterativo), então sempre tem um lance pronto quando o relógio acaba. Olhar todos os lances em todas as profundidades levaria uma eternidade, por isso a maior parte do trabalho é não olhar para lances que não podem fazer diferença:

• Alfa-beta. Assim que uma resposta refuta um lance, o motor para de examinar esse lance. Com uma boa ordenação dos lances, isso pula a maior parte da árvore sem mudar o resultado.
• Melhores lances primeiro. O lance que foi o melhor da última vez que esta posição apareceu, as capturas de peças valiosas e os lances tranquilos que funcionaram em posições parecidas (killer moves e uma tabela de histórico) são testados primeiro.
• Memória. Uma tabela de transposição guarda as posições já analisadas, porque a mesma posição muitas vezes surge por ordens de lances diferentes.
• Atalhos bem pensados. Lances tardios pouco promissores são analisados com menos profundidade (late move reductions); uma posição tão boa que até passar a vez manteria a vantagem é cortada mais cedo (null move pruning); os xeques são analisados um lance mais fundo.
• Só posições calmas. A busca nunca para no meio de uma troca: no fim de cada linha ela continua seguindo as capturas até a posição se acalmar (busca de quiescência), para que a avaliação nunca veja uma dama prestes a ser recapturada.
• Vários núcleos. O motor pode buscar com várias threads ao mesmo tempo, todas compartilhando uma única tabela de transposição (Lazy SMP).

O tabuleiro

Dentro do motor, o tabuleiro é um conjunto de números de 64 bits, um bit por casa (bitboards): um número para os cavalos brancos, outro para as torres pretas, e assim por diante. Lances e ataques viram algumas operações de bits, e as peças de longo alcance consultam seus ataques em tabelas pré-calculadas (magic bitboards). As peças compostas da variante — o Marajá, o Arcebispo e o Chanceler — se movem como a união de seus componentes, então reaproveitam as mesmas tabelas.

Avaliando uma posição à mão

A avaliação original do motor é uma lista de regras práticas do xadrez, cada uma com um peso: material, onde cada peça está, quantas casas ela controla, peões passados e isolados, o par de bispos, torres em colunas abertas, o escudo de peões na frente do rei. Os pesos mudam aos poucos da abertura para o final.

Ela funciona, e é ela que joga no app hoje, mas só sabe o que alguém pensou em anotar. Todo o resto é invisível para ela.

A rede neural

A rede neural substitui apenas a avaliação. A busca continua exatamente como está — a rede não escolhe lances, ela responde a uma pergunta, muitas vezes por segundo: quão boa é esta posição?

• A entrada é o próprio tabuleiro. Existem 18 tipos de peças — peão, cavalo, bispo, torre, dama, rei e as três peças compostas, em duas cores — e 64 casas: 18 × 64 = 1152 perguntas de sim ou não, como “há um cavalo branco em f3?”. Numa posição normal, umas 32 delas são “sim”. As peças compostas são entradas próprias, não uma mistura de outras peças, então a rede aprende quanto vale um Marajá nos termos dele.
• Os dois pontos de vista. O tabuleiro entra duas vezes: como o lado que joga o vê e, espelhado, como o adversário o vê. A rede nunca precisa aprender xadrez duas vezes, uma para as brancas e outra para as pretas.
• Os neurônios não são programados. Ninguém diz a um neurônio o que procurar. Durante o treino, eles se tornam detectores por conta própria — algo como “um rei sem proteção de peões” ou “uma torre que chegou à sétima fileira”.

Por que é rápido

O nome da rede, NNUE, vem de Efficiently Updatable Neural Network, uma rede neural atualizável de forma eficiente. A primeira camada é uma tabela com uma coluna de números por entrada, e os neurônios são simplesmente a soma das colunas das entradas que estão em “sim”. Um lance muda apenas de duas a quatro entradas, então a soma nunca é recalculada do zero — ela é atualizada:

Tudo é calculado com inteiros pequenos, muitos de uma vez, com as instruções vetoriais do processador. Nas nossas medições, o motor com a rede alcança a mesma profundidade de busca cerca de duas vezes mais rápido do que com a avaliação escrita à mão (0,95 contra 2,0 segundos nas nossas posições de teste, em um núcleo da nossa máquina de testes).

Como aprende

Cada exemplo de treino é uma posição com dois rótulos: a nota que uma busca de alguns lances de profundidade deu a ela, e como a partida terminou. A rede aprende a adivinhar os dois num relance. Esse é todo o truque: quando a busca pergunta à rede sobre uma posição, a resposta já traz o que uma análise mais profunda teria encontrado, como se a busca tivesse ido mais longe de graça.

O motor aprende só com as próprias partidas, incluindo peças compostas e exércitos personalizados — nenhuma análise de outro motor entra nele. Uma nova rede só é mantida se vencer a anterior num match de centenas de partidas. Até agora, cada rodada foi claramente mais forte que a anterior:

Esses números vêm de partidas com aberturas clássicas entre versões do nosso próprio motor, 600 partidas por match. Jogos de um motor contra si mesmo tendem a exagerar os ganhos; a medição contra um motor externo está na página de força do motor.

Onde está hoje

• A quarta rede já está embutida no motor. Contra o Fairy-Stockfish ajustado para uma força de 2500, ela faz 55%, cerca de 2535 nessa escala; a avaliação escrita à mão chega a cerca de 2210 no mesmo teste.
• A rede conhece a variante pior do que o xadrez clássico. Todo exército personalizado com que ela treinou saiu do nosso gerador, não de um jogador, então essas posições iniciais são um tanto artificiais. Que exércitos jogadores de verdade montariam, ainda não sabemos. Além disso, a variante é simplesmente mais difícil: mais tipos de peças e uma posição inicial nova em quase toda partida.
• As partidas dos jogadores ainda não são coletadas. A ideia é que o servidor guarde as partidas em que um jogador escolheu o nível 5 e venceu o motor com um exército personalizado. Isso ainda não é possível. Uma rede precisa de dezenas de milhões de posições de treino — a quarta aprendeu com 68 milhões — e os jogadores ainda estão longe de ter jogado partidas da variante suficientes para fornecê-las.