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

Escrevendo um Engine para Xadrez – Parte 11 – Mais Bitboards, Xeques e Escapadas

Tempo de leitura: 6 minutos

Olá pessoal, tudo certo!?

Hoje vou tratar de dois aspectos importantes de nossa engine:

  1. Gerar listas de movimentos de ataque ao rei (o Xeque);
  2. Gerar listas de movimentos para escapes do rei (fugir do xeque).

Todo o código foi escrito e coberto por uma boa quantidade de testes. Em um primeiro momento, me preocupei em adicionar as funcionalidades. Enquanto escrevia esse post percebi diversas oportunidades de refactoring e algum redesign.

Por favor, se desejar colaborar com o projeto, pegue o código fonte no GitHub (https://github.com/ElemarJR/StrongChess). Se você não se sentir confotável escrevendo código ou fazendo refactorings, escreva testes. Teste a “usabilidade” do código, dê seu feedback. Se encontrar algum erro, entre em contato que terei prazer em fazer correções. Github está aí para ter repositórios clonados, ampliados e combinados!

Minhas quebras exóticas de linha ocorrem por causa do layout do blog (No código fonte está diferente)

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:

Identificando o caminho da dama, do bispo e da torre – mais Bitboards

Bitboards são estrutura de dados extremamente poderosas que conseguem “responder” questões importantes a respeito do tabuleiro sem que sejam necessários loops ou condicionais. Se você está chegando agora, recomendo fortemente dar uma olhada na Parte 1 onde explico um pouco do conceito.

Há bitboards que são gerados conforme a condição do jogo (dinâmicos) e outros que podem ser gerados há qualquer momento (estáticos). Esses últimos são úteis para facilitar operações de consulta. Começo mostrando um conjunto todo novo que passou a incorprar nossa engine. Observe:

1 using System; 2 using System.Collections.Generic; 3 using System.Linq; 4 using System.Text; 5 6 namespace StrongChess.Model 7 { 8 public struct AttackPath : IBoardUnit 9 { 10 public Bitboard AsBoard 11 { 12 get { return _AttackPaths[(int)From, (int)To]; } 13 } 14 15 public bool IsValid 16 { 17 get 18 { 19 return 20 From.File == To.File || From.Rank == To.Rank || 21 From.RayTo.NE.Contains(To) || 22 From.RayTo.NW.Contains(To) || 23 To.RayTo.NE.Contains(From) || 24 To.RayTo.NW.Contains(From); 25 } 26 } 27 28 public Square From { get; private set; } 29 public Square To { get; private set; } 30 31 public AttackPath(Square from, Square to) 32 : this() 33 { 34 From = from; 35 To = to; 36 } 37 38 static Bitboard[,] _AttackPaths = new Bitboard[64, 64]; 39 static AttackPath() 40 { 41 Square from, to; 42 for (int i = 0; i < 64; i++) 43 for (int j = 0; j < 64; j++) 44 { 45 if (i < j) 46 { from = i; to = j; } 47 else 48 { from = j; to = i; } 49 50 AttackMasks f = new AttackMasks(from); 51 AttackMasks t = new AttackMasks(to); 52 53 if (from.Rank == to.Rank) 54 _AttackPaths[i, j] = from.RayTo.E.Intersect(to.RayTo.W); 55 else if (from.File == to.File) 56 _AttackPaths[i, j] = from.RayTo.N.Intersect(to.RayTo.S); 57 else if (from.RayTo.NE.Contains(to)) 58 _AttackPaths[i, j] = from.RayTo.NE.Intersect(to.RayTo.SW); 59 else 60 _AttackPaths[i, j] = from.RayTo.NW.Intersect(to.RayTo.SE); 61 } 62 } 63 } 64 }

Essa estrutura, muito simples, recebe em seu construtor dois Squares. A propriedade IsValid verifica se as duas Squares estão na mesma linha, coluna ou diagonal, retornando verdadeiro em caso positivo.

O construtor estático inicia uma coleção de bitboards com todas as combinações From e To. Todos os caminhos para squares na mesma linha, coluna ou diagonal ficam ligados. Todas as combinações From/To inválidas resultam em um bitboard vazio.

Mais adiante, você perceberá que uso esses bitboards para identificar peças (blockers) que se encontrem entre um bispo, torre ou dama e uma peça atacada.

Xeque ao rei

Entre os métodos que foram incluídos para a struct Side (verifique o post passado) estão alguns que geram movimentos que resultem em xeque ao rei adversário. Observe:

1 public IEnumerable<Move> GetCheckMoves 2 (Side opponent, Square? enpassant) 3 { 4 return 5 GetDirectAttackMoves 6 (opponent.KingLocation, opponent.Occupation, enpassant) 7 .Union(GetDiscoveredAttackMoves 8 (opponent.KingLocation, opponent.Occupation, enpassant)); 9 }

Esse método devolve uma “união” entre duas listas de movimentos:

  1. A primeira, gerada pelo método GetDirectAttackMoves, retorna a lista de movimentos das peças disponíveis para atacar a casa especificada.
  2. A segunda, gerada pelo método GetDiscoverdAttackMoves, verifica movimentos de peças que “descobrem” um ataque pela remoção de bloqueios entre uma dama, bispo ou torre e a casa especificada.

Vejamos o primeiro método. Observe:

1 public IEnumerable<Move> GetDirectAttackMoves 2 (Square target, Bitboard enemies, Square? enpassant = null, 3 bool includeKingAttacks = false) 4 { 5 var t = target.AsBoard; 6 var notblockers = ~(this.Occupation | enemies); 7 Bitboard pawnsFilterTo; 8 if (this.IsWhite) 9 pawnsFilterTo = t.Shift(-1, -1).And(t.Shift(-1, 1)); 10 else 11 pawnsFilterTo = t.Shift(1, -1).And(t.Shift(1, 1)); 12 13 var result = Pawns.GetCaptures 14 (enemies, Bitboard.Full, pawnsFilterTo, enpassant) 15 .Union(Pawns.GetMovesOneSquareForward 16 (notblockers, Bitboard.Full, pawnsFilterTo)) 17 .Union(Pawns.GetMovesTwoSquaresForward 18 (notblockers, Bitboard.Full, pawnsFilterTo)) 19 ; 20 21 result = result 22 .Union( 23 Queens.GetDirectAttackMoves(target, Occupation, enemies)) 24 .Union( 25 Bishops.GetDirectAttackMoves(target, Occupation, enemies)) 26 .Union( 27 Knights.GetDirectAttackMoves(target, Occupation, enemies)) 28 .Union( 29 Rooks.GetDirectAttackMoves(target, Occupation, enemies)); 30 31 if (includeKingAttacks) 32 result = result.Union( 33 _King.GetDirectAttackMoves(target, Occupation, enemies)); 34 35 return result; 36 }

 

Esse método é bem simples. Ele começa verificando os lances de peão que gerariam ataque a casa especificada. Observe que os peões que são movimentados são selecionados conforme a cor das peças. Logo depois, utilizo os métodos de ataque direto desenvolvidos para Pieces (veja post passado) para “somar” os ataques das demais peças. Há um parâmetro opcional para dizer se ataques do rei devem ser incluídos (em caso de ataques ao rei adversário, seria um movimento inválido).

Para os ataques descobertos, um novo método “unificador”, observe:

1 public IEnumerable<Move> GetDiscoveredAttackMoves 2 (Square target, Bitboard enemies, Square? enpassant) 3 { 4 return GetDiscoveredDiagonalAttackMoves 5 (target, enemies, enpassant) 6 .Union(GetDiscoverdStraightAttackMoves 7 (target, enemies, enpassant)); 8 }

Esse método “unifica” os ataques descobertos para peças de ataque diagonal (bispos e dama) e para peças de ataque por linha/coluna (torre e damas). Ataques descobertos são aqueles gerados por um movimento de outra peça que esteja “no caminho” entre a peça atacante e a casa atacada. Observe o método de ataques descobertos de bispo e dama:

1 public IEnumerable<Move> GetDiscoveredDiagonalAttackMoves 2 (Square target, Bitboard enemies, Square? enpassant = null) 3 { 4 var filterFrom = GetBlockersToDiagonalAttacks 5 (target, enemies); 6 7 var result = Knights.GetMoves 8 (Occupation, enemies, filterFrom, Bitboard.Full) 9 .Union(Rooks.GetMoves( 10 Occupation, enemies, filterFrom, Bitboard.Full)) 11 ; 12 13 if ((_King.Locations & filterFrom) > 0) 14 { 15 var kl = KingLocation; 16 int offset = target - kl; 17 Bitboard filterTo = Bitboard.Full; 18 19 if (offset % 9 == 0) 20 filterTo = ~(kl.AsBoard.Shift(1, 1) | 21 kl.AsBoard.Shift(-1, -1)); 22 else if (offset % 7 == 0) 23 filterTo = ~(kl.AsBoard.Shift(1, -1) | 24 kl.AsBoard.Shift(-1, 1)); 25 26 result = result.Union(_King.GetMoves(Occupation, 27 enemies, filterFrom, filterTo)); 28 } 29 30 if ((Pawns.Locations & filterFrom) > 0) 31 { 32 Bitboard notblockers = ~(Occupation | enemies); 33 result = result.Union( 34 Pawns.GetMovesOneSquareForward(notblockers, filterFrom, 35 Bitboard.Full)).Union( 36 Pawns.GetMovesTwoSquaresForward(notblockers, filterFrom, 37 Bitboard.Full)).Union( 38 Pawns.GetCaptures(enemies, filterFrom, Bitboard.Full, 39 enpassant)); 40 } 41 42 return result; 43 }

Perceba:

  • Já no início do método, identifico onde estão os “bloqueios” para ataques dos bispos e dama (esse método foi mostrado no final do post anterior).
  • Serão movimentos para cheque descoberto, todos os movimentos de cavalo e de torre (invariavelmente, sairiam da diagonal). Logo, todos os cavalos e torres sinalizados como bloqueadores têm seus movimentos computados.
  • Se o rei estiver “no caminho”, também deverá ser deslocado. Tomo o cuidado de criar um filtro das casas dessa diagonal para que o rei, mesmo movimentado, não continue bloqueando o ataque.
  • Por fim, se houverem peões, retorno movimentos para esses peões também.

Utilizo lógica bem semelhante para computar os ataques descobertos para damas e torres. Observe:

1 public IEnumerable<Move> GetDiscoverdStraightAttackMoves 2 (Square target, Bitboard enemies, Square? enpassant = null) 3 { 4 var filterFrom = GetBlockersToStraightAttacks(target, enemies); 5 6 var result = Knights.GetMoves 7 (Occupation, enemies, filterFrom, Bitboard.Full) 8 .Union( 9 Bishops.GetMoves(Occupation, enemies, filterFrom, 10 Bitboard.Full)); 11 12 if ((_King.Locations & filterFrom) > 0) 13 { 14 Bitboard filterTo; 15 if (KingLocation.File == target.File) 16 filterTo = ~(target.File.AsBoard); 17 else 18 filterTo = ~(target.Rank.AsBoard); 19 20 result = result.Union( 21 _King.GetMoves(Occupation, enemies, filterFrom, filterTo)); 22 } 23 24 if ((Pawns.Locations & filterFrom) > 0) 25 { 26 Bitboard notblockers = ~(Occupation | enemies); 27 if ((Pawns.Locations & target.File.AsBoard) > 0) 28 result = result.Union( 29 Pawns.GetCaptures( 30 enemies, 31 Pawns.Locations & target.File.AsBoard, 32 Bitboard.Full, enpassant)); 33 34 if ((Pawns.Locations & target.Rank.AsBoard) > 0) 35 result = result.Union( 36 Pawns.GetCaptures( 37 enemies, 38 Pawns.Locations & target.Rank.AsBoard, 39 Bitboard.Full, enpassant)) 40 .Union(Pawns.GetMovesOneSquareForward 41 (notblockers, Pawns.Locations & target.Rank.AsBoard, 42 Bitboard.Full)) 43 .Union 44 (Pawns.GetMovesTwoSquaresForward 45 (notblockers, Pawns.Locations & target.Rank.AsBoard, 46 Bitboard.Full)); 47 } 48 return result; 49 }

Minhas quebras exóticas de linha ocorrem por causa do layout do blog (No código fonte está diferente)

Escapando do Xeque

Já conseguimos gerar os movimentos de ataque ao rei. Agora, vamos ver como gerar uma lista de movimentos escapando do xeque.

Começamos com o nosso “método unificador”:

1 public IEnumerable<Move> GetCheckEvasionMoves 2 (Side enemy, Square? enpassant = null) 3 { 4 return 5 GetCheckEvasionKingMoves(enemy) 6 .Union(GetCheckEvasionPinningPiecesMoves 7 (enemy, enpassant)); 8 }

Esse método também está em Side. A lógica é simples: para escapar de um cheque, o rei pode se mover ou adicionar um bloqueio ao ataque.  Comecemos pelo primeiro tipo de escapada:

1 public IEnumerable<Move> GetCheckEvasionKingMoves(Side enemy) 2 { 3 var alternatives = Rules.For<King>().GetMoveBoard 4 (KingLocation, this.Occupation, enemy.Occupation); 5 foreach (var sq in alternatives.Squares) 6 if (!enemy.Attacks(sq, this.Occupation)) 7 yield return new Move(KingLocation, sq); 8 }

Tudo começa gerando um bitboard com as casas candidatas para o rei. Para cada casa, verfica-se se esta não é atacada por uma peça adversária. Não sendo, gera-se um movimento do rei para aquela casa.

Escapar do cheque por bloqueio é um pouco mais complicado. Observe:

1 public IEnumerable<Move> GetCheckEvasionPinningPiecesMoves 2 (Side enemy, Square? enpassant = null) 3 { 4 var black = enemy; var white = this; 5 if (this.IsBlack) { black = this; white = enemy; } 6 Bitboard checkers = KingLocation.AttackedFrom(white, black) & 7 enemy.Occupation; 8 9 if (checkers.BitCount != 1) 10 return Enumerable.Empty<Move>(); 11 if ((checkers & Knights.Locations) != 0) 12 return Enumerable.Empty<Move>(); 13 14 Bitboard path = 15 new AttackPath(checkers.HighestSquare, KingLocation).AsBoard 16 | checkers.HighestSquare.AsBoard; 17 18 Bitboard notblockers = ~(this.Occupation | enemy.Occupation); 19 20 return Knights.GetMoves 21 (this.Occupation, enemy.Occupation, Bitboard.Full, path) 22 .Union 23 (Bishops.GetMoves(this.Occupation, enemy.Occupation, 24 Bitboard.Full, path)) 25 .Union 26 (Rooks.GetMoves(this.Occupation, enemy.Occupation, 27 Bitboard.Full, path)) 28 .Union 29 (Queens.GetMoves(this.Occupation, enemy.Occupation, 30 Bitboard.Full, path)) 31 .Union 32 (Pawns.GetMovesTwoSquaresForward(notblockers, 33 Bitboard.Full, path)) 34 .Union 35 (Pawns.GetMovesOneSquareForward(notblockers, 36 Bitboard.Full, path)) 37 .Union 38 (Pawns.GetCaptures(enemy.Occupation, Bitboard.Full, 39 path, enpassant)); 40 }

No início do método, obtenho um bitboard com todas as peças (de ambos os lados) que estão atacando a posição do rei. Usando uma combinação, deixo ligadas apenas as posições de peças adversárias.

Se houver mais que uma peça atacando o rei em um dado momento, não há bloqueios possíveis. Da mesma fora, para ataques de cavalo.

Utilizo os bitboards que apresentei no início desse post para gerar as casas que são bloqueios possíveis. Adiciono a essas casas a posição da atacante (para captura). Depois, gero todos os movimentos que colocariam uma peça em uma daquelas casas.

Por hoje, era isso.

Smiley piscando

0 Comentários

  1. Dublado 6 anos ago says:

    Seu blog está entre os melhores sobre o tema abordado nele, parabéns

    Responder
  2. Fernando Tenorio 5 anos ago says:

    Que sorte de ter achado esse blog, posts de alta qualidade!

    Há algum tempo atrás eu me aventurei em escrever uma engine em Java (ia passar pra C depois). Cheguei a implementar os bitboards de movimento das peças, mas parei por aí... quem sabe agora não pego novamente!

    É uma área de programação fascinante, as engines Top de hoje espancam qualquer GM (Houdini, Rybka 4, Stock Fish, etc...).

    Parabéns, e espero que continue com essa série!

    Responder
  3. Moises Antonio de Barros 1 ano ago says:

    Muito bom seu blog. Cheguei até ele porque queria aprender a programar em C++ e sempre fui fascinado a entender o código que está por traz de uma Engine de Xadrez. Gostaria de saber como você testa seus códigos. Você compila e testa em um software de terceiro ou tem um simulador? Você não teria uma fração do código que funcione como Engine para que eu possa compilar e testar e a partir deste ir entendendo C++ e o código por traz das Engines. Muito obrigado e parabéns pelo blog.

    Responder

Trackbacks para este post

  1. Tweets that mention Escrevendo um Engine para Xadrez – Parte 11 – Mais Bitboards, Xeques e Escapadas « Elemar DEV -- Topsy.com