Qual é o limite inferior mais alto conhecido para mate em N da posição inicial?

Edit : Parece que minha pergunta não estava clara o suficiente. Deixe-me reformular: Qual é o maior N para o qual podemos conscientemente dizer "o xadrez, desde a posição inicial, não é um companheiro forçado nos movimentos de N"?

O xadrez não está resolvido, ou seja, não se sabe qual é o resultado perfeito da posição inicial.

No entanto, se a posição inicial for ganha para qualquer jogador, é um companheiro em N para alguns N. Além disso, por exemplo, se tivermos certeza de que a posição inicial não pode ser ganha em 5 jogadas (para qualquer jogador), 5 é um limite inferior para N.

Aproximadamente, até que ponto é possível pesquisar exaustivamente a partir da posição inicial na prática? Qual é o limite máximo de N conhecido?

Esta é essencialmente a questão de qual é a complexidade do jogo de xadrez. Observe que, por finura, sabemos que o xadrez é determinado, mas não sabemos se a posição inicial é uma vitória para as brancas, uma vitória para as pretas ou um empate. A complexidade do jogo de xadrez é aproximadamente o número mínimo de posições que precisamos verificar na árvore do jogo para determinar o estado da posição inicial. Isso é conhecido como número de Shannon . No influente artigo Programando um computador para jogar xadrez , Shannon estimou que o número de Shannon é de pelo menos 10 ^ {120). Observe que o número de partículas no Universo é estimado em 10 ^ (80). Para responder à pergunta, na verdade queremos saber a alturada árvore do jogo quando a posição inicial se torna determinada. Também devemos dividir essa altura por 2, pois um movimento no xadrez é normalmente considerado um movimento branco e preto. O fator de ramificação da árvore é estimado em cerca de 30. Assim, podemos pegar o maior N de modo que 30 ^ (2N) <10 ^ (120).

Responda. Na parte de trás do envelope, N = 40 funciona. Coincidentemente, isso acontece com a duração de um jogo médio entre os mestres (embora eles geralmente se demitam e não joguem o jogo até a conclusão).

Editar. A moral da história é que eu estava tentando estimar um limite superior para o seu limite inferior. A primeira parte do raciocínio de Shannon não é circular; ele diz que existem cerca de 30 jogadas legais de cada posição, e esse número é razoavelmente constante na primeira parte de um jogo.

Assim, podemos estimar o valor atual conhecido de N (que é realmente o que você está pedindo, vamos chamar de N ') como no máximo log_30 (C), em que C é igual à quantidade de poder de computação que existe na história da humanidade. Mesmo com estimativas conservadoras para C, obtemos algo como N 'no máximo 20. Na prática, não acho que alguém tenha realizado esse cálculo muito acima da árvore, pois, a priori, sabemos que o cálculo se torna inviável após muito tempo. baixa altura e não é necessário pesquisar exaustivamente a árvore para escrever bons programas de xadrez.

Observe, no entanto, que você está fazendo uma pergunta um pouco mais fraca, pois é possível que o estado inicial do jogo seja um empate com o jogo ideal. Portanto, é possível obter limites para N escrevendo um programa cujo objetivo era não perder o máximo de tempo possível. Poderíamos então jogar esse programa contra os melhores programas ou jogadores humanos do mundo e ver qual seria a duração de um jogo mais curto. Novamente, isso não responde adequadamente à pergunta, já que não podemos assumir que nossos oponentes estão jogando da melhor maneira . O jogo ideal verdadeiro requer conhecimento completo da árvore do jogo, mas vimos que isso é computacionalmente inviável. Assim, o melhor que podemos fazer atualmente é aproximar um oponente com um Kasparov ou um programa de xadrez muito bom.

Não é verdade que a posição inicial não seja ganha em 5 movimentos ou menos, usando a definição canônica de um movimento completo no xadrez. Isso pode ser feito em 2 movimentos através do companheiro do tolo .

Para responder à sua pergunta, a força de um mecanismo de xadrez depende do software e do hardware. Em 1997, o Deep Blue era uma prova do conceito de hardware, um supercomputador massivamente paralelo capaz de avaliar 200 milhões de jogadas por segundo com uma profundidade média de 7-8 jogadas. No entanto, em 2006, o Deep Fritz rodando em um computador pessoal de dois núcleos teve resultados equivalentes ao avaliar apenas 8 milhões de movimentos por segundo.

Hoje, o supercomputador mais forte aplicado ao xadrez é o Blue Gene . Usando 131.000 processadores, a Blue Gene pode calcular 280 trilhões de operações por segundo . Embora não existam dados para confirmar a profundidade em que o Blue Gene pode calcular, eu suponho que seria bastante profundo. Obviamente, isso depende de quanto tempo o computador funciona.

No entanto, neste caso, não podemos usar o termo 'exaustivo' ao 'resolver' e abrir. Um motor de xadrez não precisa ir até o final da linha quando estiver certo de que o resultado final é decisivo. Nesse sentido, o programa encerraria quando se tornasse claro que a avaliação era claramente a favor de um lado. Isso é conhecido na ciência da computação como poda alfa-beta .

Se eu tivesse que fazer uma estimativa aproximada, diria que o Blue Gene seria capaz de calcular entre 15 e 20 movimentos por segundo. Embora seu hardware e software sejam extremamente impressionantes, devemos lembrar que a complexidade do xadrez aumenta exponencialmente. De acordo com estimativas recentes , a complexidade da árvore de jogo do xadrez é de pelo menos 10 ^ 123 e o número de posições possíveis em 10 ^ 46,7.

Assumindo que há uma continuação vencedora de uma determinada posição e assumindo um jogo perfeito, implica Né fixo e não é limitado (caso contrário, não é um jogo perfeito!).

Nesse caso, é preciso realmente trabalhar para trás - o que é realizado pelo Endgame Tablebase

As bases de tabela de todos os jogos finais com até seis peças estão disponíveis para download gratuito e também podem ser consultadas usando interfaces da web (consulte os links externos abaixo). A base de tabela Nalimov requer mais de um terabyte de espaço de armazenamento

Você pode procurar aqui uma discussão. Claro que você não deve usar a regra dos 50 movimentos, mas, de acordo com este fórum, o registro é mantido até o momento nesta posição (preto para mover):

517 se move para uma posição vencedora e 525 para acasalar (melhor jogada de ambos os lados). Veja aqui , entrada 316. Portanto, esta é uma posição vencedora sem vitória em menos de 525 jogadas.

Permitam-me também reproduzir os comentários de Bourzutschky: "Podem existir ainda finais mais profundos de 7 homens, mas duvido. Que uma profundidade tão grande ainda seja possível com tanto poder de fogo no quadro sugere que finais mais profundos podem surgir com 8 peças, talvez em krnnkbbn. Esse final pode ser gerado com 64 GB de RAM em alguns meses em uma única CPU rápida e cerca de 5 terabytes de armazenamento.

Edit: Desculpe, parece que eu li mal a pergunta. Meu palpite é que qualquer N razoável está bem fora do horizonte de um computador. Se configurarmos um computador muito poderoso para calcular a posição inicial que provavelmente é o único X confiável que poderíamos mostrar, digamos que ele poderia 10 milhões de nós por segundo após 10 dias, poderíamos calcular 10 * 86400 * 10 ^ 8 nós = 8,64 * 10 ^ 13 nós. Se assumirmos que a posição média nos primeiros 20 movimentos tem cerca de 15 movimentos legais (menor porque o início tem muito menos e provavelmente até um pouco menor por causa da poda alfa-beta), que é apenas cerca de 12 movimentos após 10 dias (posição somente após o movimento 6 ) para ver por que esse problema é feio. No entanto, acho que o jogo prático provavelmente sugere um valor muito, muito, muito maior. EU'

Vamos ignorar que o xadrez provavelmente é um empate. Devemos considerar as regras sob as quais o xadrez é jogado na prática. Em quase todas as situações de torneio, há uma regra de 50 jogadas em vigor, que declara que o jogo é empate se "os últimos 50 jogadas consecutivas foram feitas por cada jogador sem o movimento de nenhum peão e sem a captura de nenhuma peça".

Portanto, isso significa que podemos ter 49,5 movimentos por captura ou movimento de peão. Cada peão pode se mover até 6 vezes e há 15 peças que podem ser capturadas para cada lado (embora uma peça deva ser entregue para o xeque-mate), para que possamos colocar um limite superior no número de movimentos.

Isso resulta em 49,5 * (8 * 2 * 6 (movimentos de peões) + 29) = 6187,5 Portanto, isso significa que, se o xadrez é uma vitória forçada para as brancas, aderindo à regra dos 50 movimentos, é no máximo 6188 jogadas para as brancas . Provavelmente, eu poderia diminuir um pouco isso sem fazer muito, dizendo que todos os companheiros de peça de K + v companheiros de K que são forçados (apenas Rook at Queen) são factíveis em substancialmente menos de 50 movimentos (penso em 16 brincando com Nalimov por Em alguns casos "difíceis", acho que podemos subtrair 34 movimentos desse total com confiança para 6134!

Portanto: se o xadrez é uma vitória forçada para as brancas, aderindo à regra dos 50 movimentos, é no máximo 6134 movimentos.