Banco de dados de todos os movimentos possíveis no xadrez

13

Imagine que exista um banco de dados de xadrez de todos os movimentos e posições possíveis. Este banco de dados contém todos os movimentos possíveis, da abertura ao fim do jogo.

Se joguei usando minha intuição contra um mecanismo de xadrez, ele pode prever qual jogada me fará perder e vencer.

Portanto, isso significa que não há necessidade de um "mecanismo de xadrez" porque todos os movimentos possíveis já estão registrados.

Se esse banco de dados existir, ele terá as seguintes vantagens:

  • Em jogos de blitz rápido, o mecanismo de xadrez definitivamente perderá contra o banco de dados de movimentos de possibilidade de xadrez.
  • Podemos saber exatamente qual abertura terá mais oportunidades de ganhar contra os outros.

Ou, se esse banco de dados ainda não existisse, poderíamos ter um cálculo matemático de todos os movimentos possíveis, desde a abertura até o final do jogo.

Seria possível que esse banco de dados existisse?

Ahmad Azwar Anas
fonte
4
Não, não é possível com nenhuma tecnologia imaginável.
Tony Ennis
Estou vagando um pouco .. E ainda não o criou. Você está certo. Ahaha.
Ahmad Azwar Anas 01/03
Boa sorte a construção de um banco de dados com mais bytes do que átomos no universo
David

Respostas:

32

Acredito que sua pergunta se resume essencialmente ao tema de se é possível "resolver" completamente o xadrez. A Wikipedia possui um excelente artigo sobre o assunto, que deve fornecer uma boa visão geral.

Para resumir, o número de variações possíveis de jogos no xadrez é estimado em 10 ^ 120. Este é um número incrivelmente grande, para comparação, considere que o número de átomos no universo observável é estimado em cerca de 10 ^ 80 . Em outras palavras, se você estivesse usando todo o universo observável como seu disco rígido, ainda precisaria armazenar 10 ^ 40 combinações de jogos de xadrez em cada átomo , para simplesmente armazenar tudo. Escusado será dizer que isso está muito além das nossas tecnologias atuais e previsíveis, que a maioria das pessoas considera completamente impossível.

Os jogos finais de xadrez são consideravelmente menos complexos, e chegamos a um ponto em que é possível calcular todas as combinações possíveis para jogos finais de cinco e seis peças . Normalmente, esses empreendimentos são enormes, feitos por pesquisadores de pesquisa com acesso a supercomputadores, e os bancos de dados resultantes do jogo final são enormes (da ordem de centenas de terabytes). Cada vez que uma nova peça é adicionada, o tamanho e a complexidade dos cálculos aumentam exponencialmente, o que significa que, em um futuro previsível, podemos esperar que esses resultados se expandam em apenas algumas peças.

Daniel B
fonte
agora estou imaginar que há algoritmo que representam End Table Jogo .. ^^
Ahmad Azwar Anas
2
@AhmadAzwarAnas Bem, acho que os mais simples já são usados ​​nos motores de xadrez, e os mais completos serão adicionados conforme a tecnologia permitir. Em termos de algoritmo, acho que você pode "compactar" uma tabela de jogo final analisando-a por padrões e generalizando-a em um conjunto de regras que claramente levam a um resultado. Com toda a probabilidade, no entanto, esse conjunto de regras ainda seria absolutamente maciço, pois pequenas variações (como ter oposição ou não) podem mudar o resultado do jogo.
Daniel B
@AhmadAzwarAnas, na verdade, por que não apenas um algoritmo para o xadrez? deve haver um movimento em todo jogo perdido que seja errado, certo? isto é, o movimento antes do qual existia um caminho para não perder, independentemente do movimento dos adversários, mas após o que isso não é mais verdade. então "tudo" o algoritmo deve fazer é identificar esses movimentos para que você possa evitá-los.
Michael
1
@ Michael, é mais difícil do que isso - como você pode saber que existe um caminho para vencer, independentemente do que o oponente se move? na melhor das hipóteses, haveria apenas 50% das vezes, porque se uma pessoa vencer, a outra será forçada a perder. Na verdade, vamos voltar às posições iniciais - para que exista um caminho mais adiante no jogo, deveria existir um "caminho absoluto para a vitória" naquele momento - se descobrimos isso, por que alguém jogaria mais a cor perdida , sabendo que, independentemente do que eles se movem, eles perderão? por que alguém mais jogaria xadrez se pudéssemos fazer isso?
user2813274
1
+1, mas sua análise está errada. Para armazenar uma base de tabela, você só precisa armazenar cada posição, não cada jogo possível. Shannon estima que existem cerca de 10 ^ 43 posições , o que se compara a cerca de 10 ^ 50 átomos na Terra . Então você pode resolver o xadrez transformando a Terra inteira em um computador .
David Richerby
7

Não, não seria possível que esse banco de dados existisse. Calculá-lo exigiria um computador imensamente grande e o cálculo levaria tanto tempo que seu computador não existiria por tempo suficiente para concluir a tarefa.

Claude Shannon estimou que existem cerca de 10 43 posições possíveis no xadrez e seu banco de dados precisaria armazenar o resultado de todas elas (isso seria, essencialmente, uma base de tabela de 32 homens ). No entanto, estima-se que a Terra contenha apenas cerca de 10 50 átomos; portanto, mesmo se você pudesse construir uma célula de memória com apenas 10.000.000 de átomos, ainda seria necessário um computador do tamanho da Terra para armazenar todas as posições.

Mas um computador tão grande traz grandes problemas. O diâmetro da Terra é de cerca de 12.800 quilômetros e a luz leva cerca de 43ms para atravessar essa distância. Isso significa que, se um ciclo de clock durar mais de 43ms, você não apenas terá uma distorção horrível do relógio, mas diferentes partes do seu computador não estarão no mesmo ciclo de clock. Evitar isso limita a velocidade do relógio a cerca de 23,5Hz (não GHz ou MHz; apenas Hz). Mesmo se você pudesse avaliar completamente uma posição em um único ciclo de relógio, isso significa que o computador levaria cerca de 4,3 x 10 41 segundos para concluir sua tarefa. Isso é cerca de 1,4x10 34 anos. São 14 milhões de bilhões de bilhões de anos.

Os astrofísicos acreditam que o universo parecerá radicalmente diferente em 1,4x10 34 anos do que agora. Até então, as estrelas deixaram de existir há muito tempo e até elementos que não são de maneira significativa radioativos terão sofrido grandes quantidades de decaimento radioativo. Até os prótons que formam núcleos atômicos sofreram decaimento radioativo significativo. Portanto, seu computador do tamanho da terra simplesmente não existirá mais.

David Richerby
fonte
2
Então você quer dizer que há uma chance?
bpromas
5

Acho que a resposta de Daniel é excelente (+1), mas quero acrescentar alguns pensamentos de qualquer maneira.

Uma base de mesa de 32 peças substituiria realmente os mecanismos de xadrez? A resposta é definitivamente não!

Para jogar um bom xadrez, são necessárias mais informações do que se uma jogada está ganhando, empatando ou perdendo. É claro que esse banco de dados seria imbatível, mas também não venceria ninguém.

Para jogar xadrez com força, não basta escolher uma jogada sem perder a cada turno. Dos muitos movimentos de empate em cada posição, há apenas alguns que exercem pressão real sobre o oponente.

Os mecanismos de xadrez existentes são significativamente mais fortes acessando as bases de tabela. Mas à medida que os bancos de dados crescem, o tempo de acesso se tornaria um fator proibitivo muito antes de usar todos os átomos do universo para memória ;-).

Então, acho que sua conclusão está errada: esse banco de dados nunca perderia e quase nunca venceria. Isso não nos diz nada sobre vagas, exceto que quase todas são empates. Provavelmente poderíamos criar novos algoritmos para explorar esse banco de dados e chegar a conclusões interessantes sobre todos os tipos de posições, mas acho que isso não mudaria o mundo do xadrez de maneira significativa.

BlindKungFuMaster
fonte
Você entendeu mal o que o banco de dados conteria. Cada jogada possível seria marcada como "Se eu jogar isso, meu oponente pode forçar uma vitória o que eu fizer a seguir", "Se eu jogar isso, eu posso forçar uma vitória o que meu oponente fizer a seguir" ou "empate". Portanto, você não jogaria "jogadas sem perder a cada turno": jogaria vitórias forçadas a cada turno, desde que tal jogada existisse.
David Richerby
Bem, na verdade eu entendi exatamente o que o banco de dados conteria ... O ponto que eu estava tentando destacar é que, nos jogos de xadrez de alto nível "Não há vitórias forçadas!" em mais de 90% das posições. E você precisa de muito mais informações do que "esse lance empata e esse lance perde" para realmente chegar a uma posição vencedora contra um jogador decente.
BlindKungFuMaster
1
Para dar um exemplo: na posição inicial, com toda a probabilidade, as únicas informações no banco de dados seriam "Todos os movimentos desenham". Então você estaria completamente sozinho. E se você está completamente sozinho, como consegue uma posição vencedora contra um jogador forte? A resposta é: você não. Sua posição ficará cada vez pior até o ponto em que você seguir a única linha de desenho.
BlindKungFuMaster
Não, isso não está certo. É trivial conseguir sua jogada vencedora. Simplesmente calcule todos os movimentos possíveis da posição atual, verifique as posições resultantes no banco de dados e escolha um que ganhe ou empate. Por definição, se sua posição atual for "você venceu", haverá pelo menos uma nas próximas posições que é "você venceu"; e se a sua posição atual for "empate", pelo menos uma das próximas posições será "empate" (e possivelmente algumas "você ganha" se o seu oponente não jogar perfeitamente).
Ignacio Calvo
O ponto é que a posição atual geralmente não é "você vence". Por exemplo, é muito provável que não haja vitória forçada na posição inicial.
BlindKungFuMaster
3

Acho que um dia o xadrez será resolvido. Por quê? Porque, bem, não faz muito tempo, jogar xadrez contra um computador era estranho e impensável! Como você pode treinar um computador para jogar xadrez? Bem, eles fizeram isso! (Além disso, a idéia de um computador era estranha ...) Meu argumento é que pode parecer estranho, porque nunca vimos ou ouvimos falar dele. Não é algo que possamos imaginar facilmente. Mas a tecnologia está se expandindo a uma taxa exponencial. Eu não ficaria surpreso se, em um futuro próximo (mais de 10 anos), isso fosse resolvido, de uma forma ou de outra.

Ryan Orr
fonte
O obstáculo para resolver o xadrez é a quantidade literalmente astronômica de dados que você precisa classificar. Shannon estimou que existem aproximadamente 10 ^ 43 posições no xadrez e você precisaria armazenar o resultado para cada uma delas. Para colocar isso em perspectiva, a Terra contém cerca de 10 ^ 50 átomos; portanto, mesmo se você pudesse construir uma célula de memória de 10.000.000 átomos, ainda seria necessário converter a Terra inteira em um banco de memória apenas para armazenar o resultado!
David Richerby
1
@DavidRicherby Digamos que o xadrez seja um empate com a melhor jogada. Então, para cada movimento branco, há uma resposta adequada para o preto. Para o próximo movimento branco, o preto também tem uma resposta adequada e assim por diante. É concebível que a construção de uma "árvore de desenho" exija muito menos que 10 ^ 43 posições.
Dag Oskar Madsen
2
@DagOskarMadsen Sim, é possível que realmente armazenar a árvore exija muito menos memória (embora ainda seja uma quantidade astronômica). No entanto, a técnica atual para construir essas árvores é fazer análises retrógradas de todas as posições finais, o que exige a criação do banco de dados completo do que fazer em todas as posições, como pelo menos um estágio intermediário.
David Richerby
Lamento anunciar que você está errado! @DagOskarMadsen Mas se você não sabe refutar as respostas "inadequadas", pode realmente afirmar que resolveu o jogo?
David
2

De volta à faculdade, no início dos anos 80, li em um jogo um texto que, se um computador pudesse planejar, avaliar e executar um movimento, qualquer movimento, desde o início do jogo até todas as conclusões possíveis a cada 1/3 de nanossegundo, isto é, aproximadamente 3 bilhões de movimentos / segundo, para fazer isso para cada resultado concebível levaria 10 a 120 séculos para ser concluído. E quem tem tanto tempo para esperar?

Outra estatística impressionante? Você obviamente ouviu falar de um googol? Não é o Google, mas o número? É 10 a 100 potência. Um 10 seguido por 100 zeros. Agora imagine o googolplex. Isso é 10 para o poder do googol'th.

Eu li que não há o suficiente de qualquer coisa no universo conhecido, nem mesmo átomos, para exigir o uso do Googleplex. De fato, até o googol é grande demais para descrever qualquer coisa. Você deve conferir algumas das curiosidades surpreendentes sobre esses números.

Jon
fonte
-1

Sim, acho que seria possível. Mas apenas se o banco de dados fosse mais como uma rede neural, realizando movimentos que causavam a sua perda e excluindo-os. Esse cálculo é baseado em exponenciar (tenha paciência comigo) todas as ações possíveis em um jogo de xadrez no primeiro movimento, no 100 ou algo assim. Enquanto isso, se nos livramos das repetições, ((Ke3 Ke4 Ke3 Ke4) em loop) 10 ^ 120 provavelmente poderia se tornar algo como 10 ^ 70. Isso ainda é ridiculamente grande, mas se de alguma forma pudéssemos codificá-lo em um avião 4D (que eu acredito que seja possível), seria brincadeira de criança.

user19889
fonte
2
Bem-vindo ao xadrez ! Por favor, faça o passeio enquanto você está nisso. Sua postagem pode ter voto negativo porque é mais uma opinião e menos uma resposta, como esperamos aqui; consulte o artigo da Central de Ajuda Como responder .
Glorfindel
1
Eu não sou um jogador de xadrez e, para constar, também não sou uma das pessoas que menosprezaram seu voto, mas li que existem 10 ^ 43 posições diferentes. Só porque você tem um método que permite filtrar alguns dados, por que você assume automaticamente que isso é possível? Eu acho que você está subestimando exatamente o quão concebivelmente grande esse banco de dados precisaria ser. Isso está tão além do escopo da tecnologia de computação moderna que não consigo imaginar que estamos em uma trajetória para que isso aconteça daqui a um século. Mas seja bem-vindo ao SE Chess. (E me receber, também, suponho: P)
Joe Majewski