Fator de Ramificação & Contagem de Nós
Uma árvore de jogos modela cada sequência possível de movimentos a partir de uma posição inicial. Cada nó representa um estado do tabuleiro. Cada aresta representa um movimento legal. A estrutura da árvore determina se a busca permanece viável.
Parâmetros Principais
Fator de ramificação b: número de movimentos legais disponíveis em uma posição típica.
Profundidade d: número de plies (meio-movimentos) para buscar adiante.
Contagem de nós na profundidade d: b^d
Total de nós em todas as profundidades: 1 + b + b² + ... + b^d = (b^(d+1) − 1) / (b − 1)
Para b e d grandes, o total ≈ b^d (dominado pelo nível das folhas).
Jogo da Velha 4×4×4
A árvore de jogos completa: b ≈ 64 (quadrados legais), d = 64 (movimentos totais). Contagem de nós completa ≈ 64^64 ≈ 10^115. O universo observável contém aproximadamente 10^80 átomos. A busca por força bruta é fisicamente impossível.
Calculando o Tamanho da Árvore
Xadrez fornece números mais realistas. Fator de ramificação médio b ≈ 35. Uma busca de 6 plies (3 movimentos de cada lado) requer aproximadamente 35^6 nós.
Poda Alfa-Beta: Reduzindo o Expoente
A poda alfa-beta elimina subárvores que não podem afetar o resultado minimax. A ideia principal: se você já sabe que um ramo dá valor V, você pode podar qualquer ramo irmão cujo valor comprovadamente cai abaixo de V (para o jogador maximizador) ou acima de V (para o jogador minimizador).
Geometria do Melhor Caso
Sob ordenação ótima de movimentos (melhores movimentos pesquisados primeiro), a poda alfa-beta reduz o fator de ramificação efetivo de b para √b. A profundidade de busca efetivamente duplica para o mesmo orçamento de nós:
Busca completa: b^d nós
Melhor caso alfa-beta: b^(d/2) nós
Exemplo: b=35, d=6. Completo: 35^6 ≈ 1.84 × 10^9. Alfa-beta: 35^3 = 42.875. Fator de redução: ~43.000.
Na prática, a ordenação de movimentos é imperfeita. Redução típica: b^(d×0.75) — fator de ramificação equivalente ≈ b^0.75.
Dualidade Centro-Canto
Hamming observa uma dualidade geométrica no cubo 4×4×4: existe uma inversão que envia as 8 posições de canto para as 8 posições de centro (o cubo interno 2×2×2) & vice-versa, preservando todas as 76 linhas vencedoras.
Contando Linhas Através de uma Posição
Em um cubo 4×4×4, as posições diferem em quantas linhas vencedoras passam por elas:
Posições de canto: 7 linhas cada (4 diagonais de face, 2 linhas de aresta, 1 diagonal de espaço)
Posições de centro de aresta: 4 linhas cada
Posições de centro de face: 6 linhas cada
Posições de centro do corpo (interno 2×2×2): 7 linhas cada
A dualidade mapeia cantos (7 linhas) para centros de corpo (7 linhas). Ambos os conjuntos formam 'pontos quentes.'
Por Que Pontos Quentes Importam Geometricamente
Um jogador que controla mais posições de contagem de linhas altas controla mais linhas vencedoras potenciais. Este é um argumento geométrico direto: a maximização da cobertura de linha guia a seleção de movimento sem nenhuma busca.
Funções de Avaliação
Todo programa de jogos precisa de uma função de avaliação: uma função que mapeia estados do tabuleiro para valores numéricos (positivo = bom para o jogador maximizador, negativo = bom para o jogador minimizador). A função de avaliação fornece a condição de contorno nas folhas da árvore de busca.
Funções de Avaliação Linear
Uma função de avaliação linear atribui um peso w_i para cada característica f_i da posição:
E(posição) = w_1 × f_1 + w_2 × f_2 + ... + w_n × f_n
Para jogo da velha 4×4×4: recursos podem incluir linhas abertas controladas, posições em quadrados de contagem de linhas altas, garfos ameaçados. Para xadrez: contagem de material, controle do centro, segurança do rei, estrutura de peões.
Esta é uma função linear no espaço de características — um hiperplano em ℝ^n. Duas posições com os mesmos valores de características recebem a mesma avaliação independentemente de todas as outras diferenças. A geometria da função de avaliação determina o que o programa 'vê'.
O programa de damas de Samuel melhorou ajustando o vetor de peso w — descida de gradiente no espaço de funções de avaliação linear.
Geometria & o Limite da Formalização
A árvore de jogos tem uma estrutura geométrica limpa: crescimento exponencial na profundidade d, redutível a b^(d/2) por alfa-beta, ainda redutível restringindo a posições de alto valor (pontos quentes reduzem b efetivo). A função de avaliação define um hiperplano no espaço de características.
Tudo isto é limpo, preciso, formalmente completo. Descreve o centro do problema do jogo — a região onde a estrutura matemática fornece orientação clara.
O limite — onde mudar de aplicação de regra para exploração, quando trocar vantagem posicional por oportunidade tática, como reconhecer padrões emergentes além da função de avaliação — resiste a essa formalização. O conhecimento tácito de Hamming vive naquele limite.
A geometria permite que você calcule quanto de busca você pode se permitir. Ela não lhe diz o que procurar.