Vá e matemática - Go and mathematics

Parte de uma série sobre
Ir
Vá embarcar part.jpg
Especificidades do jogo
História e cultura
Jogadores e organizações
Computadores e matemática

O jogo Go é um dos jogos mais populares do mundo. Como resultado de suas regras elegantes e simples, o jogo tem sido uma inspiração para pesquisas matemáticas . Shen Kuo , um estudioso chinês do século 11, estimou que o número de posições possíveis no conselho é de cerca de 10 172 em The Dream Pool Essays . Em anos mais recentes, a pesquisa do jogo por John H. Conway levou à invenção dos números surreais e contribuiu para o desenvolvimento da teoria dos jogos combinatórios (com Go Infinitesimals sendo um exemplo específico de seu uso em Go).

Complexidade computacional

Generalized Go é jogado em n × n placas, ea complexidade computacional de determinar o vencedor em uma determinada posição de Go generalizada depende crucialmente as regras ko .

Go é “quase” no PSPACE , uma vez que no jogo normal os movimentos não são reversíveis, e é apenas através da captura que existe a possibilidade de repetir os padrões necessários para uma complexidade maior.

Sem ko

Sem o ko, Go é difícil para o PSPACE . Isso é provado reduzindo a Fórmula Booleana Quantificada Verdadeira , que é conhecida por ser PSPACE-completa, à geografia generalizada , à geografia planar generalizada, à geografia plana generalizada com grau máximo 3 e finalmente às posições Go.

Go with superko não é conhecido por estar no PSPACE. Embora os jogos reais pareçam nunca durar mais do que os movimentos, em geral não se sabe se houve um limite polinomial na duração dos jogos Go. Se houvesse, Go seria PSPACE completo. Como está atualmente, pode ser PSPACE completo, EXPTIME completo ou mesmo EXPSPACE completo.

Regra do ko japonês

As regras do ko japonês afirmam que apenas o ko básico, ou seja, um movimento que reverte o tabuleiro para a situação anterior, é proibido. Situações repetitivas mais longas são permitidas, potencialmente permitindo que um jogo seja repetido para sempre, como o ko triplo, onde há três kos ao mesmo tempo, permitindo um ciclo de 12 movimentos.

Com as regras do ko japonês, Go é EXPTIME -completo.

Regra Superko

A regra do superko (também chamada de regra do superko posicional) afirma que é proibida a repetição de qualquer posição do tabuleiro que tenha ocorrido anteriormente. Esta é a regra ko usada na maioria dos conjuntos de regras chineses e americanos.

É um problema em aberto saber qual é a classe de complexidade do Go sob a regra do superko. Embora a regra Go with Japanese ko seja EXPTIME-completa, os limites inferior e superior da prova de integridade EXPTIME de Robson quebram quando a regra superko é adicionada.

É sabido que é pelo menos PSPACE-hard, já que a prova em da PSPACE-dureza de Go não se baseia na regra do ko, ou na falta da regra do ko. Sabe-se também que Go está em EXPSPACE.

Robson mostrou que se a regra do superko, ou seja, “nenhuma posição anterior pode ser recriada”, for adicionada a certos jogos de dois jogadores que estão completos em EXPTIME, então os novos jogos serão completos em EXPSPACE. Intuitivamente, isso ocorre porque uma quantidade exponencial de espaço é necessária até mesmo para determinar os movimentos legais de uma posição, porque o histórico do jogo que leva a uma posição pode ser exponencialmente longo.

Como resultado, as variantes superko (movimentos que repetem uma posição anterior do tabuleiro não são permitidas) do xadrez generalizado e das damas são EXPSPACE-complete, já que o xadrez generalizado e as damas são EXPTIME-complete. No entanto, este resultado não se aplica ao Go.

Complexidade de certas configurações Go

Um final de jogo Go começa quando o tabuleiro é dividido em áreas que são isoladas de todas as outras áreas locais por pedras vivas, de forma que cada área local tenha uma árvore de jogo canônica de tamanho polinomial. Na linguagem da teoria dos jogos combinatórios , isso acontece quando um jogo Go se decompõe em uma soma de subjogos com árvores de jogo canônicas de tamanho polinomial.

Com essa definição, os jogos finais de Go são difíceis para PSPACE.

Isso é provado convertendo o problema da Fórmula Booleana Quantificada , que é PSPACE-completo, em uma soma de subjogos Go pequenos (com árvores canônicas de tamanho polinomial). Observe que o artigo não prova que os jogos finais de Go estão em PSPACE, então eles podem não ser PSPACE completos.

Determinar qual lado vence uma corrida de captura de escada é PSPACE completo, seja a regra do ko japonês ou a regra do superko em vigor. Isso é comprovado pela simulação de QBF, conhecido por ser PSPACE completo, com escadas que saltam ao redor do tabuleiro como feixes de luz.

Cargos legais

Como cada local no tabuleiro pode ser vazio, preto ou branco, há um total de 3 n 2 posições possíveis do tabuleiro em um tabuleiro quadrado com comprimento n ; no entanto, nem todos eles são legais. Tromp e Farnebäck derivada uma fórmula de recorrência para posições legais de uma placa de rectângulo com comprimento m e n . O número exato de foi obtido em 2016. Eles também encontram uma fórmula assintótica , onde , e . Foi estimado que o universo observável contém cerca de 10 80 átomos, muito menos do que o número de posições legais possíveis de tamanho de placa regular (m = n = 19). À medida que o conselho aumenta, a porcentagem das posições que são legais diminui.

Tamanho do tabuleiro n × n 3 n 2 Porcentagem legal (posições legais) ( A094777 )
1 × 1 3 33,33% 1
2 × 2 81 70,37% 57
3 × 3 19.683 64,40% 12.675
4 × 4 43.046.721 56,49% 24.318.165
5 × 5 847.288.609.443 48,90% 414.295.148.741
9 × 9 4,43426488243 × 10 38 23,44% 1.03919148791 × 10 38
13 × 13 4.30023359390 × 10 80 8,66% 3,72497923077 × 10 79
19 × 19 1.74089650659 × 10 172 1,20% 2.08168199382 × 10 170

Complexidade da árvore do jogo

O cientista da computação Victor Allis observa que os jogos típicos entre especialistas duram cerca de 150 jogadas, com uma média de cerca de 250 opções por jogada, sugerindo uma complexidade de árvore de jogo de 10 360 . Para o número de jogos teoricamente possíveis , incluindo jogos impossíveis de jogar na prática, Tromp e Farnebäck fornecem limites inferior e superior de 10 10 48 e 10 10 171, respectivamente. O limite inferior foi melhorada para um Googolplex por Walraet e Tromp. O número mais comumente citado para o número de jogos possíveis, 10 700, é derivado de uma simples permutação de 361 movimentos ou 361! = 10 768 . Outra derivação comum é assumir N interseções e L jogo mais longo para N L jogos totais. Por exemplo, 400 movimentos, como visto em alguns jogos profissionais, seria um de 361 400 ou 1 × 10 1023 jogos possíveis.

O número total de jogos possíveis é uma função tanto do tamanho do tabuleiro quanto do número de jogadas jogadas. Embora a maioria dos jogos dure menos de 400 ou mesmo 200 movimentos, muitos mais são possíveis.

Tamanho do jogo Tamanho do tabuleiro N (intersecções) N ! Duração média do jogo L N L Duração máxima do jogo (# de movimentos) Limite inferior de jogos Limite superior de jogos
2 × 2 4 24 3 64 386.356.909.593 386.356.909.593
3 × 3 9 3,6 × 10 5 5 5,9 × 10 4
4 × 4 16 2,1 × 10 13 9 6,9 × 10 10
5 × 5 25 1,6 × 10 25 15 9,3 × 10 20
9 × 9 81 5,8 × 10 120 45 7,6 × 10 85
13 × 13 169 4,3 × 10 304 90 3,2 × 10 200
19 × 19 361 1,0 × 10 768 200 3 × 10 511 10 48 10 10 48 10 10 171
21 × 21 441 2,5 × 10 976 250 1,3 × 10 661

O número total de jogos possíveis pode ser estimado a partir do tamanho do tabuleiro de várias maneiras, algumas mais rigorosas do que outras. O mais simples, uma permutação do tamanho do tabuleiro, ( N ) L , não inclui capturas e posições ilegais. Tomando N como o tamanho do tabuleiro (19 × 19 = 361) e L como o jogo mais longo, N L forma um limite superior. Um limite mais preciso é apresentado no artigo Tromp / Farnebäck.

Jogo mais longo L (19 × 19) ( N ) L Limite inferior de jogos Limite superior de jogos Notas
1 361 361 361 As brancas renunciam após o primeiro movimento, 361 ignorando toda a simetria incluindo y = x else (distâncias do canto) 10 × 10−10 = 90 90/2 = 45 +10 (adicionando de volta x = y pontos de simetria) = 55.
2 722 721 As pretas renunciam após o primeiro movimento das brancas, 721 ignorando toda simetria incluindo y = x mais 19 × 19−19 = 342 342/2 = 171 +19 = 190 - 1 = 189.
50 2,1 × 10 126 7,5 × 10 127
100 1,4 × 10 249 5,6 × 10 255
150 6,4 × 10 367 4,2 × 10 383
200 1,9 × 10 481 3,2 × 10 511
250 8,2 × 10 587 2,4 × 10 639
300 2,8 × 10 684 7,8 × 10 766
350 3,6 × 10 760 1,3 × 10 895
361 1,4 × 10 768 1,8 × 10 923 Jogo mais longo usando 181 pedras pretas e 180 brancas
411 n / D 1,3 × 10 1051 Jogo profissional mais longo
500 n / D 5,7 × 10 1278
1000 n / D 3,2 × 10 2557
47 milhões n / D 10 10 8 361 3 movimentos
10 48 n / D 10 10 48 10 10 171 Jogo mais longo

10 700 é, portanto, uma superestimativa do número de jogos possíveis que podem ser jogados em 200 movimentos e uma subestimação do número de jogos que podem ser jogados em 361 movimentos. Como existem cerca de 31 milhões de segundos em um ano, levaria cerca de 2+1 ⁄ 4 anos, jogando 16 horas por dia em um movimento por segundo, para jogar 47 milhões de movimentos.

Veja também

Notas

Referências

links externos