1
boardgamestheory
5 min de leitura ·

Solução Matemática do Jogo de Damas (8x8): Bitboards de 32 Bits e Bases de Finais Chinook

Em 2007, a equipe de cientistas da computação liderada por Jonathan Schaeffer na Universidade de Alberta publicou na revista Science um dos maiores marcos da inteligência artificial: a resolução matemática definitiva do jogo de Damas (English draughts / checkers 8x8). Após quase duas décadas de computação distribuída, provou-se rigorosamente que o jogo perfeito por ambos os lados conduz invariavelmente ao empate (draw).

O espaço de estados do jogo de damas possui aproximadamente 5 × 10²⁰ (quinhentos quintilhões) de posições legais. A demonstração desse resultado exigiu a união de duas abordagens computacionais de alta performance: Tabelas de Finais Retrógradas (Endgame Tablebases) calculadas exaustivamente até 10 peças e Busca Heurística em Árvore com Poda Seletiva para conectar a posição inicial às bases resolvidas.

Neste artigo, detalhamos como estruturar um motor de damas de alta performance utilizando Bitboards de 32 bits e analisamos a matemática por trás da análise retrógrada.

1. Topologia de 32 Bits: A Geometria Compacta do Tabuleiro

No jogo de damas internacional e inglês, todas as peças movem-se exclusivamente nas casas escuras do tabuleiro 8x8. Isso significa que exatamente 32 casas participam da dinâmica do jogo. Em vez de desperdiçar um inteiro de 64 bits ou uma matriz 8x8, um estado de damas pode ser encapsulado de forma ideal em registradores de 32 bits (uint32_t).

A numeração canônica das casas (1 a 32) mapeia diretamente para os índices de bits 0 a 31:

  Linha 7:     .  28   .  29   .  30   .  31
  Linha 6:    24   .  25   .  26   .  27   .
  Linha 5:     .  20   .  21   .  22   .  23
  Linha 4:    16   .  17   .  18   .  19   .
  Linha 3:     .  12   .  13   .  14   .  15
  Linha 2:     8   .   9   .  10   .  11   .
  Linha 1:     .   4   .   5   .   6   .   7
  Linha 0:     0   .   1   .   2   .   3   .

A estrutura de dados completa para representar um estado exige apenas 4 inteiros de 32 bits:

typedef struct {
    uint32_t black_men;    // Peças simples pretas (movem-se para frente)
    uint32_t black_kings;  // Damas pretas (movem-se em ambas as direções)
    uint32_t white_men;    // Peças simples brancas (movem-se para trás)
    uint32_t white_kings;  // Damas brancas
} CheckersState;

#define BLACK_PIECES(s) ((s)->black_men | (s)->black_kings)
#define WHITE_PIECES(s) ((s)->white_men | (s)->white_kings)
#define ALL_PIECES(s)   (BLACK_PIECES(s) | WHITE_PIECES(s))
#define EMPTY_SQUARES(s) (~ALL_PIECES(s))

2. Geração Paralela de Lances via Deslocamento de Bits (Bitshifts)

Na geometria de 32 casas alternadas, os deslocamentos diagonais dependem da paridade da linha (se a linha é par ou ímpar). Uma diagonal para a frente-esquerda corresponde a um deslocamento de 4 bits em linhas pares e 3 bits em linhas ímpares; frente-direita corresponde a 5 bits e 4 bits, respectivamente.

Para unificar as operações e eliminar branches condicionais caros, utiliza-se o deslocamento mascarado:

// Máscaras de borda para evitar saltos ilegais para o lado oposto do tabuleiro
#define MASK_LEFT_EDGE  0x0E0E0E0EU
#define MASK_RIGHT_EDGE 0x70707070U

// Lances simples de avanço para pretas (linhas pares / ímpares combinadas)
static inline uint32_t black_forward_left(uint32_t b, uint32_t empty) {
    // Avanço diagonal esquerdo em um único passo
    uint32_t moves_even = (b & 0x07070707U) << 4;
    uint32_t moves_odd  = (b & 0x70707070U) << 3;
    return (moves_even | moves_odd) & empty;
}

Detecção de Capturas Obrigatórias

Uma regra fundamental e intransigente do jogo de damas é a obrigatoriedade de captura. Se um jogador puder capturar uma ou mais peças adversárias, lances normais de deslocamento simples tornam-se estritamente ilegais.

Com bitboards, a existência de saltos válidos de captura pode ser computada em menos de 10 instruções assembly por meio de operações lógicas combinadas:

uint32_t find_jumpers(uint32_t pieces, uint32_t opponents, uint32_t empty) {
    // Peças que podem saltar sobre um adversário para a diagonal direita
    uint32_t over_diag = (pieces << 4) & opponents;
    uint32_t landing   = (over_diag << 4) & empty;
    return (landing >> 8) & pieces;
}

Se o bitboard resultante for diferente de zero (jumpers != 0), o gerador de lances ignora imediatamente toda a geração de passos simples, podando 80% do espaço de ramificação na própria raiz do nó de busca.

3. Análise Retrógrada e a Construção do Endgame Chinook

A pedra angular da resolução do Chinook foi o cálculo de Endgame Tablebases através de Retrograde Value Iteration. Em vez de simular partidas a partir da abertura, a análise retrógrada inicia nos estados terminais finais conhecidos (onde um dos jogadores já perdeu todas as peças ou está bloqueado) e propaga o valor da teoria dos jogos (Game-Theoretic Value: Vitória, Derrota ou Empate) em direção aos estados precursores.

Para cada configuração contendo N peças (onde N variou de 1 até 10):

  1. Indexação Perfeita: Mapeamento bijetivo entre as posições das N peças no tabuleiro e um índice inteiro contíguo.
  2. Classificação Terminal: Atribui-se o valor de DERROTA a posições onde o jogador da vez não possui lances legais.
  3. Propagação de Lances:
    • Se uma posição tem pelo menos um lance que leva a uma DERROTA do oponente, essa posição é marcada como VITÓRIA no menor número de passos (DTC - Distance to Conversion ou DTM - Distance to Mate).
    • Se todos os lances possíveis a partir de uma posição levam a uma VITÓRIA do oponente, essa posição é marcada como DERROTA.
    • Posições que permanecem sem convergência após a estabilização de todos os ciclos são marcadas como EMPATE (Draw).

O banco de dados de 10 peças do Chinook totalizou 39.271.258.882.814 (39 trilhões) de estados, compactados de forma eficiente para acesso direto em tempo O(1).

4. Conexão com Motores Modernos e Aprendizado Prático

Enquanto o Chinook foi projetado como uma superestrutura acadêmica em clusters de computação maciça, os princípios de bitboards compactos e avaliação posicional exata fundamentam hoje os melhores engines acessíveis a desenvolvedores e jogadores.

Para aqueles interessados em vivenciar a aplicação prática dessas regras táticas e no estudo aprofundado de estratégias de damas clássicas em plataformas contemporâneas, o ambiente de jogo e análise de damas do Checkers Crown no Boardgammon oferece um exemplo excelente de renderização reativa limpa e aplicação estrita das regras combinatórias e de captura obrigatória.

O estudo das damas 8x8 permanece como um dos maiores triunfos da inteligência artificial simbólica e da teoria combinatória de jogos, provando que mesmo espaços de busca astronômicos podem ser domados quando a matemática e a arquitetura de baixo nível operam em harmonia.

Carregando publicação patrocinada...