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

Escrevendo um Engine para Xadrez – Parte 4 – Tempo para Refactoring

Tempo de leitura: 4 minutos

Olá pessoal, tudo certo?

Esse é um projeto vivo, com código vivo, testes e tudo mais. Então, nada mais normal que, escrito algum código, fazer algum refactoring.

Ontem fiz a publicação do que já havia escrito no GitHub (você tem acesso para esse código nesse commit). Meu amigo Juan Lopes foi um dos primeiros a acessar o projeto e observou alguns pontos falhos no design proposto e… partiu para o refactoring. Logo após, realizou o pull request que nos coloca na atual versão do projeto (você pode obter essa versão nesse commit).

Esse post objetiva apresentar algumas mudanças realizadas pelo Juan Lopes (o mérito pelo design [muito superior ao original] é dele, não meu).

Posts anteriores dessa série

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

Organização das pastas e arquivos

Quem assistiu a palestra do Juan Lopes no DNAD (material da palestra está aqui) sabe o quanto o cara saca de build. Uma das contribuições mais importantes que ele trouxe ao projeto foi reestruturar as pastas com conteúdo do projeto escrevendo um processo build inteiramente novo.

As pastas do projeto ficaram organizadas assim:

  • src – Onde estão localizados todos os fontes do projeto (código e testes);
  • lib – todas as dependências (para esse projeto, arquivos do nunit);
  • util – utilitários e complementos para o projeto do build. Aqui, complementos para o MSBuild e executáveis essenciais do nUnit (já falo dele);
  • build – resultado do build (dlls e pdbs) e testes;
  • bin – dlls e pdbs

Além disso, o Juan escreveu um pequeno script de build (utilizando MSBuild [escreverei uma série sobre ele]). Esse Script de Build executa todos os testes e cria a pasta build. Se você baixar o código fonte e desejar executar esse script de build, localize e execute o arquivo build.cmd (na pasta raiz do projeto)

Utilização do nUnit no lugar do MSTest

Se você acompanhou os primeiros posts dessa série, percebeu que utilizei o MSTest. Juan trouxe uma boa proposta de migrar os testes para o nUnit. Não quero iniciar uma “gerra santa” sobre qual framework de testes é o mais adequado. Por hora, basta dizer que simpatizo bastante com a idéia de ver uma “barra verde” indicando que tudo está ok.

Uma característica interessante da proposta do Juan foi utilizar, além do nUnit, uma extensão chamada SharpTestEx. Essa extensão deixa os testes mais legíveis.

Representando melhor o tabuleiro

Minha proposta inicial e mais pobre representava o tabuleiro através de enumerações. Como o Juan bem observou, abri mão de algumas abstrações mais interessantes utilizando essa abordagem. Na proposta dele, os três elementos passam a ser objetos. Assim, o projeto ganhou três novas structs:

  • Square – Representando as casas do tabuleiro [A1..H8];
  • Rank – Representando as linhas do tabuleiro [1..8];
  • File – Representando as colunas do tabuleiro [A..H].

Esses “elementos representativos” do tabuleiro possuem algumas características em comum. Todos possuem:

  • Um índice – sendo 0..63 para casas, 0..7 para linhas, 0..7 para colunas;
  • Um bitmask – um bitboard representando  o elemento com:
    • o bit correspondente ligado para Square
    • Todos os bits da linha ligados para Rank
    • Todos os bits da coluna ligados para File
  • um indicador de validade;

Essas características em comum representam uma interface. Juan identificou a mesma como IBoardUnit

1 public interface IBoardUnit 2 { 3 int Index { get; } 4 ulong Bitmask { get; } 5 bool IsValid { get; } 6 }

A implementação de Square ficou assim:

1 public struct Square : IBoardUnit 2 { 3 public int Index { get; private set; } 4 5 public Rank Rank { get { return Index / 8; } } 6 public File File { get { return Index % 8; } } 7 8 public bool IsValid 9 { 10 get { return File.IsValid && Rank.IsValid; } 11 } 12 13 public ulong Bitmask { get { return _Bitmasks[Index]; } } 14 15 public Square(int index) 16 : this() 17 { 18 Index = index; 19 } 20 21 public Square(Rank rank, File file) 22 : this(IndexOf(rank, file)) { } 23 24 public Square(string name) 25 : this(name[1].ToString(), name[0].ToString()) { } 26 27 28 public static int IndexOf(Rank rank, File file) 29 { 30 return rank * 8 + file; 31 } 32 33 34 private static ulong[] _Bitmasks = new ulong[64]; 35 static Square() 36 { 37 for (Rank i = 0; i < 8; i++) 38 for (File j = 0; j < 8; j++) 39 _Bitmasks[IndexOf(i, j)] = i.Bitmask & j.Bitmask; 40 } 41 42 #region converters 43 public static implicit operator int(Square square) 44 { 45 return square.Index; 46 } 47 48 public static implicit operator Square(int square) 49 { 50 return new Square(square); 51 } 52 53 public static implicit operator Square(string square) 54 { 55 return new Square(square); 56 } 57 58 59 #endregion 60 61 #region object overrides 62 public override string ToString() 63 { 64 return File.ToString() + Rank.ToString(); 65 } 66 #endregion 67 }

Alguns comentários importantes sobre essa estrutura:

  • é imutável;
  • o processamento pesado (cálculo dos bitmasks) é realizado apenas uma vez (construtor estático);
  • operadores implícitos e sobrecarga de construtores evitam a necessidade de casts espalhados pelo código;
  • é extremamente leve.

Igualmente elegante, eis a implementação para Rank

1 public struct Rank : IBoardUnit 2 { 3 public int Index { get; private set; } 4 public ulong Bitmask { get { return _Bitmasks[Index]; } } 5 6 public bool IsValid 7 { 8 get { return Index >= 0 && Index < 8; } 9 } 10 11 12 public Rank(int index) 13 : this() 14 { 15 Index = index; 16 } 17 18 public Rank(string name) 19 : this(name[0] - '1') { } 20 21 public int DistanceFrom(Rank otherRank) 22 { 23 return Math.Abs(Index - otherRank.Index); 24 } 25 26 27 28 public static implicit operator int(Rank rank) 29 { 30 return rank.Index; 31 } 32 33 public static implicit operator Rank(int rank) 34 { 35 return new Rank(rank); 36 } 37 38 public static implicit operator Rank(string rank) 39 { 40 return new Rank(rank); 41 } 42 43 private static ulong[] _Bitmasks = new ulong[8]; 44 static Rank() 45 { 46 for (int i = 0; i < 8; i++) 47 _Bitmasks[i] = 0xFFul << i * 8; 48 } 49 50 51 52 public override string ToString() 53 { 54 if (Index < 0 || Index >= 8) return "#"; 55 56 return ((char)(Index + '1')).ToString(); 57 } 58 59 60 }

Todas as observações feitas para Square são novamente válidas aqui. Por fim, a mesma lógica aplicada para File.

1 public struct File : IBoardUnit 2 { 3 public int Index { get; private set; } 4 public ulong Bitmask { get { return _Bitmasks[Index]; } } 5 6 public bool IsValid 7 { 8 get { return Index >= 0 && Index < 8; } 9 } 10 11 12 public File(int index) 13 : this() 14 { 15 Index = index; 16 } 17 18 public File(string name) 19 : this(char.ToUpperInvariant(name[0]) - 'A') {} 20 21 public int DistanceFrom(File otherFile) 22 { 23 return Math.Abs(Index - otherFile.Index); 24 } 25 26 27 public static implicit operator int(File file) 28 { 29 return file.Index; 30 } 31 32 public static implicit operator File(int file) 33 { 34 return new File(file); 35 } 36 public static implicit operator File(string file) 37 { 38 return new File(file); 39 } 40 41 42 private static ulong[] _Bitmasks = new ulong[8]; 43 static File() 44 { 45 for (int i = 0; i < 8; i++) 46 _Bitmasks[i] = 0x0101010101010101ul << i; 47 } 48 49 50 51 public override string ToString() 52 { 53 if (Index < 0 || Index >= 8) return "#"; 54 55 return ((char)(Index + 'A')).ToString(); 56 } 57 58 }

Bitboard turbinado

Na minha abordagem bitboard era sempre um UInt64 “incrementado” com algums extension methods. Juan promoveu Bitboards a uma estrutura mais organizada. Eis a implementação dele.

1 public struct Bitboard 2 { 3 public ulong Value { get; private set; } 4 5 public Bitboard(ulong value) 6 : this() 7 { 8 this.Value = value; 9 } 10 11 public Bitboard Set(params IBoardUnit[] unit) 12 { 13 return new Bitboard( 14 Value | unit.Aggregate(0ul, (s, v) => s | v.Bitmask)); 15 } 16 17 public Bitboard Clear(params IBoardUnit[] unit) 18 { 19 return new Bitboard( 20 Value & unit.Aggregate(~0ul, (s, v) => s & ~v.Bitmask)); 21 } 22 23 public bool IsSet(IBoardUnit unit) 24 { 25 return (Value & unit.Bitmask) != 0; 26 } 27 28 public bool IsClear(IBoardUnit unit) 29 { 30 return !IsSet(unit); 31 } 32 33 public bool IsEmpty 34 { 35 get { return Value == 0; } 36 } 37 38 public int BitCount 39 { 40 get 41 { 42 return BitOperations.PopCountIn(Value); 43 } 44 } 45 46 public Square? LeadingSquare 47 { 48 get 49 { 50 var index = BitOperations.HighestBitPosition(Value); 51 if (index == -1) return null; 52 return index; 53 } 54 } 55 56 public IEnumerable<Square> GetSetSquares() 57 { 58 var bcopy = this; 59 while (!bcopy.IsEmpty) 60 { 61 var lead = bcopy.LeadingSquare; 62 yield return lead.Value; 63 bcopy = bcopy.Clear(lead); 64 } 65 } 66 67 public static implicit operator ulong(Bitboard board) 68 { 69 return board.Value; 70 } 71 72 public static implicit operator Bitboard(ulong board) 73 { 74 return new Bitboard(board); 75 } 76 77 public override string ToString() 78 { 79 return "[" + string.Join("; ", GetSetSquares().Reverse().Select(x => x.ToString()).ToArray()) + "]"; 80 } 81 }

Agora UInt64 (ulong) volta a ser um tipo simples (e com todo o significado que deve ter). Bitboard está melhor representado.

  • Oculta a representação dos dados (nosso ulong ficou oculto);
  • fornece importantes funções utilitárias;
  • utiliza LINQ de forma extremamente elegante;

Outra decisão importante: separação de responsabilidades. Bitboard tem apenas dados, e operações de negócio. Operações com bits estão em uma classe utilitária. Segue:

1 public static class BitOperations 2 { 3 public static int PopCountIn(ulong value) 4 { 5 unchecked 6 { 7 const ulong mask0 = 0x0101010101010101; 8 const ulong mask1 = ~0ul / 3 << 1; 9 const ulong mask2 = ~0ul / 5; 10 const ulong mask3 = ~0ul / 17; 11 value -= (mask1 & value) >> 1; 12 value = (value & mask2) + ((value >> 2) & mask2); 13 value += value >> 4; 14 value &= mask3; 15 return (int)(((value * mask0) >> 56)); 16 } 17 } 18 19 public static int HighestBitPosition(ulong value) 20 { 21 if (value == 0) return -1; 22 23 int r = 0; 24 25 if (value > 0xFFFFFFFFul) { value >>= 32; r += 32; } 26 if (value > 0xFFFFul) { value >>= 16; r += 16; } 27 if (value > 0xFFul) { value >>= 8; r += 8; } 28 if (value > 0xFul) { value >>= 4; r += 4; } 29 if (value > 0x3ul) { value >>= 2; r += 2; } 30 if (value > 0x1ul) { r += 1; }; 31 32 return r; 33 } 34 }

Sim … além de tudo o cara achou uma alternativa sem pré-processamento para identificação da quantidade de bits ligados e da posição mais alta.

Representando as peças de forma adequada

Por fim, Juan implementou uma representação adequada para as peças (começando pelo cavalo):

1 public struct Knight : IPiece 2 { 3 public Bitboard Board { get; private set; } 4 public Knight(Square location) : this(location.Bitmask) 5 { 6 } 7 public Knight(Bitboard board) : this() 8 { 9 Board = board; 10 } 11 12 13 public Bitboard GetMoveBoard() 14 { 15 return GetMoveBoard(Board); 16 } 17 18 public Bitboard GetMoveBoard(Bitboard avoid) 19 { 20 var result = new Bitboard(); 21 foreach(var square in Board.GetSetSquares()) 22 { 23 result = result.Set(_Moves[square.Index]); 24 } 25 26 return result & ~avoid & ~Board; 27 } 28 29 static readonly Bitboard[] _Moves = new Bitboard[64]; 30 31 static Knight() 32 { 33 int[] knightsq = new int[] { -17, -15, -10, -6, 6, 10, 15, 17 }; 34 for (Square i = 0; i < 64; i++) 35 { 36 var bboard = new Bitboard(); 37 38 for (int j = 0; j < 8; j++) 39 { 40 Square target = i + knightsq[j]; 41 if (target.IsValid && 42 target.File.DistanceFrom(i.File) <= 2 && 43 target.Rank.DistanceFrom(i.Rank) <= 2) 44 bboard = bboard.Set(target); 45 } 46 47 _Moves[i] = bboard; 48 } 49 } 50 }

 

Basicamente, essa classe contem toda a lógica demonstrada no post anterior.

O que todo esse refactoring nos trouxe?!

Basicamente, nosso projeto, agora, está orientado a objetos. Todas as classes são representações de dados + operações. Além disso, detalhes da implementação ficaram “envolvidos” pelas implementações.

É muito importante observar que não foi introduzida qualquer penalidade de performance. Nosso código está muito mais bonito; com processo de build bem mais inteligente.

Mais uma vez, sou grato ao Juan pela importante colaboração com o projeto.

Sinta-se a vontade para contribuir com esse projeto. Meu próximo passo será programar o “Movimento do Rei”

Por hoje, era isso!

Smiley piscando