Supra chess engine

O primeiro motor de xadrez Português

Introdução

Supra Chess é o primeiro motor de xadrez português. O código fonte é totalmente original, aberto, escrito em c++ e está disponível para download no final da página. ↓

Criador e desenvolvedor: Pedro Mourão Soares Correia.

`Novidades`

Supra 29.1 disponível para download em baixo na página↓

Executável mais eficiente devido a utilização de compilador com melhores características.

Supra 29.0 disponível para download em baixo na página↓

Entre as melhorias destacam-se:

Melhoria substancial do algoritmo de Shashin, através da implementação nos nodos finais do processo de decisão em função dos critérios posicionais específicos do algoritmo, tal como é executado no nível 0 e 1.
Desbloqueio da imposição de valor máximo de um peão para avaliação posicional nos nodos finais, o que significa que a avaliação posicional pode assumir valores superiores a um peão, levando a sacrifícios materiais efetivos nos nodos finais em benefício de critérios posicionais nomeadamente os graus de liberdade, compactação e critérios de defesa de rei, entre outros.
Uma real conceção dos graus de liberdade nos níveis 0 e 1 de deeph. Através de uma função de verifica_rei sobre todos os movimentos possíveis.
Compreensão aprimorada dos finais com peças menores com ou sem peões.
Melhoria substancial do algoritmo Late move reductions e aplicação em todos os níveis de profundidade. Implementação de um novo algoritmo chamado early move reductions.

Ficha Técnica

• Tipo: Motor de xadrez UCI (ou seja, um programa totalmente lógico, sem estrutura gráfica própria, necessitando de um programa de xadrez gráfico para poder interferir e visualizar. Pode ser conectado com qualquer programa de xadrez gráfico, como fritz, light chessbase , hiarcs, entre outros).

• Linguagem: C++

• Tamanho: Cerca de 15 000 linhas de código na versão 1.0. Executável com aproximadamente 1,5 MB. Cerca de 330 000 linhas de código na presente versão. Executável com aproximadamente 6,5 MB.

• Idealizador e implementador: Pedro Mourão Correia.

• Ano de criação: 2010.

Algoritmos usados:

Algoritmo Principal:

*Algoritmo base (equivalente a minimax): Algoritmo recursivo que para cada nó, encontra o filho mais forte (min ou max) de acordo com a perspetiva do lado a ser jogado. Este algoritmo Base foi desenhado por mim em 2011 na Ver#são Supra 2.0. Mais tarde percebi que já havia sido descoberto muito antes!

Algoritmos relacionados ao algoritmo base:

Algoritmo alfa beta: quando Supra analisa os filhos de um determinado nó, ele interrompe a pesquisa sempre que beta <= alfa, pois mesmo que beta ainda possa diminuir mais, não importa, porque não será relevante para crescer alfa. Quando este corte ocorre, significa que o nó em questão não é melhor que o nó mais forte neste nível de profundidade e secção da árvore.
*wormhole: Este algoritmo aplica a mesma condição que o algoritmo alfa beta, mas a estende a todos os níveis anteriores: Por exemplo, no nível deph=5: a condição em vez de "if (beta5 <= alfa4)" é "if (beta5) <= alfa4 || beta5 <= alfa2 || beta5 <= alfa0)". O ganho é avassalador!

Algoritmos de ordenação de dados para acelerar cortes no algoritmo alfa beta:

Internal Iterative Deepening: Este algoritmo faz varreduras completas sucessivas com profundidade crescente a cada varredura. Isso permite agrupar melhor os nós em ordem (aprimorando o corte alfa beta) e gerenciar melhor o tempo gasto em pesquisa.
Killer moves: Permite que Supra analise sempre primeiro o movimento que fez o corte alfa beta na seção anterior no mesmo nível de profundidade. Muitas vezes, mesmo em posições diferentes, o mesmo movimento da peça produz corte alfa beta, se anteriormente também produzia.

Algoritmos de filtragem por condição:

*filtro vertical: Filtro poderoso de variantes francamente ruins de deph>=3.

*Filtro turbo: Permite que Supra use um método de pesquisa um pouco mais rápido por incrementos escalonados de alfa.

Algoritmos de filtragem com pré-pesquisa com menor nível de profundidade:

Null move pruning: O lado a mover não se move e deixa o adversário jogar: se o resultado desta análise (com deph = deph-2) ainda for ruim para o adversário existe um corte total neste nó.

Late move reductions: Este algoritmo faz com que Supra analise os primeiros filhos de um nó com profundidade normal. Se após a análise destes primeiros (cerca de 5) nós não houver corte alfa beta a pesquisa continua mas agora com uma profundidade menor. Este procedimento economiza muito tempo na pesquisa, pois o corte alfa beta normalmente não é produzido a não ser nos primeiros nós. Se um corte for produzido, Supra terá que reanalisar os nós restantes com profundidade normal. Supra usa uma versão mais radical deste algoritmo e só varre novamente esse nó com deph normal se esse nó produziu corte alfa beta e não todos os nós indiscriminadamente. Em outras palavras, se o corte alfa beta com menor deph for produzido em um determinado nó (após o 5 inicial), então supra analisa esse nó com deph normal. Se não for confirmado o corte alfa beta, Supra analisa o próximo nó com menor deph e executa o mesmo procedimento.
Principal Variation Search: Supra para cada nó começa com uma varredura com janela de tamanho muito reduzido (<1) se o valor beta não sair da janela a pesquisa com janela ilimitada não é realizada e Supra economiza muito tempo varrendo o ramo desse nó.

*: algoritmos descobertos por mim ou descobertos independentemente por mim.