pattern coding in bitboards

PK · Post by PK » Thu Feb 26, 2015 12:00 pm

As some of You may know, currently I am trying to implement some pawn chain knowledge in Rodent. Moreover, I was lucky enough to get some progress, confirmed both by a test match and by finding more correct moves in King's Indian structures.

The only thing that bugs me (pun intended!) is code. It is ugly. It is bloated. It basically looks like a copy-paste of a flow chart diagram - a decision tree that works right now, but may quickly become unmanageable. Below I show one section, two chains and 4 bonuses only. sd is side for which we evaluate, op is the other side, RelSqBb returns a bitboard of a single square relative for the side (i.e. D4,BLACK -> D5).

Code: Select all

if &#40;RelSqBb&#40;E4, sd&#41; & bbPc&#40;p, op, P&#41;) &#123;

   if &#40;RelSqBb&#40;D5, sd&#41; & bbPc&#40;p, op, P&#41; // c6-d5-e4 triad
   && RelSqBb&#40;C6, sd&#41; & bbPc&#40;p, op, P&#41;) &#123;
      if &#40;RelSqBb&#40;D4, sd&#41; & bbPc&#40;p, sd, P&#41;
      && RelSqBb&#40;E3, sd&#41; & bbPc&#40;p, sd, P&#41;)
         mgResult -= bigChainScore;
      else
         mgResult -= smallChainScore;
   &#125;

   if &#40;RelSqBb&#40;F3, sd&#41; & bbPc&#40;p, op, P&#41; // d5-e4-f3 triad
   && RelSqBb&#40;D5, sd&#41; & bbPc&#40;p, op, P&#41;) &#123;
      if &#40;RelSqBb&#40;E3, sd&#41; & bbPc&#40;p, sd, P&#41;) 
         mgResult -= bigChainScore;
      else
         mgResult -= smallChainScore;
   &#125;
&#125;

Now, does any of You know a better way of coding this kind of knowledge? Can it be represented in a better way (I thought about masks and PopCnt, but it cuts off only a couple of lines)? Can this pattern recognition be coded in a way acceptable for Stockfish developers?

mcostalba · Post by **mcostalba** » Thu Feb 26, 2015 12:24 pm

PK wrote:As some of You may know, currently I am trying to implement some pawn chain knowledge in Rodent. Moreover, I was lucky enough to get some progress, confirmed both by a test match and by finding more correct moves in King's Indian structures.

The only thing that bugs me (pun intended!) is code. It is ugly. It is bloated. It basically looks like a copy-paste of a flow chart diagram - a decision tree that works right now, but may quickly become unmanageable. Below I show one section, two chains and 4 bonuses only. sd is side for which we evaluate, op is the other side, RelSqBb returns a bitboard of a single square relative for the side (i.e. D4,BLACK -> D5).
Code: Select all
if &#40;RelSqBb&#40;E4, sd&#41; & bbPc&#40;p, op, P&#41;) &#123;

   if &#40;RelSqBb&#40;D5, sd&#41; & bbPc&#40;p, op, P&#41; // c6-d5-e4 triad
   && RelSqBb&#40;C6, sd&#41; & bbPc&#40;p, op, P&#41;) &#123;
      if &#40;RelSqBb&#40;D4, sd&#41; & bbPc&#40;p, sd, P&#41;
      && RelSqBb&#40;E3, sd&#41; & bbPc&#40;p, sd, P&#41;)
         mgResult -= bigChainScore;
      else
         mgResult -= smallChainScore;
   &#125;

   if &#40;RelSqBb&#40;F3, sd&#41; & bbPc&#40;p, op, P&#41; // d5-e4-f3 triad
   && RelSqBb&#40;D5, sd&#41; & bbPc&#40;p, op, P&#41;) &#123;
      if &#40;RelSqBb&#40;E3, sd&#41; & bbPc&#40;p, sd, P&#41;) 
         mgResult -= bigChainScore;
      else
         mgResult -= smallChainScore;
   &#125;
&#125;
Now, does any of You know a better way of coding this kind of knowledge? Can it be represented in a better way (I thought about masks and PopCnt, but it cuts off only a couple of lines)? Can this pattern recognition be coded in a way acceptable for Stockfish developers?

Well regarding Stockfish developers, I see 2 immediate improvments:

1) Naming is obscure, please use better and clear names that even people not deeply involved with the code can understand

2) Split this evaluation in 2: one for white pieces and another for black. This get rids of all the 'relative' stuff and is also faster. In SF we use templates in this case, so to not duplicate the source. But I suggest to use this approach also in C, at least to start removing cruft and better see possibilities for further improvment.

mcostalba · Post by **mcostalba** » Thu Feb 26, 2015 12:49 pm

I have rewritten your code, using current SF functions.

It would be like this:

Code: Select all

    if (&#40;theirPawns & SQ_C6&#41; && &#40;theirPawns & SQ_D5&#41; && &#40;theirPawns & SQ_E4&#41;)
        mgResult -= &#40;ourPawns & SQ_D4&#41; && &#40;ourPawns & SQ_E3&#41; ? bigChainScore &#58; smallChainScore;

    if (&#40;theirPawns & SQ_D5&#41; && &#40;theirPawns & SQ_E4&#41; && &#40;theirPawns & SQ_F3&#41;)
        mgResult -= &#40;ourPawns & SQ_E3&#41; ? bigChainScore &#58; smallChainScore;

If you have a lot of this formulas, perhaps would make sense to add something more specific.

PK · Post by PK » Thu Feb 26, 2015 2:07 pm

Thank You, this was helpful. BTW, if I propose a chain patch, what would be preconditions for it to be tested? Symmetry (i.e. adding similar queenside code)? Trying one chain at a time?

mcostalba · Post by **mcostalba** » Thu Feb 26, 2015 2:16 pm

mcostalba wrote: If you have a lot of this formulas, perhaps would make sense to add something more specific.

Indeed it is enough to define somewhere

Code: Select all

 const Bitboard BB = 0;

To be able to write (with current SF code):

Code: Select all

if (!(~theirPawns & &#40;BB | SQ_C6 | SQ_D5 | SQ_E4&#41;))
    mgResult -= (~ourPawns & &#40;BB | SQ_D4 | SQ_E3&#41;) ? smallChainScore &#58; bigChainScore;

if (!(~theirPawns & &#40;BB | SQ_D5 | SQ_E4 | SQ_F3&#41;))
    mgResult -= (~ourPawns & SQ_E3&#41; ? smallChainScore &#58; bigChainScore;

Evert · Post by **Evert** » Thu Feb 26, 2015 2:18 pm

I haven't committed any relevant code to disk yet, but I was throwing around some ideas for how to add terms like this in Jazz without producing a load of ad-hoc unmaintainable spaghetti.

The idea I came up with is to have a "database" of patterns, something like this:

Code: Select all

struct &#123;
   bitboard_t wpawn, bpawn, wking, bking;
   int mg, eg;
&#125; pawn_patterns&#91;&#93; = &#123;
   &#123; BB_D4 | BB_E3, BB_C6 | BB_D5 | BB_E4, 0, 0, -big_chain, 0 &#125;,
   &#123; 0,             BB_C6 | BB_D5 | BB_E4, 0, 0, -small_chain, 0 &#125;,
&#125;;

In order for the pattern to match, wpawn and bpawn must match exactly, while the positions of the king must match wking and bking (which may be empty to indicate they are not relevant for this particular pattern). The database is defined once, for white's point of view, and then an equivalent database for black is constructed from it by flipping the board and scores when the evaluation is initialised.

The evaluation code then loops over the database and applies any bonus/penalties that match based on it:

Code: Select all

for &#40;all pawn patterns&#41; &#123;
   if (&#40;pattern.wpawn & wpawn&#41; == pattern.wpawn &&
       &#40;pattern.bpawn & bpawn&#41; == bpawn &&
       (!pattern.bking || &#40;pattern.bking & bking&#41;) && 
       (!pattern.wking || &#40;pattern.wking & wking&#41;)) &#123;
      mg += pattern.mg;
      eg += pattern.eg;
   &#125;
&#125;

but so far this is all just an idea. I haven't experimented with it yet, and in particular I don't know yet if doing it this way will limit how versatile the pattern matching can be. I like the idea of just having one central pattern library that is automatically updated for white and black.

mcostalba · Post by **mcostalba** » Thu Feb 26, 2015 2:24 pm

PK wrote:Thank You, this was helpful. BTW, if I propose a chain patch, what would be preconditions for it to be tested? Symmetry (i.e. adding similar queenside code)? Trying one chain at a time?

The _only_ precondition for your patch to be tested is that you submit the test yourself on fishtest

mcostalba · Post by **mcostalba** » Thu Feb 26, 2015 2:53 pm

The previous solution, although very compact, it is probably a bit too tricky for average user, so in this case I'd prefer to write some helper function more but let the code more easily understandable at first read (all those negations do not easy the reading).

Code readibility is always more valuable than 'elegance' of the solution, so in this case my vote goes for the following:

Code: Select all

if &#40;contains&#40;theirPawns, SQ_C6, SQ_D5, SQ_E4&#41;)
    mgResult -= contains&#40;ourPawns, SQ_D4, SQ_E3&#41; ? bigChainScore &#58; smallChainScore;

if &#40;contains&#40;theirPawns, SQ_D5, SQ_E4, SQ_F3&#41;)
    mgResult -= &#40;ourPawns & SQ_E3&#41; ? bigChainScore &#58; smallChainScore;

Where

Code: Select all

inline bool contains&#40;Bitboard b, Square s1, Square s2&#41; &#123; return &#40;b & s1&#41; && &#40;b & s2&#41;; &#125;
inline bool contains&#40;Bitboard b, Square s1, Square s2, Square s3&#41; &#123; return contains&#40;b, s1, s2&#41; && &#40;b & s3&#41;; &#125;

stegemma · Post by **stegemma** » Thu Feb 26, 2015 4:01 pm

I would suggest you to separate conditions from the if itself:

Code: Select all


bool bE4Test = RelSqBb&#40;E4, sd&#41; & bbPc&#40;p, op, P&#41;;
bool bD5Test = RelSqBb&#40;D5, sd&#41; & bbPc&#40;p, op, P&#41;;
bool bC6Test = RelSqBb&#40;C6, sd&#41; & bbPc&#40;p, op, P&#41;;
...

if &#40;bE4Test&#41; &#123; 
   if ( bD5Test && bC6Test&#41; &#123; 
...

Using macros or functions to handle RelSqBb(...) & bbPc(...), as suggested by others, could help you more again. Using more clear names could help but the method that i've shown is the best that i can find, to let more clear the if structure.

Gerd Isenberg · Post by **Gerd Isenberg** » Thu Feb 26, 2015 8:35 pm

Why not working set-wise for defended defenders in two disjoint directions to get the member (center) of at least triple chains?

Code: Select all

U64 noEaOne &#40;U64 b&#41; &#123;return &#40;b << 9&#41; & notAFile;&#125;
U64 soWeOne &#40;U64 b&#41; &#123;return &#40;b >> 9&#41; & notHFile;&#125;
U64 soEaOne &#40;U64 b&#41; &#123;return &#40;b >> 7&#41; & notAFile;&#125;
U64 noWeOne &#40;U64 b&#41; &#123;return &#40;b << 7&#41; & notHFile;&#125;

U64 defendedDefenders1 &#40;U64 b&#41; &#123;return b & soWeOne&#40;b&#41; & noEaOne&#40;b&#41;;&#125;
U64 defendedDefenders2 &#40;U64 b&#41; &#123;return b & soEaOne&#40;b&#41; & noWeOne&#40;b&#41;;&#125;

Now, if d5 is member of defendedDefenders2(pawnsOfOneColor), you know there is a pawn of the same color on e4 and c6.

pattern coding in bitboards

pattern coding in bitboards

Re: pattern coding in bitboards

Re: pattern coding in bitboards

Re: pattern coding in bitboards

Re: pattern coding in bitboards

Re: pattern coding in bitboards

Re: pattern coding in bitboards

Re: pattern coding in bitboards

Re: pattern coding in bitboards

Re: pattern coding in bitboards