beta2.3.0

beta2.3.0

• Adicionado suporte ao protocolo UCI

Importante

• O loop UCI ainda é executado em uma única thread
• Não há suporte ao comando stop

beta2.1.2

beta2.1.2

Patch para corrigir erro na geração de roques a partir de uma posição dada por um FEN

beta 2.1.1

Versão beta 2.1.1

Uma pequena versão trazendo algumas correções de bugs e pequenas melhoras

Bugfixes

• Corrigi erro na obtenção de direitos de roque a partir de um FEN personalizado - Os valores do bitboard de direitos de roque estavam errados.
• Reduzi a quantidade de ifs redundantes na função de realizar lances - O tipo da peça estava sendo verificado mais de uma vez para saber se era um peão.

Optimizações

• Substituido ffsll por ctzll - O que elimina a necessidade de uma operação extra de subtração ao fazer um bitscan

Recursos adicionados (em fase de testes)

• Bitboards PEXT

Ganhos de ELO

As alterações realizadas corrigiram bugs e não apresentaram nenhum ganho de rating

beta 2.1.0

Versão beta 2.1.0

Mais um release trazendo diversos recursos novos.
Dessa vez, esse release está totalmente focado em recursos para melhorar a pesquisa de lances, tornando-a mais rápida e mais eficiente na poda de lances

Recursos novos

• Killer move heuristic: Adicionado a heuristica do killer move, que acrescenta um bonus na ordenação de lances para lances de não captura que causaram um beta-cutoff em posições semelhantes, dessa forma, a ordenação de lances consegue encontrar mais rapidamente os principais lances a serem pesquisados e ao mesmo tempo, mantém na memória planos de curto prazo na posição.
• Internal Iterative Deepening: Em posições onde não há lances armazenados na tabela de transposição, o algoritmo performa uma pré-pesquisa a uma pequena profundidade apenas com a intenção de optimizar a ordenação de lances.
• Aspiration windows: O algoritmo inicia a pesquisa alpha-beta com estimativas dos valores de alpha e beta baseados na avaliação da última iteração da pesquisa. Isso faz com que o algoritmo consiga efetuar mais beta-cutoffs.
• Late-move-reductions: Os últimos lances a serem pesquisados recebem uma redução em sua profundidade caso se encaixem em critérios pré-definidos

Optimizações

• Removido a soma de bonus do historico para lances de heuristicas: Lances que já caíram em alguma heuristica de ordenação de lances não recebem mais o acréscimo da tabela de histórico, uma vez que esse acréscimo é insignificante para ordenação de lances.

Bugfixes

• Corrigido erro na pesquisa em posições de mate forçado: O valor padrão para posições de xeque-mate era maior que o valor inicial de alpha, sendo assim, quando a pesquisa encontrava uma posição de xeque-mate, esta causava um fail-high, portanto, o algoritmo evitava essa continuação.

Comparações

Em comparação com a última versão o capizero demonstrou grandes melhoras na pesquisa de lances, avaliando o dobro de posições por segundo: capizero beta2.0.2 = 3869K e capizero beta2.1.0 = 6818K e pesquisando cerca de 45% a menos de lances por profundidade em profundidades maiores que 10.
Além disso, é notável a melhora do capizero em posições de mate, que na versões anteriores ele não conseguia encontrar, causando empates em posições ganhas. Essa evolução pode ser percebida nos jogos de teste disponibilizados em capizero.xyz

Ganhos de ELO

De acordo com os calculos realizados em 300 partidas através do CuteChess, essa versão do Capizero ganhou 8 pontos de rating em relação a versão anterior

beta 2.0.2

Versão beta 2.0.2

Mais outra atualização rápida com algumas funcionalidades novas e correções de bugs

O que há de novo

Comando fen / setboard

Com esse comando agora é possível configurar a engine para calcular a partir de posições especificas informando o FEN da posição desejada.
O comando fen funciona no modo normal e é equivalente ao comando setboard do modo xboard

Alguns outros comandos xboard

Implementado alguns comandos que foram deixados de lado na versão beta1.2.0 (versão que introduziu o protocolo xboard), esses novos comandos são: ping e protover (para mais informações a respeito desses comandos, consulte a documentação oficial do protocolo xboard

Correções de bugs

• Corrigido bug na deteção de legalidade do roque menor das pretas.

beta 2.0.1

Versão beta 2.0.1

Uma rápida atualização para correção de bugs

Correções

• Alterado código para que os lances de promoção sejam notados corretamente no modo xboard. Atualmente o capizero ignora sub-promoções, mas isso pode ser tópico de futuras atualizações, por enquanto não há planos de mudar essa catecteristica.

beta 2.0.0

Versão beta 2.0.0

Depois de vários meses sem atualizações aqui no projeto, finalmente uma nova versão com grandes novidades!

O que há de novo nessa versão

Todos os esforços desde a última versão foram para melhorar a performance da geração de lances, principalmente com o uso de bitboards mágicos.

Geração de lances com bitboards mágicos

Essa técnica visa eliminar os loops excessivos na geração de lances para bispos e torres.
A abordagem antiga consistia em loopar na direção do ataque da peça, casa por casa, verificando se há uma peça ocupando aquela casa.
Caso a peça seja do adversário, ela pode ser capturada e o loop se encerra, caso contrário, o loop se encerra sem adicionar a captura.
Caso não haja nenhuma peça ocupando a casa em questão, o loop continua.

for (direcao = NORTE; direcao < NO + 1; direcao += 2){
    if (mask_vetores[casa][direcao] & bit_total){
        for (casa_destino = casa;;){
            casa_destino = dtb_moves[casa_destino][direcao];
            if (mask[casa_destino] & bit_total){
                if (mask[casa_destino] & bit_lados[contraLado]){
                    adicionar_captura(casa, casa_destino, tx[tabuleiro[casa_destino]]);
                }
                break;
            }
            adicionar_lance(casa, casa_destino);
        }
    }
    else{
        for (casa_destino = casa;;){
            casa_destino = dtb_moves[casa_destino][direcao];
            if (casa_destino == -1){
                break;
            }
            adicionar_lance(casa, casa_destino);
        }
    }
}

Essa quantidade de loops acaba sendo muito intensa para o processador na hora de gerar esses lances, portanto a técnica de geração de lances com bitboard mágicos consiste em pré-gerar o bitboard de lances legais de bispo e torre por casa para cada combinação possível de peças bloqueadoras. Esses bitboards serão armazenados em uma tabela hash indexadas pela casa e por um número mágico obtido através de uma multiplicação do bitboard de peças bloqueadoras por um número mágico.
Para isso, apenas as peças no raio de ação da torre ou bispo em questão são levadas em conta, pois essas são as únicas peças que interferem no conjunto de lances possíveis dessas peças.

Sendo assim, o processo de geração de lances para bispos e torres acaba sendo o processo de obter o bitboard de peças bloqueadoras, calculando o hash a partir de uma multiplicação por um número mágico (o que graças às instruções de multiplicação rápida de inteiros de 64 bits, acaba sendo um processo muito veloz), e o acesso do bitboard de lances legais a partir do hash:

bloqueadores = bit_total & bit_casas_relevantes_torres[casa];
chave_hash = (bloqueadores * magicas_torres[casa]) >> (64 - bits_indices_torres[casa]);
ataques = bit_magicas_torre[casa][chave_hash];

Para maiores referências a respeito da geração de lances, estou deixando dois links ótimos que explicam mais a fundo essa técnica.

• Link 1 - Essa postagem em inglês do autor da engine Shallow Blue explicando a implementação dos bitboards mágicos
• Link 2 - O artigo do chess programming wiki sobre esse assunto

Resultados

Poda de lances

capizero beta2.0.0 pesquisa em média 8% de lances a menos do que capiezero beta1.3.0para chegar na mesma profundidade.

Velocidade de pesquisa

capizero beta2.0.0 pesquisa 4 vezes mais lances por segundo do que a versão capizero beta1.3.0. Isso se deve pelo aumento na velocidade de geração de lances.
Como base de comparação, a versão atual do capizero chega na profunidade 12 em 1.9 segundos, enquanto o versão anterior demorava cerca de 5.4 segundos.

Avaliação de posições

Apesar de não ter sido o foco dessa versão, a avaliação de posições também se tornou mais rápida devido às novas flags de optimização do gcc que foram adicionadas: --march=native -O3 -flto.
Essas optimizações do compilador impactaram significativamente a velocidade da avaliação de posições, ficando mais de 4 vezes mais veloz do que a versão anterior.

Geração de lances

A geração de lances também teve um aumento enorme em sua performance. Cerca de 4 vezes mais rápido do que a versão anterior.
Como base de comparação, a versão capizero beta1.3.0 gerava em média 9356K de lances por segundo de acordo com o binário stats. A versão atual capizero beta2.0.0 consegue gerar em média 31694K de lances por segundo.

Notas pessoais

Estou focado em implementar uma por uma das funcionalidades listadas no arquivo README desse repositório, mas por questões de tempo não é possível trabalhar nesse projeto com uma frequência boa, sendo assim, pode ser bem comum de agora em diante, meses parados sem desenvolvimento até que eu finalmente volte para implementar um novo algoritmo nesse projeto.
Não pretendo abandonar o desenvolvimento desta engine de xadrez, inclusive estou com várias ideas para continuar aprimorando sua performance, portanto, mesmo que demore, ainda há muita coisa interessante por vir!

beta 1.3.0

Versão Beta 1.3.0

Agora estamos em uma nova fase no desenvolvimento do capizero.
Agora que as funcionalidades básicas da engine estão funcionando bem e as interfaces e protocolos estão estáveis.
O foco agora é em implementar diversas tecnicas e algoritmos de pesquisa, avaliação e geração de lances com o objetivo de aumentar a performance, além de tornar a engine mais inteligente, com uma pesquisa mais eficiente.

O que há de novo nessa versão

Alguns valores e parâmetros de avaliação foram aprimorados.
Foram implementados dois algoritmos novos para aumentar a eficiencia da pesquisa e ordenação de lances, além de novas builds disponíveis no Makefile

Comando make stats

Gera um binário do capizero com o objetivo de testar a performance da engine na máquina atual. Ele executa pesquisas e funções muito recorrentes durante o uso comum da engine diversas vezes, retornando a quantidade média de execuções por segundo de determinada função em sua máquina.
Pode ser usado para medir os impactos das mudanças no código em relação a performance geral.

Implementação da PVS (Principal Variation Search)

Este algoritmo melhora a poda de lances da engine, pesquisando lances que não fazem parte da variante principal com uma janela alpha-beta menor (equivalente a 1 ponto), a menos que estes apresentem uma pontuação maior que alpha. Neste caso, a pesquisa será re-feita, desta vez com a janela alpha-beta comum, para obter o novo valor de alpha.
Esta tecnica faz com que a engine não perca muito tempo tentando encontrar o valor exato de avaliação de uma linha que não refuta a variante principal naquela posição, uma vez que o objetivo primário é apenas saber se seu valor é maior que o alpha atual, e apenas em caso positivo, ela pesquisará pelo valor exato da linha.

Implementação da CMH (Countermove heuristic)

Todos os lances que causarem uma beta-cutoff serão armazenados em uma array [64][64] (Butterfly board), indexados pelo último lance realizado pelo oponente.
Caso o lance re-apareça durante a pesquisa, o lance armazenado na array de contra-lances, desde que esse seja um lance disponível e legal na posição, recebe uma pontuação que faz com que este seja pesquisado antes das capturas (o valor exato da pontuação e se ele realmente deverá ser pesquisado antes das capturas ainda será revisto e testado nas proximas versões).

Resultados

Com o uso do binário de stats, foi possível medir os impactos que as últimas atualizalções no código realizaram na performance geral da engine, principalmente devido a PVS e a CMH:

Poda de lances (quantidade de lances pesquisados na mesma posição com a mesma profundidade)

capizero beta1.3.0 pesquisa em média 18% de lances a menos para chegar na mesma profundidade em relação a sua versão anterior
Isso demonstra que a engine está perdendo menos tempo pesquisando lances não-uteis.

Velocidade de pesquisa (lances por segundo)

capizero beta1.3.0 tem a pesquisa por volta de 4% mais lenta que sua versão anterior
Devido aos novos algoritmos na pesquisa, o que acaba tornando-a mais pesada, porém esta perda em velocidade é compensada pela redução na quantidade de lances que precisam ser pesquisados.

Geração de lances (lances por segundo)

Não houve diferença significativa

Avaliação de lances (lances por segundo)

Não houve diferença significativa

beta 1.2.1

Pequenos bugfixes

• Corrige problemas na implementação do protocolo xboard
• Atualiza valores de avaliação

beta 1.2.0

Xboard!

Nessa versão, foi adicionado compatibilidade com o protocolo Xboard, portanto, o capizero agora pode ser usado em softwares de interfaces gráficas como o Arena.
O protocolo xboard ainda apresenta diversas instabilidades, mas estas serão corrigidas nas próximas atualizações do programa.

Sem o uso do xboard, agora os comandos estão em português.

Além disso, foram feitas diversas alterações no código fonte visando melhorar a leitura e compreensão do código, mas sem perder performance.

Foram adicionados novos detalhes no Makefile, como exibir a versão do capizero no nome do binário e as opções de compilação usadas.