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

Escrevendo um Engine para Xadrez – Parte 6 – O movimento dos peões

Tempo de leitura: 4 minutos

Olá pessoal, tudo certo?

Hoje pretendo demonstrar como calcular os movimentos que podem ser feitos por peões.

Calcular o movimento para os peões é um pouco mais complicado do que para cavalos e reis. É assim por algumas razões:

  1. Peões brancos e pretos se movem em direções opostas (sempre para frente);
  2. Cada peão pode avançar uma ou duas casas na sua primeira jogada;
  3. Embora “ande” sempre para frente, os peões tomam na diagonal;
  4. Peões, ao chegar na oitava casa, são promovidos.

Temos uma boa quantidade de trabalho pela frente. Vamos a ele.

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 um movimento

Quando falei sobre movimentos para o Cavalo e movimentos para o Rei, representei os movimentos retornando um bitboard com os bits correspondentes as possíveis ocupações “destino” ligados. Para a movimentação do peão, resolvi evoluir um pouco mais nosso modelo. Observe:

1 public enum MoveTypes 2 { 3 Normal, 4 Castling, 5 PawnToQueenPromotion, 6 PawnToRookPromotion, 7 PawnToKnightPromotion, 8 PawnToBishopPromotion 9 } 10 11 public struct Move 12 { 13 public Square From { get; private set; } 14 public Square To { get; private set; } 15 public MoveTypes Type { get; private set; } 16 17 public Move(Square from, Square to, MoveTypes type = MoveTypes.Normal) 18 : this() 19 { 20 this.From = from; 21 this.To = to; 22 this.Type = type; 23 } 24 25 public bool IsValid 26 { 27 get 28 { 29 if (this.From == this.To) 30 return false; 31 32 return true; 33 } 34 } 35 } 36

A idéia é bem simples. Mantenho a linha de criar objetos imutáveis. Acredito que o código seja suficientemente claro. Certo?

Peões não devem ser analisados de forma independente

O refactoring do @juanplopes trouxe um conceito importante: Cavalos são instanciados individualmente. Segui a mesma linha com o rei (que aliás, só existe um para cada lado, SEMPRE). Entretanto, com os peões isso faz pouco sentido. Se você joga Xadrez, sabe do que estou falando.

Por causa disso, iniciei um novo conceito no engine: conjuntos. Peões são analisados como conjunto e seus movimentos também são gerados em conjunto. Observe a interface que descreve conjuntos de peões:

1 public interface IPawns 2 { 3 Bitboard Bitboard { get; } 4 IEnumerable<Move> GetAllMoves( 5 Bitboard notblockers, 6 Bitboard enemies, 7 Square? enpassant 8 ); 9 10 IEnumerable<Move> GetCaptures( 11 Bitboard enemies, 12 Square? enpassant = null 13 ); 14 15 IEnumerable<Move> GetMovesOneSquareForward(); 16 IEnumerable<Move> GetMovesOneSquareForward(Bitboard notblockers); 17 IEnumerable<Move> GetMovesTwoSquaresForward(); 18 IEnumerable<Move> GetMovesTwoSquaresForward(Bitboard notblockers); 19 bool IsValid { get; } 20 }

O que essa interface apresenta:

  1. propriedade Bitboard – bitboard representando as posições onde os peões se encontram (bits ligados para posições dos peões);
  2. método GetMovesOneSquareForward – retorna uma enumeração de todos os movimentos “avança-um” válidas para os peões representados no bitboard. O parâmetro representa todas as casas não bloqueantes (ou seja, casas que não estejam ocupadas);
  3. método GetMovesTwoSquaresForward – retorna uma enumeração de todos os movimentos “avança-dois” válidas para os peões representados no bitboard (peões ainda não movimentados). O parâmetro representa todas as casas não bloqueantes (ou seja, que não estejam ocupadas);
  4. método GetCaptures – retorna todos os movimentos de captura válidos. O parâmetro enemies é um bitboard com as posições de todas as peças adversárias. Há ainda um parâmetro opcional enpassant que representa a posição para enpassant (óbvio, né?);
  5. propriedade IsValid – O conjunto é válido? Tendo mais que oito peões, ou peões na primeira linha, ou peões na última linha, não é;
  6. Método GetAllMovies – Apenas um “acumulador” dos movimentos “calculados” por GetMovesOneSquareForward, GetMovesTwoSquaresForward e GetCaptures.

Optei por fazer duas implementações para essa interface: WhitePawns e BlackPawns. Fiz isso pelas seguintes razões:

  1. Embora os dois conjuntos (peões pretos e brancos) tenham comportamentos semelhantes, se movem para lados opostos;
  2. Optei por não colocar condicionais ou parâmetros nas implementações;
    1. Para manter o tamanho da estrutura no mínimo (apenas 8 bytes do bitboard);
    2. Para remover quaisquer condicionais;
  3. Embora cenários de testes sejam semelhantes, são diferentes em função da direção.

No post, vou tratar apenas da implementação de WhitePawns. Você pode conferir BlackPawns no código-fonte, disponível em https://github.com/elemarjr/StrongChess.

Configuração inicial (posição inicial dos peões)

Nossa estrutura de peões precisa ter acelerador para gerar a configuração inicial, certo? Também acho. Criei um método estático para gerar as posições iniciais e aqui está o teste:

1 [Test] 2 public void InitialPosition() 3 { 4 var wp = WhitePawns.InitialPosition; 5 6 Bitboard expected = new Bitboard() 7 .Set(new Square("A2")) 8 .Set(new Square("B2")) 9 .Set(new Square("C2")) 10 .Set(new Square("D2")) 11 .Set(new Square("E2")) 12 .Set(new Square("F2")) 13 .Set(new Square("G2")) 14 .Set(new Square("H2")); 15 16 wp.Bitboard.Should().Be(expected); 17 }

Bacana. Eis a implementação:

1 public struct WhitePawns : IPawns 2 { 3 public Bitboard Bitboard { get; private set; } 4 5 public WhitePawns(Bitboard bitboard) 6 : this() 7 { 8 this.Bitboard = bitboard; 9 } 10 11 public static WhitePawns InitialPosition 12 { 13 get 14 { 15 return new WhitePawns(0xFFul << 8); 16 } 17 } 18 }

O método InitialPosition cria um bitboard com os bits correspondentes as posições iniciais dos peões (bits 8 até 15). Bonito, certo!

Avanço de uma casa

Já indiquei que os movimentos “avança-um” são calculados pelo método GetMovesOneSquareForward. Vamos ver os testes para esse método? Observe:

1 [Test] 2 public void GetMovesOneSquareForward_B4_ReturnsNormalB4B5() 3 { 4 var wp = new WhitePawns(new Bitboard().Set(new Square("B4"))); 5 var move = wp.GetMovesOneSquareForward().First(); 6 move.From.Should().Be(new Square("B4")); 7 move.To.Should().Be(new Square("B5")); 8 move.Type.Should().Be(MoveTypes.Normal); 9 } 10 11 [Test] 12 public void GetMovesOneSquareForward_BlockedB4_ReturnsNoMoves() 13 { 14 var wp = new WhitePawns(~(new Bitboard().Set(new Square("B4")))); 15 var moves = wp.GetMovesOneSquareForward(new Bitboard().Set(new Square("B5"))); 16 moves.Count().Should().Be(0); 17 } 18 19 [Test] 20 public void GetMovesOneSquareForward_A7_ReturnsPromotions() 21 { 22 var wp = new WhitePawns(new Bitboard().Set(new Square("A7"))); 23 var m = wp.GetMovesOneSquareForward(); 24 var moves = m.GetEnumerator(); 25 26 27 moves.MoveNext(); 28 var f1 = moves.Current; 29 f1.From.Should().Be(new Square("A7")); 30 f1.To.Should().Be(new Square("A8")); 31 f1.Type.Should().Be(MoveTypes.PawnToQueenPromotion); 32 33 moves.MoveNext(); 34 var f2 = moves.Current; 35 f2.From.Should().Be(new Square("A7")); 36 f2.To.Should().Be(new Square("A8")); 37 f2.Type.Should().Be(MoveTypes.PawnToRookPromotion); 38 39 moves.MoveNext(); 40 var f3 = moves.Current; 41 f3.From.Should().Be(new Square("A7")); 42 f3.To.Should().Be(new Square("A8")); 43 f3.Type.Should().Be(MoveTypes.PawnToBishopPromotion); 44 45 moves.MoveNext(); 46 var f4 = moves.Current; 47 f4.From.Should().Be(new Square("A7")); 48 f4.To.Should().Be(new Square("A8")); 49 f4.Type.Should().Be(MoveTypes.PawnToKnightPromotion); 50 51 m.Count().Should().Be(4); 52 }

Os testes são bem claros. Aliás, acho plenamente justificáveis os “mais que um” asserts por método de teste nesse caso. Consideração especial apenas para o último teste: considero cada “tipo” de promoção de peão como um movimento independente. Isso será importante na hora de avaliar e selecionar o movimento que será “jogado” pela engine.

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

1 public IEnumerable<Move> GetMovesOneSquareForward 2 (Bitboard notblockers) 3 { 4 Bitboard b = (this.Bitboard << 8 & notblockers); 5 return GetMoves(b, 8); 6 } 7 8 public IEnumerable<Move> GetMovesOneSquareForward() 9 { 10 return this.GetMovesOneSquareForward(Bitboard.Full); 11 } 12 13 private IEnumerable<Move> GetMoves(Bitboard b, int offsetFrom) 14 { 15 while (b != 0) 16 { 17 Square to = (Square)b.LeadingSquare; 18 Square from = to - offsetFrom; 19 b = b.Clear(to); 20 if (to >= 56) 21 { 22 yield return new Move(from, to, MoveTypes.PawnToQueenPromotion); 23 yield return new Move(from, to, MoveTypes.PawnToRookPromotion); 24 yield return new Move(from, to, MoveTypes.PawnToBishopPromotion); 25 yield return new Move(from, to, MoveTypes.PawnToKnightPromotion); 26 27 } 28 else 29 { 30 yield return new Move(from, to); 31 } 32 } 33 }

Simples e bonito! Para gerar os movimentos:

  1. avanço todos os peões uma casa (shift);
  2. removo os avanços inválidos (pelos bloqueios) fazendo um “AND” com as casas livres para os peões;
  3. Utilizou um método auxiliar para retornar todos os movimentos. Enquanto houver bits ligados no bitboard destino
    1. obtenho o bit mais alto ligado;
    2. obtenho o índice da casa de origem aplicando offset (para avanço de uma casa, 8)
    3. limpo a casa no bitboard destino ;
    4. se o índice da casa destino for maior que 56 (última linha), retorno movimentos correspondentes a promoções;
    5. se o índice for inferior a 56; retorno movimento simples.

Bonitinho, não?!

Avanço de duas casas

Nosso engine já sabe fazer “avança-um”. Agora é hora de implementar o “avança-dois”. Os testes são:

1 [Test] 2 public void GetMovesTwoSquareForward_B2_ReturnsNormalB2B4() 3 { 4 var wp = new WhitePawns(new Bitboard().Set(new Square("B2"))); 5 var moves = wp.GetMovesTwoSquaresForward(); 6 moves.Count().Should().Be(1); 7 var m = moves.First(); 8 m.From.Should().Be(new Square("B2")); 9 m.To.Should().Be(new Square("B4")); 10 m.Type.Should().Be(MoveTypes.Normal); 11 } 12 13 [Test] 14 public void GetMovesTwoSquareForward_B2C5_ReturnsNormalB2B4() 15 { 16 var wp = new WhitePawns(new Bitboard() 17 .Set(new Square("B2")) 18 .Set(new Square("C5")) 19 ); 20 var moves = wp.GetMovesTwoSquaresForward(); 21 moves.Count().Should().Be(1); 22 var m = moves.First(); 23 m.From.Should().Be(new Square("B2")); 24 m.To.Should().Be(new Square("B4")); 25 m.Type.Should().Be(MoveTypes.Normal); 26 } 27 28 [Test] 29 public void GetMovesTwoSquareForward_B2BlockedInB3_ReturnsNothing() 30 { 31 var wp = new WhitePawns(new Bitboard().Set(new Square("B2"))); 32 var blockers = new Bitboard().Set(new Square("B3")); 33 var notblockers = ~(blockers); 34 var moves = wp.GetMovesTwoSquaresForward(notblockers); 35 moves.Count().Should().Be(0); 36 } 37 38 [Test] 39 public void GetMovesTwoSquareForward_B2BlockedInB4_ReturnsNothing() 40 { 41 var wp = new WhitePawns(new Bitboard().Set(new Square("B2"))); 42 var blockers = new Bitboard().Set(new Square("B4")); 43 var notblockers = ~(blockers); 44 var moves = wp.GetMovesTwoSquaresForward(notblockers); 45 moves.Count().Should().Be(0); 46 } 47 48 [Test] 49 public void GetMovesTwoSquareForward_B3_ReturnsNothing() 50 { 51 var wp = new WhitePawns(new Bitboard().Set(new Square("B3"))); 52 var moves = wp.GetMovesTwoSquaresForward(); 53 moves.Count().Should().Be(0); 54 }

Os testes também são simples. Basicamente, verifico condições válidas, algumas inválidas e boqueios. O código para movimentar duas casas é simples. Observe:

1 public IEnumerable<Move> GetMovesTwoSquaresForward() 2 { 3 return this.GetMovesTwoSquaresForward(Bitboard.Full); 4 } 5 6 public IEnumerable<Move> GetMovesTwoSquaresForward 7 (Bitboard notblockers) 8 { 9 Bitboard b = (this.Bitboard & (new Rank(1)).Bitmask); 10 b = (b << 8) & notblockers; 11 b = (b << 8) & notblockers; 12 while (b != 0) 13 { 14 Square to = (Square)b.LeadingSquare; 15 Square from = to - 16; 16 b = b.Clear(to); 17 yield return new Move(from, to); 18 } 19 }

Basicamente,

  1. seleciono todos os peões que estejam em sua casa inicial (segunda linha);
  2. avanço todos esses peões uma casa (shift de 8);
  3. desligo os bits correspondentes as casas de bloqueio;
  4. avanço todos esses peões mais uma casa (shift de 8);
  5. desligo os bits correspondentes as casas de bloqueio;

O bitboard resultante tem todos os avanços válidos para peões brancos.

Como não preciso me preocupar com promoções, gero os retornos no próprio método (não uso o método auxiliar GetMoves). Observe que o offset que utilizei agora é 16 (duas linhas para trás).

Lindo!

Capturas

Capturas dos peões são bacanas. Eles tomam na diagonal (uma casa), podendo ser promovidos (oitava casa). Há também a regra do enpassant. Eis os testes que escrevi:

1 [Test] 2 public void GetCaptures_D4EnemiesD5C5_ReturnsNormalD4C5() 3 { 4 var wp = new WhitePawns( 5 new Bitboard().Set(new Square("D4")) 6 ); 7 8 var enemies = new Bitboard() 9 .Set(new Square("C5")) 10 .Set(new Square("D5")); 11 12 var moves = wp.GetCaptures(enemies); 13 moves.Count().Should().Be(1); 14 var move = moves.First(); 15 move.From.Should().Be(new Square("D4")); 16 move.To.Should().Be(new Square("C5")); 17 move.Type.Should().Be(MoveTypes.Normal); 18 } 19 20 [Test] 21 public void GetCaptures_D4EnemiesD5E5_ReturnsNormalD4E5() 22 { 23 var wp = new WhitePawns( 24 new Bitboard().Set(new Square("D4")) 25 ); 26 27 var enemies = new Bitboard() 28 .Set(new Square("E5")) 29 .Set(new Square("D5")); 30 31 var moves = wp.GetCaptures(enemies); 32 moves.Count().Should().Be(1); 33 var move = moves.First(); 34 move.From.Should().Be(new Square("D4")); 35 move.To.Should().Be(new Square("E5")); 36 move.Type.Should().Be(MoveTypes.Normal); 37 } 38 39 [Test] 40 public void GetCaptures_A4EnemiesB5_ReturnsNormalA4B5() 41 { 42 var wp = new WhitePawns( 43 new Bitboard().Set(new Square("A4")) 44 ); 45 46 var enemies = new Bitboard() 47 .Set(new Square("B5")); 48 49 var moves = wp.GetCaptures(enemies); 50 moves.Count().Should().Be(1); 51 var move = moves.First(); 52 move.From.Should().Be(new Square("A4")); 53 move.To.Should().Be(new Square("B5")); 54 move.Type.Should().Be(MoveTypes.Normal); 55 } 56 57 [Test] 58 public void GetCaptures_H4EnemiesG5_ReturnsNormalH4G5() 59 { 60 var wp = new WhitePawns( 61 new Bitboard().Set(new Square("H4")) 62 ); 63 64 var enemies = new Bitboard() 65 .Set(new Square("G5")); 66 67 var moves = wp.GetCaptures(enemies); 68 moves.Count().Should().Be(1); 69 var move = moves.First(); 70 move.From.Should().Be(new Square("H4")); 71 move.To.Should().Be(new Square("G5")); 72 move.Type.Should().Be(MoveTypes.Normal); 73 }

Novamente, acho que o código fala por sí. Agora, vamos a implementação:

1 public IEnumerable<Move> GetCaptures 2 (Bitboard enemies, Square? enpassant = null) 3 { 4 if (enpassant != null) 5 enemies &= new Bitboard().Set((Square)enpassant); 6 7 var bleft = (Bitboard)((Bitboard & ~(new File(0).Bitmask)) << 7); 8 bleft = bleft & enemies; 9 var bright = (Bitboard)((Bitboard & ~(new File(7).Bitmask)) << 9); 10 bright = bright & enemies; 11 12 return GetMoves(bleft, 7).Union(GetMoves(bright, 9)); 13 14 }

Algumas explicações:

  1. Se foi provida uma posição de enpassant, acrescento ela no bitboard das posições “inimigas”;
  2. Desloco todos os peões (fora os da primeira coluna [removidos pelo And com a negativa da primeira coluna]) uma casa na diagonal esquerda (shift de 7);
  3. Mantenho ligados apenas os bits correspondente a posições ocupadas com peças inimigas (And da linha 8);
  4. Desloco todos os peões (fora os da última coluna) uma casa para diagonal direita;
  5. Mantenho ligados apenas os bits correspondente a posições ocupadas com peças inimigas;
  6. Gero todos os movimentos para as casas correspondentes aos dois bitboards (para a esquerda e para a direita).

Todos os testes passam!

Por hoje, era isso.

Lembre-se de pegar o código-fonte em https://github.com/ElemarJR/StrongChess/

Smiley piscando