Understanding first rank attack state generation

[kalyan4code]

I am trying to understand how hyperbola quintessence works. While I got to understand how it works for files, diagonals & anti-diagonals and it doesn't work for rooks/queens moving along the ranks. I ended up with Richard Delorme's hqperft project in which he uses following code to generate first rank attack state:

Code: Select all

int generate_rank_attack(int o, int  f) {
	int x, y;
	int b;
	y = 0;
	for (x = f - 1; x >= 0; --x) {
		b = 1 << x;
		y |= b;
		if ((o & b) == b) break;
	}
	for (x = f + 1; x < 8; ++x) {
		b = 1 << x;
		y |= b;
		if ((o & b) == b) break;
	}
	return y;
}

I understood most part of the code except this lines (appearing twice in generate_rank_attack):

Code: Select all

if ((o & b) == b) break;

What is the use of the above if loop conditional?

Many Thanks,
Kalyan

[mar]

since b=1<<x, I guess it's simply a test whether bit #x is set in o

[kalyan4code]

since b=1<<x, I guess it's simply a test whether bit #x is set in o

The question is why to check this condition and when it evaluates to true why break out of the for loop?

[mar]

I assume o is occupancy and f is file, so you or the attack mask first, then if occupancy bit was set, you break out of the loop.
One loop goes to the left, other loop goes to the right. No rocket science.

[kalyan4code]

I assume o is occupancy and f is file, so you or the attack mask first, then if occupancy bit was set, you break out of the loop.
One loop goes to the left, other loop goes to the right. No rocket science.

Thanks Martin. I now understand the if loop conditional check. One more clarification requested:

f is file for sure & but I think o may not be simply occupancy, it's twice each square on the board {0..63} as seen in the initialization of RANK_ATTACKS array below:

Code: Select all

    
     for (x = 0; x < 64; ++x) {
               for (f = 0; f < 8; ++f) {
			RANK_ATTACK[x * 8 + f] = generate_rank_attack(x * 2, f);
		}
    }

I guess that o is used to compute first rank byte array state in generate_rank_attacks(). But why it should be x * 2 and not simply x ?

[mar]

I assume o is occupancy and f is file, so you or the attack mask first, then if occupancy bit was set, you break out of the loop.
One loop goes to the left, other loop goes to the right. No rocket science.

Thanks Martin. I now understood the if loop conditional check. One more clarification requested:

f is file for sure & but I think o may not be simply occupancy, it's twice each square on the board {0..63} as seen in the initialization of RANK_ATTACKS array below:

Code: Select all

    
     for (x = 0; x < 64; ++x) {
               for (f = 0; f < 8; ++f) {
			RANK_ATTACK[x * 8 + f] = generate_rank_attack(x * 2, f);
		}
    }

I guess that o is used to compute first rank byte array state in generate_rank_attacks(). But why it should be x * 2 and not simply x ?

My guess is this is indeed occupancy (all combinations), but simply an optimization to not generate first and last bit (because the loops then terminate naturally)
so *2 is eqivalent to bit shift left, so 0..63 shifted generates occupancy masks with all but leftmost and rightmost bits.

However it's also used to index into RANK_ATTACK for rank x, so I suspect it's some clever representation that's useful later, I'm not quite sure what it's supposed to do.

EDIT: actually I think it can be used for direct lookup, you mask the occupancy to remove 0th a 7th bit and then do a table lookup with file to get rank attack mask. clever! something like RANK_ATTACK[(occupancy & 63*2)*4+file]

I'm not familiar with how hyperbola quintessence works so perhaps Gerd or Richard himself can give you more insight.

(by the way the results of hqperft are actually pretty good performance-wise)

[kalyan4code]

(by the way the results of hqperft are actually pretty good performance-wise)

Appreciation goes out to Richard for hqperft & who ever invented Hyperbola Quintessence! That's one of the reason why I'm looking at hyperbola quintessence.

My guess is this is indeed occupancy (all combinations), but simply an optimization to not generate first and last bit (because the loops then terminate naturally)

I think you are correct. This CPW page is helpful.

[abulmo2]

I
I understood most part of the code except this lines (appearing twice in generate_rank_attack):

Code: Select all

if ((o & b) == b) break;

What is the use of the above if loop conditional?

Many Thanks,
Kalyan

The purpose of this code is to generate an attack mask containing empty squares and the first occupied squares. As you cannot move or capture beyond occupied squares, the loop breaks when an occupied square has been found.

[kalyan4code]

I
I understood most part of the code except this lines (appearing twice in generate_rank_attack):

Code: Select all

if ((o & b) == b) break;

What is the use of the above if loop conditional?

Many Thanks,
Kalyan

The purpose of this code is to generate an attack mask containing empty squares and the first occupied squares. As you cannot move or capture beyond occupied squares, the loop breaks when an occupied square has been found.

Thanks Richard. BTW hqperft is cool & fast! Great job!

[kalyan4code]

From the CPW documentation on "Attacks on All Ranks" I didn't quite understand the following statement:
// Copied from CPW Wiki Page --start
The array is defined one-dimensional, and has to indexed by 8*occ + file. The reason was playing the optimization game and to safe the right shift one, but to scale by 4 instead of 8, which is done by the address calculation unit anyway. This routine may complete the Hyperbola Quintessence.
// Copied from CPW Wiki Page --end

The code referred in above is here:

Code: Select all

BYTE arrFirstRankAttacks64x8[64*8]; // 512 Bytes = 1/2KByte

U64 rankAttacks(U64 occ, enumSquare sq) {
   unsigned int file = sq &  7;
   unsigned int rkx8 = sq & 56; // rank * 8
   occ = (occ >> rkx8) & 2*63;
   U64 attacks = arrFirstRankAttacks64x8[4*occ + file];
   return attacks << rkx8;
}

I am trying to understand why the array index computation is

Code: Select all

4 * occ + file

& why not it is

Code: Select all

8 * occ + file 

? i.e. in the following line of code from rankAttacks routine above:

Code: Select all

U64 attacks = arrFirstRankAttacks64x8[4*occ + file];