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
- Vá e matemática
- Jogo resolvido
- Resolvendo xadrez
- Número Shannon
- lista de jogos e quebra-cabeças NP-completos
- lista de jogos e quebra-cabeças completos do PSPACE