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

Escrevendo um Engine para Xadrez – Parte 9 – Refactoring e Redesign

Tempo de leitura: 7 minutos

Olá pessoal, tudo certo?

Nessa série, estamos escrevendo códigos desafiadores em um design que está em constante evolução.

A cada post, na exata medida em que avançamos na “cobertura” do nosso objetivo, temos a sensação de compreender mais sobre o domínio (e, consequentemente, sobre nosso objetivo).

Na medida em que escrevemos mais código percebemos que  vamos, automaticamente, adicionando algumas rupturas no design vigente. Aos poucos, aceitamos e “reforçamos” alguns débitos técnicos que, antes de se tornarem monstros, precisam ser combatidos e derrotados.

Nosso cuidado em escrever testes nos autoriza a fazer refactoring. Mais do que isso, permite que o código seja explorado e entendido por quem não o escreveu originalmente. Os testes revelam a intencionalidade de cada elemento do design.

No post de hoje, apresento o resultado do refactoring realizado, mais uma vez, pelo @juanplopes que insiste em ser tratado como colaborador eventual e não como co-autor (o que de fato é). Durante o refactoring, discutimos um bocado sobre o domínio. Mais que isso, confrontamos diversos posicionamentos e produzimos, quase sempre, consenso.

Importante destacar que nem todos os melhoramentos feitos no design e no código estão refletidos aqui. Pegue o código fonte no site desse projeto no GitHub (faça um “clone” ou simplesmente baixe o código fonte para acompanhar).

Para mim, esse projeto está se convertendo em um exemplo sólido de design emergente.

Posts anteriores dessa série

Se está chegando agora, talvez queira ler o que já foi escrito nessa série. Considere a leitura dos posts anteriores dessa série. São eles:

Antes de avançar, seja um colaborador!

Gosta de projetos desafiadores? Gostaria de dar e receber feedback? Aprimorar suas competências? Participe desse projeto! Como?

  1. Escreva testes;
  2. Implemente funcionalidades;
  3. Faça refactoring;
  4. Discuta, questione e ajude a aprimorar o design.

Quer fazer isso? Faça um clone do projeto no GitHub! Me mande mensagens pelo twitter (respondo mais rápido que por emails)! Comente aqui no blog.

Gosta de trabalhar com UI? StrongChess será compatível com o Winboard (XBoard) mas nada impede que tenha uma interface também. WPF, Silverlight, whatever! Se você se interessou, faça contato.

Isolando complexidades

Alguns programas são naturalmente mais complexos que outros. Um Engine de Xadrez está, para mim, entre os programas mais complexos.

Para fazer o computador “pensar” precisamos usar técnicas avançadas de programação. Nesse projeto, por exemplo, usamos intensamente técnicas de manipulação de mapas de bit.

Técnicas avançadas de programação implicam em código difícil de ler para a maioria dos programadores. Isolar essa complexidade libera o time para pensar em aspectos mais relevantes da implementação, como abstrações para representar as regras do jogo, por exemplo, no lugar de tratar com códigos “gregos”.

Boa parte do refactoring que foi realizado no projeto agora visava fazer exatamente isso: isolar complexidades.

Isolando a complexidade para criação de um bitboard

Bitboard é ponto central de nosso design. Até o post passado, criávamos bitboards novos combinando bitboards existentes. Além disso, mantinhamos algums bitboards comuns para facilitar essa operação. Para lembrar como criávamos bitboards, observe:

1 var expected = Squares.A4 | 2 Squares.B5 | 3 Squares.C6 | 4 Squares.D7 | 5 Squares.E8;

 

Nessa implementação havia uma classe estática, chamada Squares, que armazenava um bitboard, com apenas o bit correspondente ligado, para cada casa. Perceba que não fica claro que o resultado dessa operação será um bitboard.

Bitboard é um caso típico de objeto com inicialização complexa. Inicializações complexas podem ser simplicados pela utilização de um Builder.

O Builder planejado para o Bitboard permite inicializações assim:

1 var expected = Bitboard.With.A4.B5.C6.D7.E8.Build();

Ou, ainda, construções mais complexas:

1 var e1 = Bitboard.With.FileA.Rank1.Except.A1.A6.A7.A8.Build(); 2 var e2 = Bitboard.With.DiagonalA1H8.Except.A1.Build();

Lindo, não?! Destaco nessa nova abordagem dois aspectos importantes:

  1. é mais econômica – preciso escrever menos código, com o mesmo resultado;
  2. oculta detalhes da implementação – a metodologia anterior deixava clara a constituição de um mapa de bits. Além de ser significativamente “restritiva” por deixar “aberta” a combinação (OR) de bits (que não é familiar para a maioria dos desenvolvedores).

O Builder, como proposto, torna a linguagem de construção de bitboard mais natural e oculta detalhes da implementação.

Complexidade isolada: o builder de Bitboards

O primeiro desafio é “iniciar” o builder. Para tornar a interface mais “natural”, foi incluída uma propriedade estática a estrutura Bitboard. Observe:

1 public struct Bitboard : IBoardUnit 2 { 3 // ... 4 public static BoardBuilder With 5 { 6 get { return new BoardBuilder(); } 7 } 8 / ... 9 }

Essa propriedade liberta o programador “cliente” de saber da existência do builder.

BoardBuilder é uma estrutura implementada em duas partes (implementações parciais).

A primeira:

1 public partial struct BoardBuilder 2 { 3 private Bitboard result; 4 private bool inverted; 5 6 private BoardBuilder(Bitboard board, bool inverted) 7 : this() 8 { 9 this.result = board; 10 this.inverted = inverted; 11 } 12 13 public Bitboard Build() 14 { 15 return inverted ? result.Inverted : result; 16 } 17 18 public BoardBuilder And(IBoardUnit unit) 19 { 20 return new BoardBuilder(result.Set(unit), inverted); 21 } 22 23 public BoardBuilder Except 24 { 25 get { return new BoardBuilder(~result, !inverted); } 26 } 27 28 public static implicit operator Bitboard(BoardBuilder builder) 29 { 30 return builder.Build(); 31 } 32 }

Nosso builder possui algumas características que merecem algum destaque:

  • existe um conversor implícito para Bitboard. Isso permite que o programador utilize “construções” de bitboard livremente. [Bitboard b = Bitboard.With.E4 é perfeitamente válido].
  • o builder mantém um mapa de bits (atributo result), interno, correspondente ao bitboard que está sendo construído;
  • o método Build constrói um Bitboard a partir da representação binária, interna;
  • o método And cria um novo Builder, combinado o bitboard representado internamente com o bitboard recebido por parâmetro;
  • o atributo “inverted” é usado para permitir a operação Except (alguma lógica binária foi empregada aqui).

Alem dessa construção básica, nosso builder possui propriedades “aceleradoras”, como A1, B2, C7, Rank1, entre outras. Na prática, essas propriedades são implementações mecânicas que devolvem um novo Builder obtido por um And com o mapa de bits correspondente. Perceba que:

  • Há 64 propriedades aceleradoras para representar cada uma das casas (squares, de a1 até h8);
  • Há 8 propriedades aceleradoras para representar cada uma das colunas (files, de a até h);
  • Há 8 propriedades aceleradoras para representar cada uma das linhas (ranks, de 1 até 8);
  • Há 15 propriedades aceleradoras para representar cada uma das diagonais.

Essas propriedades foram implementadas assim:

1 using System; 2 using System.Collections.Generic; 3 using System.Linq; 4 using System.Text; 5 6 namespace StrongChess.Model.Util 7 { 8 public partial struct BoardBuilder 9 { 10 <# for(var i=0; i<64; i++) { #> 11 public BoardBuilder <#=(char)('A'+(i%8))#><#=(i/8)+1#> { get { return And(new Square(<#=i#>)); } } 12 <# } #> 13 14 <# for(var i=0; i<8; i++) { #> 15 public BoardBuilder Rank<#=i+1#> { get { return And(new Rank(<#=i#>)); } } 16 <# } #> 17 18 <# for(var i=0; i<8; i++) { #> 19 public BoardBuilder File<#=(char)(i+'A')#> { get { return And(new File(<#=i#>)); } } 20 <# } #> 21 22 23 public BoardBuilder DiagonalA1H8 { get { return And(new DiagonalNE(7)); } } 24 public BoardBuilder DiagonalH1A8 { get { return And(new DiagonalNW(7)); } } 25 <# for(var i=1; i<8; i++) { #> 26 public BoardBuilder DiagonalA<#=i+1#><#=(char)('H'-i)#>8 { get { return And(new DiagonalNE(<#=7-i#>)); } } 27 public BoardBuilder Diagonal<#=(char)('A'+i)#>1H<#=8-i#> { get { return And(new DiagonalNE(<#=7+i#>)); } } 28 public BoardBuilder DiagonalH<#=i+1#><#=(char)('A'+i)#>8 { get { return And(new DiagonalNW(<#=7+i#>)); } } 29 public BoardBuilder Diagonal<#=(char)('H'-i)#>1A<#=8-i#> { get { return And(new DiagonalNW(<#=7-i#>)); } } 30 <# } #> 31 32 } 33 }

Se você não está familiarizado com essa segunda parte, cabe a você aprender T4.

O que esse código faz é escrever a implementação real para essa parte da struct. Por haver muita “repetição” de lógica, apenas alterando parâmetros, codificamos a lógica e transferimos a responsabilidade por escrever o código repetitivo para o Visual Studio.

Não escreva código “mecânico”. Deixe o Visual Studio fazer isso por você. Aprenda T4

O código gerado a partir de nosso T4, pelo Visual Studio, fica parecido com:

1 public partial struct BoardBuilder 2 { 3 public BoardBuilder A1 { get { return And(new Square(0)); } } 4 public BoardBuilder B1 { get { return And(new Square(1)); } } 5 public BoardBuilder C1 { get { return And(new Square(2)); } } 6 public BoardBuilder D1 { get { return And(new Square(3)); } } 7 public BoardBuilder E1 { get { return And(new Square(4)); } } 8 public BoardBuilder F1 { get { return And(new Square(5)); } } 9 // .. segue com uma propriedade para cada Square 10 11 public BoardBuilder Rank1 { get { return And(new Rank(0)); } } 12 public BoardBuilder Rank2 { get { return And(new Rank(1)); } } 13 public BoardBuilder Rank3 { get { return And(new Rank(2)); } } 14 public BoardBuilder Rank4 { get { return And(new Rank(3)); } } 15 public BoardBuilder Rank5 { get { return And(new Rank(4)); } } 16 public BoardBuilder Rank6 { get { return And(new Rank(5)); } } 17 public BoardBuilder Rank7 { get { return And(new Rank(6)); } } 18 public BoardBuilder Rank8 { get { return And(new Rank(7)); } } 19 20 public BoardBuilder FileA { get { return And(new File(0)); } } 21 public BoardBuilder FileB { get { return And(new File(1)); } } 22 public BoardBuilder FileC { get { return And(new File(2)); } } 23 public BoardBuilder FileD { get { return And(new File(3)); } } 24 public BoardBuilder FileE { get { return And(new File(4)); } } 25 public BoardBuilder FileF { get { return And(new File(5)); } } 26 public BoardBuilder FileG { get { return And(new File(6)); } } 27 public BoardBuilder FileH { get { return And(new File(7)); } } 28 29 30 public BoardBuilder DiagonalA1H8 { get { return And(new DiagonalNE(7)); } } 31 public BoardBuilder DiagonalH1A8 { get { return And(new DiagonalNW(7)); } } 32 public BoardBuilder DiagonalA2G8 { get { return And(new DiagonalNE(6)); } } 33 public BoardBuilder DiagonalB1H7 { get { return And(new DiagonalNE(8)); } } 34 public BoardBuilder DiagonalH2B8 { get { return And(new DiagonalNW(8)); } } 35 public BoardBuilder DiagonalG1A7 { get { return And(new DiagonalNW(6)); } } 36 // .. segue com uma propriedae para cada diagonal 37 }

Você pode consultar a implementação completa desse builder acessando o GitHub desse projeto.

Isolando a complexidade para execução de Shifts em bitboards

Como bitboard está no centro de nossa representaçã de estado para o tabuleiro, facilitar sua operação torna o código, em geral, mais simples. A operação mais comum, executada em um bitboard é um shift, visando “mover” um bit ligado de uma posição do tabuleiro para outra.

Considere:

  • Para avançar o bit de um peão branco, uma casa “para frente”, teríamos que executar algo como: bitpeao << 8;
  • Deslocar o cavalo, uma casa para a esquerda, e duas casas para trás, seria algo como: bitcavalo << –17;

Deslocar 8 ou 17 bits, para um lado ou para o outro, é operação trivial para quem está acostumado com matemática binária, mas pode não ser tão trivial para quem esteja começando. Por isso, foi implementada um facilitador.

1 public struct Bitboard : IBoardUnit 2 { 3 // ... 4 public Bitboard Shift(int ranks, int files) 5 { 6 return value.ChessShift(ranks, files); 7 } 8 // ... 9 }

Onde ranks e files são offsets para deslocamentos. Apenas para título de exemplo, o deslocamento do peão pode ser feito com um bitpeao.Shift(1,0) e o do cavalo com um bitcavalo.Shift(-1,-2).

Além de “programar” o deslocamento de um bit isolado, há a possibilidade deslocar conjuntos inteiros de bits. Observe a nova rotina para geração dos bitboards de diagonais:

1 static Bitboard[] masks = new Bitboard[15]; 2 static DiagonalNE() 3 { 4 var initial = Bitboard.With.A1.B2.C3.D4.E5.F6.G7.H8.Build(); 5 6 for (int i = 7; i >= 0; i--) 7 masks[i] = initial.Shift(7 - i, 0); 8 9 for (int i = 8; i < 15; i++) 10 masks[i] = initial.Shift(0, i - 7); 11 12 }

Compare esse código com o desenvolvido no post anterior e verá o quanto o shift conseguiu simplificar nossa lógica (todos os bits que saíram do tabuleiro foram descartados).

Não deixe a complexidade se espalhar pelo projeto. Oculte a complexidade e libere os desenvolvedores para trabalhar com aspectos mais críticos.

Complexidade isolada: shifts em um bitboard de xadrez

Como pode ser observado, a mágica em um método auxiliar ChessShift. Verifique sua implementação:

1 public static class BoardShifter 2 { 3 static ulong[] vshift = new ulong[15]; 4 static ulong[] hshift = new ulong[15]; 5 6 static BoardShifter() 7 { 8 vshift[7] = 0; 9 hshift[7] = 0; 10 11 for (int i = 6; i >= 0; i--) 12 vshift[i] = vshift[i + 1] | (0xFFul << ((6 - i) * 8)); 13 14 for (int i = 0; i <= 6; i++) 15 vshift[i + 8] = ~vshift[i]; 16 17 for (int i = 6; i >= 0; i--) 18 hshift[i] = hshift[i + 1] | (0x0101010101010101ul << (6 - i)); 19 20 for (int i = 0; i <= 6; i++) 21 hshift[i + 8] = ~hshift[i]; 22 23 } 24 25 public static ulong ChessShift(this ulong value, int ranks, int files) 26 { 27 value = value & ~(vshift[ranks + 7] | hshift[files + 7]); 28 var shift = ranks * 8 + files; 29 return shift > 0 ? value << shift : value >> -shift; 30 } 31 }

Por hora, vamos dizer apenas que esse “extension method” realiza os deslocamentos de bits nas direções indicadas, limpando eventuais estouros. Sua lógica de funcionamento será explicada em outro post. (Segundo o @juanplopes, esse método é tenso)

Complexidade isolada é mais facilmente justificada. Não há problemas em escrever código com performance superior e alta complexidade agregada se houver baixa necessidade de manutenção.

Menos manutenção, mais isolamento, mais complexidade autorizada

Novo conceito: PieceRule

Até este ponto, para “calcular” os movimentos possíveis para uma peça criávamos uma peça, informando sua posição no tabuleiro, e chamávamos um método que nos retornasse um bitboard com as casas “atacadas” pela peça. O problema é que usávamos diferentes abordagens:

  • Cavalo era iniciado com um bitboard (uma instância de cavalo podia apontar para todos os cavalos no tabuleiro [conceito feio e abandonado para as outras peças]);
  • Torre, bispo e dama recebiam informações adicionais, visto que as casas atacadas são restringidas pela posição de outras peças no tabuleiro;

Não é bacana! Na prática, no lugar de representar as peças, o que tínhamos era o registro codificado das regras de movimentação de cada peça. Após algum redesign, ponderou-se a seguinte interface:

1 public interface IPieceRule 2 { 3 Bitboard GetMoveBoard(Square from, Bitboard friends, Bitboard enemies); 4 }

O que estamos dizendo aqui é: para um determinado tipo de peça, podemos definir seus movimentos válidos sabendo a casa onde a peça se encontra, a posição de seus amigos (peças da mesma cor) e a posição das peças adversárias.

Com esse conceito, no lugar de “criar” um cavalo em D5, solicitamos a regra que nos informe quais são os movimentos válidos para o cavalo. Observe a nova implementação de Knight, agora como IPieceRule:

1 public struct Knight : IPieceRule 2 { 3 public Bitboard GetMoveBoard(Square from) 4 { 5 return GetMoveBoard(from, 0); 6 } 7 8 9 public Bitboard GetMoveBoard(Square from, Bitboard friends) 10 { 11 return GetMoveBoard(from, friends, 0); 12 } 13 14 public Bitboard GetMoveBoard(Square from, Bitboard friends, Bitboard enemies) 15 { 16 return _Moves[from].Clear(friends); 17 } 18 19 #region static 20 21 static readonly Bitboard[] _Moves = new Bitboard[64]; 22 static Knight() 23 { 24 for (Square i = 0; i < 64; i++) 25 { 26 var square = i.AsBoard; 27 var board = Bitboard.Empty.Set( 28 square.Shift(1, 2), square.Shift(1, -2), 29 square.Shift(2, 1), square.Shift(2, -1), 30 square.Shift(-1, 2), square.Shift(-1, -2), 31 square.Shift(-2, 1), square.Shift(-2, -1) 32 ); 33 _Moves[i] = board; 34 } 35 } 36 37 #endregion 38 }

Da mesma forma que ocorria antes, pré-calculamos todos os movimentos para o cavalo.

Você pode consultar como ficaram as Rules para todas as peças acessando o GitHub desse projeto.

Revise elementos do design verificando se eles ainda fazem pleno sentido. Um elemento de design “deslocado” se converte, lentamente, em um “sabotador”.

Criando um “ponto de acesso” para todas as PieceRules

Visando criar uma “linguagem mais concisa”, foi criado um “provedor” de regras para o sistema. No lugar de acessar as regras para o bispo usando um new Bishop(), chegamos a regra por uma requisição do tipo Rules.For().

A implementação desse “provider” ficou assim:

1 public static class Rules 2 { 3 class Instances<T> 4 where T : new() 5 { 6 public static T instance = new T(); 7 } 8 9 public static T For<T>() 10 where T : new() 11 { 12 return Instances<T>.instance; 13 } 14 }

Isso revela mais claramante a intenção do código. Observe um dos testes para o movimento do Rei:

1 [Test] 2 public void GetMoveBoard_H1_ReturnsH2G2G1() 3 { 4 var test = Rules.For<King>().GetMoveBoard("H1"); 5 var expected = Bitboard.With.H2.G2.G1.Build(); 6 test.Should().Be(expected); 7 }

Repare como ficou evidente o acesso as “regras" relacionadas ao movimento do Rei.

Amplie o vocabulário de seu sistema.

Há muitas outras melhorias “locais” que foram feitas em todo o projeto. Infelizmente, não dá para cubrir tudo aqui.

Por hoje, era isso!

0 Comentários

  1. tisciencia 6 anos ago says:

    Olá Elemar tudo bem? Ficou muito boa essa refatoração.

    Só tenho uma dúvida. Da forma como foi criado o provedor de regras, teria como garantir que somente objetos que possuem regras sejam passados como parâmetro?

    Abraço

    Responder
  2. tisciencia 6 anos ago says:

    Fiz uns testes aqui e talvez essa implementação resolva a questão da minha pergunta.

    public static T For()
    where T : IPieceRule, new()
    {
    return Instances.instance;
    }

    Agora teremos somente um provedor de regras para peças ou objetos que implementam a interface IPieceRule. O que acha?

    Abraço

    Responder

Trackbacks para este post

  1. Escrevendo um Engine para Xadrez – Parte 10 – PieceSet, Side, AttackMoves, Rays e Otimizações « Elemar DEV
  2. Escrevendo um Engine para Xadrez – Parte 11 – Mais Bitboards, Xeques e Escapadas « Elemar DEV