Jogo resolvido

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:

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.

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). Primeiro jogador pode forçar uma vitória. Fortemente resolvido por João de Prensar com 8 camadas de base de dados (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) (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×10²⁰. O número de cálculos envolvidos foi de 10¹⁴, 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.

Hexapawn

3×3 variante resolvido como uma vitória para o preto, vários outros grandes variantes também resolvido.

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. 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.

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

Fortemente resolvido por Jason Doucette (2001). O jogo é um empate. Existem apenas duas únicas primeiro se move se você descartar espelhado posições. Uma força-o a desenhar, e o outro dá o adversário forçado vitória em 15.

Pentago

Fortemente resolvido. O primeiro jogador ganha.

Pentaminó

Fracamente resolvido por H. K. Andrade. é uma vitória para o primeiro jogador.

Quarto (jogo de tabuleiro)

Resolvido por Luc Goossens (1998). Duas perfeito jogadores sempre desenhar.

Qubic

Fracamente resolvido por Oren Patashnik (1980) e Victor Allis. O primeiro jogador ganha.

Renju-como o jogo sem abrir regras envolvidas

Alegou ser resolvido por János Wagner e István Virág (2001). Uma primeira vitória de jogador.

Sim

Fracamente resolvido: vitória para o segundo jogador.

Teeko

Resolvido por Guy Steele (1998). Dependendo da variante a primeira vitória do jogador, ou um sorteio.

Três Homens Morris

Trivialmente resolvido. Qualquer jogador pode forçar o jogo em um sorteio.

Três Mosqueteiros

Fortemente resolvido por Johannes Laire em 2009. É uma vitória para as peças azuis (Cardeal Richelieu homens, ou seja, o inimigo).

Jogo da velha

Trivialmente resolvido. Qualquer jogador pode forçar o jogo em um empate.

Bagha-Chall

Fracamente resolvidos pelo Teixo Jin Lim (2007). O jogo é um empate.

Reversi (Otelo)

Fracamente resolvidos em um 4×4 e 6×6 em julho de 1993, por Joel Feinstein. O bioinformático japonês Hiroki Takizawa confirmou ter resolvido Othello 8x8 fortemente em 2023.

Parcialmente resolvido jogos

Xadrez

Totalmente de problemas de xadrez permanece vago, e especula-se que a complexidade do jogo, poderá impedir que isso já está sendo resolvido. Através retrógrado de análise do computador, endgame tablebases (forte de soluções) foram encontrados para as três - sete-peça, e cerca de oito peças finais, contando os dois reis como peças.

Algumas variantes de xadrez em uma pequena placa com número reduzido de peças ter sido resolvido. Algumas outras variedades populares também têm sido resolvido; por exemplo, uma solução fraca de Marajá e o Sepoys é facilmente memorável série de movimentos que garante a vitória para o "sepoys" de jogador.

Go

O 5×5 conselho é fracamente resolvido para todos os movimentos da abertura. os seres Humanos costumam jogar em um 19×19 conselho, que é mais de 145 ordens de magnitude mais complexo do que 7×7.

Damas

Todas as posições finais, com dois a sete peças foram resolvidos, bem como os cargos com 4×4 e 5×3 peças onde cada lado havia um rei ou menos, posições com cinco homens, em vez de quatro homens, com cinco posições de homens contra três homens e um rei, e as posições com quatro homens e um rei em vez de quatro homens. O jogo final de posições, foram resolvidos em 2007 por Ed Gilbert dos Estados Unidos. Análise de computador mostrou que era altamente provável para terminar em um empate se os dois jogadores jogado perfeitamente.

m,n,k-jogo

É trivial mostrar que o segundo jogador pode nunca ganhar; consulte a estratégia de roubar argumento. Quase todos os casos foram resolvidos fracamente para k ≤ 4. Alguns resultados são conhecidos para k = 5. Os jogos são desenhados para k ≥ 8.

Veja também

• Xadrez por computador
• Complexidade de jogoso
• Teorema de Zermelo (teoria dos jogos)

Ler mais

• Allis, Batendo o Campeão do Mundo? O estado-da-arte em computador do jogo de jogo. em Novas Abordagens para Jogos de Tabuleiro de Pesquisa.

Ligações externas

• Computational Complexity of Games and Puzzles por David Eppstein.
• GamesCrafters solução de jogos duas pessoas com informação perfeita e sem chance