Se tivesse um poder infinito de processamento, existe um algoritmo que jogaria xadrez perfeitamente?

29

Existe um algoritmo desse tipo em que, se obtivesse infinito poder de processamento, um computador pudesse jogar xadrez perfeitamente para nunca perder?

Em caso afirmativo, onde posso encontrar pseudo-código para ele?

Jonah
fonte
8
O que você quer dizer com xadrez perfeito?
Herb Wolfe
5
@HerbWolfe Suponho que ele queira dizer que nunca faz um movimento que permita que seu oponente o force a perder e renuncia se, e somente se, todo movimento possível permitir que seu oponente o force a perder.
David Schwartz
5
@DavidSchwartz - "xadrez perfeito", é claro, não pode ser definido. Nem o "poder infinito de processamento". Isso significa "executa todas as seqüências de instruções no tempo 0"? "Existe um número infinito de processadores disponíveis"? FWIW - minha definição de "xadrez perfeito" é "nunca perde um jogo".
Bob Jarvis - Restabelece Monica
24
Sim, isso se chama força bruta. Com poder infinito de processamento, você não precisa fazer a poda alfa-beta, embora também seja necessário um armazenamento bastante grande para armazenar sua árvore de pesquisa.
Michael
4
O conceito de "algoritmo" e o conceito de poder infinito de processamento não se misturam realmente. A teoria dos algoritmos e da computabilidade baseia-se na suposição de alcançar um resultado em um número finito de etapas. Se você receber um número infinito de etapas, a distinção entre o que é computável e o que não é desaparece.
Michael Kay

Respostas:

62

Existe um algoritmo? Sim. De acordo com o Teorema de Zermelo , existem três possibilidades para um jogo de dois jogadores com informações perfeitas determinísticas finitas, como o xadrez: ou o primeiro jogador tem uma estratégia vencedora, ou o segundo jogador tem uma estratégia vencedora, ou qualquer um pode forçar um empate. Ainda não sabemos o que é o xadrez. (Damas, por outro lado, foi resolvido : qualquer jogador pode forçar um empate.)

Conceitualmente, o algoritmo é bastante simples: construa uma árvore de jogo completa , analise os nós das folhas (as posições finais do jogo) e faça o movimento inicial vencedor, renuncie ou ofereça um empate.

O problema está nos detalhes: existem aproximadamente 10 43 posições possíveis e um número ainda maior de movimentos (a maioria das posições pode ser alcançada de mais de uma maneira). Você realmente precisa do seu computador infinitamente poderoso para tirar proveito disso, pois um computador que pode tirar proveito desse algoritmo não pode se encaixar no universo conhecido ou não terminará a computação até que o universo acabe.

Marca
fonte
13
@Wildcard Não, ele não assume nada: apenas contém todos os possíveis jogos legais de xadrez e escolhe todos aqueles em que o jogador em questão não perde.
suavizado
11
@gented, eu estava me referindo à etapa de "renúncia" do algoritmo. Não é um passo necessário.
Curinga
38
A regra das três repetições limita o espaço de pesquisa, para que o computador não precise ser infinitamente poderoso, apenas astronomicamente poderoso.
Hoa Long Tam
9
Para referência, compare um limite inferior para o número de jogos possíveis ( 10 ^ 120 ) com o número de átomos no universo observável (na ordem de 10 ^ 80 ). O algoritmo mais simples teria que encontrar todos esses jogos e armazenar seus dados. Armazenar um jogo por átomo levaria 10 ^ 40 vezes mais átomos do que estimamos no universo observável.
Engineer Toast
6
Essa resposta é ótima até o final, quando você se refere a um "computador infinitamente poderoso". Não é isso que você quer dizer, e essa frase não pertence à pergunta nem à discussão.
Don escotilha
25

Veja https://en.wikipedia.org/wiki/Endgame_tablebase .

Com o poder infinito do computador, poderia-se construir uma mesa para a posição inicial e resolver o xadrez .

Na prática, apenas posições com até sete "homens" (peões e peças, contando os reis) foram resolvidas usando os supercomputadores atuais, por isso estamos muito longe de resolver o xadrez. A complexidade do problema aumenta exponencialmente com o número de peças.

itub
fonte
9
Como observação lateral, se você realmente produziu uma tabela como essa, não importa em que armazenou as informações, ela pesaria aproximadamente 10 ^ 43 vezes mais que o universo observável; considerando que existem ~ 10 ^ 123 posições possíveis no xadrez e apenas ~ 10 ^ 80 bárions no universo observável.
Shufflepants
6
@ Shufflepants que disse que eu o estava armazenando usando bárions?
Michael
3
@Christoph E assumindo a conservação da informação, e supondo que você tivesse um detector e seu super computador com infinito poder de processamento, você poderia lentamente, ao longo de algo como um ano de polêmicas, ler a base da mesa como radiação penetrante.
Shufflepants
3
@Shufflepants Observe que uma estratégia vencedora real pode exigir muito menos espaço do que uma base de tabela completa. Por exemplo, o Nim tem uma estratégia vencedora que é simples de descrever, não há necessidade de criar uma enorme tabela de todos os estados possíveis.
Federico Poloni
1
Esta solução, como indicado, não é viável. A massa dessa tabela formaria um buraco negro e seria impossível exfiltrar dados dela.
Emory
19

Se você realmente tivesse um poder infinito de processamento, esse algoritmo seria realmente trivial para escrever. Como o xadrez tem um número finito de estados possíveis, você poderia, em teoria, percorrer todos eles até encontrar um caminho de jogo perfeito. Seria terrivelmente ineficiente, mas se você tiver um poder infinito de processamento, isso não importaria.

vsz
fonte
Isso não é verdade. Ele disse que você tem um poder infinito de processamento, mas não disse nada sobre o espaço infinito.
Ubadub
@ubadub: Não precisaríamos de espaço infinito. A duração de um jogo é limitada devido à regra de 50 movimentos, e uma regra pode ser criada para classificar todos os movimentos possíveis de uma posição. Como eles podem ser classificados, eles podem ser armazenados como um número inteiro. Essa é toda a memória necessária para percorrer a árvore inteira. E se você tiver tempo infinito, poderá andar na árvore quantas vezes quiser, para não armazenar todos os jogos de xadrez possíveis.
vsz
A duração do jogo é limitada, mas é extremamente grande; como alguém apontou, se você produzisse uma tabela para armazenar todos esses jogos ", não importa em que informação você armazenasse, ela pesaria aproximadamente 10 ^ 43 vezes mais que o universo observável; considerando que existem ~ 10 ^ 123 possíveis posições de xadrez e apenas ~ 10 ^ 80 bárions no universo observável
ubadub
2
@ubadub: Isso é verdade, mas eu não estava falando sobre "uma mesa para armazenar todos esses jogos". Existem muitos algoritmos relacionados à árvore que não precisam armazenar todos os nós da árvore inteira na memória.
vsz
@ vsz good point
ubadub
13

Para abordar diretamente a questão: sim, existe um algoritmo desse tipo. É chamado minimax. (As bases de tabela do final de jogo são geradas usando esse algoritmo (para trás!), Mas o algoritmo simples e minimax simples e antigo é tudo o que você precisa). Esse algoritmo pode jogar perfeitamente qualquer jogo com soma zero de dois jogadores. Encontre o pseudocódigo aqui:

https://en.wikipedia.org/wiki/Minimax

observe que variantes desse algoritmo são usadas por programas modernos de xadrez por computador.

programador de xadrez
fonte
4

Não apenas existe um algoritmo para jogar xadrez perfeito, como também é possível escrever um programa curto que (com recursos infinitos) reproduzirá perfeitamente qualquer jogo determinístico de dois jogadores com duração perfeita e conhecimento perfeito determinístico .

O mecanismo do jogo nem precisa saber as regras do jogo que está sendo jogado. Tudo o que precisa é de uma representação opaca de um "estado do jogo" e funcione que (a) dado qualquer estado do jogo, forneça uma lista dos próximos estados legais do jogo e (b) dado um estado do jogo, decida se é uma vitória para o jogador 1 , uma vitória para o jogador 2, um empate ou não é um estado final.

Dadas essas funções, um simples algoritmo recursivo "resolve" o jogo.

Esse fato foi mencionado nas respostas anteriores pelo chessprogrammer (minimax) e pelo Acccumulation (que fornece uma versão do programa em python).

Eu escrevi esse programa há mais de 20 anos. Eu testei jogando o jogo do galo, se você é americano. Com certeza, jogou um jogo perfeito.

É claro que isso cairá rapidamente em qualquer computador imaginável para qualquer jogo sério. Por ser recursivo, está efetivamente construindo toda a árvore do jogo na pilha, para que você tenha um "estouro de pilha" (trocadilho pretendido) antes de chegar perto da análise dos 10 ^ 123 estados de xadrez mencionados em outras respostas. Mas é divertido saber que, em princípio, esse pequeno programa faria o trabalho.

Para mim, isso também diz algo interessante sobre a IA: por mais que você pense que "inteligência" seja exibida por Deep Blue, ou Go Zero, ou mesmo por um ser humano jogando xadrez ou Go, há um sentido em que esses jogos têm um ideal trivial e exatamente computável soluções. O desafio é como obter uma solução boa, mas não ótima, em um tempo razoável.

gareth
fonte
Seu algoritmo funciona apenas para jogos para dois jogadores com conhecimento perfeito. Ele será substituído por jogos com informações ocultas, como o Stratego , porque qualquer implementação da função (a) viola as regras do jogo. Ele também falha em jogos de duração potencialmente infinita: por exemplo, abandona a regra dos 50 movimentos do xadrez, e não se pode dizer que dois reis se perseguindo em volta do tabuleiro não são um estado vencível. Tudo o que posso dizer é que não é um estado final.
Mark
Pontos válidos. Vou editar minha resposta.
Gareth
3

Ignorarei as possibilidades de empates ou seqüências infinitas de movimentos por simplicidade. Uma vez que o algoritmo é entendido, não é particularmente difícil estendê-lo a esses casos.

Primeiro, algumas definições:

  1. Qualquer jogada que ganha o jogo para o jogador que faz essa jogada é uma jogada vencedora.

  2. Qualquer jogada que perde o jogo para o jogador que faz essa jogada é uma jogada perdida.

  3. Qualquer jogada que deixe o outro jogador com pelo menos uma jogada vencedora também é uma jogada perdida. (Como o oponente pode fazer esse movimento e forçar uma perda.)

  4. Qualquer jogada que deixe o outro jogador com apenas jogadas perdidas também é uma jogada vencedora. (Não importa que movimento seu oponente faça, você vencerá.)

  5. Uma estratégia perfeita significa sempre fazer jogadas vencedoras, se houver, e renunciar quando houver apenas uma jogada perdida.

Agora, é trivial escrever uma estratégia perfeita. Simplesmente exploda todas as sequências de movimentos possíveis e identifique movimentos de vitória / derrota. Ignorando o impasse, isso acabará por identificar todos os movimentos como um movimento vencedor ou um movimento perdedor.

Agora, a estratégia é trivial. Veja todos os seus movimentos possíveis. Se alguma jogada vencedora permanecer, pegue uma e vença. Se apenas os movimentos perdedores permanecerem, renuncie, pois seu oponente pode forçá-lo a perder.

Não é difícil ajustar a estratégia para incluir a possibilidade de um impasse.

Atualização : Caso não esteja claro como isso identifica cada jogada como uma jogada vencedora ou perdida, considere:

  1. Cada jogada que resulta em vitória é uma jogada vencedora.
  2. Todo movimento que resulta em perda é um movimento perdedor.
  3. Todo movimento que resulta no oponente tendo apenas movimentos vencedores ou perdedores é um movimento vencedor ou perdedor.
  4. Ligue para no número de jogadas no jogo de xadrez mais longo possível. Por enquanto, estamos ignorando sequências ilimitadas, embora não seja difícil incluí-las.
  5. Não há movimentos com nmovimentos anteriores que precisamos considerar.
  6. Cada jogada com n-1jogadas anteriores é uma jogada vencedora ou uma jogada perdida, pois as njogadas terminam o jogo mais longo.
  7. Assim, todo movimento em profundidade n-2é seguido apenas por movimentos vencedores ou perdidos e, portanto, é um movimento vencedor ou perdedor.
  8. E assim por diante, de volta ao primeiro passo.
David Schwartz
fonte
1
Suas definições de movimentos vencedores e perdedores não são abrangentes o suficiente. O primeiro lance, por exemplo, não vence o jogo (# 1), nem deixa o oponente apenas com lances perdidos (# 4), portanto, não é um "lance vencedor". Nem perde o jogo (# 2), nem deixa o oponente com qualquer jogada vencedora (# 3), por isso não é uma "jogada perdida". Sua estratégia exige que cada jogada seja definida como uma "jogada vencedora" ou uma "jogada perdida", o que simplesmente não é o caso como você a definiu.
Nuclear Wang
2
@NuclearWang Ele define todos os movimentos como um movimento vencedor ou um movimento perdedor. O que você acha que é a terceira alternativa? Visualize a árvore de todos os possíveis jogos de xadrez (e lembre-se, estamos excluindo empates ou sequências infinitas por enquanto). Toda cadeia termina em uma vitória ou uma perda. Isso percorre a árvore, eventualmente identificando cada movimento como um movimento vencedor ou um movimento perdedor.
David Schwartz
13
@NuclearWang ou o primeiro lance é um lance vencedor para um jogador, ou o xadrez é (como tic-tac-toe) um jogo empatado com jogo perfeito. Não sabemos qual porque ninguém jamais teve o poder de computação para executar esse algoritmo até a conclusão e ninguém encontrou uma prova mais direta.
perfil completo de hobbs
8
Não há aleatoriedade nem informações ocultas no xadrez, o que não deixa espaço para "talvez". Cada posição é ganha, perdida ou empatada (mesmo que não tenhamos conseguido identificá- las como tal). E essa explicação está deixando de fora a opção "empatada" por simplicidade, mas na maior parte equivale a 1) uma posição é sorteada se for sorteada de acordo com as regras e 2) uma posição é sorteada se não tiver jogadas vencedoras, mas tiver pelo menos um lance que deixa o oponente sem lances vencedores.
perfil completo de hobbs
2
@DavidSchwartz: A menos que alguém esteja em uma posição perdida, todos os movimentos que não são perfeitos são ruins. Em uma posição perdida, geralmente não haveria um movimento "perfeito" (exceto em uma situação de movimento forçado), pois qualquer movimento legal poderia ter alguma probabilidade de ser o único movimento vencedor ou empate em algumas circunstâncias concebíveis (possivelmente altamente inventadas). Renunciar, no entanto, pareceria o pior "movimento" inequívoco. Suponha que o jogo seja comprovadamente resolvido como uma vitória para as brancas com d4. Você gostaria de jogar um programa de xadrez que respondesse 1. d4com ...resigns?
Supercat
2

Suponha que você tem três funções: win_state, get_player, e next_states. A entrada para win_stateé um estado de jogo e a saída é -1 se o branco estiver no xeque-mate, 0 se for um empate, 1 se o preto estiver no xeque-mate e, Nonecaso contrário. A entrada para get_playeré um estado do jogo e a saída é -1 se for a vez do preto e 1 se for a vez do branco. A entrada para next_statesé uma lista dos possíveis próximos estados do jogo que podem resultar de uma jogada legal. Então, a função a seguir, quando receber um estado de jogo e um jogador, deve informar em que estado de jogo se mover para que esse jogador ganhe.

def best_state(game_state,player)
  def best_result(game_state):
     if win_state(game_state):
        return(win_state)
     else:
         player = get_player(game_state)
         return max([best_result(move)*player for move in next_states(game_state)])*player
  cur_best_move = next_states(games_state)[0]
  cur_best_outcome = -1
  for state in next_states(game_state):
     if best_result(state)*player > cur_best_outcome:
           cur_best_outcome = best_result(state)*player
           cur_best_move = state
return(best_move)
Acumulação
fonte
0

Use uma tabela de consulta

Sim. É fácil. Você nem precisa de poder de processamento infinito. Tudo o que você precisa é de uma mesa de consulta que contenha, para cada posição possível no tabuleiro, a melhor jogada para jogar nessa posição. Aqui está o pseudo-código:

def play-move(my-color, board-position):
    return table-of-best-moves[my-color, board-position]

A pegada

O único problema é que essa tabela de pesquisa teria que ser muito, muito grande - talvez maior que a galáxia da Via Láctea - e levaria muito tempo para construí-la - talvez mais do que a idade atual do universo, a menos que haja alguma regularidade desconhecida no xadrez que a torna muito mais simples do que podemos ver agora. Mas se você tivesse essa tabela de consulta, a sub-rotina para escolher uma jogada perfeita toda vez poderia ser implementada em apenas uma instrução da CPU.

Além disso, dado nosso conhecimento atual de xadrez, não há como ter certeza de que o jogo perfeito garante que você não perderá. Por exemplo, se o jogo perfeito garantir uma vitória para as brancas, as pretas perderão mesmo que as pretas joguem perfeitamente.

Ben Kovitz
fonte