12 janeiro, 2011 0 Comentários AUTOR: elemarjr CATEGORIAS: Sem categoria Tags:, ,

Escrevendo um Engine para Xadrez – Parte 8 – Bispo e Dama

Tempo de leitura: 2 minutos

Olá pessoal, tudo certo?

Hoje vou demonstrar como “calcular” os movimentos para bispos e damas. O bispo se move nas diagonais, nunca muda de “cor-de-casa”, e não pode “pular” peças. Uma dama combina os movimentos de uma torre e de um bispo. Essas duas peças se encaixam também na categoria de Sliding Pieces. Ou seja, peças que têm seus movimentos limitados pelo posicionamento de outras peças no tabuleiro.

O post de hoje encerra uma parte importante do projeto. Temos código suficiente para representar o posicionamento das diversas peças e os movimentos que podem executar.

Como em todo projeto, idéias foram surgindo e ajustes foram sendo feitos. O código, atualmente, apresenta alguns débitos técnicos que precisam ser resolvidos. Por isso, o próximo post deverá mostrar pequenos ajustes e refactoring.

Posts anteriores dessa série

Se está chegando agora, talvez queira ler o que já foi escrito nessa série. Considere a leitura de:

As diagonais

Até esse momento, tinhamos algumas estruturas para representar o tabuleiro. Eram elas:

  • Square representando uma “casa”;
  • Rank representando uma linha;
  • File representando uma colula.

Todas essa estruturas mantém um bitboard onde os bits ligados correspondem as “casas” que estão sendo representadas.

No post passado, utilizamos Rank e File para estabelecer condição de parada na geração do bitboard com as casas atacadas por uma torre em uma determinada posição. Para o movimento do bispo, precisaremos de duas novas estruturas representativas do tabuleiro:

  • DiagonalsNE representando todas as diagonais North-East (ex: A1/H8);
  • DiagonalsNW representando todas as diagonais North-Weast (ex: H1/A8).

O “esqueleto” do código é o seguinte:

1 public struct DiagonalNE : IBoardUnit 2 { 3 public DiagonalNE(Square square) 4 : this() 5 { 6 this.Bitmask = _Bitmasks[square]; 7 } 8 9 public ulong Bitmask 10 { 11 get; 12 private set; 13 } 14 15 public bool IsValid 16 { 17 get { return this.Bitmask > 0; } 18 } 19 20 public bool Contains(IBoardUnit bu) 21 { 22 return (this.Bitmask & bu.Bitmask) > 0; 23 } 24 25 public bool Contains(ulong board) 26 { 27 return (this.Bitmask & board) > 0; 28 } 29 30 // .. construção do bitmask 31 }

O código para DiagonalNW é idêntico. Como você pode perceber, logo no construtor recupero um bitmask de uma coleção pré-calculada (Aí está a diferença entre as duas estruturas).

Testando as diagonais

Queria escrever testes bem abrangentes para as diagonais. Optei, mas não recomendo para todos os casos, adicionar alguma lógica aos meus testes (@vquaiato não gostaria disso!).

Eis os testes para DiagonalNE:

1 [TestFixture] 2 public class DiagonalNETests 3 { 4 5 [Test] 6 public void ctor_DiagonalA1H8() 7 { 8 Square[] squares = new Square[] { 9 Squares.A1, 10 Squares.B2, 11 Squares.C3, 12 Squares.D4, 13 Squares.E5, 14 Squares.F6, 15 Squares.G7, 16 Squares.H8 17 }; 18 19 var expected = Squares.A1 | 20 Squares.B2 | 21 Squares.C3 | 22 Squares.D4 | 23 Squares.E5 | 24 Squares.F6 | 25 Squares.G7 | 26 Squares.H8; 27 28 for (int i = 0; i < squares.Length; i++) 29 { 30 var d = new DiagonalNE(squares[i]); 31 d.Bitmask.Should().Be(expected.Value); 32 } 33 } 34 35 [Test] 36 public void ctor_DiagonalA4E8() 37 { 38 Square[] squares = new Square[] { 39 Squares.A4, 40 Squares.B5, 41 Squares.C6, 42 Squares.D7, 43 Squares.E8 44 }; 45 46 var expected = Squares.A4 | 47 Squares.B5 | 48 Squares.C6 | 49 Squares.D7 | 50 Squares.E8; 51 52 for (int i = 0; i < squares.Length; i++) 53 { 54 var d = new DiagonalNE(squares[i]); 55 d.Bitmask.Should().Be(expected.Value); 56 } 57 } 58 59 [Test] 60 public void ctor_DiagonalA7B8() 61 { 62 Square[] squares = new Square[] { 63 Squares.A7, 64 Squares.B8 65 }; 66 67 var expected = Squares.A7 | 68 Squares.B8; 69 70 for (int i = 0; i < squares.Length; i++) 71 { 72 var d = new DiagonalNE(squares[i]); 73 ((Bitboard)d.Bitmask).Should().Be((Bitboard)expected.Value); 74 } 75 } 76 77 [Test] 78 public void ctor_DiagonalE1H4() 79 { 80 Square[] squares = new Square[] { 81 Squares.E1, 82 Squares.F2, 83 Squares.G3, 84 Squares.H4, 85 }; 86 87 var expected = Squares.E1 | 88 Squares.F2 | 89 Squares.G3 | 90 Squares.H4; 91 92 93 for (int i = 0; i < squares.Length; i++) 94 { 95 var d = new DiagonalNE(squares[i]); 96 d.Bitmask.Should().Be(expected.Value); 97 } 98 } 99 100 [Test] 101 public void ctor_DiagonalH1() 102 { 103 var d = new DiagonalNE(Squares.H1); 104 d.Bitmask.Should().Be(Squares.H1.Bitmask); 105 } 106 107 [Test] 108 public void ctor_DiagonalA8() 109 { 110 var d = new DiagonalNE(Squares.A8); 111 ((Bitboard)d.Bitmask).Should().Be((Bitboard)Squares.A8.Bitmask); 112 } 113 }

Em todos os testes, crio uma lista das casas (Squares) que formam uma diagonal e monto um bitboard com elas. Logo depois, crio uma “diagonal” para cada casa comparando o bitboard resultante com o gerado previamente.

Os testes para DiagonalNW seguem o mesmo raciocínio. Obviamente mudo a “direção” das diagonais. Se desejar ver o código para os testes de DiagonalNW, acesse https://github.com/ElemarJR/StrongChess.

Gerando Bitmasks para DiagonalNE e DiagonalNW

Como indiquei no “esqueleto”, faço todo o processamento de Bitmasks antecipadamente. Eis o código para geração dos bitmasks para DiagonalNE:

1 static ulong[] _Bitmasks = new ulong[64]; 2 static DiagonalNE() 3 { 4 5 for (int i = 0; i < 8; i++) 6 { 7 ulong diagonalH = 0; // A..H 8 ulong diagonalV = 0; // 1..8 9 for (int j = 0; j < 8 - i; j++) 10 { 11 diagonalH |= ((1ul << i) << (9 * j)); 12 diagonalV |= ((1ul << (i * 8)) << (9 * j)); 13 } 14 15 for (int j = 0; j < 8 - i; j++) 16 { 17 _Bitmasks[i + (j * 9)] = diagonalH; 18 _Bitmasks[(i * 8) + (j * 9)] = diagonalV; 19 } 20 } 21 }

Lindo, não?! Para cada casa, componho um bitmask correspondente a diagonal que essa casa pertence. Explicando um pouco mais:

  • diagonalH é usada para o cálculo dos bitboards que começam no Rank1 (A1, B1, C1, D1…)
  • diagonalV é usada para o cálculo dos bitboards que começam na primeira coluna (A1, A2, B1,..)
  • Cada loop for para variável i (linha 5) calcula duas diagonais;
  • O loop for j nas linhas 9 até 13 ligam os bits correspondentes a diagonal que está sendo calculada, onde;
    • para diagonalH
      • (1ul << i) liga um bit na casa de início para diagonal (A1, B1, C1, D1… conforme i);
      • << (9 * j) avança o bit uma casa “para frente” e uma para a direita (A1, B2, C3… conforme J);
      • diagonalH |= combina o bit ligado para a casa com os bits que já foram calculados.
    • para diagonalV
      • (1ul << (i * 8)) liga o bit na casa de início para diagonal (A1, A2, A3 .. conforme i).
  • O loop for j nas linhas 15 até 19 atribuem os bitboards calculados para as respectivas casas no vetor bitmask

A lógica para o cálculo de DigitalNW segue o mesmo princípio. Observe:

1 static ulong[] _Bitmasks = new ulong[64]; 2 static DiagonalNW() 3 { 4 for (int i = 7; i >= 0; i--) 5 { 6 ulong diagonalH = 0; 7 ulong diagonalV = 0; 8 for (int j = 0; j < 8 - (7 - i); j++) 9 { 10 diagonalH |= ((1ul << i) << (7 * j)); 11 diagonalV |= (((1ul << 7) << (8 * (7 - i)) << (7 * j))); 12 } 13 14 for (int j = 0; j < 8 - (7 - i); j++) 15 { 16 _Bitmasks[i + (j * 7)] = diagonalH; 17 _Bitmasks[8 * (8 - i) - 1 + (7 * j)] = diagonalV; 18 } 19 } 20 }

Entendido?!

Calculando o movimento do bispo

Esse post já está meio “grandinho” demais. Por isso, acho que basta dizer que a lógica para geração dos movimentos para o bispo é a mesma que a utilizada para geração dos movimentos da torre (consulte o post anterior para maiores detalhes).

Eis o código que gera o bitboard com os movimentos do bispo:

1 public Bitboard GetMoveBoard(Bitboard friends, Bitboard enemies) 2 { 3 Bitboard allpieces = friends | enemies; 4 5 Bitboard result = Bitboard.Empty; 6 7 var ne = this.Location.DiagonalNE; 8 var nw = this.Location.DiagonalNW; 9 10 var newSq = this.Location.Bitmask; 11 while (true) 12 { 13 newSq = newSq << 9; 14 if (!ne.Contains(newSq)) break; 15 //if (friends.Contains(newSq)) break; 16 result = result | newSq; 17 //if (enemies.Contains(newSq)) break; 18 if (allpieces.Contains(newSq)) break; 19 } 20 21 newSq = this.Location.Bitmask; 22 while (true) 23 { 24 newSq = newSq >> 9; 25 if (!ne.Contains(newSq)) break; 26 //if (friends.Contains(newSq)) break; 27 result = result | newSq; 28 //if (enemies.Contains(newSq)) break; 29 if (allpieces.Contains(newSq)) break; 30 } 31 32 newSq = this.Location.Bitmask; 33 while (true) 34 { 35 newSq = newSq << 7; 36 if (!nw.Contains(newSq)) break; 37 //if (friends.Contains(newSq)) break; 38 result = result | newSq; 39 //if (enemies.Contains(newSq)) break; 40 if (allpieces.Contains(newSq)) break; 41 } 42 43 newSq = this.Location.Bitmask; 44 while (true) 45 { 46 newSq = newSq >> 7; 47 if (!nw.Contains(newSq)) break; 48 //if (friends.Contains(newSq)) break; 49 result = result | newSq; 50 //if (enemies.Contains(newSq)) break; 51 if (allpieces.Contains(newSq)) break; 52 } 53 54 result = result & ~friends; 55 56 return result; 57 }

Da mesma forma que utilizei o Rank e o File para determinar a condição de parada nos loops para o movimento da torre, utilizei as diagonais NE e NW para condição de parada do loop para movimentos do bispo.

Consulte o arquivo Bishop.cs em https://github.com/ElemarJR/StrongChess para ver o código completo.

Calculando o movimento da dama

Sabendo calcular o movimento da torre e do bispo, é fácil calcular o movimento da Dama. Observe:

1 public Bitboard GetMoveBoard(Bitboard friends, Bitboard enemies) 2 { 3 return 4 new Bishop(this.Location).GetMoveBoard(friends, enemies) | 5 new Rook(this.Location).GetMoveBoard(friends, enemies); 6 }

O que eu faço, combino os bitboards do Bispo e da Torre.

Smiley piscando

Consulte o arquivo Queen.cs em https://github.com/ElemarJR/StrongChess para ver o código completo.

Por hoje, era isso!

Agora é pagar débitos técnicos e fazer algum refactoring.