Bitboards

Bitboard é uma representação de tabuleiro peça-cêntrica, ou seja, voltada às peças e não às posições. Isso quer dizer que é rápido olhar para a peça e descobrir onde ela está no tabuleiro, mas é custoso olhar para a posição e descobrir qual peça se encontra nela.

Os bitboards são muito bons para representar tabuleiros de xadrez porque os inteiros de 64 bits tem exatamente 64 posições, exatamente como um tabuleiro convencional de 8x8. Cada um dos bits do inteiro representa uma posição, e cada peça tem um ou mais bits setados.

Traduzindo... vamos imaginar um tabuleiro hipotético de 2x2, com quatro posições possíveis. Nesse tabuleiro, as posições seriam representadas da seguinte forma:



0b0000 -> nenhuma posição, peça não se encontra no tabuleiro
0b0001 -> posição A1
0b0010 -> posição B1
0b0100 -> posição A2
0b1000 -> posição B2

Por exemplo, se as brancas só tem um peão, e ele estiver na posição A1, vamos ter um inteiro chamado iPeaoBrancas com o valor 0b0001 (ou, simplesmente, 1). Se as brancas tiverem um peão em A1 e um peão em A2, então iPeaoBrancas vai ter o valor 0b0011 (ou 3 em decimal). Uma observação interessante sobre os bitboards é que cada posição corresponde a uma potência de 2 (2 elevado a 0, 2 elevado a 1, 2 elevado a 2, etc). Se você numerar as casas do tabuleiro de 0 a 3, no nosso caso, ou de 0 a 63 no tabuleiro real, vai notar que o bitboard correspondente a cada casa vai ser 2 elevado ao número da casa.

Qual é a vantagem disso? Simples. Imagine que você queira testar se o peão branco pode capturar alguma peça. Imagine que, estando na posição A1, o peão branco pode capturar uma peça na posição B2 e, estando na posição B1, ele pode capturar peças na posição A2. No caso de estar na linha 2, o peão não poderá fazer nenhuma captura.

No nosso exemplo pra lá de simples, você poderia testar se existe um peão em A1 e uma peça inimiga em B2; depois testaria se existe um peão em B1 e uma peça inimiga em A2. Mas, no caso de um tabuleiro 8x8, os testes ficariam muito mais complicados. Então vamos definir uma forma genérica de dar a mesma resposta, e que seja muito mais rápida.

Para fazer isso, em primeiro lugar temos que definir algumas constantes que irão nos ajudar mais para frente. No nosso tabuleiro imaginário, temos apenas duas linhas e duas colunas; devemos definir constantes para as quatro possibilidades.

Começando com a linha 1: em quais posições uma peça pode estar para estar na linha 1? Resposta óbvia: A1 e B1. Então, a constante da coluna 1 vai ser A1 e B1 ao mesmo tempo, ou seja, 0b0011. Para a linha 2, seria A2 e B2 ao mesmo tempo, ou 0b1100. Para as colunas, o raciocínio é parecido. No final, ficaríamos com:

LINHA_1 0b0011
LINHA_2 0b1100
COLUN_A 0b0101
COLUN_B 0b1010

Agora conseguimos mostrar o verdadeiro valor dos bitboards. Podemos fazer operações lógicas bit-a-bit e os inteiros irão responder as nossas perguntas. Por exemplo, se você quiser saber quais são os peões brancos que estão na linha 1, é só fazer:

iPeoesLinhaA = iPeoesBrancos & LINHA_1

Aí começa a mágica. O operador usado na linha do exemplo é o & bit-a-bit, ou seja, ele faz uma 'E' de cada um dos bits entre as duas variáveis. Para exemplificar, vamos pegar uma situação em que existam dois peões brancos; um em A1 e um em B2. Aí, vamos querer saber quais peões estão na linha 1. Nesse caso, o bitboard iPeoesBrancos será:

iPeoesBrancos = 0b1001

Ou, no tabuleiro:



E a operação & bit-a-bit irá realizar o seguinte:


iPeoesBrancos -> 0b1001
LINHA_1 ->       0b0011
& bit-a-bit -----------
Resultado ->     0b0001

Como pode ser visto, o resultado está correto; Só o peão localizado em A1 está na linha 1.

O & bit-a-bit funciona como uma máscara sobre o tabuleiro que só mostra a posição que queremos olhar. Imagine que o tabuleiro está coberto com um pano preto. Em algumas posições, o pano está cortado e você consegue observar aquela parte do tabuleiro. No nosso caso, a parte 'recortada' do pano é a linha 1, conforme a figura:



No próximo post, vou colocar mais operações bit-a-bit e como elas se juntam para dar as respostas certas para a engine de xadrez.