Move Generation: Forks

[Gerd Isenberg]

Actually I think one slits one's own wrists as a pre-emptive strike to prevent one's own head from exploding when thinking about this stuff.

Hey, that is quite simple algebra, I guess. You are the professor

Academic or math guys usually write it in much more elegant and shorter form of algebra, may be you understand that better than my naive expressions.

You have 8 direction sets (eg. from hanging pieces and king) and there are 7+6+5+4+3+2+1 = (n*n - n)/2 = 28 combinations for distinct intersections of all pairs of eight sets. So the union of all those intersections, where for instance a queen may fork two hanging pieces (including checking the king), requires 28 ands and 27 ors at the first glance, which can be reduced to 7+12 ops as mentioned.

Still some work, not to mention the eight kogge-stone fills...

[Gerd Isenberg]

You have 8 direction sets (eg. from hanging pieces and king) and there are 7+6+5+4+3+2+1 = (n*n - n)/2 = 28 combinations for distinct intersections of all pairs of eight sets. So the union of all those intersections, where for instance a queen may fork two hanging pieces (including checking the king), requires 28 ands and 27 ors at the first glance, which can be reduced to 7+12 ops as mentioned.

Still some work, not to mention the eight kogge-stone fills...

Rather than eight directions one may better traverse hanging pieces (if any) and king, to intersect their respective magic bitboards attacksets pairwise for a final union-set of fork-targets for the attacking queen. Considering bishop-attacks of each hanging rook, rook-attacks from each hanging bishop and queen-attacks from either king and each hanging knight (or even pawns).

Anyway, for both approaches, the

Code: Select all

n * (n - 1) - 1  to 
3 * (n - 1) - 2  and/or ops

reduction by distributive law is O(n^2) to O(n) and pays off for n > 2.