Como os motores melhoraram desde o Deep Blue?

Os mecanismos de xadrez para computador melhoraram desde que o Deep Blue venceu Kasparov em 1997.

Os algoritmos melhoraram ou as melhorias foram principalmente devido aos mesmos algoritmos que rodavam mais rapidamente, graças ao hardware mais rápido, etc.?

No primeiro caso, essas melhorias algorítmicas são públicas?

E se sim, quais foram as melhorias? Onde posso ler sobre eles?

Talvez você possa dar uma olhada no TalkChess , um fórum dedicado ao xadrez do computador. Encontrei um tópico recente que pode ser interessante para você: Progresso em 30 anos em quatro intervalos de 7-8 anos

Algumas partidas entre os (antigos) principais mecanismos são disputadas no mesmo hardware . O teste sugere que, nos últimos anos (2002-2017), o ganho é obtido principalmente por melhorias de software. No teste, Stockfish (2017) marcou impressionante 94/100 contra RobboLito (2009), enquanto RobboLito, por sua vez, esmagou Shredder (2002) com 92/100.

Uma observação importante: como a computação paralela não é implementada nos mecanismos mais antigos, o teste foi realizado em um único núcleo. Como resultado, o ganho de hardware por máquinas paralelas não é medido. Por outro lado, você poderia argumentar que a computação paralela também é um ganho de software: não é fácil projetar e implementar uma paralelização eficiente e bem dimensionada para o algoritmo de pesquisa.

O mecanismo do Stockfish é de código aberto, portanto as melhorias algorítmicas são públicas. Muita documentação pode ser encontrada em https://chessprogramming.wikispaces.com

Não posso falar pelo algoritmo usado para o Deep Blue, mas vou tentar explicar as melhorias na programação do xadrez. A velocidade é a maior melhoria. A Deep Blue usou computadores dedicados com vários processadores, portanto, uma comparação não é realmente possível.

https://chessprogramming.wikispaces.com/ é uma ótima fonte, mas é difícil de navegar.

Existem três funções principais que são aprimoradas para melhorar um mecanismo de xadrez: as funções de avaliação, geração de movimento e pesquisa.

A avaliação é a mais difícil de programar, pois há muitas exceções às regras. Com o espaço do disco rígido ficando mais barato, a função eval permite que mais exceções sejam avaliadas.

A geração de movimentos, juntamente com a realização e a remoção de movimentos, consome muita memória porque ela precisa ser pré-formada tantas vezes. As funções de geração mais comuns são caixa de correio, painel de bits, 0x88, 8x8, placas estendidas (10x10, 10x12) e uma matriz / tabela de movimentação predeterminada (* eu uso uma tabela de movimentação indexada). A opinião atual é de que os painéis de bit são mais rápidos e o uso de bitboards mágicos acelera isso em até 30%. O Dr. Robert Hyatt, professor e criador do mecanismo de xadrez cratfy, afirma que não há aumento significativo de velocidade.

A função de pesquisa inicial eram as funções min-max primitivas. Basicamente, você tentava maximizar a pontuação do lado para se mover e minimizar a pontuação do oponente. Alpha-Beta foi a primeira melhoria. Eles reduziram o número de movimentos pesquisados ​​pela tabela de transposição, valores de corte, janelas de aspiração e heurísticas do histórico. Essas são pesquisas profundas. Há também a busca de aprofundamento iterativo interno, que tenta buscar os "melhores" movimentos, a mais profunda esperança de que a busca por outros movimentos seja infrutífera.

NOTA: Minha tabela de índice. GNUChess e Jester usam uma matriz de índice para gerar seus movimentos. Eles inicializam o mecanismo preenchendo a matriz com possíveis movimentos. Pegue as seis peças e calcule as jogadas legais disponíveis em cada quadrado. Então cada peça tinha uma matriz [64] [8]. Eu peguei essa ideia e a comprimi em dois índices e uma tabela. A tabela contém um valor que informa se os 16 movimentos são possíveis, um índice mantém o deslocamento do movimento e o outro mantém a máscara.

deslocamento [] = {-8, -1, 1, 8, -9, -7, 7, 9, -17, -15, -10, -6, 6, 10, 15, 17};

mask [] = {1, 2, 4, 8, 16, 32, 64, 128, 256, ...};

Então, a geração de um movimento deslizante é tão fácil quanto procurar a validade de sua máscara em suas compensações permitidas contra a tabela de movimentos.

Os algoritmos melhoraram?

Obviamente, sim um pouco.

ou as melhorias foram principalmente devido aos mesmos algoritmos rodando mais rapidamente, graças ao hardware e software mais rápidos?

Menor nit: se os algoritmos melhoraram, então o software está melhorando, então não há "ou".

A Lei de Moore nos diz que a velocidade do processador dobrará aproximadamente a cada 18 meses. Isso significa que dobrou cerca de 13 vezes em 20 anos. Isso torna os processadores modernos em algum lugar na região 8.000 vezes mais rápidos. Portanto, de longe, a maior melhoria no desempenho do motor se deve ao hardware mais rápido.

No primeiro caso, essas melhorias algorítmicas são públicas?

E se sim, quais foram as melhorias? Onde posso ler sobre eles?

Bem, não foi o primeiro, foi o último. No entanto, as melhorias são principalmente de código aberto e visíveis livremente, baixando as fontes de mecanismos como o Stockfish . Talvez também valha a pena fornecer o link geral de download do Stockfish, pois o link do código-fonte específico provavelmente expirará quando a versão 9 for lançada.

É tudo sobre algoritmos.

Enfrentar um jogador de xadrez humano levou um dos computadores mais poderosos do mundo na época. Essa abordagem de computação de força bruta permitiu que a Deep Blue olhasse em torno de seis a oito movimentos à frente. Em uma disputa acirrada, a máquina acabou derrotando Kasparov por 3 1/2 jogos e 2 1/2.

Seis anos depois, Kasparov se envolveu em outra disputa entre homem e máquina. Desta vez, ele jogou contra o sucessor de Deep Blue, Deep Junior. O resultado foi uma série empatada em três jogos. A maior diferença foi que o Deep Junior rodou em uma máquina com cerca de um por cento do poder de computação do Deep Blue. Os algoritmos de xadrez haviam melhorado a ponto de alcançar praticamente o mesmo resultado, com cem vezes menos poder de computação.

Isenção de responsabilidade: não é um especialista.

Os algoritmos ficaram melhores e os melhores mecanismos atuais de 1995 (lembre-se que o Deep Blue era 1999) venceram Kasparov com facilidade. Pelo que entendi, existem dois aspectos dos algoritmos:

Pesquisar . Se, por exemplo, eu levar sua rainha com minha rainha, um oponente humano automaticamente procurará primeiro se recuperar. Para um computador, no entanto, ele avaliará todas as respostas possíveis ao QxQ. Na maioria das vezes, isso desperdiça poder de processamento. Um bom algoritmo de pesquisa reduz todos esses "ramos", pois eles são irrelevantes de qualquer maneira.

O algoritmo de pesquisa padrão é a poda alfa-beta e foi usado nos primeiros computadores de xadrez. Não sei se o Deep Blue usou poda alfa-beta, mas os motores modernos não. Como resultado, suas buscas são "inseguras" - elas podem perder, por exemplo, que alguns movimentos além de recuperar a rainha teriam vencido o jogo. No entanto, é raro que isso aconteça e, em troca, eles aumentam muito a profundidade. ("Profundidade" é um termo técnico para a profundidade em que o mecanismo pesquisa, por exemplo, um mecanismo que pesquisa em profundidade 30 provavelmente supera um que somente busca em profundidade 20, sendo todas as outras coisas iguais.

Avaliação . Este é o outro ponto do código do mecanismo. Dada uma posição específica, é melhor para branco, preto ou igual? Isso pode envolver todos os tipos de funções, por exemplo

• Se um lado tiver material / espaço extra, dê um bônus para avaliar.
• Se o branco tem um cavaleiro avançado apoiado por um peão, dê um bônus ao branco para avaliar.
• Se o rei do preto estiver impasse, dê um bônus às brancas para avaliar.
• Se as brancas tiverem uma torre no 7º ranking, dê um bônus às brancas para avaliar.
• Se for um fim de jogo (e houver algoritmos para decidir se a posição é um fim de jogo) e ambos os lados tiverem bispos de cores opostas, imponha uma penalidade para avaliar (ou seja, empurre-o para 0,00).

Os motores de hoje avaliam posições muito melhores que o Deep Blue.

Quanto ao fato de os algoritmos serem públicos, o Stockfish é atualmente o mecanismo mais forte do mundo e é de código aberto. Você pode fazer o download do código você mesmo no Github .