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

Escrevendo um Engine para Xadrez – Parte 3 – O movimento do cavalo

Tempo de leitura: 6 minutos

Olá pessoal, tudo certo?

Depois de introduzirmos o conceito de bitboards (parte 1) e enfatizarmos a relevância de antecipar processamento (parte 2), começamos a trabalhar com um dos elementos cruciais de uma boa engine de xadrez: a geração dos movimentos válidos para uma dada posição.

Esse assunto é crítico pois está envolvido em todas as operações do jogo. Para cada posição a analisar, é necessário gerar as alternativas válidas para aquela posição. Por isso, a performance dessas rotinas está diretamente assoicada a performance do engine como um todo.

Hoje, trataremos especificamente da geração de movimentos para o cavalo.

Cavalos e o bitboard

Retomando o conceito de bitboard, trata-se de um vetor contínuo de 64 posições. Cada uma representando uma posição do tabuleiro. Observe:

image

Como você já viu nas partes anteriores, representamos esse “bitboard” em um UInt64. Ou seja, um bit para cada posição do tabuleiro. Essa estrutura de dados é muito flexível pois permite representar, por exemplo, toda a ocupação do tabuleiro com um mapa de bits, para cada tipo de peça e peões, para as duas cores (Peão, Torre, Cavalo, Bispo, Rei e Rainha; Brancas e Negras), totalizando 12 bitboards.

Na posição inicial, com cavalos brancos em B1 (índice 1) e G1 (indice 6), temos um bitboard com o segundo e o sétimo bits ligados e com os demais desligados. Colocando isso em um UInt64, diríamos que Knights[Sides.White]=66 (introduzo as enumerações na parte 1).

Bom, agora consideremos a construção de bitboards que indiquem os movimentos possíveis para um cavalo em determina posição. Considere:

Se o cavalo estiver em A1, este poderá se mover para C2 ou para B3.

image

 

Se o cavalo estiver em E4, poderá se mover para D2, F2, G3, G5, F6, D6, C5 e C3.

image

 

Os bitboards são extremamente funcionais e rápidos. Considere que tenhamos os bitboards de movimento para um cavalo em A1 e para um cavalo em E4 (os indicados acima, com as cazas “laranjas” ligadas) e desejássemos saber quais são toda as casas “atacadas” por cavalos. Bastaria uma operação “OR” entre os dois bitboards.

Se tivéssemos um bitboard indicando as posições das peças adversárias, poderíamos saber facilmente quais estariam “ameaçadas”, procedendo um “AND” entre o bitboard das casas atacadas pelos cavalos e o bitboard das casas ocupadas por peças adversárias.

As possibilidades são muitas!

Interface pública para os movimentos do cavalo

Já vimos o poder dos bitboards e quanto relevantes eles podem ser para calcular movimento das peças. Começando a pensar em implementação, considerei os seguintes métodos estáticos (aqui, acho que caberia melhor o termo “funções”).

1 public static UInt64 2 GetKnightAttacksBitboard(Squares square) 3 { /* ... */ } 4 5 public static UInt64 6 GetKnightAttacksBitboard(UInt64 knightsBitboard) 7 { /* ... */ } 8 9 public static UInt64 10 GetKnightAttacksBitboard(UInt64 knightsBitboard, UInt64 friends) 11 { /* ... */ }

Onde:

  • GetKnightAttacksBitboard(Squares) retorna o bitboard com as casas atacadas por um cavalo na “casa” (square) especificada.
  • GetKnightAttacksBitboard(UInt64) retorna o bitboard com as casas atacadas pelos cavalos nas “casas”especificadas no bitboard de entrada, removendo as casas ocupadas por outros cavalos.
  • GetKnightAttacksBitboard(UInt64, UInt64) retorna o bitboard com as casas atacadas pelos cavalos nas “casas” especificadas no bitboard de entrada, removendo as casas ocupadas por peças e peões amigos [movimentos em potencial].

Os primeiros testes

Já temos uma interface pública, agora precisamos testar sua eficiência. Quando falo em testes, me refiro a dois aspectos:

  1. Testar a facilidade de uso de interface. Ou seja, quanto a interface é prática de utilizar e quanto facilita o código;
  2. Obviamente, testar as respostas dos métodos (ainda prefiro funções aqui).

Os testes que escrevi para GetKnightAttacksBitboard(Squares) foram:

1 [TestMethod] 2 public void GetKnightAttacksBitboad_A1_ReturnsC2andB3() 3 { 4 UInt64 test = Bitboard.GetKnightAttacksBitboard 5 (Squares.A1); 6 7 UInt64 expected = 0; 8 expected = expected 9 .Set(Squares.B3) 10 .Set(Squares.C2); 11 12 Assert.AreEqual(expected, test); 13 } 14 15 [TestMethod] 16 public void GetKnightAttacksBitboad_H1_ReturnsF2andG3() 17 { 18 UInt64 test = Bitboard.GetKnightAttacksBitboard 19 (Squares.H1); 20 21 UInt64 expected = 0; 22 expected = expected 23 .Set(Squares.G3) 24 .Set(Squares.F2); 25 26 Assert.AreEqual(expected, test); 27 } 28 29 [TestMethod] 30 public void GetKnightAttacksBitboad_H8_ReturnsF7andG6() 31 { 32 UInt64 test = Bitboard.GetKnightAttacksBitboard 33 (Squares.H8); 34 35 UInt64 expected = 0; 36 expected = expected 37 .Set(Squares.F7) 38 .Set(Squares.G6); 39 40 Assert.AreEqual(expected, test); 41 } 42 43 [TestMethod] 44 public void GetKnightAttacksBitboad_A8_ReturnsC7andB6() 45 { 46 UInt64 test = Bitboard.GetKnightAttacksBitboard 47 (Squares.A8); 48 49 UInt64 expected = 0; 50 expected = expected 51 .Set(Squares.C7) 52 .Set(Squares.B6); 53 54 Assert.AreEqual(expected, test); 55 } 56 57 [TestMethod] 58 public void GetKnightAttacksBitboad_B1_ReturnsA3andC3andD2() 59 { 60 UInt64 test = Bitboard.GetKnightAttacksBitboard 61 (Squares.B1); 62 63 UInt64 expected = 0; 64 expected = expected 65 .Set(Squares.A3) 66 .Set(Squares.C3) 67 .Set(Squares.D2); 68 69 Assert.AreEqual(expected, test); 70 } 71 72 [TestMethod] 73 public void GetKnightAttacksBitboad_G8_ReturnsH6andF6andE7() 74 { 75 UInt64 test = Bitboard.GetKnightAttacksBitboard 76 (Squares.G8); 77 78 Assert.IsTrue(test.IsSet(Squares.H6), "H6?!"); 79 Assert.IsTrue(test.IsSet(Squares.F6), "F6?!"); 80 Assert.IsTrue(test.IsSet(Squares.E7), "E7?!"); 81 UInt64 expected = 0; 82 expected = expected 83 .Set(Squares.H6) 84 .Set(Squares.F6) 85 .Set(Squares.E7); 86 87 Assert.AreEqual(expected, test); 88 } 89 90 [TestMethod] 91 public void GetKnightAttacksBitboad_E4_ReturnsF6G5G3F2D2C3C5D6() 92 { 93 UInt64 test = Bitboard.GetKnightAttacksBitboard 94 (Squares.E4); 95 96 UInt64 expected = 0; 97 expected = expected 98 .Set(Squares.F6) 99 .Set(Squares.G5) 100 .Set(Squares.G3) 101 .Set(Squares.F2) 102 .Set(Squares.D2) 103 .Set(Squares.C3) 104 .Set(Squares.C5) 105 .Set(Squares.D6); 106 107 Assert.AreEqual(expected, test); 108 } 109 110 [TestMethod] 111 public void GetKnightAttacksBitboard_H4_ReturnsF3G2G6F5() 112 { 113 UInt64 test = Bitboard.GetKnightAttacksBitboard 114 (Squares.H4); 115 116 UInt64 expected = 0; 117 expected = expected 118 .Set(Squares.F3) 119 .Set(Squares.G2) 120 .Set(Squares.G6) 121 .Set(Squares.F5); 122 123 Assert.AreEqual(expected, test); 124 }

Basicamente, crio um bitboard que espero como resposta e faço as comparações. Esse não é um teste exaustivo. O que fiz foi selecionar algumas casas que considero chave.

Importante deixar claro que, aqui, parti para o desenvolvimento da implementação para esse método (aqui meu SUT). Considero tedioso demais escrever todos os testes, para todos os métodos, antes de começar a escrever algum código. Fico ansioso e desanimo …

Pensemos em alguma lógica …

Calculando o salto do cavalo

Como poderíamos “programar” o salto do cavalo em um bitboard. O processo em geral é simples: usando offsets.

Voltemos ao bitboard das casas “atacadas” por um cavalo em E4. São offsets os deslocamentos de E4 até cada uma das casas sombreadas. Observe:

image

 

Se desejarmos saber os “bits ligados” para um cavalo em D4 (27), basta aplicar os offsets e teremos B3 (-10), C2 (-17), E2 (-15), F3 (-6), F5 (+10), E6 (+17), C6 (+15) e B5 (+6). Lindo!

Obviamente, há situações onde a coisa não funciona tão bem! Considere o cavalo em B4 (25). Aplicando os deslocamentos (offsets) teríamos:

image

Obviamente, H2 e H4 não são destinos válidos ao cavalo. Torna-se necessária uma verificação adicional (distância em colunas [Files] e linhas [Ranks] não ser maior que 2).

Esse é o raciocínio que utilizei para “gerar” os bitboards.

Pensando em pré-processamento

Executar todas as operações matemáticas e comparações toda vez que desejar conhecer os movimentos de um cavalo é uma operação “burra”. Digo isso porque sacrifica tempo importante do processador fazendo com que ele execute operações que poderiam ser antecipadas.

Com isso em mente, resolvi gerar todos os bitboards representando “ataques”, um para cada casa do tabuleiro, armazenando-os em um vetor com 64 posições (uma para cada casa). O código é bem simples. Observe:

1 static readonly UInt64[] KnightAttacksBitboardsField = 2 new UInt64[64]; 3 4 static void InitializeKinightAttacksBitboards() 5 { 6 int [] knightsq = new int[] 7 { -17, -15, -10, -6, 6, 10, 15, 17 }; 8 for (int i = 0; i < 64; i++) 9 { 10 UInt64 bboard = 0; 11 int source_rank = i / 8; 12 int source_file = i % 8; 13 14 for (int j = 0; j < 8; j++) 15 { 16 int target = i + knightsq[j]; 17 if (target >= 0 && target <= 63) 18 { 19 int target_rank = target / 8; 20 int target_file = target % 8; 21 if (Math.Abs(target_file - source_file) <= 2 22 && Math.Abs(target_rank - source_rank) <= 2) 23 bboard |= SetMasksField[target]; 24 } 25 } 26 KnightAttacksBitboardsField[i] = bboard; 27 } 28 }

A lógica que utilizei já foi explicada. Nas linhas 6 e 7 inicio um pequeno vetor com os deslocamentos (offsets) que desejo considerar. Para cada casa:

  1. inicio um bitboard vazio (um UInt64 setado para 0);
  2. calculo a linha (rank) e coluna (file) correspondente a casa sendo processada;
  3. aplico cada um dos offsets, verificando se são válidos;
  4. acumulo no bitboard (com um OR) o bitboard correspondente a casa resultante da aplicação do offset;
  5. armazendo o bitboard na casa correspondente.

Essa operação é feita apenas uma vez. Depois disso, a implementação do método consiste simplesmente em retornar um bitboard já processado. Observe:

1 public static UInt64 2 GetKnightAttacksBitboard(Squares square) 3 { 4 return KnightAttacksBitboardsField[(int)square]; 5 }

Não dá para ser mais rápido!

Testes para mais de um cavalo (considerando casas amigas)

Recuperar o bitboard das casas atacadas por um cavalo em uma determinada posição ficou bem simples. Agora vamos considerar os outros dois métodos de nossa interface pública.

Copiei e modifiquei os testes que já havia escrito para passar, no lugar de um Square, um bitboard (Teria que obter a mesma resposta). Além disso, escrevi apenas dois testes específicos (Honestamente, não senti necessidade para mais que isso). Eis os testes novos:

1 [TestMethod] 2 public void GetKnightAttacksBitboard_B1C3Bitboard_ReturnsD2A3A2A4B5D5E4E2D1() 3 { 4 UInt64 test = 0; 5 test = test.Set(Squares.B1).Set(Squares.C3); 6 test = Bitboard.GetKnightAttacksBitboard(test, test); 7 8 UInt64 expected = 0; 9 expected = expected 10 .Set(Squares.D2) 11 .Set(Squares.A3) 12 .Set(Squares.A2) 13 .Set(Squares.A4) 14 .Set(Squares.B5) 15 .Set(Squares.D5) 16 .Set(Squares.E4) 17 .Set(Squares.E2) 18 .Set(Squares.D1); 19 20 Assert.AreEqual(expected, test); 21 } 22 23 [TestMethod] 24 public void 25 GetKnightAttacksBitboard_B1C3BitboardAndFriendsA4B5D5E4_ReturnsD2A3A2E2D1() 26 { 27 UInt64 test = 0; 28 test = test.Set(Squares.B1).Set(Squares.C3); 29 30 var friends = test 31 .Set(Squares.A4) 32 .Set(Squares.B5) 33 .Set(Squares.D5) 34 .Set(Squares.E4); 35 36 test = Bitboard.GetKnightAttacksBitboard(test, friends); 37 38 UInt64 expected = 0; 39 expected = expected 40 .Set(Squares.D2) 41 .Set(Squares.A3) 42 .Set(Squares.A2) 43 .Set(Squares.E2) 44 .Set(Squares.D1); 45 46 Assert.AreEqual(expected, test); 47 }

No primeiro teste, passo dois cavalos. Um em B1, outro em C3. Obviamente, eles se atacam “mutuamente”! Como são “amigos” espero que suas casas não estejam entre as casas atacas.

No segundo teste, crio um bitboard com algumas casas amigas (daquelas que seriam atacadas). Espero que essas casas também não estejam presentes no retorno.

Calculando bitboards para mais de um cavalo (e amigos)

Agora, minha implementação.

1 public static UInt64 2 GetKnightAttacksBitboard(UInt64 knightsBitboard) 3 { 4 return GetKnightAttacksBitboard(knightsBitboard, knightsBitboard); 5 } 6 7 public static UInt64 8 GetKnightAttacksBitboard(UInt64 knightsBitboard, UInt64 friends) 9 { 10 UInt64 result = 0; 11 while (knightsBitboard > 0) 12 { 13 var sq = knightsBitboard.GetLeadingSquare(); 14 knightsBitboard = knightsBitboard.Clear(sq); 15 result |= GetKnightAttacksBitboard(sq); 16 } 17 return result & (~friends); 18 }

O primeiro método (caso passe bitboards com as posições de cavalos) simplesmente repassa a responsabilidade para sua versão “mais qualificada” considerando o mesmo bitboard como “amigos”.

Na versão com dois bitboards faço a implementação propriamente dita. A lógica é simples.

  1. Inicio um bitboard resultado vazio (= 0);
  2. Inicio um loop enquanto o bitboard recebido tiver alguma coisa (> 0);
  3. Identifico o cavalo mais avançado (tema do post anterior);
  4. Retiro esse cavalo do bitboard (tema do primeiro post);
  5. Combino o bitboard resultado com o bitboard correspondente a casa sendo processada (com um OR);
  6. Por fim, removo do bitboard resultado as casas ocupadas por peças amigas (com um AND).

Por hoje, era isso!

Espero seus comentários e feedbacks.

Smiley piscando