Escrevendo um Engine para Xadrez – Parte 1 – Bitboards

Posted on 30/12/2010 by

20


Olá pessoal, tudo certo?

Depois de algum tempo escrevendo posts sem código, começo uma série que promete “tirar o atraso”. Vou construir e publicar, aqui no blog, um engine completo para um jogo de xadrez.

Este código, naturalmente, não é trivial. Alguns elementos importantes de inteligência artificial serão necessários. Além disso, uma boa dose de matemática seria importante. A idéia é escrever um engine realmente forte, que tenha condições de competir sem “fazer feio” com engines comerciais.

Vou aproveitar essa série para mostrar um bocado sobre otimizações e ganhos de performance. Espero realmente que goste. Não deixe de comentar.

Sem mais…

Algumas enumerações…

Aqui segue um conceito fundamental: Sempre que possível, evito constantes e utilizo enumerações. Aqui escrevi algumas:


              

                1 namespace StrongChess.Model 2 { 3 public enum Squares 4 { 5 A1, B1, C1, D1, E1, F1, G1, H1, 6 A2, B2, C2, D2, E2, F2, G2, H2, 7 A3, B3, C3, D3, E3, F3, G3, H3, 8 A4, B4, C4, D4, E4, F4, G4, H4, 9 A5, B5, C5, D5, E5, F5, G5, H5, 10 A6, B6, C6, D6, E6, F6, G6, H6, 11 A7, B7, C7, D7, E7, F7, G7, H7, 12 A8, B8, C8, D8, E8, F8, G8, H8, 13 INVALID 14 } 15 16 public enum Pieces 17 { 18 Pawn, 19 Rook, 20 Knight, 21 Bishop, 22 Queen, 23 King, 24 None 25 } 26 27 public enum Sides 28 { 29 White, 30 Black, 31 Both 32 } 33 34 public enum Ranks 35 { 36 Rank1, Rank2, Rank3, Rank4, 37 Rank5, Rank6, Rank7, Rank8 38 } 39 40 public enum Files 41 { 42 FileA, FileB, FileC, FileD, 43 FileE, FileF, FileG, FileH 44 } 45 }
              

              

              

            

            
Algumas notas sobre as enumerações:

            
    
              
  • 
Squares – Identificação das “casas” do tabuleiro. Formalmente, as casas são identificadas pela coluna (A .. H) mais o número da linha (1 .. 8)

    • 
            

            

            
    
              
  • 
Pieces – Nome das peças do Xadrez (peão, torre, cavalo, bispo, rainha [dama] e rei). Utilizarei essa enumeração para identificar, quando necessário, as peças do jogo no código. none será utilizado em condições onde desejo explicitar a inexistência de uma peça (uma casa vazia);
    • 
              
  • 
Sides – Lados ou Jogadores. Convenciona-se no Xadrez chamar os lados (jogadores) de Brancas e Pretas. Both será utilizado em situações do código onde quiser fazer referência para peças/jogadas para ambos os lados;
    • 
              
  • 
Ranks – Cada uma das linhas [1..8];
    • 
              
  • 
Files – Cada uma das colunas [a .. h].
    • 
            

            
Representando o estado do tabuleiro

            
O estado do tabuleiro consiste de:

            
    
              
  1. quem lado jogar;
    2. 
              
  2. posição das diversas peças;
    3. 
              
  3. possibilidade de “en-passant”;
    4. 
              
  4. jogadas possíveis;
    5. 
              
  5. resultado do jogo [Mate para um dos lados, empate, indefinido] ;
    6. 
              
  6. etc …
    7. 
            

            
Smiley piscando

            
A representação completa do tabuleiro será assunto para os próximos posts. Por hora, me concentro em trabalhar apenas a posição das peças. Para isso, utilizarei bitboards.

            
O que é um bitboard?

            
Como você representaria as peças que estão posicionadas no tabuleiro? Quem sabe um vetor de duas dimensões table[8][8]? Até pode ser! Mas não é a melhor forma. Por hora basta saber isso.

            
Quase todos os programas de xadrez modernos utilizam uma representação inteligente chamada bitboard. Na prática, consiste da utilização de um bitarray de 64 bits. Cada bit representa uma “casa” do tabuleiro; Ou seja A1 = bit 0, A2 = bit 1, .. , H8 = bit 63. Quando há uma peça ocupando uma determinada casa, o bit correspondente está ligado (= 1). Caso a casa não esteja sendo ocupada, o bit correspondente fica desligado (= 0).

            
Todas as peças que podem estar no tabuleiro podem ter suas posições representadas por apenas 12 bitboards. Um para cada tipo de peça (rei, rainha, torre, bispo, cavalo e peões, de cada lado). Para ilustrar, consideremos os bitboards que utilizaria para representar as peças do jogo, em suas posições iniciais.

            
    
              
  • Rooks[Sides.White] – Torres brancas. Uma em A1, outra em H1. Bits 0 e 7 ligados;
    • 
              
  • Knights[Sides.White] – Cavalos brancos. Um em B1, outro em G1. Bits 1 e 6 ligados;
    • 
              
  • Bishops[Sides.White] – Bispos brancos. Um em C1, outro em F1. Bits 2 e 5 ligados;
    • 
              
  • Queens[Sides.White] – Rainha branca. Em D1. Bit 3 ligado;
    • 
              
  • Kings[Sides.White] – Rei branco. Em E1. Bit 4 ligado;
    • 
              
  • Pawns[Sides.White] – Peões brancos. De A2 até H2. Bits 8 até 15 ligados;
    • 
              
  • Rooks[Sides.Black] – Torres negras. A8 e H8. Bits 56 e 63 ligados;
    • 
              
  • Knights[Sides.Black] – Cavalos negros. B8 e G8. Bits 57 e 62 ligados;
    • 
              
  • Bishops[Sides.Black] – Bispos negros. C8 e F8. Bits 58 e 61 ligados;
    • 
              
  • Queens[Sides.Black] – Dama negra. D8. Bit 59 ligado;
    • 
              
  • Kings[Sides.Black] – Rei negro. E8. Bit 60 ligado;
    • 
              
  • Pawns[Sides.Black] – Peões negros. A7 até H7. Bits 48 até 55.
    • 
            

            
Essa é uma prática bastante elegante pois consome bem pouca memória. Entretanto, mais importante que isso, esse tipo de representação facilita “consultas” ao tabuleiro por permitir consultas binárias. Tudo por meio de operações binárias and e or. Por exemplo. Para conhecer a posição de todas as peças:

            
    
              
  • AllPieces[Sides.White] – Pawns[Sides.White] and Rooks[Sides.White] and Knights[Sides.White] and Bishops[Sides.White] and Queens[Side.White] and Kings[Sides.White];
    • 
              
  • AllPieces[Sides.Black] – Pawns[Sides.Black] and Rooks[Sides.Black] and Knights[Sides.Black] and Bishops[Sides.Black] and Queens[Side.Black] and Kings[Sides.Black];
    • 
              
  • AllPieces[Sides.Both] = AllPieces[Sides.White] and AllPieces[Sides.Black].
    • 
            

            
Um bom exemplo do “poder” dos bitboards pode ser percebido na verificação de um “peão passado”. Ou seja, um peão que não encontra “na frente” (nas casas posteriores a ocupada pelo peão, na coluna atual e nas duas adjacentes) qualquer peão adversário. Por exemplo, um peão branco em d5, será passado se não houver peão negro em c6, d6, e6, c7, d7, e7. Para checar, basta fazer um and do bitboard Pawns[Sides.Black] com um bitboard com os bits correspondentes ao que se quer verificar… Se der zero, o peão é passado.

            
Minha implementação para Bitboard

            
No engine que está sendo desenvolvido, um bitboard será representado por um Int64 (correspondente a um long).

            
Para facilitar a operação dos bitboards, criei uma classe com extension methods. Verifique:

            

            

              

              

                1 public static partial class Bitboard 2 { 3 // ...  4  public static Int64 Set 5 (this Int64 bitboard, Squares square) 6 { 7 return bitboard |  8 Bitboard.SetMasksField[(int)square]; 9 } 10 11 public static Int64 Clear 12 (this Int64 bitboard, Squares square) 13 { 14 return bitboard & 15 Bitboard.ClearMasksField[(int)square]; 16 } 17 18 public static bool IsSet 19 (this Int64 bitboard, Squares square) 20 { 21 return (bitboard & 22 Bitboard.SetMasksField[(int)square]) != 0; 23 } 24 25 public static bool IsClear 26 (this Int64 bitboard, Squares square) 27 { 28 return (bitboard & 29 Bitboard.SetMasksField[(int)square]) == 0; 30 } 31 }
              

              

              

            

            

            
Basicamente, criei facilitadores para ligar e desligar bits dos bitboards. Além disso, criei verificadores para testar se um bit está ou não ligado. Para reduzir o “custo computacional”, antecipo algum processamento calculando antecipadamente bitboards com apenas um bit ligado (para cada casa). Também criei bitboards com apenas um bit desligado (para cada casa).

            

            

              

              

                1 private static void InitializeSquareMasks() 2 { 3 for (int i = 0; i < 64; i++) 4 { 5 SetMasksField[i] =  6 (Int64)1 << i; 7  8 ClearMasksField[i] =  9 ~SetMasksField[i]; 10 } 11 }
              

              

              

            

            

            
Outros bitboards facilitadores:

            

            

              

              

                1 private static void InitializeRankMasks() 2 { 3 SetRankMasksField[0] = 255; 4 ClearRankMasksField[0] = ~255; 5 for (int i = 1; i < 8; i++) 6 { 7 SetRankMasksField[i] =  8 SetRankMasksField[i - 1] << 8; 9 ClearRankMasksField[i] = 10 ~SetRankMasksField[i - 1] << 8; 11 } 12 } 13 14 private static void InitializeSquareMasks() 15 { 16 for (int i = 0; i < 64; i++) 17 { 18 SetMasksField[i] = 19 (Int64)1 << i; 20 21 ClearMasksField[i] = 22 ~SetMasksField[i]; 23 } 24 }
              

              

              

            

            

            
São 32 bitboards. 8 ligando cada uma das colunas, 8 desligando. 8 ligando cada linha, 8 desligando. Escrevi métodos Set e Clear análogos para ligar e desligar os bits dos bitboards.

            
Agora, os métodos auxiliares para ligar e desligar colunas e linhas inteiras:

            

              

              

                1 public static Int64 Set(this Int64 bitboard, Files file) 2 { 3 return bitboard | SetFileMasksField[(int) file]; 4 } 5  6 public static Int64 Set(this Int64 bitboard, Ranks rank) 7 { 8 return bitboard | SetRankMasksField[(int)rank]; 9 } 10 11 public static Int64 Clear(this Int64 bitboard, Files file) 12 { 13 return bitboard & Bitboard.ClearFileMasksField[(int)file]; 14 } 15 16 public static Int64 Clear(this Int64 bitboard, Ranks rank) 17 { 18 return bitboard & Bitboard.ClearRankMasksField[(int)rank]; 19 } 20 21 public static bool IsClear(this Int64 bitboard, Ranks rank) 22 { 23 return (bitboard & Bitboard.SetRankMasksField[(int)rank]) == 0; 24 } 25 26 public static bool IsClear(this Int64 bitboard, Files file) 27 { 28 return (bitboard & Bitboard.SetFileMasksField[(int)file]) == 0; 29 }
              

              

              

            

            
Os testes que escrevi para Bitboard

            
Fino! Fico feliz de ter feito a opção de usar TDD na escrita desses métodos. Embora sejam métodos pequenos, todos são “complicados”. Incrível os testes que escrevi pensando serem inúteis e que revelaram falhas do meu código. Observe:

            

              

              

                1 [TestClass] 2 public class BitboardTests 3 { 4 [TestMethod] 5 public void Set_Rank2() 6 { 7 // arrange  8  Int64 bitboard = 0; 9  10 // act  11  bitboard = bitboard.Set(Ranks.Rank2); 12  13 // assert  14  Assert.IsTrue(bitboard.IsSet(Squares.A2), "a2 should be setted"); 15 Assert.IsTrue(bitboard.IsSet(Squares.B2), "b2 should be setted"); 16 Assert.IsTrue(bitboard.IsSet(Squares.C2), "c2 should be setted"); 17 Assert.IsTrue(bitboard.IsSet(Squares.D2), "d2 should be setted"); 18 Assert.IsTrue(bitboard.IsSet(Squares.E2), "e2 should be setted"); 19 Assert.IsTrue(bitboard.IsSet(Squares.F2), "f2 should be setted"); 20 Assert.IsTrue(bitboard.IsSet(Squares.G2), "g2 should be setted"); 21 Assert.IsTrue(bitboard.IsSet(Squares.H2), "h2 should be setted"); 22 } 23 [TestMethod] 24 public void IsClear_SettedRank2_Rank2ReturnsFalse() 25 { 26 // arrange  27  Int64 bitboard = 0; 28  29 // act  30  bitboard = bitboard.Set(Ranks.Rank2); 31  32 // assert  33  Assert.IsTrue(bitboard.IsClear(Ranks.Rank1), "Rank1 should be clear"); 34 Assert.IsFalse(bitboard.IsClear(Ranks.Rank2), "Rank2 should not be clear"); 35 Assert.IsTrue(bitboard.IsClear(Ranks.Rank3), "Rank3 should be clear"); 36 Assert.IsTrue(bitboard.IsClear(Ranks.Rank4), "Rank4 should be clear"); 37 Assert.IsTrue(bitboard.IsClear(Ranks.Rank5), "Rank5 should be clear"); 38 Assert.IsTrue(bitboard.IsClear(Ranks.Rank6), "Rank6 should be clear"); 39 Assert.IsTrue(bitboard.IsClear(Ranks.Rank7), "Rank7 should be clear"); 40 Assert.IsTrue(bitboard.IsClear(Ranks.Rank8), "Rank8 should be clear"); 41 } 42  43 [TestMethod] 44 public void Clear_D_SettedFileDAndE() 45 { 46 // arrange  47  Int64 bitboard = 0; 48  49 // act  50  bitboard = bitboard 51 .Set(Files.FileD) 52 .Set(Files.FileE); 53  54 bitboard = bitboard.Clear(Files.FileD); 55  56 // assert  57  Assert.IsTrue(bitboard.IsClear(Files.FileA), "A should be clear"); 58 Assert.IsTrue(bitboard.IsClear(Files.FileB), "B should be clear"); 59 Assert.IsTrue(bitboard.IsClear(Files.FileC), "C should be clear"); 60 Assert.IsTrue(bitboard.IsClear(Files.FileD), "D should be clear"); 61 Assert.IsFalse(bitboard.IsClear(Files.FileE), "E should not be clear"); 62 Assert.IsTrue(bitboard.IsClear(Files.FileF), "F should be clear"); 63 Assert.IsTrue(bitboard.IsClear(Files.FileG), "G should be clear"); 64 Assert.IsTrue(bitboard.IsClear(Files.FileH), "H should be clear"); 65 } 66  67 [TestMethod] 68 public void Clear_5_SettedRank4And5() 69 { 70 // arrange  71  Int64 bitboard = 0; 72  73 // act  74  bitboard = bitboard 75 .Set(Ranks.Rank4) 76 .Set(Ranks.Rank5); 77  78 bitboard = bitboard.Clear(Ranks.Rank5); 79  80 // assert  81  Assert.IsTrue(bitboard.IsClear(Ranks.Rank1), "1 should be clear"); 82 Assert.IsTrue(bitboard.IsClear(Ranks.Rank2), "2 should be clear"); 83 Assert.IsTrue(bitboard.IsClear(Ranks.Rank3), "3 should be clear"); 84 Assert.IsFalse(bitboard.IsClear(Ranks.Rank4), "4 should be clear"); 85 Assert.IsTrue(bitboard.IsClear(Ranks.Rank5), "5 should not be clear"); 86 Assert.IsTrue(bitboard.IsClear(Ranks.Rank6), "6 should be clear"); 87 Assert.IsTrue(bitboard.IsClear(Ranks.Rank7), "7 should be clear"); 88 Assert.IsTrue(bitboard.IsClear(Ranks.Rank8), "8 should be clear"); 89 } 90  91 [TestMethod] 92 public void Set_FileE() 93 { 94 // arrange  95  Int64 bitboard = 0; 96  97 // act  98  bitboard = bitboard.Set(Files.FileE); 99 100 // assert 101  Assert.IsTrue(bitboard.IsSet(Squares.E1), "e1 should be setted"); 102 Assert.IsTrue(bitboard.IsSet(Squares.E2), "e2 should be setted"); 103 Assert.IsTrue(bitboard.IsSet(Squares.E3), "e3 should be setted"); 104 Assert.IsTrue(bitboard.IsSet(Squares.E4), "e4 should be setted"); 105 Assert.IsTrue(bitboard.IsSet(Squares.E5), "e5 should be setted"); 106 Assert.IsTrue(bitboard.IsSet(Squares.E6), "e6 should be setted"); 107 Assert.IsTrue(bitboard.IsSet(Squares.E7), "e7 should be setted"); 108 Assert.IsTrue(bitboard.IsSet(Squares.E8), "e8 should be setted"); 109 } 110 111 [TestMethod] 112 public void Set_A1() 113 { 114 // arrange 115  Int64 bitboard = 0; 116 Int64 bitboard1; 117 Int64 bitboard2; 118 119 // act 120  bitboard1 = bitboard.Set(Squares.A1); 121 bitboard2 = bitboard1.Clear(Squares.A1); 122 123 // assert 124  Assert.AreEqual(((long)1 << (int)Squares.A1), bitboard1); 125 //Assert.AreEqual(0, bitboard2); 126  } 127 128 [TestMethod] 129 public void Clear_A1() 130 { 131 // arrange 132  Int64 bitboard = 0; 133 Int64 bitboard1; 134 Int64 bitboard2; 135 136 // act 137  bitboard1 = bitboard.Set(Squares.A1); 138 bitboard2 = bitboard1.Clear(Squares.A1); 139 140 // assert 141  Assert.AreEqual(0, bitboard2); 142 } 143 144 [TestMethod] 145 public void IsSet_SettedA1_ReturnsTrue() 146 { 147 // arrange 148  Int64 bitboard = 0; 149 Int64 bitboard1; 150 Int64 bitboard2; 151 152 // act 153  bitboard1 = bitboard.Set(Squares.A1); 154 bitboard2 = bitboard1.Clear(Squares.A1); 155 156 // assert 157  Assert.IsTrue(bitboard1.IsSet(Squares.A1)); 158 Assert.IsFalse(bitboard2.IsSet(Squares.A1)); 159 } 160 161 [TestMethod] 162 public void IsClear_SettedA1_ReturnsFalse() 163 { 164 // arrange 165  Int64 bitboard = 0; 166 Int64 bitboard1; 167 Int64 bitboard2; 168 169 // act 170  bitboard1 = bitboard.Set(Squares.A1); 171 bitboard2 = bitboard1.Clear(Squares.A1); 172 173 // assert 174  Assert.IsFalse(bitboard1.IsClear(Squares.A1), "Should return False!"); 175 Assert.IsTrue(bitboard2.IsClear(Squares.A1), "Should return true!"); 176 } 177 178 [TestMethod] 179 public void Set_F5() 180 { 181 // arrange 182  Int64 bitboard = 0; 183 Int64 bitboard1; 184 Int64 bitboard2; 185 186 // act 187  bitboard1 = bitboard.Set(Squares.F5); 188 bitboard2 = bitboard1.Clear(Squares.F5); 189 190 // assert 191  Assert.AreEqual(((long)1 << (int)Squares.F5), bitboard1); 192 //Assert.AreEqual(0, bitboard2); 193  } 194 195 [TestMethod] 196 public void Clear_F5() 197 { 198 // arrange 199  Int64 bitboard = 0; 200 Int64 bitboard1; 201 Int64 bitboard2; 202 203 // act 204  bitboard1 = bitboard.Set(Squares.F5); 205 bitboard2 = bitboard1.Clear(Squares.F5); 206 207 // assert 208 //Assert.AreEqual(((long)1 << (int)Squares.F5), bitboard1); 209  Assert.AreEqual(0, bitboard2); 210 } 211 212 [TestMethod] 213 public void IsSet_SettedF5_ReturnsTrue() 214 { 215 // arrange 216  Int64 bitboard = 0; 217 Int64 bitboard1; 218 Int64 bitboard2; 219 220 // act 221  bitboard1 = bitboard.Set(Squares.F5); 222 bitboard2 = bitboard1.Clear(Squares.F5); 223 224 // assert 225  Assert.IsTrue(bitboard1.IsSet(Squares.F5)); 226 Assert.IsFalse(bitboard2.IsSet(Squares.F5)); 227 } 228 229 [TestMethod] 230 public void IsClear_SettedF5_ReturnsFalse() 231 { 232 // arrange 233  Int64 bitboard = 0; 234 Int64 bitboard1; 235 Int64 bitboard2; 236 237 // act 238  bitboard1 = bitboard.Set(Squares.F5); 239 bitboard2 = bitboard1.Clear(Squares.F5); 240 241 // assert 242  Assert.IsFalse(bitboard1.IsClear(Squares.F5)); 243 Assert.IsTrue(bitboard2.IsClear(Squares.F5)); 244 } 245 246 [TestMethod] 247 public void IsClear_A1_SettedF5A1ClearingA1_ReturnsTrue() 248 { 249 // arrange 250  Int64 bitboard = 0; 251 Int64 bitboard1; 252 Int64 bitboard2; 253 254 // act 255  bitboard1 = bitboard 256 .Set(Squares.F5) 257 .Set(Squares.A1); 258 259 bitboard2 = bitboard1.Clear(Squares.A1); 260 261 // assert 262  Assert.IsFalse(bitboard1.IsClear(Squares.A1)); 263 Assert.IsTrue(bitboard2.IsClear(Squares.A1)); 264 } 265 266 [TestMethod] 267 public void IsClear_F5_SettedF5A1ClearingA1_ReturnsFalse() 268 { 269 // arrange 270  Int64 bitboard = 0; 271 Int64 bitboard1; 272 Int64 bitboard2; 273 274 // act 275  bitboard1 = bitboard 276 .Set(Squares.F5) 277 .Set(Squares.A1); 278 279 bitboard2 = bitboard1.Clear(Squares.A1); 280 281 // assert 282  Assert.IsFalse(bitboard1.IsClear(Squares.F5)); 283 Assert.IsFalse(bitboard2.IsClear(Squares.F5)); 284 } 285 286 public void Dummy() 287 { 288 Int64[] Rooks = new Int64[2]; 289 290 Rooks[(int)Sides.White] = ((Int64)0) 291 .Set(Squares.A1) 292 .Set(Squares.A8); 293 } 294 }
              

              

              

            

            
Por hoje, era isso!

            
Smiley piscando

            
            

              Etiquetado:, , 
            

            

              Posted in: Post