Um jogo resolvido é um jogo cujo resultado (ganhar, perder ou empatar) pode ser previsto corretamente a partir de qualquer posição, presumindo que ambos os jogadores joguem perfeitamente.
Visão geral Um jogo de dois jogadores podem ser "resolvidos" em vários níveis:V. Allis, Searching for Solutions in Games and Artificial Intelligence. H. Jaap van den Herik, Jos W.H.M. Uiterwijk, Jack van Rijswijck, Games solved: Now and in the future, Artificial Intelligence 134 (2002) 277–311. Ultra-fraca Provar se o primeiro jogador vai ganhar, perder ou empatar a partir da posição inicial, dada um jogo perfeito em ambos os lados. Este pode ser uma prova não-implícita (possivelmente envolvendo uma estratégia de furto de argumento) de que não precisa, na verdade, determinar todos os movimentos do jogo perfeito.
Fraco Fornecer um algoritmo que assegura uma vitória para um jogador, ou um empate para ambos, contra possíveis jogadas do adversário, desde o início do jogo. Isto é, produzir 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 faz isso. Isso não significa necessariamente um programa de computador usando a solução vai jogar de forma otimizada contra imperfeito do adversário. Por exemplo, o jogo de damas programa de Chinook nunca vai virar um desenhada de posição em uma posição perdedora (uma vez que a solução fraca de damas prova que é um empate), mas possivelmente vire uma posição vencedora em um desenhada posição porque Chinook não espera o adversário para jogar um movimento que não vai ganhar, mas poderia perder, e por isso não analisar tais movimentos completamente.
Forte Fornecer um algoritmo que pode produzir movimentos perfeitos a partir de qualquer posição, mesmo se os erros já foram feitas em um ou ambos os lados. Apesar de seu nome, jogo que muitos teóricos acreditam que o "ultra-fraca" as provas são mais profundos, mais interessantes e valiosas. "Ultra-fraca" provas exigem um estudioso da razão sobre as propriedades abstratas do jogo, e mostrar como essas propriedades levar a certos resultados se o jogo perfeito é realizado.[citação necessários]
Por outro lado, "forte" de provas, muitas vezes, prossiga pela força bruta—a utilização de um computador, de forma exaustiva pesquisa de uma árvore de jogo para descobrir o que aconteceria se o jogo perfeito foram realizados. A prova resultante dá uma ótima estratégia para cada possível posição no tabuleiro. No entanto, essas provas não são tão úteis na compreensão mais profunda razões por que alguns jogos são solucionáveis, como um empate, e outros, aparentemente muito similar jogos são solucionáveis, como uma vitória.
Dadas as regras de qualquer jogo de duas pessoas com um número finito de posições, pode-se sempre trivialmente construir um minimax algoritmo que seria exaustivamente percorrer a árvore de jogo. No entanto, uma vez que para muitos não-trivial de jogos como um algoritmo seria inviável exigir uma quantidade de tempo para gerar um movimento em uma determinada posição, um jogo que não é considerado para ser resolvido fracamente ou fortemente a menos que o algoritmo possa ser executado por hardware existente em um tempo razoável. Muitos algoritmos dependem de uma grande banco de dados gerada, e são, efetivamente, nada mais.
Como um exemplo de uma solução forte, o jogo de tic-tac-toe é resolvido como um empate para ambos os jogadores com o jogo perfeito (um resultado, mesmo manualmente determinável por crianças). Jogos como o nim também admitir uma rigorosa análise combinatória teoria dos jogos.
Se um jogo é resolvido não é necessariamente o mesmo como se ele continua a ser interessante para os seres humanos para jogar. Mesmo fortemente resolveu o jogo ainda pode ser interessante se a sua solução for muito complexa para ser memorizado; por outro lado, um pouco resolvidos jogo pode perder sua atração se a estratégia vencedora é simples o suficiente para lembrar (e.g. Marajá e o Sepoys). Um ultra-solução fraca (e.g. Chomp ou Hexadecimal em um suficientemente grande conselho), geralmente, não afeta a jogabilidade.
Além disso, mesmo se o jogo não for resolvido, é possível que um algoritmo produz uma boa solução aproximada: por exemplo, um artigo na Science , a partir de janeiro de 2015, afirma que suas cabeças até o limite de Texas hold 'em poker bot de Cepheus garante que a vida de um ser humano de jogar não é suficiente para estabelecer, com significância estatística de que a sua estratégia não é uma solução exata.
Jogo perfeito Na teoria do jogo, o jogo perfeito é o comportamento ou a estratégia de um jogador que leva para o melhor resultado possível para o jogador, independente da resposta do adversário. Com base nas regras de um jogo, cada possível posição final pode ser avaliada (como uma vitória, perda ou empate). Por trás de raciocínio, pode-se recursivamente a avaliação de um não-final, posição idêntica à do cargo de que é um mover-se longe e mais valorizadas para o jogador cuja movê-lo. Assim, uma transição entre as posições nunca pode resultar em uma melhor avaliação para mover o jogador, e um perfeito mover-se em uma posição seria uma transição entre as posições que são igualmente avaliados. Como um exemplo, um leitor perfeito, em um desenhada de posição sempre se empatar ou ganhar, nunca uma perda. Se há várias opções com o mesmo resultado, o jogo perfeito é às vezes considerado o método mais rápido, levando a um bom resultado, ou o método mais lento, levando a um mau resultado.
Jogo perfeito pode ser generalizada para não-perfeito informações de jogos, como estratégia de garantir a máxima mínima resultado esperado , independentemente da estratégia do adversário. Como exemplo, a estratégia perfeita para Pedra, Papel, Tesoura seria escolher aleatoriamente a cada uma das opções com a igualdade (1/3) de probabilidade. A desvantagem, neste exemplo, é que essa estratégia nunca vai explorar melhor as estratégias do adversário, de modo que o resultado esperado desta estratégia contra qualquer estratégia será sempre igual ao mínimo resultado esperado.
Embora a melhor estratégia de um jogo não pode (ainda) ser conhecido, um jogo de computador pode ainda beneficiar de soluções de jogo a partir de determinados posições final jogo (na forma de final jogo tabelas de dados), o que permitirá a jogar perfeitamente após algum ponto no jogo. Programa de computador de xadrez são bem conhecidos para fazer isso.
Resolvido jogos Awari (um jogo de Mancala família) A variante de Oware permitindo que o jogo termina com "grand slams" foi fortemente resolvido por Henri Bal e João Romein na Vrije Universiteit, em Amesterdão, Holanda (2002). Qualquer jogador pode forçar o jogo em um sorteio. Observe que o espanhol Oware mestre Viktor Bautista eu Roca afirmou, diante de sua antiga página inicial manqala.org que o "Awari Oracle" (completamente baseado em Bal e Romein de pesquisa) tinha várias falhas no jogo final e que, portanto, pode-se duvidar de que a solução de Bal e Romein é válido. No entanto, ambos os sites (manqala.org e Oracle), foram retiradas da internet e não há mais pesquisa parece ser possível. Isso revela um grande problema: a Maioria das pesquisas feitas na resolução de problemas de jogos não é totalmente revisados. Pequenos erros na programação, que, no entanto, pode dar resultados muito diferentes, geralmente passam despercebidos.
Damas Veja damas, inglês abaixo.
Pauzinhos O segundo jogador sempre pode forçar uma vitória.
Lig 4 Resolvido primeiro por James D. Allen (1 de Outubro de 1988), e de forma independente por Victor Allis (Oct 16, 1988).John's Connect Four Playground Primeiro jogador pode forçar uma vitória. Fortemente resolvido por João de Prensar com 8 camadas de base de dadoshttp://archive.ics.uci.edu/ml/datasets/Connect-4 (dia 4 de Fevereiro, 1995). Fracamente resolvido para todos os tabuleiros onde a largura+altura é de, no máximo, 15 (bem como 8x8 no final de 2015)John's Connect Four Playground (Fev 18, de 2006).
Damas, Inglês (Damas) Este 8×8 variante do jogo de damas foi fracamente resolvido em 29 de abril de 2007 pela equipe de Jonathan Schaeffer, conhecido por Chinook, o "Mundo do Homem-Máquina Damas Campeão". A partir do padrão da posição de partida, ambos os jogadores podem garantir um empate com o jogo perfeito. Damas é o maior jogo que já foi resolvido até à data, com um espaço de pesquisa, de 5×1020. O número de cálculos envolvidos foi de 1014, que foram feitas ao longo de um período de 18 anos. O processo envolveu a partir de 200 computadores desktop em seu pico para baixo para cerca de 50.
Fanorona Fracamente resolvido por Maarten Schadd. O jogo é um empate.
Gomoku Resolvido por Victor Allis (1993). Primeiro jogador pode forçar uma vitória sem abrir regras.
Ghost Resolvido por Alan Frank usando o Oficial de Scrabble Jogadores Dicionário em 1987.
Hex (jogo) Uma estratégia de furto de argumento (como o usado por John Nash) vai mostrar que todos os quadrados tamanhos de conselho não pode ser perdido pelo primeiro jogador. Combinado com uma prova da impossibilidade de um empate, isso mostra que o jogo é ultra-fraca resolvido como um primeiro jogador a ganhar. Fortemente resolvido por vários computadores de bordo tamanhos até o 6×6. Jing Yang tem demonstrado uma estratégia vencedora (solução diluída) para tamanhos de conselho de 7×7, 8×8 e 9×9. Uma estratégia vencedora para Hex com a troca é conhecido por 7×7 conselho. Fortemente resolução de hex em um N×N conselho é improvável, pois o problema tem sido mostrado para ser PSPACE-completo. Se Hex é jogado em um N × N+1 tabuleiro, então o jogador que tem a menor distância para conectar-se pode ganhar sempre por uma simples estratégia de emparelhamento, mesmo com a desvantagem de jogar o segundo. Uma solução fraca é conhecida por todos os movimentos da abertura do 8×8 conselho.P. Henderson, B. Arneson, and R. Hayward[webdocs.cs.ualberta.ca/~hayward/papers/solve8.pdf, Solving 8×8 Hex ], Proc.
Hexapawn 3×3 variante resolvido como uma vitória para o preto, vários outros grandes variantes também resolvido.Hexapawn
Kalah A maioria das variantes resolvido por Geoffrey Irving, Jeroen Donkers e Jos Uiterwijk (2000), exceto Kalah (6/6). (6/6) variante foi resolvido por Anders Carstensen (2011). Forte de primeira vantagem de jogador foi comprovada na maioria dos casos.Solving Kalah by Geoffrey Irving, Jeroen Donkers and Jos Uiterwijk.Solving (6,6)-Kalaha by Anders Carstensen. Marcos Rawlings, de Gaithersburg, MD, quantifica a magnitude do primeiro jogador a vencer no (6/6) variante (2015). Após a criação de 39 GB de finais, bancos de dados, pesquisas, totalizando 106 dias de tempo de CPU e mais de 55 trilhões de nós, foi provado que, com o jogo perfeito, o primeiro jogador ganha por 2. Note que todos estes resultados se referem ao Vazio-poço de Captura de variante e, portanto, são de muito interesse limitado para o padrão de jogo. Análise do padrão de regra do jogo já foi postada por Kalah(6,4), que é uma vitória por 8 para o primeiro jogador, e Kalah(6,5), o que é uma vitória por 10 para o primeiro jogador. Análise de Kalah(6,6) com as regras padrão está em curso, no entanto, tem sido comprovado que ele é de uma vitória por pelo menos 4 para o primeiro jogador.
L jogo Facilmente solucionáveis. Qualquer jogador pode forçar o jogo em um sorteio.
Marajá e o Sepoys Este assimétrico jogo é uma vitória para a sepoys jogador com o jogo correto.
Nim (jogo) Fortemente resolvido.
Trilha (jogo) Resolvido por Ralph Gasser (1993). Qualquer jogador pode forçar o jogo em um sorteio.Nine Men's Morris is a Draw by Ralph Gasser
Ohvalhu Fracamente solucionados por seres humanos, mas comprovada por computadores. (Dakon é, no entanto, não é idêntico ao Ohvalhu, o jogo que, na verdade, tinha sido observado por de Voogt)
Pangki