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

Escrevendo um Engine para Xadrez – Parte 5 – O movimento do Rei

Tempo de leitura: 3 minutos

Olá pessoal, tudo certo?

Depois de organizar a casa (refactoring do @juanplopes), é hora de avançar no desenvolvimento de nosso engine. Hoje implementaremos o cálculo de movimento do Rei.

Não serão abordados o roque, e nem serão consideradas as posições invalidadas por ataque de outras peças (rei entrando em cheque). O que vamos implementar é apenas o movimento simples do Rei (uma casa, em qualquer direçã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:

Representando o Rei

O refactoring realizado no post anterior direcionou nossa implementação para uma estrutura por peça (o cavalo, por exemplo, tem sua própria struct [arquivo Knight.cs]). O caminho mais óbvio é replicar a estrutura fundamental para o Rei. Observe:

1 public struct King : IPiece 2 { 3 public Bitboard Board { get; private set; } 4 public King(Square location) : this(location.Bitmask) 5 { 6 } 7 public King(Bitboard board) 8 : this() 9 { 10 Board = board; 11 } 12 13 public Bitboard GetMoveBoard() 14 { 15 return this.GetMoveBoard(0); 16 } 17 18 public Bitboard GetMoveBoard(Bitboard alsoAvoid) 19 { 20 throw new NotImplementedException(); 21 } 22 }

Isso nos leva a um primeiro conflito … DRY (Don´t repeat yourserf). Basicamente, essa estrutura possui a mesma interface pública e a mesma implementação que encontramos na estrutura Knight. Isso é um bad smell.. Deixemos a coisa assim, por enquanto.

O resultado que esperamos (movimentos válidos para o rei)

Já temos condições de escrever alguns testes. Então, vamos a eles. O que desejamos, por hora é detectar movimentos válidos para o rei. Observe:

1 [Test] 2 public void GetKingAttacksBitboard_A1_ReturnsA2B2B1() 3 { 4 Bitboard test = new King("A1").GetMoveBoard(); 5 6 Bitboard expected = new Bitboard(); 7 expected = expected 8 .Set(new Square("A2")) 9 .Set(new Square("B2")) 10 .Set(new Square("B1")) 11 ; 12 13 test.Should().Be(expected); 14 } 15 16 [Test] 17 public void GetKingAttacksBitboard_H8_ReturnsH7G7G8() 18 { 19 Bitboard test = new King("H8").GetMoveBoard(); 20 21 Bitboard expected = new Bitboard(); 22 expected = expected 23 .Set(new Square("H7")) 24 .Set(new Square("G7")) 25 .Set(new Square("G8")) 26 ; 27 28 test.Should().Be(expected); 29 } 30 31 [Test] 32 public void GetKingAttacksBitboard_H1_ReturnsH2G2G1() 33 { 34 Bitboard test = new King("H1").GetMoveBoard(); 35 36 Bitboard expected = new Bitboard(); 37 expected = expected 38 .Set(new Square("H2")) 39 .Set(new Square("G2")) 40 .Set(new Square("G1")) 41 ; 42 43 test.Should().Be(expected); 44 } 45 46 [Test] 47 public void GetKingAttacksBitboard_A8_ReturnsA7B7B8() 48 { 49 Bitboard test = new King("A8").GetMoveBoard(); 50 51 Bitboard expected = new Bitboard(); 52 expected = expected 53 .Set(new Square("A7")) 54 .Set(new Square("B7")) 55 .Set(new Square("B8")) 56 ; 57 58 test.Should().Be(expected); 59 }

Estes testes demonstram que, estando em um canto, o rei vai conseguir identificar seus movimentos válidos. Agora, vamos cuidar do rei em outras quatro posições criticas: nas bordas. Observe:

1 [Test] 2 public void GetKingAttacksBitboard_A4_ReturnsA3A5B3B4B5() 3 { 4 Bitboard test = new King("A4").GetMoveBoard(); 5 6 Bitboard expected = new Bitboard(); 7 expected = expected 8 .Set(new Square("A3")) 9 .Set(new Square("A5")) 10 .Set(new Square("B3")) 11 .Set(new Square("B4")) 12 .Set(new Square("B5")) 13 ; 14 15 test.Should().Be(expected); 16 } 17 18 [Test] 19 public void GetKingAttacksBitboard_H4_ReturnsH3H5G3G4G5() 20 { 21 Bitboard test = new King("H4").GetMoveBoard(); 22 23 Bitboard expected = new Bitboard(); 24 expected = expected 25 .Set(new Square("H3")) 26 .Set(new Square("H5")) 27 .Set(new Square("G3")) 28 .Set(new Square("G4")) 29 .Set(new Square("G5")) 30 ; 31 32 test.Should().Be(expected); 33 } 34 35 [Test] 36 public void GetKingAttacksBitboard_E1_ReturnsD1F1D2E2F2() 37 { 38 Bitboard test = new King("E1").GetMoveBoard(); 39 40 Bitboard expected = new Bitboard(); 41 expected = expected 42 .Set(new Square("D1")) 43 .Set(new Square("F1")) 44 .Set(new Square("D2")) 45 .Set(new Square("E2")) 46 .Set(new Square("F2")) 47 ; 48 49 test.Should().Be(expected); 50 } 51 52 [Test] 53 public void GetKingAttacksBitboard_E8_ReturnsD8F8D7E7F7() 54 { 55 Bitboard test = new King("E8").GetMoveBoard(); 56 57 Bitboard expected = new Bitboard(); 58 expected = expected 59 .Set(new Square("D8")) 60 .Set(new Square("F8")) 61 .Set(new Square("D7")) 62 .Set(new Square("E7")) 63 .Set(new Square("F7")) 64 ; 65 66 test.Should().Be(expected); 67 }

Perfeito! Agora, testar o rei em uma posição central. Observe:

1 [Test] 2 public void GetKingAttacksBitboard_E4_ReturnsD3E3F3D4F4D5E5F5() 3 { 4 Bitboard test = new King("E4").GetMoveBoard(); 5 6 Bitboard expected = new Bitboard(); 7 expected = expected 8 .Set(new Square("D3")) 9 .Set(new Square("E3")) 10 .Set(new Square("F3")) 11 .Set(new Square("D4")) 12 .Set(new Square("F4")) 13 .Set(new Square("D5")) 14 .Set(new Square("E5")) 15 .Set(new Square("F5")) 16 ; 17 18 test.Should().Be(expected); 19 }

Por fim, vamos testar a sobrecarga que remove casas ocupadas por peças amigas:

1 [Test] 2 public void GetKingAttacksBitboard_E4AndFriendsD3E3F3D4_ReturnsF4D5E5F5() 3 { 4 Bitboard friends = new Bitboard(); 5 friends = friends 6 .Set(new Square("D3")) 7 .Set(new Square("E3")) 8 .Set(new Square("F3")) 9 .Set(new Square("D4")); 10 11 Bitboard test = new King("E4").GetMoveBoard(friends); 12 13 Bitboard expected = new Bitboard(); 14 expected = expected 15 .Set(new Square("F4")) 16 .Set(new Square("D5")) 17 .Set(new Square("E5")) 18 .Set(new Square("F5")) 19 ; 20 21 test.Should().Be(expected); 22 }

Testes implementados … tudo precisa estar vermelho… Vejamos:

image

Perfeito!

Implementando o “movimento do rei”

Testes escritos. Hora de fazer a barra ficar “verde”.

A lógica que pretendo utilizar é a mesma que foi utilizada para o movimento do cavalo. “Calcular” o bitboard dos movimentos válidos partindo da posição do cavalo e aplicando offsets (Para ver a explicação deste conceito em detalhes, consulte a parte 3). Observe os offsets:

image

 

Novamente, há necessidade de checar “aberrações” em função de posição inválida. O código para cálcular todos os bitboards para todas as posições fica assim:

1 static readonly Bitboard[] _Moves = new Bitboard[64]; 2 static King() 3 { 4 int[] knightsq = new int[] { -9, -8, -7, -1, 1, 7, 8, 9 }; 5 for (Square i = 0; i < 64; i++) 6 { 7 var bboard = new Bitboard(); 8 9 for (int j = 0; j < 8; j++) 10 { 11 Square target = i + knightsq[j]; 12 if (target.IsValid && 13 target.File.DistanceFrom(i.File) <= 1 && 14 target.Rank.DistanceFrom(i.Rank) <= 1) 15 bboard = bboard.Set(target); 16 } 17 18 _Moves[i] = bboard; 19 } 20 }

Como você pode ver, bem parecido com o que já está escrito para o cavalo.

Agora, a implementação do método GetMoveBoard. Observe:

1 public Bitboard GetMoveBoard(Bitboard alsoAvoid) 2 { 3 Bitboard result = 0; 4 5 foreach (var square in Board.GetSetSquares()) 6 result = result.Set(_Moves[square]); 7 8 return result.Clear(alsoAvoid, Board); 9 }

Como você pode ver, idêntico a implementação para o cavalo … Bad, bad smells Alegre

Entretanto, nossos testes estão passando.. Por enquanto, estamos satisfeitos.

Por hoje, era isso…

Pegue o código-fonte em http://github.com/ElemarJR/StrongChess