Another Sliding Piece Move Generator -> BlockerTable Look

[smatovic]

i am sure someone else tested this before....and my first implementation is slower than magic bitboards...anyway..

The Idea is to compute for every piece and all 8 directions the possible sliding-blockers and check this table against an precomputed AttackTable.

Here some pseudocode:

Code: Select all

BlockerTable[9*64]      // precomputed sliding-blockers
DirectionTable[4096]    // from-to direction table
AttackTables[2*7*64]    // precomputed attack tables

bbBlockersDirection[9]  // BitBoards for dummy and 8 direction-BlockedMap


// *** Move Generator ***

// create blocked map

for every piece do {

    pos = getPiecePos();

    bbBlockersDirection[1]  |= BlockerTable[1*64+pos];
    bbBlockersDirection[2]  |= BlockerTable[2*64+pos];
    bbBlockersDirection[3]  |= BlockerTable[3*64+pos];
    bbBlockersDirection[4]  |= BlockerTable[4*64+pos];
    bbBlockersDirection[5]  |= BlockerTable[5*64+pos];
    bbBlockersDirection[6]  |= BlockerTable[6*64+pos];
    bbBlockersDirection[7]  |= BlockerTable[7*64+pos];
    bbBlockersDirection[8]  |= BlockerTable[8*64+pos];


}

// create moves
for every own piece do {

    from = getPiecePos();

    piece = getPieceType();

    // Get Pseudo-Legal Attacks
    bbTemp  = AttackTables[(som*7*64)+(piece*64)+from];

    // TODO: pawn handling

    
    while( bbTemp )

        to = pop_1st_bit(bbTemp);

        // Legality Attack Test, Test if slider is blocked
        if ( IsSlider?(piece) && ( SetMaskBB[to] & bbBlockersDirection[DirectionTables[from*64+to]] ) )
            continue;

        // make and store move

    }
}

[smatovic]

nevermind...it doesn't work...

[hgm]

I am not sure how exactly this was supposed to work. I know that there is a representation where the 'occupied' information is stored per ray, and you have board-size tables that indicate which 4 rays intersect a square. A change in occupancy then has to be recoded in 4 different rays, in a way very similar to rotated bitboard. The main differene is that in the latter parallel rays are packed into the same machine word. When you don't do that, you can afford much larger boards. This method is therefore frequently used in Xiangqi engines, which need a 9x10 board (and only needs 2 rays per square, as there are no diagonally moving sliders).

In principle this woud work even for 32x32 boards on a 32-bit architecture, but of course to use the occupancy of a ray as the index in a lookup table puts a practical limit on how many bits of the word can be used. But it still can give a speedup over a plain mailbox board scan to simply extract the moves from the rays separately. You would need both BSF and BSB in that case, but this can be avoided by duplicating the occupancy info for the ray in a single word (so you could go to 16x16 boards in 32-bit, or 18x18 actually, since there is no need to store the edge occupancy) in the inverted direction, or using 8 rays through each square (in which case you could go again to 34x34).

Unfortunately Taikyoku Shogi needs 36x36...

So for now I am stuck with the board scan. But this can also be sped up by keeping a count for each square of the number of attacks that is coming from each of the 8 directions, as 3-bit fields in a single word (with still a byte to spare for Knight attacks or similar info). Then you can suppress scans in directions from which there are no listed attacks.