A profundidade (número de camadas) ainda é importante quando é alta o suficiente?

Isso não é real, apenas imagine isso acontecendo.

Computer Aé supercomputador. Pode calcular 30 dobras em 20 segundos.

Computer Bé supercomputador. Pode calcular 15 dobras em 20 segundos.

Eles jogam um contra o outro xadrez.

Essas 15 profundidades realmente importam? Acho que nessas 15 profundezas pode haver um trilhão de maneiras de escapar de um xeque-mate ou de uma peça importante. Claro, Computer Asabe mais. Mas Computer Bé capaz de prever o futuro também, na minha opinião, o suficiente para se defender muito bem.

Sim, essas 15 profundidades são muito importantes.

Considere esta posição que ocorreu no jogo imortal de Kasparov contra Topalov.

Eu testei essa posição com vários motores. Alguns motores, na profundidade 15, não conseguiram detectar que 24 ... cxd4 é uma jogada perdida e pensei que estava ganhando. Esses mesmos motores, em maior profundidade, jogaram o movimento correto 24 ... Kb6!

Por exemplo, mesmo um mecanismo tão poderoso quanto o Stockfish 4, inicialmente na profundidade 21, acha que o movimento perdedor 24 ... cxd4 está correto.

Stockfish DD 64 SSE4.2: 24...cxd4 25. Re7+ Kb6 26. Qxd4+ Kxa5 27. Qc3+ Kb6 
28. Qd4+ Qc5 29. Qxf6+ Bc6 30.Qxc6+ Qxc6 31. dxc6 Rd1+ 32. Ka2 f5 33. c7 Rc8 
34. Rxh7 Rxc7 35. Rh6 Rc6 36. g4 f4 37. g5 Rd2 38. c3 Rxc3 39. Rxg6+ Kc5 
40. Bg4 Rcc2 41. Rxa6 Rxb2+ 42. Ka1 Rbc2 43. Kb1 
(-1.45/21)

O mesmo mecanismo, quando mantido por um pouco mais de profundidade, mostra 24 ... Kb6 para o movimento correto.

Stockfish DD 64 SSE4.2: 24...Kb6 25. b4 Qxf4 26. Rxf4 Nxd5 27. Rxf7 cxb4 
28. axb4 Rhe8 29. Rxe8 Rxe8 30. Nb3 Re1+ 31. Kb2 Re2 32. Rxh7 Nxb4 
33. Kc3 Nd5+ 34. Kd3 Rxh2 35. Rh4 Ne7 36. Nd4 Nc6 37. Nxc6 Bxc6 38. f4 Kc5 
39. Be6 Rxh4 40. gxh4 Bd5 41. f5 gxf5 42. Bxf5 a5
(-0.78/26)

O Fritz 11 SE, na profundidade 15, também falhou. Mas encontrou o movimento correto na profundidade 16!

Fritz 11 SE: 24... cxd4 25. Qxd4+ Qb6 26. Re7+ Nd7 27. Qe5 f6 28. Qc3 Qg1+ 
29. Ka2 Bxd5+ 30. Nb3 f5 31. Qc7+ Ka8 32. Rxd7 Rxd7 33. Qxd7 Bxf3 34. Qd6 Qa7  
(-1.44/15) 

Fritz 11 SE: 24... Kb6 25. b4 Qxf4 26. Rxf4 Nxd5 27. Rxf7 cxb4 28. axb4 Nxb4 
29. Nb3 Bd5 30. Rf6+ Nc6 31. Nd4 Rdf8 32. Rd6 Kc5 33. Rxc6+ Bxc6 34. Ne6+ Kd6 
35. Nxf8 
(-0.59/16)

Considere também esse problema incrível, como a posição que encontrei aqui .

O Stockfish não conseguiu encontrar a linha vencedora 1. Be2 +! até a profundidade 31 e até então achava que era uma péssima jogada. Eu demonstro a vitória aqui. O ponto é que as pretas estão em zugswang por causa das ameaças dos companheiros e precisam desistir da rainha ou mover o peão que permitiria às brancas criar um peão passado e vencer.

Aqui está o registro do motor do Stockfish 4. Como você pode ver, ele detecta que 1. Be2 + está ganhando, apenas na profundidade 31!

Stockfish DD 64 SSE4.2: 1. Be2+ Kf5 2.Bc4 c6 3. Ne2 Qf6 4. Kg2 Kg4 5. Nf4 Qxd4 
6. Bd3 Qe3 7. Be2+ Kf5 8. Bf3 Qd2+ 9. Kh3 Qxb4 10. e7 Qe1 11. Ne2 Qf1+ 12. Kh2 Qf2+
13. Kh3 Qe3 (-1.05/22) 

Stockfish DD 64 SSE4.2: 1. Be2+ Kf5 2. Bc4 Qf6 3. Ne2 c6 4. Bxa6 Qxe6 5. Bd3+ Kf6 
6. Nf4 Qe1 7. d5 Qxb4 8. dxc6 Qxc5 9. Be4 Ke7 10. c7 Kd7 11. Nd5 Kd6 12. Kh3 Qc4 
13. Bg2 Qg4+ 14. Kh2 Qc8 15. Be4 (-1.15/26) 

Stockfish DD 64 SSE4.2: 1. Be2+ Kf5 2. Bc4 Qf6 3. Ne2 c6 4. d5 cxd5 5. Bxd5 Qb2 
6. Bc4 Kf6 (-1.01/28) 

Stockfish DD 64 SSE4.2:  1. Be2+ Kf5 2. Nd5 Qxe6 3. Bd3+ Kg4 4. Be4 Qh6 5. Nf4 Qf6 
6. Nd3 Qxd4 7. c6 Qxe4 8. Nf2+ Kf3 9. Nxe4 Kxe4 10. Kg2 Ke5 11. Kf3 Kf5 12. g4+ Kf6
13. gxh5 Kg7 14. Kf4 Kf6 15. h6 Kg6 16. h5+ Kh7 17. Kg5 Kg8 18. h7+ Kxh7 19. Kf5 Kg7
20. Ke6 Kh6 21. Kd7 Kxh5 22. Kxc7 Kg5 23. Kd7 (6.06/31) 

A relação entre ganhos de desempenho e profundidade de pesquisa é, na verdade, uma área ativa de pesquisa há bastante tempo nas comunidades de programação de xadrez de computador. Havia uma teoria de que aumentos na profundidade da pesquisa resultavam em retornos decrescentes na força ... isso parecia ser verificado em resultados experimentais.

Na minha perspectiva, há uma base intuitiva para isso. Imagine sua correspondência hipotética entre dois supercomputadores, começando pelas posições da base da tabela no final do jogo. A maioria das vitórias forçadas em mesas ocorre em um horizonte inferior a (por exemplo) 50 dobras. A maioria das posições restantes é sorteada, apenas uma pequena fração resolve vencer em uma profundidade maior. Um computador pesquisando 100 dobras teria vantagem limitada sobre um computador de 50 dobras, porque (como você mencionou) o programa mais fraco é capaz de navegar por quase todas as linhas perdidas, ocorrendo em profundidade mais limitada. Na verdade, um programa de 50 dobras teria uma vantagem muito maior do que um programa de 25 dobras ... assim como um programa de 4 dobras teria uma vantagem ainda maior do que um programa de 2 dobras.

Eu me deparei com esse conceito pela primeira vez há cerca de 15 anos, na série de artigos sobre Dark Thought , experimentando pesquisas profundas. Esta é uma ótima leitura se você estiver interessado em xadrez por computador.

Embora eu não tenha encontrado uma referência on-line, há um artigo do ano passado sobre esse tópico ...

Diogo R. Ferreira (2013). O impacto da profundidade da busca na força do jogo de xadrez. ICGA Journal, vol. 36, n. 2

A pergunta é: você quer dizer 15/30 dobras de pesquisa exaustiva ou uma profundidade / iteração nominal de 15/30 de um mecanismo de xadrez moderno como o Stockfish?

Se você quis dizer o último, 15 dobras não significa necessariamente muito. Os modernos mecanismos de xadrez podam e reduzem os movimentos supostamente ruins, portanto pode ser que um sacrifício que pareça ruim à primeira vista, a uma profundidade / iteração nominal de 15, na verdade seja apenas pesquisado a uma profundidade de, por exemplo, 5-10. Na profundidade / iteração 30, o movimento provavelmente ainda é pesquisado apenas para uma profundidade reduzida, mas pode ser uma profundidade efetiva de 15 a 20, o que pode ser suficiente para descobrir que o sacrifício é realmente bom e assim que o mecanismo descobre que a movimentação é promissora, ela diminuirá a redução, de modo que a movimentação seja pesquisada a uma profundidade mais próxima de 30 dobras (ou ainda mais profunda devido a extensões e pesquisa por quiescência). Então, sim, acho que pode fazer a diferença, mesmo que a combinação esteja dentro do horizonte nominal de 15 dobras.

Se você estava se referindo a uma pesquisa exaustiva, acho que um mecanismo com profundidade de 15 seria muito forte, desde que tenha uma boa função de avaliação e algum tipo de pesquisa de quiescência (depois dos nós de saída na profundidade 15). Devido aos retornos decrescentes, acho que o ganho dobrando a profundidade seria muito menor do que o que você obteria por uma correspondência entre dois motores modernos com profundidade 15 vs. profundidade 30. Mas isso é obviamente apenas teórico, pois uma pesquisa exaustiva para a profundidade 15 levaria várias ordens de magnitude a mais do que o que os motores normalmente levam para atingir a profundidade / iteração 15, de modo que esse experimento só seria viável em profundidades mais baixas.

FWIW Quando o ARM era novo, escrevi um programa de pesquisa exaustivo otimizado para ARM, com uma avaliação de posição apenas de material após a dobra 1.

Usei truques com código de máquina otimizado, aprofundamento iterativo, janelas alfa-beta em movimentos ordenados (quase todas as posições tinham valor 0, então obtive uma poda alfa-beta quase ideal) - e tabelas de hash que reduziram o fator de ramificação para muito menos do que o raiz quadrada teórica do alfa-beta, geralmente em torno de 4 na pior parte do jogo.

Em uma competição contra os programas padrão da época, meu programa E6P chegou a posições terríveis, mas com uma dobra ou duas pesquisas exaustivas em comparação com o software profissional da época (ou seja, normalmente 6 dobras exaustivas + pesquisa inativa no pior estágio, com até 12 dobras quando o jogo foi simplificado), ele continuou se esquivando de perder, apesar da confiança de seus oponentes. Quase todos os jogos foram julgados após muitas horas, porque os programas adversários não podiam vencer.

Mais tarde, otimizei-o para o StrongARM, onde passou para 10 dobras. Esta versão pode facilmente derrotar todos os jogadores que não são de xadrez, embora obviamente não tenha conhecimento de estratégia, então o famoso comentário se aplicava: sim, são movimentos de xadrez - mas não é xadrez!

Isso foi há alguns anos atrás, mas estou tentado a tentar exaustivamente novamente com uma avaliação de posição mais estratégica na dobra 1 - e com um Intel XEON teoricamente 10.000 a 100.000x mais rápido (e com 30k vezes mais memória de tabela de hash) que um 4MIPS ARM2 Bolota Arquimedes.

É certo que não é mainstream, mas divertido de jogar.

+1 dobras é estimado + 55..70 ganho de ELO (muitas pesquisas sobre esse tópico)

Acho que nessas 15 profundezas pode haver um trilhão de maneiras de escapar de um xeque-mate ou de uma peça importante.

O fato é que todos esses "trilhões" foram calculados com A @ D = 30, e se A escolher se mover com avaliação vencedora, significa que calculou todos esses "trilhões" e não importa qual dos "trilhões" move a resposta do oponente - mova ainda está ganhando