Existe um algoritmo perfeito para o xadrez? [fechadas]

Recentemente, estive em uma discussão com uma pessoa que não é codificadora sobre as possibilidades dos computadores de xadrez. Não sou muito versado em teoria, mas acho que sei o suficiente.

Argumentei que não poderia existir uma máquina de Turing determinística que sempre ganhasse ou empatasse no xadrez. Eu acho que, mesmo se você pesquisar todo o espaço de todas as combinações de movimentos do jogador 1/2, o único movimento que o computador decide em cada etapa é baseado em uma heurística. Sendo baseado em uma heurística, não necessariamente vence TODOS os movimentos que o oponente poderia fazer.

Meu amigo pensava, ao contrário, que um computador sempre ganharia ou empataria se nunca fizesse uma jogada "errada" (como você define isso?). No entanto, sendo um programador que estudou CS, eu sei que mesmo suas boas escolhas - dado um oponente sábio - podem forçá-lo a cometer movimentos "errados" no final. Mesmo se você souber de tudo, seu próximo movimento é ganancioso em combinar uma heurística.

A maioria dos computadores de xadrez tenta combinar um possível jogo final com o jogo em andamento, que é essencialmente um rastreio de programação dinâmico. Mais uma vez, o final do jogo em questão é evitável.

Edit: Hmm ... parece que errei algumas penas aqui. Isso é bom.

Pensando novamente, parece que não há problema teórico em resolver um jogo finito como o xadrez. Eu diria que o xadrez é um pouco mais complicado do que as damas, pois uma vitória não é necessariamente por exaustão numérica das peças, mas por um companheiro. Minha afirmação original provavelmente está errada, mas, novamente, acho que apontei algo que ainda não foi provado satisfatoriamente (formalmente).

Acho que meu experimento mental foi que sempre que um galho da árvore é pego, o algoritmo (ou caminhos memorizados) deve encontrar um caminho para um parceiro (sem ser acasalado) para qualquer galho possível nos movimentos do oponente. Depois da discussão, comprarei que, com mais memória do que podemos sonhar, todos esses caminhos podem ser encontrados.

"Argumentei que não poderia existir uma máquina de Turing determinística que sempre vencesse ou empatasse no xadrez."

Você não está certo. Pode haver tal máquina. O problema é a imensidão do espaço de estados que ele teria que pesquisar. É finito, é MUITO grande.

É por isso que o xadrez recorre à heurística - o espaço de estados é muito grande (mas finito). Até enumerar - muito menos procurar cada movimento perfeito ao longo de cada curso de cada jogo possível - seria um problema de pesquisa muito, muito grande.

As aberturas são programadas para levá-lo a um meio de jogo que lhe dê uma posição "forte". Não é um resultado conhecido. Mesmo os jogos finais - quando há menos peças - são difíceis de enumerar para determinar o melhor próximo movimento. Tecnicamente, eles são finitos. Mas o número de alternativas é enorme. Até mesmo 2 torres + rei tem algo como 22 próximos movimentos possíveis. E se forem necessários 6 movimentos para acasalar, você está olhando para 12.855.002.631.049.216 movimentos.

Faça as contas dos movimentos iniciais. Embora haja apenas cerca de 20 movimentos de abertura, existem cerca de 30 segundos movimentos, então no terceiro movimento estamos olhando para 360.000 estados de jogo alternativos.

Mas os jogos de xadrez são (tecnicamente) finitos. Enorme, mas finito. Existem informações perfeitas. Existem estados de início e fim definidos. Não há lançamentos de moeda ou dados.

Não sei quase nada sobre o que realmente foi descoberto sobre o xadrez. Mas, como matemático, aqui está o meu raciocínio:

Primeiro, devemos lembrar que as brancas vão primeiro e talvez isso dê a elas uma vantagem; talvez dê uma vantagem às pretas.

Agora, suponha que não haja uma estratégia perfeita para as pretas que o deixe sempre vencer / empatar. Isso significa que não importa o que as pretas façam, há uma estratégia que as brancas podem seguir para vencer. Espere um minuto - Isso significa que não é uma estratégia perfeita para White!

Isso nos diz que pelo menos um dos dois jogadores não têm uma estratégia perfeita que permite que o jogador sempre ganhar ou empatar.

Existem apenas três possibilidades, então:

• As brancas sempre podem vencer se jogarem perfeitamente
• As pretas sempre podem ganhar se jogarem perfeitamente
• Um jogador pode ganhar ou empatar se jogar perfeitamente (e se ambos os jogadores jogarem perfeitamente, eles sempre ficam paralisados)

Mas qual delas é realmente correto, talvez nunca saibamos.

A resposta à pergunta é sim : deve haver um algoritmo perfeito para o xadrez, pelo menos para um dos dois jogadores.

Está provado para o jogo de damas que um programa pode sempre ganhar ou empatar o jogo. Ou seja, não há escolha de movimentos que um jogador pode fazer que force o outro jogador a perder.

Os pesquisadores passaram quase duas décadas examinando os 500 bilhões de bilhões de possíveis posições de damas, que ainda é uma fração infinitesimalmente pequena do número de posições de xadrez, aliás. O esforço dos verificadores incluiu jogadores de primeira linha, que ajudaram a equipe de pesquisa a programar regras básicas dos verificadores em software que categorizava os movimentos como bem ou malsucedidos. Em seguida, os pesquisadores deixaram o programa rodar, em média, 50 computadores por dia. Alguns dias, o programa funcionou em 200 máquinas. Enquanto os pesquisadores monitoravam o progresso e ajustavam o programa de acordo. Na verdade, o Chinook venceu os humanos para ganhar o campeonato mundial de damas em 1994.

Sim, você pode resolver o xadrez, não, em breve não o fará.

Esta não é uma questão sobre computadores, mas apenas sobre o jogo de xadrez.

A questão é: existe uma estratégia à prova de falhas para nunca perder o jogo? Se tal estratégia existe, então um computador que sabe tudo pode sempre usá-la e não é mais uma heurística.

Por exemplo, o jogo da velha normalmente é jogado com base em heurísticas. Mas existe uma estratégia à prova de falhas. Qualquer que seja o movimento do oponente, você sempre encontrará uma maneira de evitar perder o jogo, se fizer isso desde o início.

Portanto, você precisaria provar se essa estratégia existe ou não para o xadrez também. É basicamente o mesmo, apenas o espaço de movimentos possíveis é muito maior.

Estou chegando neste tópico muito tarde e que você já percebeu alguns dos problemas. Mas, como ex-mestre e ex-programador de xadrez profissional, achei que poderia acrescentar alguns fatos e números úteis. Existem várias maneiras de medir a complexidade do xadrez :

• O número total de jogos de xadrez é de aproximadamente 10 ^ (10 ^ 50). Esse número é inimaginavelmente grande.
• O número de jogos de xadrez de 40 movimentos ou menos é cerca de 10 ^ 40. Esse ainda é um número incrivelmente grande.
• O número de posições de xadrez possíveis é cerca de 10 ^ 46.
• A árvore de pesquisa de xadrez completa (número de Shannon) é cerca de 10 ^ 123, com base em um fator de ramificação médio de 35 e uma duração média de jogo de 80.
• Para efeito de comparação, o número de átomos no universo observável é comumente estimado em cerca de 10 ^ 80.
• Todos os finais de 6 peças ou menos foram agrupados e resolvidos .

Minha conclusão: embora o xadrez seja teoricamente solucionável, nunca teremos o dinheiro, a motivação, o poder de computação ou o armazenamento para fazê-lo.

Alguns jogos foram, de fato, resolvidos. Tic-Tac-Toe é muito fácil de construir uma IA que sempre vencerá ou empatará. Recentemente, o Connect 4 também foi resolvido (e se mostrou injusto com o segundo jogador, já que uma jogada perfeita fará com que ele perca).

O xadrez, entretanto, não foi resolvido, e não acho que haja qualquer prova de que seja um jogo justo (ou seja, se o jogo perfeito resulta em empate). Falando estritamente de uma perspectiva teórica, porém, o xadrez tem um número finito de configurações de peças possíveis. Portanto, o espaço de busca é finito (embora incrivelmente grande). Portanto, existe uma máquina de Turing determinística que poderia tocar perfeitamente. Se algum dia poderia ser construído, entretanto, é uma questão diferente.

O desktop médio de $ 1000 será capaz de resolver verificadores em meros 5 segundos até o ano de 2040 (5x10 ^ 20 cálculos).

Mesmo nessa velocidade, ainda levaria 100 desses computadores aproximadamente 6,34 x 10 ^ 19 anos para resolver o xadrez. Ainda não é viável. Nem mesmo perto.

Por volta de 2080, nossos desktops médios terão aproximadamente 10 ^ 45 cálculos por segundo. Um único computador terá o poder computacional para resolver o xadrez em cerca de 27,7 horas. Isso definitivamente será feito em 2080, enquanto o poder de computação continuar a crescer como nos últimos 30 anos.

Em 2090, haverá poder computacional suficiente em um desktop de $ 1000 para resolver o xadrez em cerca de 1 segundo ... então, nessa data, será completamente trivial.

Verificadores de dados foi resolvido em 2007, e o poder computacional para resolvê-lo em 1 segundo vai ficar por cerca de 33-35 anos, podemos provavelmente aproximadamente estimar xadrez será resolvido em algum lugar entre 2055-2057. Provavelmente antes disso, pois quando mais poder computacional estiver disponível (o que será o caso em 45 anos), mais poderá ser dedicado a projetos como este. No entanto, eu diria 2050 no mínimo e 2060 no máximo.

Em 2060, seriam necessários 100 desktops em média 3,17 x 10 ^ 10 anos para resolver o xadrez. Perceba que estou usando um computador de $ 1000 como meu benchmark, enquanto sistemas maiores e supercomputadores provavelmente estarão disponíveis, já que sua relação preço / desempenho também está melhorando. Além disso, sua ordem de magnitude de poder computacional aumenta em um ritmo mais rápido. Considere que um supercomputador agora pode realizar 2,33 x 10 ^ 15 cálculos por segundo e um computador de $ 1000 cerca de 2 x 10 ^ 9. Em comparação, há 10 anos, a diferença era de 10 ^ 5 em vez de 10 ^ 6. Em 2060, a diferença de ordem de magnitude provavelmente será de 10 ^ 12, e mesmo isso pode aumentar mais rápido do que o previsto.

Muito disso depende se nós, como seres humanos, temos ou não a motivação para resolver o xadrez, mas o poder computacional tornará isso viável nessa época (contanto que nosso ritmo continue).

Por outro lado, o jogo Tic-Tac-Toe, que é muito, muito mais simples, tem 2.653.002 cálculos possíveis (com tabuleiro aberto). O poder computacional para resolver Tic-Tac-Toe em cerca de 2,5 (1 milhão de cálculos por segundo) segundos foi alcançado em 1990.

Retrocedendo, em 1955, um computador tinha o poder de resolver o jogo da velha (Tic-Tac-Toe) em cerca de 1 mês (1 cálculo por segundo). Novamente, isso é baseado no que $ 1000 obteriam se você pudesse empacotá-lo em um computador (um desktop de $ 1000 obviamente não existia em 1955), e este computador teria sido dedicado a resolver o jogo da velha .... que não era o caso em 1955. A computação era cara e não teria sido usada para esse propósito, embora eu não acredite que haja qualquer data em que o jogo da velha tenha sido considerado "resolvido" por um computador, mas estou certifique-se de que fica atrás do poder computacional real.

Além disso, leve em consideração que $ 1000 em 45 anos valerão cerca de 4 vezes menos do que é agora, portanto, muito mais dinheiro pode ir para projetos como este, enquanto o poder computacional continuará a ficar mais barato.

Na verdade, é possível que ambos os jogadores tenham estratégias de vitória em jogos infinitos sem uma boa ordenação; no entanto, o xadrez é bem organizado. Na verdade, por causa da regra dos 50 movimentos , há um limite superior para o número de movimentos que um jogo pode ter e, portanto, há apenas um número finito de jogos de xadrez (que podem ser enumerados para resolver exatamente .. teoricamente, finalmente :)

O fim do seu argumento é apoiado pela maneira como os programas de xadrez modernos funcionam agora . Eles funcionam dessa maneira porque exige muitos recursos para codificar um programa de xadrez para operar deterministicamente. Eles nem sempre funcionarão necessariamente dessa maneira. É possível que um dia o xadrez seja resolvido e, se isso acontecer, provavelmente será resolvido por um computador.

Só para constar, existem computadores que podem ganhar ou empatar nas damas . Não tenho certeza se o mesmo poderia ser feito para o xadrez. O número de movimentos é muito maior. Além disso, as coisas mudam porque as peças podem se mover em qualquer direção, não apenas para frente e para trás. Embora não tenha certeza, acho que o xadrez é determinístico, mas que existem muitos movimentos possíveis para um computador determinar todos os movimentos em um período de tempo razoável.

Eu acho que você está certo. Máquinas como Deep Blue e Deep Thought são programadas com vários jogos predefinidos e algoritmos inteligentes para analisar as árvores nas extremidades desses jogos. Isso é, obviamente, uma simplificação exagerada. Sempre há uma chance de "vencer" o computador ao longo de um jogo. Com isso quero dizer fazer um movimento que força o computador a fazer um movimento que não é o ideal (seja lá o que for). Se o computador não conseguir encontrar o melhor caminho antes do limite de tempo para a mudança, ele pode muito bem cometer um erro ao escolher um dos caminhos menos desejáveis.

Há outra classe de programas de xadrez que usa aprendizado de máquina real ou programação genética / algoritmos evolutivos. Alguns programas evoluíram e usam redes neurais, et al, para tomar decisões. Nesse tipo de caso, imagino que o computador possa cometer "erros", mas ainda assim terminar em uma vitória.

Há um livro fascinante sobre esse tipo de GP chamado Blondie24 que você pode ler. É sobre damas, mas poderia se aplicar ao xadrez.

Da teoria dos jogos, que é do que trata esta questão, a resposta é sim O xadrez pode ser jogado perfeitamente. O espaço do jogo é conhecido / previsível e sim, se você tivesse os computadores quânticos de seu neto, provavelmente poderia eliminar todas as heurísticas.

Você poderia escrever uma máquina perfeita de jogo da velha hoje em dia em qualquer linguagem de script e ela funcionaria perfeitamente em tempo real.

Othello é outro jogo que os computadores atuais podem facilmente jogar perfeitamente, mas a memória e a CPU da máquina precisarão de um pouco de ajuda

O xadrez é teoricamente possível, mas não praticamente possível (em 2008)

O i-Go é complicado, seu espaço de possibilidades ultrapassa a quantidade de átomos do universo, então pode levar algum tempo para fazer uma máquina i-Go perfeita.

O xadrez é um exemplo de jogo de matriz, que por definição tem um resultado ótimo (pense no equilíbrio de Nash). Se cada jogador 1 e 2 fizerem movimentos ótimos, um certo resultado SEMPRE será alcançado (se será uma vitória-empate-perda ainda é desconhecido).

Como um programador de xadrez dos anos 1970, definitivamente tenho uma opinião sobre isso. O que escrevi há cerca de 10 anos, ainda é basicamente verdade hoje:

"Trabalho inacabado e desafios para programadores de xadrez"

Naquela época, pensei que poderíamos resolver o xadrez de maneira convencional, se feito de maneira adequada.

Checkers foi resolvido recentemente (Yay, University of Alberta, Canada !!!), mas isso foi efetivamente feito de Brute Force. Para fazer xadrez de maneira convencional, você terá que ser mais inteligente.

A menos, é claro, que a Computação Quântica se torne uma realidade. Nesse caso, o xadrez será resolvido tão facilmente quanto o jogo da velha.

No início dos anos 1970 na Scientific American, houve uma pequena paródia que chamou minha atenção. Foi um anúncio de que o jogo de xadrez foi resolvido por um computador de xadrez russo. Ele determinou que há um lance perfeito para as brancas que garantiria uma vitória com jogo perfeito de ambos os lados, e esse lance é: 1. a4!

Muitas respostas aqui trazem importantes pontos teóricos do jogo:

1. O xadrez é um jogo finito e determinístico com informações completas sobre o estado do jogo
2. Você pode resolver um jogo finito e identificar uma estratégia perfeita
3. O xadrez é, no entanto, grande o suficiente para que você não seja capaz de resolvê-lo completamente com um método de força bruta

No entanto, essas observações perdem um ponto prático importante: não é necessário resolver o jogo completo perfeitamente para criar uma máquina imbatível .

Na verdade, é bastante provável que você possa criar uma máquina de xadrez imbatível (ou seja, nunca perderá e sempre forçará uma vitória ou empate) sem procurar nem mesmo uma pequena fração do espaço de estados possível.

As técnicas a seguir, por exemplo, reduzem maciçamente o espaço de pesquisa necessário:

• Técnicas de poda de árvores como Alpha / Beta ou MTD-f já reduzem enormemente o espaço de busca
• Posição vencedora provável. Muitos finais se enquadram nesta categoria: Você não precisa pesquisar KR vs K, por exemplo, é uma vitória comprovada. Com algum trabalho é possível provar muito mais vitórias garantidas.
• Vitórias quase certas - para um jogo "bom o suficiente" sem erros tolos (digamos sobre ELO 2200+?) Muitas posições de xadrez são vitórias quase certas, por exemplo, uma vantagem material decente (por exemplo, um Cavalo extra) sem nenhuma vantagem posicional compensatória. Se seu programa puder forçar tal posição e tiver heurísticas boas o suficiente para detectar vantagem posicional, ele pode assumir com segurança que vencerá ou pelo menos empatará com 100% de probabilidade.
• Heurísticas de pesquisa em árvore - com reconhecimento de padrões bom o suficiente, você pode rapidamente se concentrar no subconjunto relevante de movimentos "interessantes". É assim que os grandes mestres humanos jogam, então claramente não é uma estratégia ruim ... e nossos algoritmos de reconhecimento de padrões estão constantemente melhorando
• Avaliação de risco - uma melhor concepção do "risco" de uma posição permitirá uma pesquisa muito mais eficaz, concentrando o poder de computação em situações onde o resultado é mais incerto (esta é uma extensão natural da Pesquisa de Quiescência )

Com a combinação certa das técnicas acima, eu ficaria confortável em afirmar que é possível criar uma máquina de jogar xadrez "imbatível". Provavelmente não estamos muito longe da tecnologia atual.

Observe que é quase certamente mais difícil provar que esta máquina não pode ser derrotada. Provavelmente seria algo como a hipótese de Reimann - estaríamos bem certos de que ela joga perfeitamente e teríamos resultados empíricos mostrando que ela nunca perdeu (incluindo alguns bilhões de draws diretos contra si mesma), mas não teríamos realmente a capacidade de prove.

Nota adicional sobre "perfeição":

Tenho o cuidado de não descrever a máquina como "perfeita" no sentido da teoria do jogo, porque isso implica em condições adicionais excepcionalmente fortes, como:

• Vencendo sempre em todas as situações em que é possível forçar uma vitória, por mais complexa que seja a combinação vencedora. Haverá situações na fronteira entre vitória / empate onde isso é extremamente difícil de calcular com perfeição.
• Explorar todas as informações disponíveis sobre a imperfeição potencial no jogo de seu oponente, por exemplo, inferir que seu oponente pode ser muito ganancioso e deliberadamente jogar uma linha um pouco mais fraca do que o normal com base no fato de que tem um potencial maior para fazer seu oponente cometer um erro. Contra oponentes imperfeitos, pode de fato ser ideal perder se você estimar que seu oponente provavelmente não perceberá a vitória forçada e isso lhe dá uma probabilidade maior de vencer.

A perfeição (especialmente com oponentes imperfeitos e desconhecidos) é um problema muito mais difícil do que simplesmente ser imbatível.

se você pesquisar todo o espaço de todas as combinações de movimentos do jogador 1/2, o único movimento que o computador decide em cada etapa é baseado em uma heurística.

Existem duas ideias concorrentes aí. Uma é que você pesquisa todos os movimentos possíveis e a outra é que você decide com base em uma heurística. Uma heurística é um sistema para fazer uma boa estimativa. Se você estiver procurando por todos os movimentos possíveis, não estará mais adivinhando.

"Existe um algoritmo perfeito para o xadrez?"

Sim existe. Talvez seja para as brancas sempre vencer. Talvez seja para as pretas sempre vencer. Talvez seja para os dois sempre empatarem, pelo menos. Não sabemos qual, e nunca saberemos, mas certamente existe.

Veja também

• Algoritmo de Deus

Encontrei este artigo de John MacQuarrie que faz referência ao trabalho do "pai da teoria dos jogos" Ernst Friedrich Ferdinand Zermelo . Ele tira a seguinte conclusão:

No xadrez, o branco pode forçar uma vitória, ou o preto pode forçar uma vitória, ou ambos os lados podem forçar pelo menos um empate.

A lógica parece boa para mim.

É perfeitamente solucionável.

Existem 10 ^ 50 posições ímpares. Cada posição, pelas minhas contas, requer um mínimo de 64 bytes redondos para armazenar (cada quadrado tem: 2 bits de afiliação, 3 bits de peça). Depois de intercaladas, as posições que são xeque-mate podem ser identificadas e as posições podem ser comparadas para formar um relacionamento, mostrando quais posições levam a outras posições em uma grande árvore de resultados.

Então, o programa precisa apenas encontrar as raízes mais baixas do xeque-mate de um lado, se tal coisa existir. Em qualquer caso, o xadrez foi resolvido de forma bastante simples no final do primeiro parágrafo.

Estou apenas 99,9% convencido pela afirmação de que o tamanho do espaço de estados torna impossível esperar uma solução.

Claro, 10 ^ 50 é um número impossivelmente grande. Vamos chamar o tamanho do espaço de estado de n.

Qual é o limite para o número de movimentos no jogo mais longo possível? Como todos os jogos terminam em um número finito de movimentos, existe tal limite, chame-o de m.

Começando do estado inicial, você não pode enumerar todos os n movimentos no espaço O (m)? Claro, leva tempo O (n), mas os argumentos do tamanho do universo não tratam disso diretamente. O (m) espaço pode não ser muito. Para o espaço O (m), você também não poderia rastrear, durante esta travessia, se a continuação de qualquer estado ao longo do caminho que você está percorrendo leva a EitherMayWin, EitherMayForceDraw, WhiteMayWin, WhiteMayWinOrForceDraw, BlackMayWin ou BlackMayWinOrForceDraw? (Há uma treliça dependendo de quem é a vez, anote cada estado no histórico de sua travessia com o encontro da treliça.)

A menos que esteja faltando alguma coisa, é um algoritmo de espaço O (n) tempo / O (m) para determinar em qual das categorias possíveis o xadrez se enquadra. A Wikipedia cita uma estimativa para a idade do universo em aproximadamente 10-60 vezes Planck. Sem entrar em um argumento cosmológico, vamos adivinhar que ainda resta muito tempo antes do calor / frio / qualquer que seja a morte do universo. Isso nos deixa com a necessidade de avaliar um movimento a cada 10 ^ 10 vezes de Planck ou a cada 10 ^ -34 segundos. É um tempo impossivelmente curto (cerca de 16 ordens de magnitude mais curto do que os tempos mais curtos já observados). Vamos dizer de forma otimista que com uma implementação super-duper-good rodando no topo da linha de tecnologia presente ou previsível não quântica P-é-um-subconjunto-apropriado-de-NP, poderíamos esperar avaliar (tome uma único passo à frente, categorize o estado resultante como um estado intermediário ou um dos três estados finais) estados a uma taxa de 100 MHz (uma vez a cada 10 ^ -8 segundos). Como esse algoritmo é muito paralelizável, isso nos deixa a necessidade de 10 ^ 26 desses computadores ou cerca de um para cada átomo em meu corpo, junto com a capacidade de coletar seus resultados.

Suponho que sempre haja alguma esperança de uma solução de força bruta. Podemos ter sorte e, ao explorar apenas um dos movimentos de abertura possíveis das brancas, ambos escolheremos um com fanout muito inferior à média e um em que o branco sempre vence ou ganha ou empata.

Também podemos esperar reduzir um pouco a definição de xadrez e persuadir a todos de que ainda é moralmente o mesmo jogo. Precisamos mesmo exigir que as posições sejam repetidas 3 vezes antes de um empate? Nós realmente precisamos fazer o grupo que foge demonstrar habilidade para escapar por 50 movimentos? Alguém ao menos entende o que diabos está acontecendo com a regra en passant ? ;) Mais a sério, realmente precisamos forçar um jogador a se mover (ao invés de empatar ou perder) quando seu único movimento para escapar do cheque ou um impasse é en passant captura ? Poderíamos limitar a escolha de peças para as quais um peão pode ser promovido se a promoção de não-rainha desejada não levar a um xeque imediato ou xeque-mate?

Também estou incerto sobre o quanto permitir o acesso baseado em hash de cada computador a um grande banco de dados de estados de jogos atrasados ​​e seus resultados possíveis (que podem ser relativamente viáveis ​​em hardware existente e com bancos de dados de jogos finais existentes) poderia ajudar a eliminar a pesquisa anterior. Obviamente, você não pode memorizar a função inteira sem armazenamento O (n), mas pode escolher um número inteiro grande e memorizar muitos jogos finais enumerando para trás de cada estado final possível (ou mesmo impossível de ser provado facilmente, suponho).

Eu sei que isso é um pouco difícil, mas eu tenho que colocar meus 5 centavos aqui. É possível para um computador, ou uma pessoa para esse assunto, terminar cada jogo de xadrez em que ele / ela participa, seja com uma vitória ou um empate.

Para conseguir isso, no entanto, você deve saber precisamente todos os movimentos e reações possíveis e assim por diante, até o final de cada um dos resultados possíveis do jogo, e para visualizar isso, ou para fazer uma maneira fácil de analisar essas informações, pense em como um mapa mental que se ramifica constantemente.

O nó central seria o início do jogo. Cada ramificação de cada nó simbolizaria um movimento, cada um diferente de seus movimentos intermediários. Apresentá-lo nesta mansão exigiria muitos recursos, especialmente se você estivesse fazendo isso no papel. Em um computador, isso levaria possivelmente centenas de Terrabytes de dados, pois você teria muitos movimentos repetidos, a menos que fizesse os ramos voltarem.

Memorizar esses dados, entretanto, seria implausível, senão impossível. Fazer um computador reconhecer o movimento ideal para tirar (no máximo) 8 movimentos instantaneamente possíveis, seria possível, mas não plausível ... já que esse computador precisaria ser capaz de processar todos os ramos que se movem, até uma conclusão, conte todas as conclusões que resultam em uma vitória ou um impasse e, em seguida, aja com base no número de conclusões vencedoras contra conclusões perdidas, e isso exigiria RAM capaz de processar dados em Terrabytes, ou mais! E com a tecnologia de hoje, um computador como aquele exigiria mais do que o saldo bancário dos 5 homens e / ou mulheres mais ricos do mundo!

Então, depois de toda essa consideração, isso poderia ser feito, no entanto, ninguém poderia fazê-lo. Tal tarefa exigiria 30 das mentes mais brilhantes vivas hoje, não apenas no xadrez, mas na ciência e na tecnologia da computação, e tal tarefa só poderia ser concluída em um (vamos colocá-lo inteiramente na perspectiva básica) ... extremamente hiper super-duper computer ... que não poderia existir por pelo menos um século. Será feito! Só não nesta vida.

Existem dois erros em seu experimento de pensamento:

1. Se sua máquina de Turing não for "limitada" (em memória, velocidade, ...), você não precisa usar heurísticas, mas pode calcular avaliar os estados finais (vitória, derrota, empate). Para encontrar o jogo perfeito, você só precisa usar o algoritmo Minimax (consulte http://en.wikipedia.org/wiki/Minimax ) para calcular os movimentos ideais para cada jogador, o que levaria a um ou mais jogos ideais.

2. Também não há limite para a complexidade da heurística usada. Se você pode calcular um jogo perfeito, também há uma maneira de calcular uma heurística perfeita a partir dele. Se necessário, é apenas uma função que mapeia as posições do xadrez na forma "Se estou nesta situação S, meu melhor lance é M".

Como outros já apontaram, isso terminará em 3 resultados possíveis: o branco pode forçar uma vitória, o preto pode forçar uma vitória, um deles pode forçar um empate.

O resultado de um jogo de damas perfeito já foi "calculado". Se a humanidade não se destruir antes, haverá também um cálculo para o xadrez algum dia, quando os computadores tiverem evoluído o suficiente para ter memória e velocidade suficientes. Ou temos alguns computadores quânticos ... Ou até que alguém (pesquisador, especialista em xadrez, gênio) encontre alguns algoritmos que reduzam significativamente a complexidade do jogo. Para dar um exemplo: Qual é a soma de todos os números entre 1 e 1000? Você pode calcular 1 + 2 + 3 + 4 + 5 ... + 999 + 1000 ou pode simplesmente calcular: N * (N + 1) / 2 com N = 1000; resultado = 500500. Agora imagine não conhecer essa fórmula, você não sabe sobre indução matemática, você nem sabe como multiplicar ou somar números, ... Então, pode ser possível que haja um algoritmo atualmente desconhecido que apenas reduza a complexidade deste jogo e levaria apenas 5 minutos para calcular o melhor movimento com um computador atual. Talvez fosse possível avaliá-lo como um humano com papel e caneta, ou mesmo em sua mente, com mais algum tempo.

Portanto, a resposta rápida é: se a humanidade sobreviver por tempo suficiente, é apenas uma questão de tempo!

Pode ser solucionável, mas algo me incomoda: mesmo que toda a árvore pudesse ser atravessada, ainda não há como prever o próximo movimento do oponente. Devemos sempre basear nosso próximo movimento no estado do oponente e fazer o "melhor" movimento disponível. Então, com base no próximo estado, fazemos isso novamente. Portanto, nosso movimento ideal pode ser ótimo se o oponente se mover de uma determinada maneira. Para alguns movimentos do oponente, nosso último movimento pode ter sido abaixo do ideal.

Só não consigo ver como pode haver um movimento "perfeito" em cada etapa.

Para que seja o caso, deve haver para cada estado [no jogo atual] um caminho na árvore que leva à vitória, independentemente do próximo movimento do oponente (como no jogo da velha), e eu tenho um difícil tempo pensando nisso.

Matematicamente, o xadrez foi resolvido pelo algoritmo Minimax , que remonta à década de 1920 (encontrado por Borel ou von Neumann). Assim, uma máquina de turing pode de fato jogar xadrez perfeito.

No entanto, a complexidade computacional do xadrez o torna praticamente inviável. Os motores atuais usam várias melhorias e heurísticas. Os melhores motores de hoje superaram os melhores humanos em termos de força de jogo, mas por causa das heurísticas que estão usando, eles podem não jogar perfeitamente quando dado um tempo infinito (por exemplo, colisões de hash podem levar a resultados incorretos).

O mais próximo que temos em termos de jogo perfeito são as bases de mesa finais . A técnica típica para gerá-los é chamada de análise retrógrada . Atualmente, todas as posições com até seis peças foram resolvidas.

Sim , em matemática, o xadrez é classificado como um jogo determinado, o que significa que tem um algoritmo perfeito para cada primeiro jogador, isso é comprovado até mesmo para o tabuleiro de xadrez infinito, então um dia provavelmente um quantom AI encontrará a estratégia perfeita, e o jogo acabou

Mais sobre isso neste vídeo: https://www.youtube.com/watch?v=PN-I6u-AxMg

Existe também o xadrez quântico, onde não há prova matemática de que seja determinado jogo http://store.steampowered.com/app/453870/Quantum_Chess/

e aí está o vídeo detalhado sobre xadrez quântico https://chess24.com/en/read/news/quantum-chess

Claro que há apenas 10 elevado a cinquenta combinações possíveis de peças no tabuleiro. Tendo isso em mente, para tocar em todas as combinações, você precisaria fazer menos de 10 à potência de cinquenta movimentos (incluindo repetições, multiplique esse número por 3). Portanto, há menos de dez elevado a cem movimentos no xadrez. Basta escolher aqueles que levam ao xeque-mate e você está pronto para ir

Matemática de 64 bits (= tabuleiro de xadrez) e operadores bit a bit (= próximos movimentos possíveis) é tudo o que você precisa. Tão simples. A força bruta encontrará a melhor maneira normalmente. Claro, não existe um algoritmo universal para todas as posições. Na vida real, o cálculo também é limitado no tempo, o tempo limite irá interrompê-lo. Um bom programa de xadrez significa código pesado (peões passados, dobrados, etc.). Código pequeno não pode ser muito forte. Abrir e finalizar bancos de dados apenas economiza tempo de processamento, algum tipo de dados pré-processados. O dispositivo, quero dizer - o sistema operacional, possibilidade de threading, ambiente, requisitos de definição de hardware. A linguagem de programação é importante. Enfim, o processo de desenvolvimento é interessante.