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

Escrevendo um Engine para Xadrez – Parte 10 – PieceSet, Side, AttackMoves, Rays e Otimizações

Tempo de leitura: 8 minutos

Olá pessoal, tudo certo?

Temos um bocado de coisas para apresentar hoje! O código de nosso engine cresceu um bocado. Resumindo, nossas atividades foram:

  1. Criamos PieceSet, uma representação para as posições e os possíveis movimentos de um conjunto de peças do mesmo tipo. Por exemplo, as torres brancas;
  2. Criamos Side, uma representação para todas as peças de um “lado” no jogo. Por exemplo, todas as peças brancas ou todas as peças negras;
  3. Escrevemos um bocado de código para o “cálculo” de movimentos para uma determinada casa no tabuleiro (diretos ou indiretos);
  4. Criamos Rays, uma representação de quais são casas “ligadas” a uma determinada posição, em todas as direções (no post vai ficar mais claro);
  5. @juanplopes utilizou Rays para otimizar boas porções de código, substituindo loops por operações binárias. As alterações mais significativas estão na geração de movimentos para bispos e torres (Rook.cs e Bishop.cs).

Nesse post, pretendo explicar os resultados dessas atividades.

Por favor, pegue o código fonte desse projeto em https://github.com/ElemarJR/StrongChess

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. São eles:

Representando peças sobre o tabuleiro – PieceSet

No post anterior, fizemos um redesign que transformou nossas peças em “regras para as mesmas”. Assumindo que estamos fazendo um engine, devemos ter condições de representar as “instâncias” de nossas peças em um determinado momento da partida (ou enquanto nosso engine estiver “pensando”). Essa representação, em nosso engine, ficou na nova struct “PieceSet”. Observe:

1 public struct PieceSet<T> 2 where T : IPieceRule, new() 3 { 4 public Bitboard Locations { get; private set; } 5 public PieceSet(Bitboard locations) : this() 6 { this.Locations = locations; } 7 8 public PieceSet(IBoardUnit bu) 9 : this(bu.AsBoard) 10 {} 11 12 13 public IEnumerable<Move> GetMoves 14 (Bitboard friends, Bitboard enemies, 15 bool onlyCaptures = false) 16 { 17 foreach (var from in Locations.Squares) 18 { 19 Bitboard destinations = 20 Rules.For<T>().GetMoveBoard(from, friends, enemies); 21 if (onlyCaptures) destinations &= enemies; 22 foreach (var to in destinations.Squares) 23 yield return new Move(from, to); 24 } 25 } 26 27 public IEnumerable<Move> GetMoves(Bitboard friends, 28 Bitboard enemies, Bitboard filterFrom, 29 Bitboard filterTo, bool onlyCaptures = false) 30 { 31 Bitboard pieces = Locations & filterFrom; 32 foreach (var from in pieces.Squares) 33 { 34 Bitboard destinations = 35 Rules.For<T>().GetMoveBoard(from, friends, enemies); 36 if (onlyCaptures) destinations &= enemies; 37 destinations &= filterTo; 38 foreach (var to in destinations.Squares) 39 yield return new Move(from, to); 40 } 41 } 42 43 public Bitboard GetMoveBoard(Bitboard friends, 44 Bitboard enemies, bool onlyCaptures = false) 45 { 46 var moveboards = from f in Locations.Squares 47 select Rules.For<T>().GetMoveBoard 48 (f, friends, enemies); 49 50 var result = moveboards.Aggregate((a, b) => a | b); 51 if (onlyCaptures) result &= enemies; 52 53 return result; 54 } 55 56 public IEnumerable<Move> GetDirectAttackMoves 57 (Square target, Bitboard friends, Bitboard enemies) 58 { 59 // .. 60 } 61 } 62 }

PieceSet também é um tipo imutável. Em sua construção, especifica-se o tipo de peça que está sendo representado e, com um bitboard, as casas ocupadas.

Há duas sobrecargas para o método GetMoves. A diferença fundamental é que em uma delas podemos especificar filtros para indicar peças em que posições devem ser condideradas e quais casas devem ser atacadas. Utilizamos a Rule correspondente para gerar o bitboard de casas atacadas.

O método GetMoveBoard gera um bitboard onde todas as casas atacadas pelas peças representadas no set. Usamos a Rule para gerar as casas atacadas por cada posição e usamos o método Aggregate do link para “combinar” todos os bitboards (com um OR binário).

Gerando movimentos de ataque para uma casa – Poder da generalização

PieceSet é uma forte generalização do comportamento das diversas peças. Um único bloco de código, provido com a “Regra de Movimentação” apropriada, que consegue executar “computações” complexas. Consideremos o caso de “calcular” todos os movimentos que nossas peças poderiam fazer para atacar uma casa do tabuleiro. Por exemplo, descobrir todos os movimentos de “rainha” que gerariam um cheque (ataque a posição do rei adversário). Essa tarefa foi generalizada no método GetDirectAttackMoves. Observe:

1 public IEnumerable<Move> GetDirectAttackMoves 2 (Square target, Bitboard friends, Bitboard enemies) 3 { 4 var hotsquares = Rules.For<T>().GetMoveBoard( 5 target, friends, enemies); 6 foreach (var from in Locations.Squares) 7 { 8 var candidates = Rules.For<T>().GetMoveBoard(from, friends, enemies); 9 Bitboard spot = candidates & hotsquares; 10 foreach (var to in spot.Squares) 11 yield return new Move(from, to); 12 } 13 }

Qual a lógica desse método? Basicamente:

  • assumimos que há uma peça do mesmo tipo na casa atacada;
  • calcula-se um bitboard com todos os destinos possíveis para essa “peça imaginária” a partir da posição atacada;
  • Para cada peça representada no set, calcula-se todos os destinos possíveis partindo de suas posições atuais;
  • infere-se os destinos que geram ataque a casa atacada pelo and entre os bitboards da peça imaginária e da peça real.

Bonito. Para deixar mais claro, segue um dos testes para esse método:

1 [Test] 2 public void GetDirectAttackMoves_QueenInA2ToAttackF6() 3 { 4 // arrange 5 PieceSet<Queen> queens = new PieceSet<Queen>( 6 Bitboard.With.A2 7 ); 8 9 var target = new Square("F6"); 10 11 // act 12 var moves = queens.GetDirectAttackMoves( 13 target, Bitboard.Empty, target.AsBoard); 14 15 // assert 16 moves.Should().Have.SameSequenceAs( 17 new Move("A2", "A1"), 18 new Move("A2", "B2"), 19 new Move("A2", "F2"), 20 new Move("A2", "A6"), 21 new Move("A2", "E6"), 22 new Move("A2", "F7") 23 ); 24 }

No teste, criamos um PieceSet com uma rainha em A2. Definimos o target como sendo F6.

Representando todas as peças (e peões) para um jogador (lado) – Side

Já conseguimos representar um conjunto de peças, do mesmo tipo. Agora, precisamos representar o conjunto de todas as peças (e peões) para um lado (um dos jogadores).

1 public struct Side 2 { 3 public PieceSet<Queen> Queens { get; private set; } 4 public PieceSet<Rook> Rooks { get; private set; } 5 public PieceSet<Bishop> Bishops { get; private set; } 6 public PieceSet<Knight> Knights { get; private set; } 7 public IPawns Pawns { get; private set; } 8 9 PieceSet<King> _King; 10 public Square KingLocation 11 { get { return _King.Locations.Squares.First(); } } 12 13 public Bitboard Occupation 14 { get; private set; } 15 16 public Side( 17 Square kingLocation, 18 PieceSet<Queen> queens, 19 PieceSet<Bishop> bishops, 20 PieceSet<Knight> knights, 21 PieceSet<Rook> rooks, 22 IPawns pawns 23 ) 24 : this() 25 { 26 _King = new PieceSet<King>(kingLocation.AsBoard); 27 Queens = queens; 28 Rooks = rooks; 29 Bishops = bishops; 30 Knights = knights; 31 Pawns = pawns; 32 Occupation = queens.Locations | rooks.Locations | 33 _King.Locations | 34 bishops.Locations | knights.Locations | 35 pawns.Locations; 36 } 37 }

Outra vez, um tipo imutável. Side possui propriedades com um Set para cada tipo de peça. Repare que, mesmo representando internamente como set, mantenho a representação do rei na interface pública como um Square. Isso é para garantir que um lado nunca tenha mais do que um rei.

Logo no construtor, crio um bitboard para representar todas as casas ocupadas por peças daquele “lado” e armazeno o resultado em “Occupation”.

Criando um “Side” com todas as peças prontas para começar o jogo

Já que podemos representar todas as peças para um “lado”, por que não preparar uma representação para “jogo novo”?  Criei duas propriedades estáticas em Side para fazer isso. Observe:

1 public struct Side 2 { 3 //... 4 #region static 5 public static Side WhiteInitialPosition 6 { 7 get 8 { 9 return new Side( 10 new Square("E1"), 11 new PieceSet<Queen>(Bitboard.With.D1), 12 new PieceSet<Bishop>(Bitboard.With.C1.F1), 13 new PieceSet<Knight>(Bitboard.With.B1.G1), 14 new PieceSet<Rook>(Bitboard.With.A1.H1), 15 WhitePawns.InitialPosition 16 ); 17 } 18 } 19 20 public static Side BlackInicialPosition 21 { 22 get 23 { 24 return new Side( 25 new Square("E8"), 26 new PieceSet<Queen>(Bitboard.With.D8), 27 new PieceSet<Bishop>(Bitboard.With.C8.F8), 28 new PieceSet<Knight>(Bitboard.With.B8.G8), 29 new PieceSet<Rook>(Bitboard.With.A8.H8), 30 BlackPawns.InitialPosition 31 ); 32 } 33 } 34 #endregion 35 }

Repare como utilizo a inicialização dos peões.

Computando todos os movimentos para um lado

Agora que conseguimos representar todas as peças brancas, ou negras, podemos pensar em gerar todos os movimentos para um lado. Basicamente nossa classe Side combina os resultados dos diversos Sets. Observe:

1 public IEnumerable<Move> GetMoves(Bitboard enemies, Square? enpassant) 2 { 3 Bitboard notblockers = ~(Occupation | enemies); 4 return _King.GetMoves(Occupation, enemies) 5 .Union(Queens.GetMoves(Occupation, enemies)) 6 .Union(Rooks.GetMoves(Occupation, enemies)) 7 .Union(Bishops.GetMoves(Occupation, enemies)) 8 .Union(Knights.GetMoves(Occupation, enemies)) 9 .Union(Pawns.GetAllMoves(notblockers, enemies, enpassant)); 10 }

Bonito! A mesma lógica foi utilizada para gerar as capturas. Observe:

1 public IEnumerable<Move> GetCaptures(Bitboard enemies, Square? enpassant) 2 { 3 return _King.GetMoves(Occupation, enemies, true) 4 .Union(Queens.GetMoves(Occupation, enemies, true)) 5 .Union(Rooks.GetMoves(Occupation, enemies, true)) 6 .Union(Bishops.GetMoves(Occupation, enemies, true)) 7 .Union(Knights.GetMoves(Occupation, enemies, true)) 8 .Union(Pawns.GetCaptures(enemies, enpassant)); 9 }

Ou ainda para MoveBoards (consulte o código fonte para ver a implementação).

Bitboards importantes, até aqui ignorados – Rays

A escolha dos bitboards para representação de dados a respeito do “estado” no tabuleiro foi feliz. A partir dos bitboards, podemos realizar consultas rapidamente. Com essas consultas, poderemos, mais adiante, computar melhores movimentos.

Já temos bitboards representando uma casa, colunhas, linhas, diagonais. Já temos bitboards para representar as posições das peças no tabuleiro. Já temos bitboards para representar as posições dos peões no tabuleiro. Já temos bitboards com todas as casas ocupadas. Já temos bitboards com todas as casas atacadas. Hoje, introduzimos um conjunto inteiramente novo de bitboards. Os “Raios”. Observe:

image

Para uma determinada casa (square) no tabuleiro, há:

  • um bitboard com as casas na direção N (E5, E6, E7, E8 para E4);
  • um bitboard com as casas na direção S (E3, E2, E1 para E4);
  • um bitboard com as casas na direção W (D4, C4, B4, A4 para E4);
  • um bitboard com as casas na direção E (F4, G4, H4 para E4);
  • … você pegou a idéia.

Esses bitboards têm diversas aplicações em nosso código. Para representar os mesmos, eis um novo tipo: Rays.

1 public struct Rays 2 { 3 Square origin; 4 public Rays(Square origin) : this() { this.origin = origin; } 5 6 public Bitboard N { get { return masksN[origin]; } } 7 public Bitboard S { get { return masksS[origin]; } } 8 public Bitboard E { get { return masksE[origin]; } } 9 public Bitboard W { get { return masksW[origin]; } } 10 public Bitboard SE { get { return masksSE[origin]; } } 11 public Bitboard SW { get { return masksSW[origin]; } } 12 public Bitboard NE { get { return masksNE[origin]; } } 13 public Bitboard NW { get { return masksNW[origin]; } } 14 15 #region static 16 static Bitboard[] masksN = new Bitboard[64]; 17 static Bitboard[] masksS = new Bitboard[64]; 18 static Bitboard[] masksE = new Bitboard[64]; 19 static Bitboard[] masksW = new Bitboard[64]; 20 static Bitboard[] masksSE = new Bitboard[64]; 21 static Bitboard[] masksNE = new Bitboard[64]; 22 static Bitboard[] masksNW = new Bitboard[64]; 23 static Bitboard[] masksSW = new Bitboard[64]; 24 25 static Rays() 26 { 27 for (Square sq = 0; sq < 64; sq++) 28 { 29 masksN[sq] = sq.File.AsBoard.Shift(sq.Rank, 0) 30 .Except(sq); 31 masksS[sq] = sq.File.AsBoard.Shift(sq.Rank - 7, 0) 32 .Except(sq); 33 34 masksE[sq] = sq.Rank.AsBoard.Shift(0, sq.File) 35 .Except(sq); 36 masksW[sq] = sq.Rank.AsBoard.Shift(0, sq.File - 7) 37 .Except(sq); 38 39 masksNE[sq] = sq.DiagonalNE.AsBoard 40 .Shift(sq.Rank, sq.Rank).Except(sq); 41 masksSW[sq] = sq.DiagonalNE.AsBoard 42 .Shift(sq.Rank - 7, sq.Rank - 7).Except(sq); 43 44 masksNW[sq] = sq.DiagonalNW.AsBoard 45 .Shift(sq.Rank, -sq.Rank).Except(sq); 46 masksSE[sq] = sq.DiagonalNW.AsBoard 47 .Shift(sq.Rank - 7, 7 - sq.Rank).Except(sq); 48 } 49 } 50 #endregion 51 }

A lógica aqui foi muito simples. No construtor estático, pré-calculamos todos os bitboards correspondentes as diversas direções. Para isso, utilizamos os Bitboard que possuímos (não era assim, eu usava um bocado de loops aqui. o @juanplopes que retirou os loops colocando no lugar shifts com bitboards existentes).

Otimizando a geração de movimentos para Bispo e torre, usando Rays

Novos bitboards, possibilidades de otimizações. Basicamente, há a possibilidade de substituir loops mais “pesados” por operações binárias (novamente, essas otimizações são do @juanplopes).

Eis a nova versão da geração do MoveBitboard para um bispo (Bishop.cs):

1 public Bitboard GetMoveBoard 2 (Square from, Bitboard friends, Bitboard enemies) 3 { 4 var allpieces = friends.And(enemies); 5 var result = Bitboard.Empty.And(from.DiagonalNW, from.DiagonalNE); 6 7 return result.Except(from, friends, 8 from.RayTo.NE.Intersect(allpieces).LowestSquare.RayTo.NE, 9 from.RayTo.NW.Intersect(allpieces).LowestSquare.RayTo.NW, 10 from.RayTo.SE.Intersect(allpieces).HighestSquare.RayTo.SE, 11 from.RayTo.SW.Intersect(allpieces).HighestSquare.RayTo.SW); 12 }

Compare com o código apresentado na Parte 8. E perceba a melhoria!

Eis o código para geração do Movebitboard para a torre (Rook.cs):

1 public Bitboard GetMoveBoard 2 (Square from, Bitboard friends, Bitboard enemies) 3 { 4 var allpieces = friends.And(enemies); 5 var result = Bitboard.Empty.And(from.File, from.Rank); 6 7 return result.Except(from, friends, 8 from.RayTo.N.Intersect(allpieces).LowestSquare.RayTo.N, 9 from.RayTo.E.Intersect(allpieces).LowestSquare.RayTo.E, 10 from.RayTo.S.Intersect(allpieces).HighestSquare.RayTo.S, 11 from.RayTo.W.Intersect(allpieces).HighestSquare.RayTo.W); 12 }

Compare com o código apresentado na Parte 7.

Bonito!

Identificando bloqueios de ataque

Um dos lances mais bacanas do Xadrez é o “cheque descoberto”. Na prática, consiste em mover uma peça que estava bloqueando um ataque direto ao rei. Verifique o código para geração do bitboard com a posição das peças que estão fazendo bloqueio para um ataque diagonal direto a uma casa (Side.cs):

1 public Bitboard GetBlockersToDiagonalAttacks 2 (Square target, Bitboard enemies) 3 { 4 var allpieces = enemies | Occupation; 5 var blockers = Rules.For<Bishop>().GetMoveBoard 6 (target, Bitboard.Empty, allpieces); 7 8 blockers = blockers & 9 (_King.Locations | Rooks.Locations | 10 Knights.Locations | Pawns.Locations); 11 12 allpieces = allpieces & ~blockers; 13 var checkers = Rules.For<Bishop>().GetMoveBoard( 14 target, Bitboard.Empty, allpieces); 15 16 checkers = checkers & (Bishops.Locations | 17 Queens.Locations); 18 19 var rays = new Rays(target); 20 var ne = rays.NE; 21 if ((ne & checkers) == 0) 22 blockers &= ~ne; 23 24 var nw = rays.NW; 25 if ((nw & checkers) == 0) 26 blockers &= ~nw; 27 28 var se = rays.SE; 29 if ((se & checkers) == 0) 30 blockers &= ~se; 31 32 var sw = rays.SW; 33 if ((sw & checkers) == 0) 34 blockers &= ~sw; 35 36 return blockers; 37 }

O que ocorre aqui? Perceba:

  1. Gero um bitboard com todas as peças (enemies | Occupation);
  2. Utilizo o artifício de assumir que a casa atacada possui um bispo (ataque diagonal) e gero um bitboard com os movimentos desse bispo;
  3. Do bitboard resultante, mantenho apenas ligados os bits de peças que são possíveis bloqueadoras para ataques diagonais (Rei, Torre, Cavalos e Peões);
  4. Gero um novo MoveBitboard para nosso “bispo imaginário”, dessa vez, retirando todos os “possíveis bloqueadores”;
  5. Desse novo bitboard, mantenho ligadas apenas casas correspondentes a peças de ataque diagonal (Bispo e dama);
  6. Para cada direção, verifico se há pessas “atacantes”. Se não houver, retiro os “possíveis bloqueadores” presentes naquela direção;
  7. Retorno o bitboard com os bloqueadores que resitiram aos testes.

É bom esse bitboard! Alegre

Utilizou lógica semelhante para identificar bloqueadores horizontais e verticais (straight blockers). Verifique:

 

1 public Bitboard GetBlockersToStraightAttacks 2 (Square target, Bitboard enemies) 3 { 4 var allpieces = enemies | Occupation; 5 var blockers = Rules.For<Rook>() 6 .GetMoveBoard(target, Bitboard.Empty, allpieces); 7 blockers = blockers & (_King.Locations | Bishops.Locations | 8 Knights.Locations | Pawns.Locations); 9 10 allpieces = allpieces & ~blockers; 11 var checkers = Rules.For<Rook>() 12 .GetMoveBoard(target, Bitboard.Empty, allpieces); 13 checkers = checkers & (Rooks.Locations | Queens.Locations); 14 15 var rayTo = target.RayTo; 16 var n = rayTo.N; 17 if ((n & checkers) == 0) 18 blockers &= ~n; 19 20 var s = rayTo.S; 21 if ((s & checkers) == 0) 22 blockers &= ~s; 23 24 var e = rayTo.E; 25 if ((e & checkers) == 0) 26 blockers &= ~e; 27 28 var w = rayTo.W; 29 if ((w & checkers) == 0) 30 blockers &= ~w; 31 32 return blockers; 33 }

Bom .. por hoje, era isso

Smiley piscando