Complexidade do jogo - Game complexity

A teoria dos jogos combinatórios tem várias maneiras de medir a complexidade do jogo . Este artigo descreve cinco deles: complexidade do espaço de estado, tamanho da árvore do jogo, complexidade da decisão, complexidade da árvore do jogo e complexidade computacional.

Medidas de complexidade do jogo

Complexidade de espaço de estado

A complexidade do espaço de estado de um jogo é o número de posições legais do jogo que podem ser alcançadas a partir da posição inicial do jogo.

Quando isso é muito difícil de calcular, um limite superior pode muitas vezes ser calculado contando também (algumas) posições ilegais, ou seja, posições que nunca podem surgir no decorrer de um jogo.

Tamanho da árvore do jogo

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

A árvore do jogo é tipicamente muito maior do que o espaço de estado porque as mesmas posições podem ocorrer em muitos jogos fazendo movimentos em uma ordem diferente (por exemplo, em um jogo da velha com dois X e um O no tabuleiro, este posição poderia ter sido alcançada de duas maneiras diferentes, dependendo de onde o primeiro X foi colocado). Um limite superior para o tamanho da árvore do jogo pode às vezes ser calculado simplificando o jogo de uma forma que apenas aumenta o tamanho da árvore do jogo (por exemplo, permitindo movimentos ilegais) até que se torne tratável.

Para jogos em que o número de movimentos não é limitado (por exemplo, pelo tamanho do tabuleiro ou por uma regra sobre repetição de posição), a árvore do jogo é geralmente infinita.

Árvores de decisão

As próximas duas medidas usam a ideia de uma árvore de decisão , que é uma subárvore da árvore do jogo, com cada posição marcada com "jogador A vence", "jogador B vence" ou "empatado", se for possível provar que essa posição teve esse valor (assumindo a melhor jogada de ambos os lados) examinando apenas as outras posições no gráfico. (As posições terminais podem ser rotuladas diretamente; uma posição com o jogador A para mover pode ser rotulada como "jogador A vence" se qualquer posição sucessora for uma vitória para A, ou rotulada como "jogador B vence" se todas as posições sucessoras forem vitórias para B, ou rotulado como "empate" se todas as posições sucessoras forem empatadas ou ganharem para B. E correspondentemente para as posições com B se moverem.)

Complexidade de decisão

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

Complexidade da árvore de jogo

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

Esta é uma estimativa do número de posições que seria necessário avaliar em uma pesquisa minimax para determinar o valor da posição inicial.

É difícil até mesmo estimar a complexidade da árvore do jogo, mas para alguns jogos uma aproximação pode ser dada aumentando o fator de ramificação médio do jogo b à potência do número de camadas d em um jogo médio, ou:

.

Complexidade computacional

A complexidade computacional de um jogo descreve a dificuldade assintótica de um jogo à medida que cresce arbitrariamente grande, expressa em notação grande O ou como pertencimento a uma classe de complexidade . Este conceito não se aplica a jogos particulares, mas sim para jogos que foram generalizadas , para que possam ser feitas arbitrariamente grande, normalmente, jogando-os em um n -by- n bordo. (Do ponto de vista da complexidade computacional, um jogo em um tamanho fixo de tabuleiro é um problema finito que pode ser resolvido em O (1), por exemplo, por uma tabela de consulta de posições para o melhor movimento em cada posição.)

A complexidade assintótica é definida pelo algoritmo mais eficiente (em termos de qualquer recurso computacional que se esteja considerando) para resolver o jogo; a medida de complexidade mais comum ( tempo de computação ) é sempre limitada pelo logaritmo da complexidade do espaço de estado assintótico, uma vez que um algoritmo de solução deve funcionar para todos os estados possíveis do jogo. Ele será limitado pela complexidade de qualquer algoritmo específico que funcione para a família de jogos. Observações semelhantes se aplicam à segunda medida de complexidade mais comumente usada, a quantidade de espaço ou memória de computador usada pela computação. Não é óbvio que haja qualquer limite inferior na complexidade do espaço para um jogo típico, porque o algoritmo não precisa armazenar estados do jogo; no entanto, muitos jogos de interesse são conhecidos por serem PSPACE-hard , e segue-se que sua complexidade espacial será limitada pelo logaritmo da complexidade do espaço de estado assintótico também (tecnicamente, o limite é apenas um polinômio nesta quantidade; mas geralmente é conhecido como linear).

  • A estratégia de profundidade de minimax usará o tempo de computação proporcional à complexidade da árvore do jogo, uma vez que deve explorar toda a árvore, e uma quantidade de polinômio de memória no logaritmo da complexidade da árvore, uma vez que o algoritmo deve sempre armazenar um nó do árvore em cada profundidade de movimento possível, e o número de nós na profundidade de movimento mais alta é precisamente a complexidade da árvore.
  • A indução reversa usará memória e tempo proporcionais à complexidade do espaço de estado, pois deve calcular e registrar o movimento correto para cada posição possível.

Exemplo: jogo da velha (pontos e cruzes)

Para o jogo da velha , um limite superior simples para o tamanho do espaço de estado é 3 9 = 19.683. (Existem três estados para cada célula e nove células.) Essa contagem inclui muitas posições ilegais, como uma posição com cinco cruzes e nenhum zeros, ou uma posição em que ambos os jogadores têm uma linha de três. Uma contagem mais cuidadosa, removendo essas posições ilegais, dá 5.478. E quando as rotações e reflexos de posições são considerados idênticos, existem apenas 765 posições essencialmente diferentes.

Para limitar a árvore do jogo, existem 9 movimentos iniciais possíveis, 8 respostas possíveis e assim por diante, de modo que haja no máximo 9! ou 362.880 jogos no total. No entanto, os jogos podem levar menos de 9 movimentos para serem resolvidos e uma enumeração exata fornece 255.168 jogos possíveis. Quando rotações e reflexos de posições são considerados iguais, existem apenas 26.830 jogos possíveis.

A complexidade computacional do jogo da velha depende de como ele é generalizado . Uma generalização natural é para m , n , k -games : jogado em um tabuleiro m por n com o vencedor sendo o primeiro jogador a obter k em uma linha. É imediatamente claro que este jogo pode ser resolvido em DSPACE ( mn ) pesquisando em toda a árvore do jogo. Isso o coloca na importante classe de complexidade PSPACE . Com um pouco mais de trabalho, pode ser mostrado que é PSPACE completo .

Complexidades de alguns jogos conhecidos

Devido ao grande tamanho da complexidade do jogo, esta tabela fornece o teto de seu logaritmo para a base 10. (em outras palavras, o número de dígitos). Todos os números a seguir devem ser considerados com cautela: mudanças aparentemente menores nas regras de um jogo podem alterar os números (que geralmente são estimativas grosseiras de qualquer maneira) por fatores tremendos, que podem facilmente ser muito maiores do que os números mostrados.

Nota: ordenado pelo tamanho da árvore do jogo

Jogo Tamanho do tabuleiro

(posições)

Complexidade de espaço de estado

(como log para a base 10)

Complexidade da árvore de jogo

(como log para a base 10)

Duração média do jogo

( folhas )

Fator de ramificação Ref Classe de complexidade de jogo generalizado adequado
Jogo da velha 9 3 5 9 4 PSPACE completo
Sim 15 3 8 14 3,7 PSPACE completo
Pentominós 64 12 18 10 75 ?, mas em PSPACE
Kalah 14 13 18 50 A generalização não é clara
Connect Four 42 13 21 36 4 ?, mas em PSPACE
Dominador (8 × 8) 64 15 27 30 8 ?, mas em PSPACE ; em P para certas dimensões
Congkak 14 15 33
Rascunhos ingleses (8x8) (damas) 32 20 ou 18 40 70 2,8 EXPTIME-concluído
Awari 12 12 32 60 3,5 A generalização não é clara
Qubic 64 30 34 20 54,2 PSPACE completo
Ponte dupla falsa (52) <17 <40 52 5,6 PSPACE completo
Fanorona 45 21 46 44 11 ?, mas em EXPTIME
Morris de nove homens 24 10 50 50 10 ?, mas em EXPTIME
Tablut 81 27
Rascunhos internacionais (10x10) 50 30 54 90 4 EXPTIME-concluído
Damas chinesas (2 conjuntos) 121 23 180 EXPTIME -completo
Damas chinesas (6 jogos) 121 78 600 EXPTIME -completo
Reversi (Othello) 64 28 58 58 10 PSPACE completo
OnTop (jogo básico 2p) 72 88 62 31 23,77
Linhas de Ação 64 23 64 44 29 ?, mas em EXPTIME
Gomoku (15x15, estilo livre) 225 105 70 30 210 PSPACE completo
Hex (11x11) 121 57 98 50 96 PSPACE completo
Xadrez 64 44 123 70 35 EXPTIME completo (sem regra de desenho de 50 movimentos )
Bejeweled e Candy Crush (8x8) 64 <50 70 NP-difícil
GIPF 37 25 132 90 29,3
Connect6 361 172 140 30 46000 PSPACE completo
Gamão 28 20 144 55 250 A generalização não é clara
Xiangqi 90 40 150 95 38 ?, acredita-se ser EXPTIME-completo
Abalone 61 25 154 87 60 PSPACE-hard e em EXPTIME
Havannah 271 127 157 66 240 PSPACE completo
Twixt 572 140 159 60 452
Janggi 90 44 160 100 40 ?, acredita-se ser EXPTIME-completo
Quoridor 81 42 162 91 60 ?, mas em PSPACE
Carcassonne (jogo básico 2p) 72 > 40 195 71 55 A generalização não é clara
Amazonas (10x10) 100 40 212 84 374 ou 299 PSPACE completo
Shogi 81 71 226 115 92 EXPTIME-concluído
Thurn and Taxis (2 jogadores) 33 66 240 56 879
Go (19x19) 361 170 360 150 250 EXPTIME-concluído
Arimaa 64 43 402 92 17281 ?, mas em EXPTIME
Stratego 92 115 535 381 21,739
Xadrez infinito infinito infinito infinito infinito infinito Desconhecido, mas mate-in-n é decidível
Magic: the Gathering Infinito Ilimitado Ilimitado infinito infinito AH-difícil

Notas

Referências

Veja também

links externos