Wikipédia

Jogo resolvido

Um jogo resolvidos é 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 editar

Um jogo de dois jogadores podem ser "resolvidos" em vários níveis:[1][2]

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.[3][4][5]

Jogo perfeito editar

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 editar

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.[6]
Lig 4
Resolvido primeiro por James D. Allen (1 de Outubro de 1988), e de forma independente por Victor Allis (Oct 16, 1988).[7] Primeiro jogador pode forçar uma vitória. Fortemente resolvido por João de Prensar com 8 camadas de base de dados[8] (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)[7] (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.[9] Damas é o maior jogo que já foi resolvido até à data, com um espaço de pesquisa, de 5×1020.[10] 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.[11]
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.[12]
Hexapawn
3×3 variante resolvido como uma vitória para o preto, vários outros grandes variantes também resolvido.[13]
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.[14][15] 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.[16]
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).[17] 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.[18] O primeiro jogador ganha.
Pentaminó
Fracamente resolvido por H. K. Andrade.[19] é 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.[20]
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).[21]
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.[22]
Reversi (Otelo)
Fracamente resolvidos em um 4×4 e 6×6 em julho de 1993, por Joel Feinstein.[23] O bioinformático japonês Hiroki Takizawa confirmou ter resolvido Othello 8x8 fortemente em 2023.[24][25]

Parcialmente resolvido jogos editar

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.[26] os seres Humanos costumam jogar em um 19×19 conselho, que é mais de 145 ordens de magnitude mais complexo do que 7×7.[27]
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.[28]
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 editar

References editar

  1. ↑ V. Allis, Searching for Solutions in Games and Artificial Intelligence.
  2. ↑ 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.
  3. ↑ «Heads-up limit hold'em poker is solved». Science. 347: 145–9. Janeiro de 2015. PMID 25574016. doi:10.1126/science.1259433 
  4. ↑ Philip Ball (8 de janeiro de 2015). «Game Theorists Crack Poker». Scientific American. Nature. doi:10.1038/nature.2015.16683. Consultado em 13 de janeiro de 2015 
  5. ↑ Robert Lee Hotz (8 de janeiro de 2015). «Computer Conquers Texas Hold 'Em, Researchers Say». Wall Street Journal 
  6. ↑ «How to Always Win Chopsticks». wikiHow. Consultado em 28 de abril de 2013 
  7. ↑ a b John's Connect Four Playground
  8. ↑ http://archive.ics.uci.edu/ml/datasets/Connect-4
  9. ↑ Schaeffer, Jonathan (19 de julho de 2007). «Checkers Is Solved». Science. Consultado em 20 de julho de 2007 
  10. ↑ «Project - Chinook - World Man-Machine Checkers Champion». Consultado em 19 de julho de 2007 
  11. ↑ Mullins, Justin (19 de julho de 2007). «Checkers 'solved' after years of number crunching». NewScientist.com news service. Consultado em 20 de julho de 2007 
  12. ↑ P. Henderson, B. Arneson, and R. Hayward[webdocs.cs.ualberta.ca/~hayward/papers/solve8.pdf, Solving 8×8 Hex ], Proc.
  13. ↑ Hexapawn
  14. ↑ Solving Kalah by Geoffrey Irving, Jeroen Donkers and Jos Uiterwijk.
  15. ↑ Solving (6,6)-Kalaha by Anders Carstensen.
  16. ↑ Nine Men's Morris is a Draw by Ralph Gasser
  17. ↑ Pangki is strongly solved as a Draw by Jason Doucette
  18. ↑ Geoffrey Irving: "Pentago is a first player win" http://perfect-pentago.net/details.html
  19. ↑ Hilarie K. Orman: Pentominoes: A First Player Win in Games of no chance, MSRI Publications – Volume 29, 1996, pages 339-344.
  20. ↑ Teeko, by E. Weisstein
  21. ↑ Three Musketeers, by J. Lemaire
  22. ↑ Yew Jin Lim.
  23. ↑ «6×6 Othello weakly solved». Consultado em 14 de junho de 2016. Arquivado do original em 1 de novembro de 2009 
  24. ↑ Othello is Solved
  25. ↑ Cientista japonês conquista o jogo de tabuleiro Othello
  26. ↑ 5×5 Go is solved by Erik van der Werf
  27. ↑ Counting legal positions in Go Arquivado em 30 de setembro de 2007, no Wayback Machine., Tromp and Farnebäck, accessed 2007-08-24.
  28. ↑ Some of the nine-piece endgame tablebase by Ed Gilbert

Ler mais editar

  • 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 editar

Obtida de "https://pt.wikipedia.org/w/index.php?title=Jogo_resolvido&oldid=67566020"