Por Que o Go É Difícil?
Antes do AlphaGo aparecer, o Go era considerado a "última fortaleza" da inteligência artificial. Durante décadas, pesquisadores tentaram vários métodos, mas nunca conseguiram fazer um computador alcançar o nível de jogadores profissionais.
Isso não foi porque os pesquisadores não se esforçaram o suficiente, mas porque o Go é fundamentalmente um problema computacional extremamente difícil.
Este artigo explorará em profundidade: o que torna o Go tão difícil? Por que foi chamado de "Santo Graal da IA"?
Explosão do Espaço de Estados: O Significado de 10^170
O Que É Espaço de Estados?
Em qualquer jogo de tabuleiro, o espaço de estados (State Space) refere-se ao número total de todas as posições de tabuleiro possíveis. Esse número determina a viabilidade da busca por força bruta.
Para o Go, esse número é:
Espaço de estados do Go ≈ 10^170
Que conceito é esse? Vamos fazer algumas comparações.
Comparação com o Número de Átomos no Universo
De acordo com estimativas de físicos, o número total de átomos no universo observável é aproximadamente:
Átomos no universo ≈ 10^80
Isso significa:
O número de posições possíveis no Go é 10^90 vezes o número de átomos no universo.
Se você usasse cada átomo no universo como um supercomputador, e cada computador pudesse processar 1 bilhão de posições por segundo, desde o Big Bang até agora (cerca de 13,8 bilhões de anos) não seria possível enumerar todas as posições.
Compreensão Intuitiva dos Números
| Número | Significado |
|---|---|
| 10^9 | Um bilhão, ordem de grandeza da população humana total |
| 10^12 | Um trilhão, número de formigas no mundo |
| 10^23 | Número de moléculas em um mol |
| 10^80 | Número de átomos no universo |
| 10^120 | Espaço de estados do xadrez |
| 10^170 | Espaço de estados do Go |
Por Que o Espaço de Estados do Go É Tão Grande?
O espaço de estados do Go é enorme por várias razões:
1. Tamanho do Tabuleiro
O Go usa um tabuleiro 19×19, com 361 intersecções. Em comparação:
- Xadrez: 8×8 = 64 casas
- Xiangqi (xadrez chinês): 9×10 = 90 intersecções
- Gomoku (cinco em linha): 15×15 = 225 intersecções
2. Três Estados por Intersecção
Cada intersecção pode estar:
- Vazia (sem pedra)
- Com pedra preta
- Com pedra branca
Uma estimativa grosseira das combinações possíveis é 3^361 ≈ 10^172. Considerando as regras do Go (como ko, restrições de liberdades), o número real de posições legais é cerca de 10^170.
3. Pedras Não Se Movem
Diferente do xadrez, as pedras de Go uma vez colocadas não se movem (a menos que sejam capturadas). Isso significa que cada jogada adiciona uma pedra, em vez de mover uma peça existente, levando a mais caminhos possíveis.
Código Ilustrativo: Estimativa do Espaço de Estados
import math
# Tamanho do tabuleiro
BOARD_SIZE = 19
TOTAL_POINTS = BOARD_SIZE ** 2 # 361
# Cada intersecção tem três estados (vazio, preto, branco)
# Limite superior grosseiro
upper_bound = 3 ** TOTAL_POINTS
print(f"Limite superior grosseiro: 3^{TOTAL_POINTS} ≈ 10^{math.log10(upper_bound):.0f}")
# Saída: Limite superior grosseiro: 3^361 ≈ 10^172
# Estimativa real considerando restrições das regras
# O cálculo preciso de Tromp-Taylor dá aproximadamente 2,08 × 10^170
actual_estimate = 2.08e170
print(f"Estimativa real: {actual_estimate:.2e}")
# Comparação com átomos no universo
universe_atoms = 1e80
ratio = actual_estimate / universe_atoms
print(f"Posições de Go / Átomos no universo = 10^{math.log10(ratio):.0f}")
# Saída: Posições de Go / Átomos no universo = 10^90
A Maldição do Fator de Ramificação: Em Média 250 Escolhas
O Que É Fator de Ramificação?
Fator de ramificação (Branching Factor) refere-se ao número médio de jogadas legais em qualquer ponto de um jogo. Esse número determina a largura da árvore de busca.
| Jogo | Fator de Ramificação Médio |
|---|---|
| Jogo da velha | ~4 |
| Xadrez | ~35 |
| Xiangqi | ~38 |
| Reversi (Othello) | ~10 |
| Go | ~250 |
Crescimento Explosivo da Árvore de Busca
Suponha que queremos usar um algoritmo de busca em árvore para olhar N jogadas à frente. O número de posições a considerar é aproximadamente:
Onde b é o fator de ramificação.
Vamos comparar xadrez e Go:
| Olhar N jogadas | Xadrez (b=35) | Go (b=250) | Diferença |
|---|---|---|---|
| 1 jogada | 35 | 250 | 7× |
| 2 jogadas | 1.225 | 62.500 | 51× |
| 4 jogadas | 1,5 milhão | 3,9 bilhões | 2.600× |
| 6 jogadas | 1,8 bilhão | 2,4×10^14 | 130 milhões× |
| 10 jogadas | 2,8×10^15 | 9,5×10^23 | 340 milhões× |
Olhar 10 jogadas à frente, o Go precisa considerar 340 milhões de vezes mais posições que o xadrez.
Por Que o Método do Deep Blue Falhou no Go
O Deep Blue, que derrotou Kasparov em 1997, usou as seguintes tecnologias principais:
- Poda Alpha-Beta: Reduzir nós de busca
- Aceleração por hardware: Avaliar 200 milhões de posições por segundo
- Função de avaliação manual: Avaliação de posições projetada por especialistas
Mas mesmo usando os mesmos métodos:
- Xadrez: Olhar 12-14 jogadas requer avaliar cerca de 10^18 nós
- Go: Olhar 12 jogadas requer avaliar cerca de 10^29 nós
A diferença é de 100 trilhões de vezes. Nenhum hardware pode compensar essa diferença.
As Escolhas na Abertura São Ainda Mais Astronômicas
Na fase de abertura do Go, o fator de ramificação é ainda maior:
- Jogada 1: 361 escolhas
- Jogada 2: 360 escolhas
- Jogada 3: 359 escolhas
- ...
Apenas olhando as primeiras 10 jogadas:
É por isso que "josekis de abertura" são tão importantes — jogadores humanos precisam memorizar grandes quantidades de variações de abertura porque não podem calcular em tempo real.
A Dificuldade da Avaliação: Sem Valores Simples de Peças
Vantagem Material no Xadrez
No xadrez, avaliar posições é relativamente intuitivo:
| Peça | Valor (tradicional) |
|---|---|
| Peão | 1 |
| Cavalo | 3 |
| Bispo | 3 |
| Torre | 5 |
| Dama | 9 |
Embora a avaliação real seja mais complexa (posição, estrutura, etc.), "contar material" é um bom ponto de partida. Capturar a dama do oponente quase certamente é bom.
Go: Cada Pedra É Igual
No Go, o valor intrínseco de cada pedra é exatamente o mesmo — são apenas pedras.
O valor de uma pedra depende inteiramente de:
- Sua posição no tabuleiro
- Sua relação com outras pedras
- Seu impacto na posição geral
Isso torna a avaliação extremamente difícil.
A Abstração de Espessura e Influência
O Go tem muitos conceitos abstratos:
Espessura (Thickness)
"Espessura" refere-se a um grupo de pedras que é sólido, estável e influente. Mas "espessura" é difícil de quantificar:
- Quanto vale uma forma espessa em pontos?
- Quando usar a espessura para atacar?
- Quando a espessura se torna "forma ruim" (forma ineficiente)?
Jogadores de elite podem dizer: "Esse grupo é muito espesso, provavelmente vale cerca de 15 pontos." Mas isso é baseado em décadas de experiência intuitiva, não em cálculo preciso.
Influência (Influence)
A influência no Go refere-se ao controle potencial das pedras sobre o espaço circundante. Esse controle é "virtual" — pode se converter em território, pode desempenhar um papel em ataque e defesa, ou pode não resultar em nada.
Como avaliar valor "potencial"? Isso é extremamente difícil para computadores.
Sabor/Potencial (Aji)
"Aji" é um dos conceitos mais abstratos no Go. Refere-se às possibilidades potenciais de uma certa posição no tabuleiro.
Um grupo "morto" pode ter "valor de uso" — embora não possa ser revivido, pode criar interferência em batalhas futuras. Esse tipo de "possibilidade potencial" é quase impossível de representar numericamente.
Por Que Funções de Avaliação Manuais Falharam
No xadrez computacional antes do Deep Blue, funções de avaliação projetadas por especialistas humanos eram usadas:
Valor de avaliação = Pontuação material + Pontuação posicional + Segurança do rei + Estrutura de peões + ...
Esses itens podem ser quantificados, ter pesos ajustados, e funcionam bem.
Mas e no Go?
Pesquisadores tentaram várias características:
- Número de intersecções controladas
- "Liberdade" das pedras (número de liberdades)
- Força de conexão
- Completude da forma de olhos
- ...
Mas combinações dessas características nunca alcançaram o nível de amadores avançados.
Problema central: A avaliação de posições no Go é um problema altamente não linear e global.
O valor de uma pedra depende do estado de todo o tabuleiro, não da simples soma de características locais.
A Necessidade de Planejamento de Longo Prazo: Um Jogo de 150 Jogadas
As Três Fases Principais do Go
Um jogo padrão de Go tipicamente passa por três fases:
| Fase | Jogadas (aprox.) | Características |
|---|---|---|
| Abertura | 1-50 | Ocupar território, construir frameworks, estabelecer direção global |
| Meio de jogo | 50-200 | Batalha, ataque e defesa, equilíbrio entre local e global |
| Endgame | 200-300 | Finalização, cálculo, precisão |
Um jogo médio tem cerca de 250-300 jogadas, com as primeiras 150 determinando o resultado geral.
Abertura: Planejando 30 Jogadas à Frente
Cada jogada na fase de abertura está preparando para dezenas ou até centenas de jogadas no futuro.
Por exemplo, uma abertura "Sanrensei" (três estrelas):
. . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . .
. . . ● . . . . . ● . . . . . ● . . .
. . . . . . . . . . . . . . . . . . .
...
Essas três pedras pretas formam uma abertura "orientada à influência", com a intenção de:
- Não se apressar em cercar território
- Esperar brancas invadir e então atacar
- Ganhar território ou influência através do ataque
- Eventualmente alcançar vantagem no endgame
Este "plano" requer antecipar 50-100 jogadas no futuro. Nenhum algoritmo de busca pode ver tão longe.
Meio de Jogo: Equilíbrio Entre Local e Global
A batalha do meio de jogo é a parte mais complexa do Go. Jogadores precisam considerar em cada jogada:
- Cálculo local: Quem vai vencer esta batalha?
- Julgamento global: Vale a pena lutar aqui?
- Seleção de ordem: Onde é mais eficiente jogar primeiro?
- Decisão de abandono: Quando sacrificar pedras e mudar de direção?
Uma decisão típica de meio de jogo:
"Se eu cortar aqui, o oponente vai contra-atacar, e preciso fazer vida para um grupo, o que dará ao oponente sente para ocupar um ponto grande... no final perco cerca de 5 pontos. Mas se eu reforçar primeiro e então cortar, embora perca sente, mas..."
Este tipo de pensamento multi-camadas e multi-dimensional requer processar local e global, curto prazo e longo prazo simultaneamente.
Endgame: Cálculo Preciso e Reversões
A fase de endgame parece simples — apenas finalização. Mas na realidade:
- O "valor em pontos" de cada jogada precisa ser calculado com precisão
- A diferença entre sente e gote pode determinar a vitória
- "Ko fights" podem mudar completamente a posição
Jogadores profissionais na fase de endgame podem calcular com precisão de 0,5 pontos, e um jogo pode ser decidido por 1 ponto.
Por Que Não Conseguir Ver Longe É Fatal
Vamos fazer um cálculo simplificado:
- Um jogo médio tem 250 jogadas
- Para prever perfeitamente o resultado, teoricamente precisamos ver todas as 250 jogadas
- Mesmo se o fator de ramificação cair para 100 (fase de endgame), o espaço de busca é 100^250 ≈ 10^500
Isso está muito além da capacidade de qualquer computador.
É por isso que IA de Go deve aprender a "avaliar" posições, não apenas "calcular".
A Importância da Intuição: "Esta Jogada Parece Certa"
Como Jogadores Humanos Pensam
Quando jogadores de Go de elite descrevem seu processo de pensamento, frequentemente usam palavras como:
"Esta jogada parece certa."
"Esta forma é muito confortável."
"Aquele grupo dele tem um sabor ruim."
"Há uma sensação de perigo indescritível aqui."
Isso não é descrição poética, mas um processo cognitivo real. Jogadores humanos usam reconhecimento de padrões e julgamento intuitivo para lidar com a complexidade do Go.
Reconhecimento de Padrões: Ver o Ponto Chave em Um Segundo
Experimentos mostram que jogadores profissionais olhando para um tabuleiro (menos de 1 segundo) podem:
- Identificar áreas chave
- Descobrir possíveis "boas jogadas"
- Perceber a forma geral da posição
Esta habilidade vem do acúmulo de experiência de dezenas de milhares de jogos, formando "senso de Go".
Antes do AlphaGo, a maior dificuldade do Go computacional era não conseguir replicar essa intuição.
Descrição Matemática da Intuição
Do ponto de vista do aprendizado de máquina, a intuição humana no Go pode ser entendida como:
Um cérebro bem treinado pode, dado uma posição de tabuleiro, imediatamente produzir uma distribuição de probabilidade de cada posição ser uma "boa jogada".
Isso é exatamente o que a Policy Network precisa aprender — e isso requer redes neurais profundas.
Por Que Foi Chamado de "Santo Graal da IA"
Marcos nos Jogos de Tabuleiro
Na história da inteligência artificial, jogos de tabuleiro sempre foram marcos importantes:
| Ano | Evento | Significado |
|---|---|---|
| 1951 | Primeiro programa de damas | IA de jogos mais antiga |
| 1997 | Deep Blue derrota Kasparov | Vitória da busca por força bruta |
| 2007 | Damas completamente resolvido | Limite de jogos de informação perfeita |
| 2016 | AlphaGo derrota Lee Sedol | Vitória do aprendizado profundo |
Por Que o Go É Especial
O Go foi chamado de "Santo Graal da IA" porque combina todas as características difíceis:
| Característica | Go | Xadrez |
|---|---|---|
| Espaço de estados | 10^170 | 10^120 |
| Fator de ramificação | ~250 | ~35 |
| Jogadas médias | ~250 | ~40 |
| Dificuldade de avaliação | Extremamente alta | Média |
| Dependência de intuição | Muito alta | Alta |
Se a IA pode resolver o Go, significa que:
- Pode lidar com espaços de busca extremamente grandes
- Pode aprender avaliação abstrata
- Pode fazer planejamento de longo prazo
- Pode formar "intuição"
Essas habilidades vão muito além de "jogar jogos de tabuleiro" e são características centrais da inteligência geral.
Previsões da Academia
Antes de 2016, a previsão acadêmica de "quando a IA poderia derrotar um campeão humano de Go" era geralmente:
"Pelo menos mais 10-20 anos."
— Maioria dos pesquisadores de IA (2015)
Esta previsão foi baseada na velocidade do progresso tecnológico na época. Programas de Go estavam melhorando cerca de 1-2 dans por ano, e havia uma diferença de 18 dans para o nível de 9 dan profissional. Nesse ritmo, realmente levaria 10-20 anos.
Ninguém previu que o aprendizado profundo traria um avanço exponencial.
Correspondência com Animações
Os conceitos principais abordados neste artigo e seus números de animação:
| Número | Conceito | Correspondência Física/Matemática |
|---|---|---|
| 🎬 B2 | Explosão do espaço de estados | Matemática combinatória, crescimento exponencial |
| 🎬 B8 | Explosão combinatória | Crescimento fatorial, árvore de busca |
| 🎬 A3 | Comparação de fatores de ramificação | Teoria dos grafos, estruturas de árvore |
| 🎬 B5 | Dilema da função de avaliação | Mapeamento não linear |
Resumo dos Pontos-Chave
O Go é chamado de "Santo Graal da IA" porque combina três grandes desafios:
1. A Maldição do Espaço
- 10^170 posições possíveis, muito além do número de átomos no universo
- Fator de ramificação ~250, crescimento explosivo da árvore de busca
- Busca por força bruta é fisicamente impossível
2. A Dificuldade da Avaliação
- Cada pedra tem valor igual, sem vantagem material
- Conceitos abstratos como "espessura", "influência", "aji" são difíceis de quantificar
- Avaliação de posição é um problema altamente não linear e global
3. O Desafio do Tempo
- Um jogo tem ~250 jogadas, requerendo planejamento de longo prazo
- Decisões de abertura afetam a posição 50-100 jogadas depois
- Batalhas locais e equilíbrio global precisam ser considerados simultaneamente
É a combinação desses desafios que fez os métodos tradicionais de IA (busca por força bruta + avaliação manual) falharem completamente no Go.
E o avanço do AlphaGo foi precisamente porque usou redes neurais profundas para resolver o problema de avaliação, Busca em Árvore Monte Carlo para resolver o problema de planejamento, e aprendizado por reforço para superar os humanos.
Leitura Adicional
- Próximo artigo: Os Limites dos Métodos Tradicionais — De Minimax a MCTS, por que nenhum foi suficiente
- Detalhes técnicos: Policy Network em Detalhe — Como AlphaGo aprendeu "intuição"
- Voltar à visão geral: Análise Completa do AlphaGo — Navegação da série de artigos
Referências
- Tromp, J. (2016). "Number of legal Go positions." — Cálculo preciso do espaço de estados do Go
- Allis, L.V. (1994). "Searching for Solutions in Games and Artificial Intelligence." PhD thesis, University of Limburg. — Análise teórica da complexidade de jogos
- Müller, M. (2002). "Computer Go." Artificial Intelligence, 134(1-2), 145-179. — Revisão das primeiras pesquisas em Go computacional
- Silver, D., et al. (2016). "Mastering the game of Go with deep neural networks and tree search." Nature, 529, 484-489. — Artigo original do AlphaGo