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

Escrevendo um Engine para Xadrez – Parte 7 – O movimento da torre

Tempo de leitura: 6 minutos

Olá pessoal, tudo certo?

Hoje pretendo demonstrar como “calcular” o movimento da torre.

Torre, Bispo e Dama são peças relativamente complicadas para calculo do movimento. A razão para isso é que não é fácil criar um repositório de movimentos pré-calculados pois, diferente do que acontece com as outras peças, essas têm seus movimentos limitados pelas demais colocadas no tabuleiro. Entre desenvolvedores de engines de xadrez, essas peças são chamadas de Sliding Pieces.

Existem duas técnicas principais para criação de repositórios de movimentos pré-calculados:

  • Rotated Bitboards;
  • Magic Bitboards.

Por hora, tentando manter as coisas simples, iremos ignorar essas técnicas e realizar o “cálculo das jogadas” sempre que houver uma requisição.

Posts anteriores dessa série

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

Antes de avançar, algumas melhorias de “linguagem”

O refactoring executado pelo @juanplopes (na parte 4) converteu as enumerações Squares, Files e Ranks (ver parte 1) em estruturas.

Essa decisão, permitiu a adição de algumas abstrações realmente interessantes e a considero vantajosa. Entretanto, acabou colocando um efeito colateral não muito simpático (para mim): toda vez que vou usar um Square, por exemplo, preciso usar algo como new Square(“A1”).

Para contornar isso, criei três classes estáticas: Squares, Files e Ranks. Basicamente, essas classes possuem apenas campos estáticos somente-leitura, com acesso a “construções”. Veja:

1 public static class Squares 2 { 3 public readonly static Square A1 = new Square("A1"); 4 public readonly static Square A2 = new Square("A2"); 5 public readonly static Square A3 = new Square("A3"); 6 public readonly static Square A4 = new Square("A4"); 7 public readonly static Square A5 = new Square("A5"); 8 public readonly static Square A6 = new Square("A6"); 9 public readonly static Square A7 = new Square("A7"); 10 public readonly static Square A8 = new Square("A8"); 11 12 public readonly static Square B1 = new Square("B1"); 13 public readonly static Square B2 = new Square("B2"); 14 public readonly static Square B3 = new Square("B3"); 15 16 // continua .. 17 } 18 19 public static class Ranks 20 { 21 public readonly static Rank One = new Rank(0); 22 public readonly static Rank Two = new Rank(1); 23 public readonly static Rank Three = new Rank(2); 24 public readonly static Rank Four = new Rank(3); 25 public readonly static Rank Five = new Rank(4); 26 public readonly static Rank Six = new Rank(5); 27 public readonly static Rank Seven = new Rank(6); 28 public readonly static Rank Eight = new Rank(7); 29 } 30 31 public static class Files 32 { 33 public readonly static File A = new File(0); 34 public readonly static File B = new File(1); 35 public readonly static File C = new File(2); 36 public readonly static File D = new File(3); 37 public readonly static File E = new File(4); 38 public readonly static File F = new File(5); 39 public readonly static File G = new File(6); 40 public readonly static File H = new File(7); 41 }

Agora, para me referir a casa D5, posso utilizar Squares.D5. Ao meu ver, muito mais elegante que a abordagem antiga.

Fiz outras mudanças menores, principalmente adicionando algumas sobrecargas de operadores. Mas isso pode ser conferido no código-fonte que estará disponível para download.

Definindo a torre

A torre é uma peça extremamente importante para o Xadrez. Mantendo o padrão sugerido pelo Juan, crio uma estrutura chamada Rook para representar essa peça. Observe:

1 public struct Rook : IPiece 2 { 3 public Square Location { get; private set; } 4 public Rook(Square location) 5 : this() 6 { 7 this.Location = location; 8 } 9 10 public Bitboard GetMoveBoard() 11 { 12 return GetMoveBoard(0); 13 } 14 15 public Bitboard GetMoveBoard(Bitboard alsoAvoid) 16 { 17 return GetMoveBoard(alsoAvoid, Bitboard.Empty); 18 } 19 20 public Bitboard GetMoveBoard(Bitboard friends, Bitboard enemies) 21 { 22 //.. 23 } 24 }

A novidade nessa estrutura, com relação a interface IPiece, é a sobrecarga GetMoveBoard(Bitboard, Bitboard). Onde:

  • O primeiro parâmetro é um bitboard contendo as posições de todas as peças amigas (do mesmo lado);
  • O segundo parâmetro é um bitboard contendo as posições de todas as peças inimicas (do adversário).

Esses dois parâmetros são importantes para determinar a “parada” nos deslocamentos da torre.

Os testes

Antes de escrever qualquer código de produção, escrevo alguns testes.

Primeiro, testamos o deslocamento de uma torre sozinha no tabuleiro:

1 [Test] 2 public void GetMoveBoard_RookInA1_ReturnsFileARank1ExceptA1() 3 { 4 // arrange 5 var r = new Rook(Squares.A1); 6 Bitboard expected = (Files.A | Ranks.One).Clear(Squares.A1); 7 8 // act 9 var mb = r.GetMoveBoard(); 10 11 // assert 12 mb.Should().Be(expected); 13 } 14 15 [Test] 16 public void GetMoveBoard_RookInH1_ReturnsFileHRank1ExceptH1() 17 { 18 // arrange 19 var r = new Rook(Squares.H1); 20 Bitboard expected = (Files.H | Ranks.One).Clear(Squares.H1); 21 22 // act 23 var mb = r.GetMoveBoard(); 24 25 // assert 26 mb.Should().Be(expected); 27 } 28 29 [Test] 30 public void GetMoveBoard_RookInH8_ReturnsFileHRank8ExceptH8() 31 { 32 // arrange 33 var r = new Rook(Squares.H8); 34 Bitboard expected = (Files.H | Ranks.Eight).Clear(Squares.H8); 35 36 // act 37 Bitboard mb = r.GetMoveBoard(); 38 39 // assert 40 mb.Should().Be(expected); 41 } 42 43 [Test] 44 public void GetMoveBoard_RookInD4_ReturnsFileDRank4ExceptD4() 45 { 46 // arrange 47 var r = new Rook(Squares.D4); 48 Bitboard expected = (Files.D | Ranks.Four).Clear(Squares.D4); 49 50 // act 51 Bitboard mb = r.GetMoveBoard(); 52 53 // assert 54 mb.Should().Be(expected); 55

O teste é bem simples, verifico se o bitboard retornado (com as posições possíveis), corresponde a todas as casas da coluna e linha onde a torre está, retirando a posição atual da torre.

1 [Test] 2 public void GetMoveBoard_RookInA1EnemyInA5_ReturnsFileARank1ExceptA1A6A7A8() 3 { 4 // arrange 5 var r = new Rook(Squares.A1); 6 var enemy = new Bitboard() 7 .Set(Squares.A5); 8 9 Bitboard expected = (Files.A | Ranks.One) 10 .Clear(Squares.A1) 11 .Clear(Squares.A6) 12 .Clear(Squares.A7) 13 .Clear(Squares.A8); 14 15 // act 16 var mb = r.GetMoveBoard(0, enemy); 17 18 // assert 19 mb.Should().Be(expected); 20 } 21 22 23 [Test] 24 public void GetMoveBoard_RookInA1EnemyInF1_ReturnsFileARank1ExceptA1G1H1() 25 { 26 // arrange 27 var r = new Rook(Squares.A1); 28 var enemy = new Bitboard() 29 .Set(Squares.F1); 30 31 Bitboard expected = (Files.A | Ranks.One) 32 .Clear(Squares.A1) 33 .Clear(Squares.G1) 34 .Clear(Squares.H1); 35 36 // act 37 var mb = r.GetMoveBoard(0, enemy); 38 39 // assert 40 mb.Should().Be(expected); 41 } 42 43 [Test] 44 public void GetMoveBoard_RookInH1EnemyInB1_ReturnsFileHRank1ExceptH1A1() 45 { 46 // arrange 47 var r = new Rook(Squares.H1); 48 var enemy = new Bitboard() 49 .Set(Squares.B1); 50 51 Bitboard expected = (Files.H | Ranks.One) 52 .Clear(Squares.A1) 53 .Clear(Squares.H1); 54 55 // act 56 var mb = r.GetMoveBoard(0, enemy); 57 58 // assert 59 mb.Should().Be(expected); 60 } 61 62 [Test] 63 public void GetMoveBoard_RookInD4EnemyInD2B4_ReturnsFileDRank4ExceptD4D1A4() 64 { 65 // arrange 66 var r = new Rook(Squares.D4); 67 var enemy = new Bitboard() 68 .Set(Squares.D2) 69 .Set(Squares.B4); 70 71 Bitboard expected = (Files.D | Ranks.Four) 72 .Clear(Squares.D4) 73 .Clear(Squares.D1) 74 .Clear(Squares.A4); 75 76 // act 77 var mb = r.GetMoveBoard(0, enemy); 78 79 // assert 80 mb.Should().Be(expected); 81 }

Este segundo bloco de testes é igualmente simples. Basicamente, configuro algumas peças “adversárias” no tabuleiro. Essas peças deverão ser:

  1. bloqueios para as casas que vêm “depois” delas;
  2. alvos de ataque.

Por fim, alguns testes com peças amigas:

1 [Test] 2 public void GetMoveBoard_RookInA1FriendInA5_ReturnsFileARank1ExceptA1A5A6A7A8() 3 { 4 // arrange 5 var r = new Rook(Squares.A1); 6 var friend = new Bitboard() 7 .Set(Squares.A5); 8 9 Bitboard expected = (Files.A | Ranks.One) 10 .Clear(Squares.A1) 11 .Clear(Squares.A5) 12 .Clear(Squares.A6) 13 .Clear(Squares.A7) 14 .Clear(Squares.A8); 15 16 // act 17 var mb = r.GetMoveBoard(friend, 0); 18 19 // assert 20 mb.Should().Be(expected); 21 } 22 23 24 [Test] 25 public void GetMoveBoard_RookInA1FriendInF1_ReturnsFileARank1ExceptA1F1G1H1() 26 { 27 // arrange 28 var r = new Rook(Squares.A1); 29 var friend = new Bitboard() 30 .Set(Squares.F1); 31 32 Bitboard expected = (Files.A | Ranks.One) 33 .Clear(Squares.A1) 34 .Clear(Squares.F1) 35 .Clear(Squares.G1) 36 .Clear(Squares.H1); 37 38 // act 39 var mb = r.GetMoveBoard(friend, 0); 40 41 // assert 42 mb.Should().Be(expected); 43 } 44 45 [Test] 46 public void GetMoveBoard_RookInH1FriendInB1_ReturnsFileHRank1ExceptH1A1B1() 47 { 48 // arrange 49 var r = new Rook(Squares.H1); 50 var friend = new Bitboard() 51 .Set(Squares.B1); 52 53 Bitboard expected = (Files.H | Ranks.One) 54 .Clear(Squares.A1) 55 .Clear(Squares.B1) 56 .Clear(Squares.H1); 57 58 // act 59 var mb = r.GetMoveBoard(friend, 0); 60 61 // assert 62 mb.Should().Be(expected); 63 } 64 65 [Test] 66 public void GetMoveBoard_RookInD4FriendInD2B4_ReturnsFileDRank4ExceptB4D2D4D1A4() 67 { 68 // arrange 69 var r = new Rook(Squares.D4); 70 var friend = new Bitboard() 71 .Set(Squares.D2) 72 .Set(Squares.B4); 73 74 Bitboard expected = (Files.D | Ranks.Four) 75 .Clear(Squares.D4) 76 .Clear(Squares.B4) 77 .Clear(Squares.D2) 78 .Clear(Squares.D1) 79 .Clear(Squares.A4); 80 81 // act 82 var mb = r.GetMoveBoard(friend, 0); 83 84 // assert 85 mb.Should().Be(expected); 86 }

Assim como ocorreu com peças “inimigas”, as peças amigas são bloqueios para casas que vêm “depois” das ocupadas por elas. Mais do que isso, a “casa” onde está a peça amiga também não é atingível.

Implementando o movimento da torre

O movimento da torre, sem repositórios, não é tão complicado assim de implementar. Observe:

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

Na linha 3, combino (com um OR) os dois bitboards (peças amigas e inimigas). Depois, executo quatro loops:

  1. Para testar deslocamentos “para frente” (<< 8);
  2. Para testar deslocamentos “para trás” (>> 8);
  3. Para testar deslocamentos “para a direita” (>>1);
  4. Para testar deslocamentos para a esquerda (<<1).

Simples assim!

Nos deslocamentos na “para frente” e “para trás”, utilizo como condição de parada a mudança de coluna. Nos deslocamentos “para a esquerda” e para a direita, utilizo a mudança de linha. Outra condição de parada utilizada é a “ocupação” da casa alvo.

Todas as casas visitadas são armazenadas em um bitboard chamado result.

Por fim, removo do bitboard todas as posições de peças amigas.

Simples, não!?

O commit do post de hoje está em: https://github.com/ElemarJR/StrongChess/commit/3820f14b3fbae648cb661afb8436922f1fd2efb6

Por hoje, era isso!