Move Generation: Forks

[Edsel Apostol]

I have another crazy idea I wanted to try. I will include piece forks in my staged move generation. Has anyone done this before? I'm thinking of doing it like this:

For the rooks:

Code: Select all

u64 targetPieces= (enemy pieces to consider in the fork).
u64 targetMask = (fillWest(targetPieces, occupied) & fillEast(targetPieces, occupied)) | (fillNorth(targetPieces, occupied) & fillSouth(targetPieces, occupied));
u64 pieceMask = WhiteRooks;
while(pieceMask){
    int from = popFirstBit(&pieceMask);
    u64 moveMask = targetMask & RookMoves(from, occupied);
    .....
}

It's basically the same with pawns, bishops and queens but I can't think of an easy way for knights. Any clever ideas?

[mcostalba]

I have another crazy idea I wanted to try. I will include piece forks in my staged move generation. Has anyone done this before? I'm thinking of doing it like this:

For the rooks:

Code: Select all

u64 targetPieces= (enemy pieces to consider in the fork).
u64 targetMask = (fillWest(targetPieces, occupied) & fillEast(targetPieces, occupied)) | (fillNorth(targetPieces, occupied) & fillSouth(targetPieces, occupied));
u64 pieceMask = WhiteRooks;
while(pieceMask){
    int from = popFirstBit(&pieceMask);
    u64 moveMask = targetMask & RookMoves(from, occupied);
    .....
}

It's basically the same with pawns, bishops and queens but I can't think of an easy way for knights. Any clever ideas?

Sorry but I don't understand what it means piece forks. Possibly I could understand that if I would know what function fillWest() does

[Edsel Apostol]

I have another crazy idea I wanted to try. I will include piece forks in my staged move generation. Has anyone done this before? I'm thinking of doing it like this:

For the rooks:

Code: Select all

u64 targetPieces= (enemy pieces to consider in the fork).
u64 targetMask = (fillWest(targetPieces, occupied) & fillEast(targetPieces, occupied)) | (fillNorth(targetPieces, occupied) & fillSouth(targetPieces, occupied));
u64 pieceMask = WhiteRooks;
while(pieceMask){
    int from = popFirstBit(&pieceMask);
    u64 moveMask = targetMask & RookMoves(from, occupied);
    .....
}

It's basically the same with pawns, bishops and queens but I can't think of an easy way for knights. Any clever ideas?

Sorry but I don't understand what it means piece forks. Possibly I could understand that if I would know what function fillWest() does

Hi Marco,

Here's the definition:

http://en.wikipedia.org/wiki/Fork_(chess)

And here's the related fill functions from chess programming wiki:

http://chessprogramming.wikispaces.com/Dumb7Fill
http://chessprogramming.wikispaces.com/ ... +Algorithm
http://chessprogramming.wikispaces.com/ ... ubtraction

[Gerd Isenberg]

I have another crazy idea I wanted to try. I will include piece forks in my staged move generation. Has anyone done this before? I'm thinking of doing it like this:

For the rooks:

Code: Select all

u64 targetPieces= (enemy pieces to consider in the fork).
u64 targetMask = (fillWest(targetPieces, occupied) & fillEast(targetPieces, occupied)) | (fillNorth(targetPieces, occupied) & fillSouth(targetPieces, occupied));
u64 pieceMask = WhiteRooks;
while(pieceMask){
    int from = popFirstBit(&pieceMask);
    u64 moveMask = targetMask & RookMoves(from, occupied);
    .....
}

It's basically the same with pawns, bishops and queens but I can't think of an easy way for knights. Any clever ideas?

Guess you are aware of Knight fork targets. As a precondition you may check whether targets have the same square color than the attacking knights.

[Edsel Apostol]

I have another crazy idea I wanted to try. I will include piece forks in my staged move generation. Has anyone done this before? I'm thinking of doing it like this:

For the rooks:

Code: Select all

u64 targetPieces= (enemy pieces to consider in the fork).
u64 targetMask = (fillWest(targetPieces, occupied) & fillEast(targetPieces, occupied)) | (fillNorth(targetPieces, occupied) & fillSouth(targetPieces, occupied));
u64 pieceMask = WhiteRooks;
while(pieceMask){
    int from = popFirstBit(&pieceMask);
    u64 moveMask = targetMask & RookMoves(from, occupied);
    .....
}

It's basically the same with pawns, bishops and queens but I can't think of an easy way for knights. Any clever ideas?

Guess you are aware of Knight fork targets. As a precondition you may check whether targets have the same square color than the attacking knights.

Thanks Gerd. That was the one I'm looking for. I am not aware of it just until now. Good job with the wiki. I get a lot of ideas from there.

[mcostalba]

Here's the definition:

http://en.wikipedia.org/wiki/Fork_(chess)

ahaaa ok _that_ fork !

Sorry for the dumb question...and thanks for the answer.

[Edsel Apostol]

I have another crazy idea I wanted to try. I will include piece forks in my staged move generation. Has anyone done this before? I'm thinking of doing it like this:

For the rooks:

Code: Select all

u64 targetPieces= (enemy pieces to consider in the fork).
u64 targetMask = (fillWest(targetPieces, occupied) & fillEast(targetPieces, occupied)) | (fillNorth(targetPieces, occupied) & fillSouth(targetPieces, occupied));
u64 pieceMask = WhiteRooks;
while(pieceMask){
    int from = popFirstBit(&pieceMask);
    u64 moveMask = targetMask & RookMoves(from, occupied);
    .....
}

It's basically the same with pawns, bishops and queens but I can't think of an easy way for knights. Any clever ideas?

Here goes my code for generating forks, pawns and knights for now:

Code: Select all

// shift the parameter b with i places to the left
uint64 shiftLeft(uint64 b, uint32 i) {return (b << i);}

// shift the parameter b with i places to the right
uint64 shiftRight(uint64 b, uint32 i) {return (b >> i);}

static uint64 (*ShiftPtr[])(uint64, uint32) = {&shiftLeft, &shiftRight};

/* this generates non tactical non checking knight and pawn forking moves only */
void genForks(const position_t *pos, sort_t *sort) {
    static const int Shift[] = {9, 7};
    uint64 pc_bits, mv_bits, pawns, xpawns, enemy_pawnattacks, mask, dcc;
    int from, to, side, xside;

    ASSERT(pos != NULL);
    ASSERT(sort != NULL);

    sort->size = 0;
    side = pos->side;
    xside = side^1;
    pawns = pos->pawns & pos->color[side];
    xpawns = pos->pawns & pos->color[xside];
    dcc = discoveredCheckCandidates(pos, side);

    mask = pos->color[xside] & ~pos->kings & ~pos->pawns;
    mask = (((*ShiftPtr[xside])(mask, Shift[xside]) & ~FileABB) & ((*ShiftPtr[xside])(mask, Shift[side]) & ~FileHBB));

    mv_bits = mask & (*ShiftPtr[pos->side])(pawns, 8) & ~pos->occupied;
    while (mv_bits) {
        to = popFirstBit(&mv_bits);
        pc_bits = (PawnMoves[to][pos->side^1] & pawns) & ~dcc;
        ASSERT(bitCnt(pc_bits) <= 1);
        while (pc_bits) {
            from = popFirstBit(&pc_bits);
            sort->list[sort->size++].m = GenOneForward(from, to);
        }
    }
    mv_bits = mask & Rank4ByColorBB[pos->side] & (*ShiftPtr[pos->side])(pawns, 16)
    & (*ShiftPtr[pos->side])(~pos->occupied, 8) & ~pos->occupied;
    while (mv_bits) {
        to = popFirstBit(&mv_bits);
        pc_bits = pawns & Rank2ByColorBB[pos->side] & FileMask[to] & ~dcc;
        ASSERT(bitCnt(pc_bits) <= 1);
        while (pc_bits) {
            from = popFirstBit(&pc_bits);
            sort->list[sort->size++].m = GenTwoForward(from, to);
        }
    }

    enemy_pawnattacks = (((*ShiftPtr[xside])(xpawns, Shift[xside]) & ~FileABB) | ((*ShiftPtr[xside])(xpawns, Shift[side]) & ~FileHBB));
    mask = knightForkTargetSquare(pos->color[xside] & (pos->queens | pos->rooks | pos->bishops)) & ~enemy_pawnattacks  & ~pos->occupied;
    pc_bits = pos->knights & pos->color[side] & ~dcc;
    while (pc_bits) {
        from = popFirstBit(&pc_bits);
        mv_bits = KnightMoves[from] & mask;
        while (mv_bits) {
            to = popFirstBit(&mv_bits);
            sort->list[sort->size++].m = GenKnightMove(from, to, getPiece(pos, to));
        }
    }
}

At first I thought that rooks, bishops and queens would be as easy as I've described above, I was wrong. One needs to consider the intersection of all ray attacks. For the masks of rook and bishop, each of them would take 6 and and 5 or bit operations. For queens 28 and and 27 or bit operations. I don't think that or'ing the rook and bishop result is sufficient enough for the queen mask. Is there any better way?

[Gerd Isenberg]

At first I thought that rooks, bishops and queens would be as easy as I've described above, I was wrong. One needs to consider the intersection of all ray attacks. For the masks of rook and bishop, each of them would take 6 and and 5 or bit operations. For queens 28 and and 27 or bit operations. I don't think that or'ing the rook and bishop result is sufficient enough for the queen mask. Is there any better way?

Hanging rooks, knights and the king may be attacked by queen from the four diagonal ray directions. Hanging bishops, knights and the king from four orthogonal rays, you may build the union of all intersections of all 8 ray fills similar to the knight fork algorithm:

Code: Select all

targetD = (rooks   | knights) & ~defended; 
targetO = (bishops | knights) & ~defended; 
forks = 0;
if ( targetD | targetO )
{
   tagetD |= king;
   tagetO |= king;

   o0 = eastOccl(targetD);
   o1 = westOccl(targetD);
   o2 = nortOccl(targetD);
   o3 = soutOccl(targetD);

   d0 = soWeOccl(targetO);
   d1 = soEaOccl(targetO);
   d2 = noEaOccl(targetO);
   d3 = noWeOccl(targetO);

                        attak  = o0;
   forks  = o1 & atta;  attak |= o1;
   forks |= o2 & atta;  attak |= o2;
   forks |= o3 & atta;  attak |= o3;

   forks |= d0 & atta;  attak |= d0;
   forks |= d1 & atta;  attak |= d1;
   forks |= d2 & atta;  attak |= d2;
   forks |= d3 & atta;  
}

[Gerd Isenberg]

For queens 28 and and 27 or bit operations. I don't think that or'ing the rook and bishop result is sufficient enough for the queen mask. Is there any better way?

Application of the distributive law from 55 to 19 ops:

Code: Select all

forkTargets =
  (a1 & a0)

| (a2 & a1)
| (a2 & a0)

| (a3 & a2)
| (a3 & a1)
| (a3 & a0)

| (a4 & a3)
| (a4 & a2)
| (a4 & a1)
| (a4 & a0)

| (a5 & a4)
| (a5 & a3)
| (a5 & a2)
| (a5 & a1)
| (a5 & a0)

| (a6 & a5)
| (a6 & a4)
| (a6 & a3)
| (a6 & a2)
| (a6 & a1)
| (a6 & a0)

| (a7 & a6)   
| (a7 & a5)
| (a7 & a4)
| (a7 & a3)
| (a7 & a2)
| (a7 & a1)
| (a7 & a0)

28 ands
27 ors
55 ops

forkTargets =
  (a1 & (                  a0))
| (a2 & (               a1|a0))
| (a3 & (            a2|a1|a0))
| (a4 & (         a3|a2|a1|a0))
| (a5 & (      a4|a3|a2|a1|a0))
| (a6 & (   a5|a4|a3|a2|a1|a0))
| (a7 & (a6|a5|a4|a3|a2|a1|a0))
leaves only
 7 ands
12 ors
19 ops

How does one call for those kind of union sets of all pairwise intersections in set-theory?

[bob]

For queens 28 and and 27 or bit operations. I don't think that or'ing the rook and bishop result is sufficient enough for the queen mask. Is there any better way?

Application of the distributive law from 55 to 19 ops:

Code: Select all

forkTargets =
  (a1 & a0)

| (a2 & a1)
| (a2 & a0)

| (a3 & a2)
| (a3 & a1)
| (a3 & a0)

| (a4 & a3)
| (a4 & a2)
| (a4 & a1)
| (a4 & a0)

| (a5 & a4)
| (a5 & a3)
| (a5 & a2)
| (a5 & a1)
| (a5 & a0)

| (a6 & a5)
| (a6 & a4)
| (a6 & a3)
| (a6 & a2)
| (a6 & a1)
| (a6 & a0)

| (a7 & a6)   
| (a7 & a5)
| (a7 & a4)
| (a7 & a3)
| (a7 & a2)
| (a7 & a1)
| (a7 & a0)

28 ands
27 ors
55 ops

forkTargets =
  (a1 & (                  a0))
| (a2 & (               a1|a0))
| (a3 & (            a2|a1|a0))
| (a4 & (         a3|a2|a1|a0))
| (a5 & (      a4|a3|a2|a1|a0))
| (a6 & (   a5|a4|a3|a2|a1|a0))
| (a7 & (a6|a5|a4|a3|a2|a1|a0))
leaves only
 7 ands
12 ors
19 ops

How does one call for those kind of union sets of all pairwise intersections in set-theory?

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.