Escrevendo um Engine para Xadrez – Parte 2 – A importância do Pré-processamento

Publicado em 30/12/2010

13


Olá pessoal, tudo certo?

Antes de tudo, muito obrigado pelos feedbacks pelo primeiro post dessa série. Estou realmente muito animado com a possibilidade de escrever um grande software aqui.

Ontem mostrei uma técnica para representação do tabuleiro. Hoje, pretendo introduzir outro conceito fundamental: Pré-processamento.

As idéias apresentadas aqui são fundamentadas nos trabalhos do professor Dr Robert Hyatt.

Sem mais delongas…

Mudança no tipo de dados para representar um Bitboard

Até o post anterior, utilizei um Int64 para representar um bitboard. A partir de agora, passo a utilizar outro tipo, o UInt64.

Performance (processamento) como diferencial

Um Engine de Xadrez pode ser descrito como um tipo de programa que realiza processamento intenso. Algumas atividades realizadas são:

  1. verificar todos os movimentos possíveis (válidos) para uma posição;
  2. avaliar a “qualidade” da posição (que lado está melhor);
  3. avaliar linhas de jogo (sequências de jogadas) visando selecionar a “melhor” jogada (ou a menos pior).

Avaliar todas as possibilidades visando determinar a melhor jogada é computacionalmente inviável (não digo impossível, mas … ninguém conseguiu fazer isso ainda).

Em termos simples, quando um programa de xadrez faz uma jogada, está realizando a melhor que conseguiu encontrar. Não há garantias de que ela seja a melhor possível para aquela posição.

Encontrar uma boa alternativa (uma boa jogada) implica em permitir que um programa examine o maior número possível de boas alternativas (selecioandas por heurísticas). Além disso, um programa de Xadrez não pode ficar “calculando” por horas (ou ninguém teria paciência para ficar esperando).

Pelas razões expostas, todo programa de xadrez deverá ser extremamente otimizado. Ou seja, todo seu código deverá realizar o máximo de processamento consumindo o menor tempo possível.

Um programa mais otimizado consegue avaliar mais alternativas e, consequentemente, apresentar um desempenho superior (engine mais difícil de derrotar).

Melhorando a performance com pré-processamento

Uma das formas de melhorar performance é antecipar, sempre que possível, processamento. Na prática, significa substituir operações pesadas que seriam executadas repetidamente, por acessos a “caches” com resultados pré-processados.

Essa é uma consideração importante. Estamos, evidentemente, comprometendo um volume maior de memória para armazenar o resultado do pré-processamento. Estamos salvando muito tempo do processador em troca de algum volume de memória.

Considero essa uma estratégia arriscada e que precisa ser utilizada com moderação. Mas … é uma alternativa. Considere-a quando escrever seus aplicativos.

Duas operações importantes (e freqüentes) que podem ser otimizadas com pré-processamento

Duas operações muito comuns em um programa de Xadrez são:

  1. a descoberta da quantidade de bits ligados em um bitboard;
  2. a descoberta do índice do bit ligado (= 1) mais alto em um bitboard;

Isso é utilizado para determinar, por exemplo, a quantidade peças em um bitboard, as posições de determinadas peças, a quantidade de casas atacadas…

Considere que nosso programa tenha mais dois métodos para bitboard para executar as funções que destaquei acima:

 1 public static partial class Bitboard
 2 {
 3   //..
 4   public static int GetBitCount(this Int64 bitboard)
 5   {
 6         // ..
 7   }
 8 
 9   public static Squares GetLeadingSquare(this Int64 bitboard)
10   {
11       // ..
12   }
13   // ..
14 }

Sendo que:

  • GetBitCount retorna a quantidade de bits ligados em um bitboard;
  • GetLeadingSquare retorna o Square mais alto (menor = a1, maior = h8) ocupado.

O funcionamento desses métodos pode ser demonstrado e entendido por seus testes. Seguem os mais importantes:

 1 [TestMethod]
 2 public void GetLeadingSquare_EverySquareReverse()
 3 {
 4    
 5    for (int i = 63; i >= 0; i--)
 6    {
 7        UInt64 bitboard = 0;
 8        Squares sq = (Squares)i;
 9        bitboard = bitboard.Set(sq);
10        Assert.AreEqual(sq, bitboard.GetLeadingSquare());
11    }
12 }
13 
14 [TestMethod]
15 public void GetLeadingSquare_Empty_ReturnsINVALID()
16 {
17    // arrange
18    UInt64 bitboard = 0;
19 
20    // act
21    var result = bitboard.GetLeadingSquare();
22 
23    // assert
24    Assert.AreEqual(Squares.INVALID, result);
25 }
26 
27 [TestMethod]
28 public void GetLeadingSquare_EverySquare()
29 {
30    UInt64 bitboard = 0;
31    for (int i = 0; i < 64; i++)
32    {
33        Squares sq = (Squares)i;
34        bitboard = bitboard.Set(sq);
35        Assert.AreEqual(sq, bitboard.GetLeadingSquare());
36    }
37 }
38 
39 
40 [TestMethod]
41 public void GetBitCount_EverySquare()
42 {
43    UInt64 bitboard = 0;
44    for (int i = 0; i < 64; i++)
45    {
46        Squares sq = (Squares)i;
47        bitboard = bitboard.Set(sq);
48        Assert.AreEqual(i + 1, bitboard.GetBitCount());
49    }
50 }
51 
52 [TestMethod]
53 public void GetBitCount_EverySquareReverse()
54 {
55    UInt64 bitboard = 0;
56    for (int i = 63; i >= 0; i--)
57    {
58        Squares sq = (Squares)i;
59        bitboard = bitboard.Set(sq);
60        Assert.AreEqual(64 - i, bitboard.GetBitCount());
61    }
62 }
63 
64 [TestMethod]
65 public void GetBitCount_SettedD5andA1_Returns2()
66 {
67    // arrange
68    UInt64 bitboard = 0;
69    bitboard = bitboard
70        .Set(Squares.A1)
71        .Set(Squares.D5);
72 
73    // act
74    var result = bitboard.GetBitCount();
75 
76    // assert
77    Assert.AreEqual(2, result);
78 }

Estes testes dão um entendimento melhor da proposta dos dois métodos que estou desenvolvedo. Além deles, escrevi mais alguns testes específicos:

  1 [TestMethod]
  2 public void GetLeadingSquare_SettedA1_ReturnsA1()
  3 {
  4    // arrange
  5    UInt64 bitboard = 0;
  6    bitboard = bitboard.Set(Squares.A1);
  7 
  8    // act
  9    var result = bitboard.GetLeadingSquare();
 10 
 11    // assert
 12    Assert.AreEqual(Squares.A1, result);
 13 }
 14 
 15 [TestMethod]
 16 public void GetLeadingSquare_SettedB1_ReturnsB1()
 17 {
 18    // arrange
 19    UInt64 bitboard = 0;
 20    bitboard = bitboard.Set(Squares.B1);
 21 
 22    // act
 23    var result = bitboard.GetLeadingSquare();
 24 
 25    // assert
 26    Assert.AreEqual(Squares.B1, result);
 27 }
 28 
 29 [TestMethod]
 30 public void GetLeadingSquare_SettedA1andB1_ReturnsB1()
 31 {
 32    // arrange
 33    UInt64 bitboard = 0;
 34    bitboard = bitboard.Set(Squares.B1);
 35 
 36    // act
 37    var result = bitboard.GetLeadingSquare();
 38 
 39    // assert
 40    Assert.AreEqual(Squares.B1, result);
 41 }
 42 
 43 [TestMethod]
 44 public void GetLeadingSquare_SettedA1andH2_ReturnsH2()
 45 {
 46    // arrange
 47    UInt64 bitboard = 0;
 48    bitboard = bitboard
 49        .Set(Squares.A1)
 50        .Set(Squares.H2);
 51 
 52    // act
 53    var result = bitboard.GetLeadingSquare();
 54 
 55    // assert
 56    Assert.AreEqual(Squares.H2, result);
 57 }
 58 
 59 [TestMethod]
 60 public void GetLeadingSquare_SettedH2andA3_ReturnsA3()
 61 {
 62    // arrange
 63    UInt64 bitboard = 0;
 64    bitboard = bitboard
 65        .Set(Squares.A3)
 66        .Set(Squares.H2);
 67 
 68    // act
 69    var result = bitboard.GetLeadingSquare();
 70 
 71    // assert
 72    Assert.AreEqual(Squares.A3, result);
 73 }
 74 
 75 [TestMethod]
 76 public void GetLeadingSquare_SettedH4andA5_ReturnsA5()
 77 {
 78    // arrange
 79    UInt64 bitboard = 0;
 80    bitboard = bitboard
 81        .Set(Squares.A5)
 82        .Set(Squares.H4);
 83 
 84    // act
 85    var result = bitboard.GetLeadingSquare();
 86 
 87    // assert
 88    Assert.AreEqual(Squares.A5, result);
 89 }
 90 
 91 [TestMethod]
 92 public void GetLeadingSquare_SettedH6andA7andE8_ReturnsE8()
 93 {
 94    // arrange
 95    UInt64 bitboard = 0;
 96    bitboard = bitboard
 97        .Set(Squares.A7)
 98        .Set(Squares.E8)
 99        .Set(Squares.H6);
100 
101    // act
102    var result = bitboard.GetLeadingSquare();
103        
104    // assert
105    Assert.AreEqual(Squares.E8, result);
106 }
107 
108 [TestMethod]
109 public void GetLeadingSquare_SettedD5andA1_ReturnsD5()
110 {
111    // arrange
112    UInt64 bitboard = 0;
113    bitboard = bitboard
114        .Set(Squares.A1)
115        .Set(Squares.D5);
116 
117    // act
118    var result = bitboard.GetLeadingSquare();
119 
120    // assert
121    Assert.AreEqual(Squares.D5, result);
122 }

 

 

Mais fácil entender o propósito desses métodos agora, certo?

Agora … go code!

Escrevendo o código óbvio para GetLeadingSquare

Mais uma vez, os testes realmente ajudam a implementar código. Mesmo que ele pareça simples! Impressionante o número de vezes em que escrevo um código na certeza de que ele está correto e recebo um “vermelho” como resultado.

Dito isso, vejamos a implementação óbvia (e não otimizada) de GetLeadingSquare:

 1 public static Squares GetLeadingSquare(this UInt64 bitboard)
 2 {
 3    if (bitboard != 0)
 4    {
 5        UInt64 accum = 0;
 6        for (int i = 0; i < 64; i++)
 7        {
 8            accum += ((UInt64)1 << i);
 9            if ((bitboard & accum) == bitboard)
10                return (Squares)i;
11        }
12    }
13    return Squares.INVALID;
14 }

Esse método é bem “esperto”. O Loop procura por uma máscara compatível com o bitboard. A primeira máscara válida encontrada corresponderá ao bit mais relevante e, consequentemente, ao Square mais alto ocupado por uma peça nesse bitboard (bit mais alto que esteja ligado).

O problema dessa implementação é seu custo computacional em função do loop, comparações e shifts.

Escrevendo código otimizado para GetLeadingSquare

Como estou defendendo nesse post, em muitos casos, a saída para otimização é o pré-processamento. Ou seja, antecipação de processamento. A forma como faço isso aqui é relativamente simples. Observe:

 1 private static void InitializeLeadingBitHelperArray()
 2 {
 3    int i, j, n;
 4    
 5    n = 1;
 6    for (i = 0; i < 16; i++)
 7    {
 8        for (j = n; j < n + n; j++)
 9            LeadingBitHelperArrayField[j] = (byte)(i);
10        n += n;
11    }
12 }
13 
14 static readonly byte[] LeadingBitHelperArrayField =
15    new byte[65536];

 

O que eu fiz? Criei um vetor com 65536 posições. Esse número é suficiente para armazenar todas as combinações (ligado e desligado) de 16 bits. Para nossos conceitos, é o suficiente para armazenar duas linhas do tabuleiro.

No método, eu populo, para cada índice, a posição correspondente ao bit mais alto ligado. O método em sí é alto explicativo. (Se precisar de mais detalhes, solicite nos comentários).

Meu novo GetLeadingSquare que utiliza esse cache de pré-processamento ficou assim:

 1 public static Squares GetLeadingSquare(this UInt64 bitboard)
 2 {
 3    if (bitboard == 0) return Squares.INVALID;
 4 
 5    if ((bitboard >> 48) != 0)
 6        return (Squares)LeadingBitHelperArrayField[bitboard >> 48] + 48;
 7 
 8    if ((bitboard >> 32) != 0)
 9        return (Squares)LeadingBitHelperArrayField[bitboard >> 32] + 32;
10 
11    if ((bitboard >> 16) != 0)
12        return (Squares)LeadingBitHelperArrayField[bitboard >> 16] + 16;
13 
14    return (Squares)LeadingBitHelperArrayField[bitboard];
15 }

O que eu faço é verificar se o bitboard tem um bit ligado depois da posição 48, 32, 16 (múltiplos de 16). Se tiverem, faço o shift correspondente, obtenho a posição pré-calculada e aplico o offset. O resultado é a posição do bit ligado mais alto.

Qual o ganho? Esse método executa quase 8 vezes mais rapidamente que o primeiro.

Escrevendo um GetBitCount otimizado

Usando raciocínio semelhante ao utilizado para encontrar o bit ligado mais alto, verifico a quantidade bits ligados em um bitboard. Observe:

 1 private static void InitializeBitCountHelperArray ()
 2 {
 3   int i, j, n;
 4 
 5   BitCountHelperArrayField[0] = 0;
 6   BitCountHelperArrayField[1] = 1; 
 7   i = 1;
 8   for (n = 2; n <= 16; n++)
 9   {
10      i <<= 1;
11      for (j = i; j <= i + (i-1); j++)
12          BitCountHelperArrayField[j] = 
13              (byte)(1 + BitCountHelperArrayField[j - i]); 
14   }
15 }
16 
17 static readonly byte[] BitCountHelperArrayField =
18    new byte[65536];

Mais uma vez, crio um cache para 16 bits. Cada elemento do vetor possui o número de bits ligados para aquele índice.

Com o cache criado, a implementação da contagem é trivial:

1 public static int GetBitCount(this UInt64 bitboard)
2 {
3    return 
4        BitCountHelperArrayField[bitboard >> 48] +
5        BitCountHelperArrayField[(bitboard >> 32) & 0xffff] +
6        BitCountHelperArrayField[(bitboard >> 16) & 0xffff] + 
7        BitCountHelperArrayField[bitboard & 0xffff];
8 }

Por hoje, é isso!

Etiquetado:, ,
Publicado em: Post