Jogo resolvido - Solved game

Um jogo resolvido é um jogo cujo resultado (vitória, derrota ou empate ) pode ser previsto corretamente de qualquer posição, assumindo que ambos os jogadores joguem perfeitamente. Esse conceito é geralmente aplicado a jogos de estratégia abstratos e, especialmente, a jogos com informações completas e nenhum elemento de sorte; resolver tal jogo pode usar teoria de jogo combinatória e / ou assistência de computador.

Visão geral

Um jogo para dois jogadores pode ser resolvido em vários níveis:

Ultra fraco
Prove se o primeiro jogador vai ganhar, perder ou empatar na posição inicial, com um jogo perfeito de ambos os lados. Esta pode ser uma prova não construtiva (possivelmente envolvendo um argumento de roubo de estratégia ) que não precisa realmente determinar quaisquer movimentos da jogada perfeita.
Fraco
Fornece um algoritmo que garante uma vitória para um jogador, ou um empate para ambos, contra quaisquer movimentos possíveis do oponente, desde o início do jogo. Ou seja, produza pelo menos um jogo ideal completo (todos os movimentos do início ao fim) com a prova de que cada movimento é ideal para o jogador que o executa.
Forte
Fornece um algoritmo que pode produzir movimentos perfeitos de qualquer posição, mesmo que já tenham sido cometidos erros em um ou nos dois lados.

Apesar do nome, muitos teóricos dos jogos acreditam que as provas "ultra-fracas" são as mais profundas, interessantes e valiosas. As provas "ultra-fracas" exigem que um estudioso raciocine sobre as propriedades abstratas do jogo e mostre como essas propriedades levam a certos resultados se o jogo perfeito for realizado.

Em contraste, as provas "fortes" geralmente ocorrem por força bruta - usando um computador para pesquisar exaustivamente uma árvore de jogo para descobrir o que aconteceria se o jogo perfeito fosse realizado. A prova resultante fornece uma estratégia ótima para cada posição possível no tabuleiro. No entanto, essas provas não são tão úteis para entender razões mais profundas por que alguns jogos podem ser resolvidos como empate e outros jogos aparentemente muito semelhantes podem ser resolvidos como uma vitória.

Dadas as regras de qualquer jogo de duas pessoas com um número finito de posições, pode-se sempre construir trivialmente um algoritmo minimax que atravessaria exaustivamente a árvore do jogo . No entanto, uma vez que para muitos jogos não triviais, tal algoritmo exigiria uma quantidade inviável de tempo para gerar um movimento em uma determinada posição, um jogo não é considerado como resolvido de forma fraca ou forte, a menos que o algoritmo possa ser executado pelo hardware existente em um tempo razoável. Muitos algoritmos dependem de um enorme banco de dados pré-gerado e, na verdade, não são nada mais.

Como um exemplo de solução forte, o jogo da velha pode ser resolvido como empate para ambos os jogadores com jogo perfeito (um resultado determinável até manualmente pelos alunos). Jogos como o nim também admitem uma análise rigorosa usando a teoria dos jogos combinatória .

O fato de um jogo ser resolvido não é necessariamente o mesmo que continuar sendo interessante para os humanos jogarem. Mesmo um jogo fortemente resolvido ainda pode ser interessante se sua solução for muito complexa para ser memorizada; inversamente, um jogo mal resolvido pode perder sua atração se a estratégia vencedora for simples de lembrar (por exemplo, Maharajah e os Sepoys ). Uma solução ultra-fraca (por exemplo, Chomp ou Hex em um tabuleiro suficientemente grande) geralmente não afeta a jogabilidade.

Jogo perfeito

Na teoria dos jogos , o jogo perfeito é o comportamento ou estratégia de um jogador que leva ao melhor resultado possível para aquele jogador, independentemente da resposta do adversário. O jogo perfeito para um jogo é conhecido quando o jogo é resolvido. Com base nas regras de um jogo, todas as posições finais possíveis podem ser avaliadas (como vitória, derrota ou empate). Por raciocínio reverso , pode-se avaliar recursivamente uma posição não final como idêntica à posição que está a um movimento de distância e mais valorizada para o jogador de quem ela se move. Assim, uma transição entre posições nunca pode resultar em uma melhor avaliação para o jogador em movimento, e um movimento perfeito em uma posição seria uma transição entre posições que são igualmente avaliadas. Por exemplo, um jogador perfeito em uma posição empatada sempre teria um empate ou uma vitória, nunca uma derrota. Se houver várias opções com o mesmo resultado, o jogo perfeito às vezes é considerado o método mais rápido que leva a um bom resultado ou o método mais lento que leva a um resultado ruim.

O jogo perfeito pode ser generalizado para jogos de informação não perfeitos , como a estratégia que garantiria o maior resultado mínimo esperado independentemente da estratégia do oponente. Por exemplo, a estratégia perfeita para uma tesoura de papel pedra seria escolher aleatoriamente cada uma das opções com probabilidade igual (1/3). A desvantagem neste exemplo é que esta estratégia nunca explorará estratégias não ótimas do oponente, então o resultado esperado desta estratégia versus qualquer estratégia será sempre igual ao resultado mínimo esperado.

Embora a estratégia ideal de um jogo possa (ainda) não ser conhecida, um computador de jogo ainda pode se beneficiar de soluções do jogo de certas posições de final de jogo (na forma de bases de mesa de final de jogo ), o que permitirá que ele jogue perfeitamente após alguns ponto no jogo. Os programas de xadrez de computador são bem conhecidos por fazer isso.

Jogos resolvidos

Awari (um jogo da família Mancala )
A variante do Oware que permite "grand slams" no final do jogo foi fortemente resolvida por Henri Bal e John Romein na Vrije Universiteit em Amsterdã , Holanda (2002). Qualquer um dos jogadores pode forçar o empate.
Pauzinhos
O segundo jogador sempre pode forçar uma vitória.
Connect Four
Resolvido primeiro por James D. Allen em 1 de outubro de 1988 e independentemente por Victor Allis em 16 de outubro de 1988. O primeiro jogador pode forçar uma vitória. Fortemente resolvido pelo banco de dados de 8 camadas de John Tromp (4 de fevereiro de 1995). Fracamente resolvido para todos os tamanhos de placas onde largura + altura é no máximo 15 (bem como 8 × 8 no final de 2015) (18 de fevereiro de 2006).
Rascunhos ingleses (damas)
Esta variante 8 × 8 dos rascunhos foi fracamente resolvida em 29 de abril de 2007, pela equipe de Jonathan Schaeffer . Da posição inicial padrão, ambos os jogadores podem garantir um empate com jogo perfeito. Damas é o maior jogo resolvido até o momento, com um espaço de busca de 5 × 10 20 . O número de cálculos envolvidos foi 10 14 , os quais foram feitos ao longo de um período de 18 anos. O processo envolveu de 200 computadores desktop em seu pico até cerca de 50.
Fanorona
Fracamente resolvido por Maarten Schadd. O jogo acabou empatado.
Gomoku grátis
Resolvido por Victor Allis (1993). O primeiro jogador pode forçar uma vitória sem regras de abertura.
Fantasma
Resolvido por Alan Frank usando o Dicionário Oficial de Jogadores de Scrabble em 1987.
Hex
  • Um argumento de roubo de estratégia (como usado por John Nash ) mostra que todos os tamanhos de tabuleiro quadrados não podem ser perdidos pelo primeiro jogador. Combinado com a prova da impossibilidade de empate, mostra que o jogo é ultra-fraco resolvido com a vitória do primeiro jogador.
  • Solucionado fortemente por vários computadores para tamanhos de placa de até 6 × 6.
  • Jing Yang demonstrou uma estratégia vencedora (solução fraca) para os tamanhos de tabuleiro 7 × 7, 8 × 8 e 9 × 9.
  • Uma estratégia vencedora para Hex com troca é conhecida pelo tabuleiro 7 × 7.
  • Fortemente resolver Hex em uma N × N bordo é improvável que o problema tem se mostrado PSPACE-completo .
  • Se Hex for jogado em um tabuleiro N × ( N +1), o jogador que tiver a distância mais curta para se conectar pode sempre vencer por uma estratégia de emparelhamento simples, mesmo com a desvantagem de jogar em segundo lugar.
  • Uma solução fraca é conhecida para todos os movimentos de abertura no tabuleiro 8 × 8.
Hexapawn
A variante 3 × 3 foi resolvida como uma vitória para as pretas, várias outras variantes maiores também foram resolvidas.
Kalah
A maioria das variantes resolvidas por Geoffrey Irving, Jeroen Donkers e Jos Uiterwijk (2000), exceto Kalah (6/6). A variante (6/6) foi resolvida por Anders Carstensen (2011). A grande vantagem do primeiro jogador foi comprovada na maioria dos casos. Mark Rawlings, de Gaithersburg, MD, quantificou a magnitude da vitória do primeiro jogador na variante (6/6) (2015). Após a criação de 39 GB de banco de dados de endgame, pesquisas totalizando 106 dias de CPU e mais de 55 trilhões de nós, foi comprovado que, com uma jogada perfeita, o primeiro jogador ganha por 2. Note que todos esses resultados referem-se à Captura de Fossa Vazia variante e, portanto, são de interesse muito limitado para o jogo padrão. A análise do jogo de regras padrão agora foi postada para Kalah (6,4), que é uma vitória por 8 para o primeiro jogador, e Kalah (6,5), que é uma vitória por 10 para o primeiro jogador. A análise do Kalah (6,6) com as regras padrão está em andamento, porém, está comprovado que é uma vitória de pelo menos 4 para o primeiro jogador.
Jogo L
Facilmente solucionável. Qualquer um dos jogadores pode forçar o empate.
Perdendo xadrez
Fracamente resolvido como uma vitória para as brancas começando com 1. e3.
Maharajah and the Sepoys
Este jogo assimétrico é uma vitória para o jogador sipaio com jogo correto.
Nim
Fortemente resolvido.
Morris de nove homens
Resolvido por Ralph Gasser (1993). Qualquer um dos jogadores pode forçar o empate.
Ordem e Caos
A ordem (primeiro jogador) vence.
Ohvalhu
Fracamente resolvido por humanos, mas comprovado por computadores. (Dakon, no entanto, não é idêntico a Ohvalhu, o jogo que realmente foi observado por de Voogt)
Pangki
Fortemente resolvido por Jason Doucette (2001). O jogo acabou empatado. Existem apenas dois primeiros movimentos exclusivos se você descartar as posições espelhadas. Um força o empate e o outro dá ao adversário uma vitória forçada em 15.
Pentominós
Fracamente resolvido por HK Orman. É uma vitória para o primeiro jogador.
Poddavki ("Damas de oferta russas")
Resolvido por Osipov e Morozev em 2011. Vitória das brancas.
Quarto
Resolvido por Luc Goossens (1998). Dois jogadores perfeitos sempre empatarão.
Qubic
Fracamente resolvido por Oren Patashnik (1980) e Victor Allis . O primeiro jogador vence.
Jogo tipo Renju sem regras de abertura envolvidas
Resolvido por János Wagner e István Virág (2001). Uma vitória do primeiro jogador.
Sim
Resolvido fracamente: vitória para o segundo jogador.
Teeko
Resolvido por Guy Steele (1998). Dependendo da variante, uma vitória do primeiro jogador ou um empate.
Três morris masculinos
Trivialmente solucionável. Qualquer um dos jogadores pode forçar o empate.
Três Mosqueteiros
Fortemente resolvido por Johannes Laire em 2009, e fracamente resolvido por Ali Elabridi em 2017. É uma vitória para as peças azuis (homens do Cardeal Richelieu, ou, o inimigo).
Jogo da velha
Trivialmente fortemente solucionável por causa da pequena árvore do jogo. O jogo termina empatado se não houver erros, nem erros possíveis na jogada de abertura.
Tigres e cabras
Fracamente resolvido por Yew Jin Lim (2007). O jogo acabou empatado.
Jogo de Wythoff
Fortemente resolvido.

Jogos parcialmente resolvidos

Xadrez
Artigo principal: Resolvendo xadrez
Resolver totalmente o xadrez continua difícil de ser resolvido, e especula-se que a complexidade do jogo pode impedir que ele seja resolvido. Por meio de análise computadorizada retrógrada , bases de mesa de final de jogo (soluções fortes) foram encontradas para todos os jogos finais de três a sete peças , contando os dois reis como peças.
Algumas variantes de xadrez em um tabuleiro menor com número reduzido de peças foram resolvidas. Algumas outras variantes populares também foram resolvidas; por exemplo, uma solução fraca para o Maharajah e os Sepoys é uma série de movimentos facilmente memoráveis ​​que garante a vitória do jogador "Sepoys".
Ir
O tabuleiro 5 × 5 foi fracamente resolvido para todos os movimentos iniciais em 2002. O tabuleiro 7 × 7 foi fracamente resolvido em 2015. Os humanos geralmente jogam em um tabuleiro 19 × 19, que é 145 ordens de magnitude mais complexo do que 7 × 7.
Rascunhos internacionais
Todas as posições de final de jogo com duas a sete peças foram resolvidas, bem como as posições com peças 4 × 4 e 5 × 3 em que cada lado tinha um rei ou menos, posições com cinco homens contra quatro homens, posições com cinco homens contra três homens e um rei e posições com quatro homens e um rei contra quatro homens. As posições finais foram resolvidas em 2007 por Ed Gilbert, dos Estados Unidos. A análise do computador mostrou que era muito provável que terminasse em empate se ambos os jogadores jogassem perfeitamente.
m , n , k -jogo
É trivial mostrar que o segundo jogador nunca pode vencer; veja o argumento do roubo de estratégia . Quase todos os casos foram resolvidos fracamente para k ≤ 4. Alguns resultados são conhecidos para k = 5. Os jogos são empatados para k ≥ 8.
Reversi (Othello)
Fracamente resolvido em um tabuleiro 4 × 4 e 6 × 6 como um segundo jogador venceu em julho de 1993 por Joel Feinstein. Em um tabuleiro 8 × 8 (o padrão) não é matematicamente resolvido, embora a análise do computador mostre um empate provável. Não existem estimativas fortemente supostas além de chances aumentadas para o jogador inicial (preto) em 10 × 10 e tabuleiros maiores existem.

Veja também

Referências

Leitura adicional

  • Allis, vencendo o campeão mundial? O estado da arte em jogos de computador. em Novas Abordagens para Pesquisa de Jogos de Tabuleiro.

links externos