Complexidade de jogos

Fonte: testwiki
Revisão em 19h50min de 3 de novembro de 2022 por imported>Dorito voador20 (→growthexperiments-addlink-summary-summary:2|1|0)
(dif) ← Revisão anterior | Revisão atual (dif) | Revisão seguinte → (dif)
Saltar para a navegação Saltar para a pesquisa


A Teoria combinatória dos jogos tem diversas maneiras de medir a complexidade de jogos. Este artigo descreve cinco delas: complexidade estado-espaço, tamanho da árvore do jogo, decisão da complexidade, complexidade da árvore do jogo e complexidade computacional.

Medidas da complexidade dos jogos

Complexidade estado-espaço

A complexidade estado-espaço de um jogo é o número de posições legais acessíveis a partir da posição inicial do jogo.[1][2][3]

Quando isto é muito difícil de calcular, um limitante superior muitas vezes pode ser calculado incluindo posições ilegais ou posições que nunca poderão surgir no curso do jogo.

Tamanho da árvore do jogo

O tamanho da árvore do jogo é o número total de possíveis jogos que podem ser jogados: o número de nós folha na árvore do jogo fixada na posição inicial do jogo.

A árvore do jogo é tipicamente muito maior que o estado-espaço porque as mesma posições podem ocorrer em diversos jogos fazendo movimentos em ordens diferentes (por exemplo, a formação de um jogo da velha com dois X e um O no tabuleiro pode ter sido alcançada de duas maneiras diferentes, dependendo de onde o primeiro X foi posicionado). Um limitante superior para o tamanho da árvore do jogo pode algumas vezes ser computado através da simplificação do jogo de uma maneira que aumente o tamanho da árvore do jogo (por exemplo, permitindo movimentos ilegais) até ela se tornar tratável.

Contudo, para jogos onde o número de movimentos não é limitado (por exemplo, pelo tamanho do tabuleiro ou por uma regra sobre repetições de posição), a árvore do jogo é infinita.

Árvores de decisão

As duas próximas medições usam a ideia de árvores de decisão. Uma árvore de decisão é uma subárvore da árvore do jogo, com cada posição classificada como "jogador A venceu", "jogador B venceu" ou "empate", se essa posição pode provar ter esse valor (assumindo melhores jogadas de ambos os lados) examinando apenas outras posições no gráfico. (Posições terminais podem ser classificadas diretamente; uma posição com o jogador A em sua rodada de mover pode ser classificada como "jogador A venceu" se qualquer posição sucessora for uma vitória para A, ou classificada como "jogador B venceu" se todas posições sucessoras são empate ou vitória para B. Isto vale correspondentemente para posições com B em sua rodada de mover.)

Complexidade de decisão

Complexidade de decisão de um jogo é o número de nós folhas na menor árvore de decisão que estabelece o valor da posição inicial.

Complexidade da árvore do jogo

A complexidade da árvore do jogo de um jogo é o número de nós folha na menor árvore de decisão de largura total que estabelece o valor da posição inicial.[1] Uma árvore de largura total inclui todos os nós de cada profundidade.

Isto é uma estimativa do número de posições que teríamos que avaliar em uma busca minimax para determinar o valor da posição inicial.

É difícil de estimar a complexidade da árvore do jogo, mas para alguns jogos um limitante inferior razoável pode ser dado pelo aumento do fator de ramificação médio do jogo à potência do número de camadas, ou:

GTC≥bd

Complexidade computacional

A complexidade computacional de jogos descreve a dificuldade assintótica de um jogo à medida que cresce arbitrariamente rápido, expressa em notação big O ou como membro de uma classe de complexidade. Este conceito não se aplica a jogos específicos, mas sim a jogos que foram generalizados de modo que eles podem ser feitos arbitrariamente grandes, tipicamente sendo jogados em um tabuleiro n x n. (Do ponto de vista da complexidade computacional, um jogo com tamanho de tabuleiro fixo é um problema finito que pode ser resolvido em O(1), por exemplo através de uma tabela de consulta de posições para realizar os melhores movimentos para cada posição.)

A complexidae assintótica é definida pela mais eficiente (em termos de o que que um recurso computacional considere) algoritmo de solução do jogo; a mais comum medida de complexidade (Tempo computacional) é sempre limitada inferiormente pelo logaritmo da complexidade assintótica estado-espaço, desde que a solução algorítmica funcione para todos os possíveis estados do jogo. Ela será superiormente limitada pelas complexidades de cada algoritmo dos jogos da mesma classe. Observações similares aplicam-se a segunda medida de complexidade mais comumente usada, a quantidade de espaço ou memória computacional usada na computação. Não é óbvio que há algum limitante inferior na complexidade espacial de um jogo típico, porque o algoritmo não precisa armazenar os estados do jogo, entretanto muitos jogos de interesse são PSPACE-difícil, e segue que sua complexidade espacial também será limitada inferiormente pelo logaritmo da complexidade assintótica estado-espaço (tecnicamente o limitante é polinomial somente em sua quantidade, mas é usualmente conhecido por ser linear).

  • A estratégia minimax de busca em profundidade usará tempo computacional proporcional a complexidade da árvore dos jogos, desde que esta explore toda a árvore e uma quantidade polinomial de memória no algoritmo da complexidade da árvore, uma vez que o algoritmo sempre armazene um nó da árvore a cada possível movimento em profundidade e o número de nós no maior movimento em profundidade seja precisamente a complexidade da árvore.
  • A Indução retroativa usará memória e tempo proporcional à complexidade estado-espaço como deverá computar e gravar o movimento correto para cada possível posição.

Exemplo: Jogo da velha

Para o jogo da velha, um limitante superior simples para o tamanho do estado-espaço é de 39 = 19,683. (Há 9 células e três estados para cada célula.) Esta conta inclui várias posições ilegais, como a posição com cinco X e nenhum O, ou a posição em que os dois jogadores tem uma linha de três. Uma conta mais cuidadosa, removendo as posições ilegais, nos dá 5,478. Quando rotações e reflexões de posições são consideradas idênticas, há apenas 765 posições essencialmente diferentes.

Um limitante superior simples para o tamanho da árvore do jogo é igual a 9! = 362,880. (Há 9 posições para o primeiro movimento, oito para o segundo e assim por diante) Isto inclui jogos ilegais que continuam mesmo que um dos jogadores já tivesse ganho. Uma conta mais cuidadosa nos dá 255,168 jogos possíveis. Quando rotações e reflexões de posições são consideradas idênticas, há apenas 26,830 jogos possíveis.

A complexidade computacional do jogo da velha depende de como o jogo está generalizado. Uma generalização natural é a de m,n,k-jogos: jogados em um tabuleiro m x n com um ganhador sendo o primeiro jogador a conseguir k em uma linha. É imediatamente claro que este jogo pode ser resolvido em DSPACE(mn) pesquisando toda a árvore do jogo. Isto o coloca na importante classe de complexidade PSPACE. Como algum trabalho a mais, pode ser mostrado estar em PSPACE-completo.[4]

Complexidades de alguns jogos conhecidos

Devido ao grande tamanho das complexidades dos jogos, esta tabela nos dá o teto de seus logaritmos na base 10. (Em outras palavras, o número de zeros. Um 3 na tabela representa o tamanho de aproximadamente 1,000). Todos os seguintes números devem ser considerados com cautela: mudanças aparentemente mínimas das regras de um jogo podem mudar os números (que são muitas vezes estimativas grosseiras de qualquer maneira) por fatores enormes, que podem facilmente ser muito maiores do que os números mostrados.

Jogo Tamanho do Tabuleiro

(posições)

Complexidade estado-espaço

(log na base 10)

Complexidade da árvore do jogo

(log na base 10)

Duração média do jogo

(Camadas)

Fator de ramificação Referências Classe de complexidade de jogos generalizados
Jogo da velha 9 3 5 9 4 PSPACE-completo[4]
Sim 15 3 8 14 3.7 PSPACE-completo[5]
Pentominoes 64 12 18 10 75 [6][7] PSPACE
Kalah [8] 14 13 18 [6] Generalização não está clara
Connect Four 42 13 21 36 4 [1][9] PSPACE
Domineering (8 × 8) 64 15 27 30 8 [6] PSPACE; em P para certas dimensões [10]
Congkak 14 15 33 [6]
Damas (8x8) 32 20 ou 18 31 70 2.8 [11] or [1] EXPTIME-completo[12]
Awari[13] 12 12 32 60 3.5 [1] Generalização não está clara
Qubic 64 30 34 20 54.2 [1] PSPACE-completo[4]
Fanorona 45 21 46 44 11 [14] EXPTIME
Nine Men's Morris 24 10 50 50 10 [1] EXPTIME
Damas internacional(10x10) 50 30 54 90 4 [1] EXPTIME-completo[12]
Xadrez chinês (2 grupos) 121 23 [15] EXPTIME-completo [16]
Xadrez chinês (6 sets) 121 78 [15] EXPTIME-completo [16]
Lines of Action 64 23 64 44 29 [17] EXPTIME
Reversi (Othello) 64 28 58 58 10 [1] PSPACE-completo[18]
OnTop 72 88 62 31 23.77 [19]
Hex (11x11) 121 57 98 40 280 [6] PSPACE-completo[20]
Gomoku (15x15, estilo livre) 225 105 70 30 210 [1] PSPACE-completo[4]
Go (9x9) 81 38 45 [1][21] EXPTIME-completo[22]
Xadrez 64 47 123 80 35 [23] EXPTIME-completo (sem a regra dos 50 movimentos) [24]
Connect6 361 172 140 30 46000 [25] PSPACE-completo[26]
Gamão 28 20 144 50-60 250 [27] Generalização não está clara
Xiangqi 90 40 150 95 38 [1][2][3] acredita-se ser EXPTIME-completo
Abalone 61 25 154 87 60 [28][29] PSPACE-difícil e EXPTIME
Havannah 271 127 157 66 240 [6][30] PSPACE-completo[31]
Janggi 90 44 160 100 40 [3] acredita-se ser EXPTIME-completo
Quoridor 81 42 162 91 60 [32] PSPACE
Carcassonne 72 >40 195 71 55 [33] Generalização não está clara
Amazons (10x10) 100 40 212 84 374 ou 299[34] [35][36] PSPACE-completo[37]
Go (13x13) 169 79 90 [1][21] EXPTIME-completo[22]
Shogi 81 71 226 115 92 [2][38] EXPTIME-completo[39]
Arimaa 64 43 402 92 17281 [40][41][42] EXPTIME
Go (19x19) 361 171 360 150 250 [1][21] EXPTIME-completo[22]
Stratego 92 115 535 381 21.739 [43]
Double dummy bridge[44] (52) <17 <40 52 5.6
Bejeweled and Candy Crush (8x8) 64 <50 [45] NP-difícil

Ver também

Predefinição:Referências

Ligações externas

  1. ↑ 1,00 1,01 1,02 1,03 1,04 1,05 1,06 1,07 1,08 1,09 1,10 1,11 1,12 1,13 Predefinição:Citar tese
  2. ↑ 2,0 2,1 2,2 Predefinição:Citar periódico
  3. ↑ 3,0 3,1 3,2 Predefinição:Citar web
  4. ↑ 4,0 4,1 4,2 4,3 Predefinição:Citar periódico
  5. ↑ Wolfgang Slany: The Complexity of Graph Ramsey Games
  6. ↑ 6,0 6,1 6,2 6,3 6,4 6,5 Predefinição:Citar periódico
  7. ↑ Predefinição:Citar relatório em Games of no chance
  8. ↑ Veja van den Herik et al para regras.
  9. ↑ Predefinição:Citar web
  10. ↑ Predefinição:Citar relatório
  11. ↑ Predefinição:Citar periódico
  12. ↑ 12,0 12,1 Predefinição:Citar periódico
  13. ↑ Veja Allis 1994 para regras
  14. ↑ Predefinição:Citar periódico
  15. ↑ 15,0 15,1 Predefinição:Citar periódico arXiv:0803.1245
  16. ↑ 16,0 16,1 Predefinição:Citar periódico Prova integridade de generalizações de gráficos arbitrários.
  17. ↑ Predefinição:Citar tese
  18. ↑ Predefinição:Citar periódico
  19. ↑ Robert Briesemeister (2009). Analysis and Implementation of the Game OnTop (PDF) (Thesis). Maastricht University, Dept of Knowledge Engineering.
  20. ↑ Predefinição:Citar periódico
  21. ↑ 21,0 21,1 21,2 John Tromp and Gunnar Farnebäck (2007). "Combinatorics of Go". Este artigo decorre dos limites 48<log(log(N))<171 sobre o número de jogos N possíveis.
  22. ↑ 22,0 22,1 22,2 Predefinição:Citar livro
  23. ↑ O tamanho do estado espaço e da árvore do jogo para o xadrez foi primeiramente estimado em Predefinição:Citar periódico Shannon deu estimativas de 1043 and 10120 respectivamente, menor que o limite superior na tabela, a qual é detalhada em Número de Shannon.
  24. ↑ Predefinição:Citar periódico
  25. ↑ Chang-Ming Xu; Ma, Z.M.; Jun-Jie Tao; Xin-He Xu (2009). "Enhancements of proof number search in connect6". 2009 Chinese Control and Decision Conference. p. 4525. doi:10.1109/CCDC.2009.5191963. ISBN 978-1-4244-2722-2.
  26. ↑ On the fairness and complexity of generalized k-in-a-row games
  27. ↑ Predefinição:Citar web
  28. ↑ Predefinição:Citar web
  29. ↑ Kopczynski, Jacob S (2014). Pushy Computing: Complexity Theory and the Game Abalone (Thesis). Reed College.
  30. ↑ Joosten, B. "Creating a Havannah Playing Agent" (PDF). Visitado em 29 de março de 2012.
  31. ↑ E. Bonnet, F. Jamain and A. Saffidine (2014-03-25). "Havannah and TwixT are PSPACE-complete". arXiv:1403.6518 cs.CC.
  32. ↑ Lisa Glendenning (May 2005). Mastering Quoridor Predefinição:Wayback (PDF). Computer Science (B.Sc. thesis). University of New Mexico.
  33. ↑ Cathleen Heyden (2009). Implementing a Computer Player for Carcassonne (PDF) (Thesis). Maastricht University, Dept of Knowledge Engineering.
  34. ↑ O menor fator de ramificação é do jogador 2.
  35. ↑ Julien Kloetzer; Hiroyuki Iida; Bruno Bouzy (2007). "The Monte-Carlo Approach in Amazons".
  36. ↑ P. P. L. M. Hensgens (2001). "A Knowledge-Based Approach of the Game of Amazons" (PDF). Universiteit Maastricht, Institute for Knowledge and Agent Technology.
  37. ↑ R. A. Hearn (2005-02-02). "Amazons is PSPACE-complete". arXiv:cs.CC/0502013 cs.CC.
  38. ↑ Predefinição:Citar periódico
  39. ↑ Predefinição:Citar periódico
  40. ↑ Christ-Jan Cox (2006). "Analysis and Implementation of the Game Arimaa" (PDF).
  41. ↑ David Jian Wu (2011). "Move Ranking and Evaluation in the Game of Arimaa" (PDF).
  42. ↑ Brian Haskin (2006). "A Look at the Arimaa Branching Factor".
  43. ↑ A.F.C. Arts (2010). Competitive Play in Stratego (PDF) (Thesis). Maastricht.
  44. ↑ Double dummy bridge não é propriamente um jogo de tabuleiro mas mas tem uma árvore de jogo similar, e é estudado em computer bridge, o que motiva a inclusão deste jogo na lista.
  45. ↑ L. Gualà, S. Leucci, E. Natale (2014). "Bejeweled, Candy Crush and other Match-Three Games are (NP-)Hard".
Obtida de "https://pt.wiki.beta.math.wmflabs.org/w/index.php?title=Complexidade_de_jogos&oldid=6799"