Understanding first rank attack state generation

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
kalyan4code
Posts: 9
Joined: Sun May 12, 2019 11:41 am
Full name: Kalyankumar Ramaseshan

Understanding first rank attack state generation

Post by kalyan4code » Thu Jul 18, 2019 8:47 am

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
Thanks,
Kalyan

mar
Posts: 1992
Joined: Fri Nov 26, 2010 1:00 pm
Location: Czech Republic
Full name: Martin Sedlak

Re: Understanding first rank attack state generation

Post by mar » Thu Jul 18, 2019 9:32 am

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

kalyan4code
Posts: 9
Joined: Sun May 12, 2019 11:41 am
Full name: Kalyankumar Ramaseshan

Re: Understanding first rank attack state generation

Post by kalyan4code » Thu Jul 18, 2019 9:55 am

mar wrote:
Thu Jul 18, 2019 9:32 am
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?
Thanks,
Kalyan

mar
Posts: 1992
Joined: Fri Nov 26, 2010 1:00 pm
Location: Czech Republic
Full name: Martin Sedlak

Re: Understanding first rank attack state generation

Post by mar » Thu Jul 18, 2019 10:20 am

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.
Martin Sedlak

kalyan4code
Posts: 9
Joined: Sun May 12, 2019 11:41 am
Full name: Kalyankumar Ramaseshan

Re: Understanding first rank attack state generation

Post by kalyan4code » Thu Jul 18, 2019 11:00 am

mar wrote:
Thu Jul 18, 2019 10:20 am
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 ?
Thanks,
Kalyan

mar
Posts: 1992
Joined: Fri Nov 26, 2010 1:00 pm
Location: Czech Republic
Full name: Martin Sedlak

Re: Understanding first rank attack state generation

Post by mar » Thu Jul 18, 2019 11:11 am

kalyan4code wrote:
Thu Jul 18, 2019 11:00 am
mar wrote:
Thu Jul 18, 2019 10:20 am
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)
Martin Sedlak

kalyan4code
Posts: 9
Joined: Sun May 12, 2019 11:41 am
Full name: Kalyankumar Ramaseshan

Re: Understanding first rank attack state generation

Post by kalyan4code » Thu Jul 18, 2019 11:20 am

mar wrote:
Thu Jul 18, 2019 11:11 am
(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.
mar wrote:
Thu Jul 18, 2019 11:11 am
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.
Thanks,
Kalyan

abulmo2
Posts: 188
Joined: Fri Dec 16, 2016 10:04 am
Contact:

Re: Understanding first rank attack state generation

Post by abulmo2 » Thu Jul 18, 2019 12:03 pm

kalyan4code wrote:
Thu Jul 18, 2019 8:47 am
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.
Richard Delorme

kalyan4code
Posts: 9
Joined: Sun May 12, 2019 11:41 am
Full name: Kalyankumar Ramaseshan

Re: Understanding first rank attack state generation

Post by kalyan4code » Thu Jul 18, 2019 12:37 pm

abulmo2 wrote:
Thu Jul 18, 2019 12:03 pm
kalyan4code wrote:
Thu Jul 18, 2019 8:47 am
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!
Thanks,
Kalyan

kalyan4code
Posts: 9
Joined: Sun May 12, 2019 11:41 am
Full name: Kalyankumar Ramaseshan

Re: Understanding first rank attack state generation

Post by kalyan4code » Wed Oct 09, 2019 6:30 pm

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];
Thanks,
Kalyan

Post Reply