Número de Shannon: quantas partidas de xadrez são possíveis?

O número de Shannon é frequentemente citado para ilustrar a riqueza do jogo de xadrez. É também um excelente suporte para trabalhar potências de 10, a notação científica e as ordens de grandeza, do 3.º ciclo ao secundário. Falta saber de onde vem, o que mede exatamente e o que não mede.

Número de Shannon

Estimativa prudente, cerca de 10¹²⁰, do número de partidas de xadrez possíveis, proposta pelo matemático e engenheiro americano Claude Shannon no artigo «Programming a Computer for Playing Chess», publicado em 1950 na revista Philosophical Magazine.

O número de Shannon: de onde vem o cálculo?

Claude Shannon (1916-2001) é conhecido como o fundador da teoria da informação. Em 1950, publica um dos primeiros artigos sobre a programação de um computador para jogar xadrez. Para mostrar que uma máquina não pode simplesmente calcular todas as sequências de lances, faz uma estimativa rápida:

1. Numa posição típica, há cerca de 30 lances legais. Este número mantém-se aproximadamente constante durante grande parte da partida.
2. Uma jogada das brancas seguida de uma das pretas dá, portanto, cerca de 30 × 30 = 900 possibilidades, que Shannon arredonda para 10³.
3. Uma partida típica dura cerca de 40 lances (40 lances das brancas e 40 das pretas) até à desistência de um dos jogadores.
4. O número de sequências de lances é, portanto, de cerca de (10³)⁴⁰ = 10¹²⁰.

Shannon acrescenta que uma máquina que examinasse uma variante por microssegundo levaria mais de 10⁹⁰ anos a calcular o seu primeiro lance. Conclui que um programa de xadrez deve avaliar as posições e escolher as variantes a explorar, como faz um jogador humano.

Partidas e posições: dois números diferentes

Não se deve confundir o número de partidas (sequências de lances) com o número de posições (disposições das peças no tabuleiro). Uma mesma posição pode ser atingida por milhões de partidas diferentes.

Shannon estimava o número de posições pela fórmula 64! / (32! × 8!² × 2!⁶), que conta as maneiras de dispor as 32 peças iniciais nas 64 casas; o resultado vale cerca de 4,6 × 10⁴², que arredonda para «cerca de 10⁴³». A estimativa moderna de John Tromp, (4,82 ± 0,03) × 10⁴⁴ posições legais, obtém-se de outra forma: sorteando ao acaso dois milhões de posições de um conjunto que se sabe contar, e verificando depois quais são realmente atingíveis numa partida, com a ajuda de Peter Österlund para a análise informática.

Os primeiros lances: uma contagem exata

No início da partida, pode-se contar com exatidão. As brancas têm 20 lances possíveis (16 lances de peões e 4 lances de cavalos). As pretas também. Obtém-se:

Valores recalculados por programa a partir da posição inicial (contagem de todas as sequências de lances legais).

Após apenas dois lances de cada lado, ultrapassam-se já 197 000 sequências possíveis. O fator multiplicativo aumenta depois, porque as peças saem e têm mais escolhas: é isso que justifica a hipótese de cerca de trinta lances por posição.

De onde vem a estimativa de 10¹²³?

Em 1994, o investigador neerlandês Victor Allis refez o cálculo com hipóteses diferentes: cerca de 35 lances possíveis por posição, e partidas de 80 meios-lances (40 lances de cada lado). Obtém-se 35⁸⁰. Para o escrever em potência de 10, usa-se o logaritmo decimal: 80 × log(35) ≈ 80 × 1,544 ≈ 123,5. Daí a ordem de grandeza de 10¹²³. O método é exatamente o de Shannon; só mudam os parâmetros, o que mostra quanto o resultado depende das hipóteses.

Com os parâmetros exatos de Shannon, 900⁴⁰ vale aliás cerca de 10¹¹⁸ e não 10¹²⁰: é o arredondamento de 900 para 1000 que dá o número redondo. Para uma ordem de grandeza tão gigantesca, a diferença não tem qualquer importância prática.

Como o explicar na aula

O número de Shannon é ideal para trabalhar as potências de 10, matéria do 8.º ano. Algumas sugestões:

• Escrever o número: 10¹²⁰ escreve-se com um 1 seguido de 120 zeros. Pode pedir-se que o escrevam no quadro… e medir o tempo necessário.
• Calcular com potências: (10³)⁴⁰ = 10^{3 × 40} = 10¹²⁰ é uma aplicação direta da regra (a^m)ⁿ = a^{m × n}.
• Comparar ordens de grandeza: 10¹²⁰ a dividir por 10⁸⁰ dá 10⁴⁰. Mesmo que cada átomo do Universo fosse um computador, cada um teria ainda de tratar 10⁴⁰ partidas.
• Discutir as hipóteses: porquê 30 lances por posição? porquê 40 lances por partida? O que muda com uma partida de 60 lances? (Resposta: (10³)⁶⁰ = 10¹⁸⁰.)

O número de grãos do tabuleiro de Sissa, cerca de 1,8 × 10¹⁹, parece minúsculo ao lado: comparar os dois é um bom exercício. Ver o cálculo do tabuleiro de Sissa.

Pode-se «resolver» o xadrez?

Resolver um jogo é saber com certeza que resultado (vitória das brancas, das pretas ou empate) resulta de uma partida perfeita dos dois lados. O número de Shannon mostra que não se pode fazê-lo explorando todas as partidas. Os computadores resolveram, contudo, todas as posições com poucas peças, graças a tabelas de finais. Para saber em que ponto está a questão, o Palais des Échecs perguntou-se se o xadrez poderá um dia ser resolvido.

O número de Shannon e outros grandes números do tabuleiro

O tabuleiro é uma pequena fábrica de grandes números: 2⁶⁴ − 1 grãos de Sissa, mais de 26 000 mil milhões de percursos fechados do cavalo, 92 soluções para o problema das oito damas, 204 quadrados… Encontre-os na nossa página os grandes quebra-cabeças do tabuleiro.