What is the best way to create AttackTable in mailbox or 0x88 board representation.

[shahil4242]

My Approach of calculation is_square_attack(): is given below:

Code: Select all

// It used 0x88 board with A1 = 0 and H8 = 119
int is_square_attacked(int from,int side)
{
	int to, vector_index, piece;
	
	for(piece = PIECE_PAWN; piece <= PIECE_KING; piece++)
	{
		if(piece == PIECE_PAWN)
		{
			to = ((side) ? (from - 15) : (from + 15));
			if(IS_SQUARE(to) && is_piece(to,side,piece)) return 1;
			
			to = ((side) ? (from - 17) : (from + 17));
			if(IS_SQUARE(to) && is_piece(to,side,piece)) return 1;
	
		}
		else
		{
			for(vector_index = 0; vector_index < 8; vector_index++)
			{
				if(!vectors[piece][vector_index]) break;
				
				to = from;
				
				while(1)
				{
					to = to + vectors[piece][vector_index];
					
					if(!IS_SQUARE(to)) break;
					
					if(!is_empty(to))
					{
						if(is_piece(to,side,piece)) return 1;
						
						break;
					}
					
					if(!slide[piece]) break;
				
				}
			}
		}
	}
	
	return 0;
}

I know it degrades the searching performance.I have seen in Glaurung older version,Tord had done in different way known as vectors attack.In this approaches the move delta is difference from square to to square is saved in a data structure also the piece attack mask.Some of the code associated are as follow.

Code: Select all

// Some of the attack mask of the pieces
#define WP_MASK 1
#define BP_MASK 2
#define N_MASK 4
#define K_MASK 8
#define B_MASK 16
#define R_MASK 32
#define Q_MASK 64

// attack table data structure
typedef struct {
  uint8 may_attack;
  int8 step;
} attack_data_t;

//attack table
attack_data_t AttackData_[256];
attack_data_t *AttackData = AttackData_+128; 

//attack table is precalculated
static void init_attack_data(void) {
  int sq, piece, tosq;
  int *ptr;

  for(sq=0; sq<256; sq++) 
    AttackData_[sq].may_attack = AttackData_[sq].step = 0;
  for(sq=A1; sq<=H8; sq++) 
    for(piece=WP; piece<=BK; piece++) 
      for(ptr = Directions[piece]; *ptr; ptr++) 
        for(tosq=sq+(*ptr); Board[tosq]!=OUTSIDE; tosq+=(*ptr)) {
          AttackData[sq-tosq].step = *ptr;
          AttackData[sq-tosq].may_attack |= PieceMask[piece];
          if(!SLIDER(piece)) break;
        }
}

//the main square_attacked function
int is_attacked(int square, int side) {
  int sq, tosq, piece, step;
  attack_data_t *a = AttackData-square;

  for(sq=KSQ(side); sq!=PL_END; sq=PL_NEXT(sq)) {
    if(sq>H8) continue;
    piece = Board[sq];
    if(PieceMask[piece]&a[sq].may_attack) {
      if(!SLIDER(piece)) return 1;
      step = a[sq].step;
      for(tosq=sq+step; Board[tosq]==EMPTY&&tosq!=square; tosq+=step);
      if(tosq==square) return 1;
    }
  }
  return 0;
}

Question1: Why AttackData is offset by 128

Code: Select all

attack_data_t *AttackData = AttackData_+128; 

Question2: Please explain this.

Code: Select all

  attack_data_t *a = AttackData-square;

Question3: Are there any other way to calculated attack table before hand.

PS: For Now I donot want to use bitboard,I know there are magics bitboard which find attack map very quickly,but i donot want it learn now.They are out of scope of my mind.I had also seen qperft by hgm but i could not understand.

[hgm]

See the 'mailbox trials' discussion.

In short: do not calculate the attack map from scratch, calculate it incrementally.

[shahil4242]

See the 'mailbox trials' discussion.

In short: do not calculate the attack map from scratch, calculate it incrementally.

Thank you for the post.i will read the whole discussion.

What are the factors that affect the perft test?

[yeni_sekme]

Where do you use attack tables?
I'm using NNUE for evaluation. Can attack tables be useful for me if I use them in my movegen() and is_square_attacked() ?

[shahil4242]

It is extremely useful in is_square_attacked() function.mostly it is used in evaluation for computing mobility,attack,king safety also used in static evaluation exchange.Yup is it useful to computed pinned pieces,fast checks,generate check evasions moves etc etc.Look the source code of Glaurung 1.0.2 to find out more.

[hgm]

Where do you use attack tables?
I'm using NNUE for evaluation. Can attack tables be useful for me if I use them in my movegen() and is_square_attacked() ?

NNUE is a rather expensive form of evaluation. So if you do that, speed of the rest of your engine doesn't have a large effect on overall speed.

[dangi12012]

My Approach of calculation is_square_attack(): is given below:

Code: Select all

// It used 0x88 board with A1 = 0 and H8 = 119
int is_square_attacked(int from,int side)
{
	int to, vector_index, piece;
	
	for(piece = PIECE_PAWN; piece <= PIECE_KING; piece++)
	{
		if(piece == PIECE_PAWN)
		{
			to = ((side) ? (from - 15) : (from + 15));
			if(IS_SQUARE(to) && is_piece(to,side,piece)) return 1;
			
			to = ((side) ? (from - 17) : (from + 17));
			if(IS_SQUARE(to) && is_piece(to,side,piece)) return 1;
	
		}
		else
		{
			for(vector_index = 0; vector_index < 8; vector_index++)
			{
				if(!vectors[piece][vector_index]) break;
				
				to = from;
				
				while(1)
				{
					to = to + vectors[piece][vector_index];
					
					if(!IS_SQUARE(to)) break;
					
					if(!is_empty(to))
					{
						if(is_piece(to,side,piece)) return 1;
						
						break;
					}
					
					if(!slide[piece]) break;
				
				}
			}
		}
	}
	
	return 0;
}

I know it degrades the searching performance.I have seen in Glaurung older version,Tord had done in different way known as vectors attack.In this approaches the move delta is difference from square to to square is saved in a data structure also the piece attack mask.Some of the code associated are as follow.

Code: Select all

// Some of the attack mask of the pieces
#define WP_MASK 1
#define BP_MASK 2
#define N_MASK 4
#define K_MASK 8
#define B_MASK 16
#define R_MASK 32
#define Q_MASK 64

// attack table data structure
typedef struct {
  uint8 may_attack;
  int8 step;
} attack_data_t;

//attack table
attack_data_t AttackData_[256];
attack_data_t *AttackData = AttackData_+128; 

//attack table is precalculated
static void init_attack_data(void) {
  int sq, piece, tosq;
  int *ptr;

  for(sq=0; sq<256; sq++) 
    AttackData_[sq].may_attack = AttackData_[sq].step = 0;
  for(sq=A1; sq<=H8; sq++) 
    for(piece=WP; piece<=BK; piece++) 
      for(ptr = Directions[piece]; *ptr; ptr++) 
        for(tosq=sq+(*ptr); Board[tosq]!=OUTSIDE; tosq+=(*ptr)) {
          AttackData[sq-tosq].step = *ptr;
          AttackData[sq-tosq].may_attack |= PieceMask[piece];
          if(!SLIDER(piece)) break;
        }
}

//the main square_attacked function
int is_attacked(int square, int side) {
  int sq, tosq, piece, step;
  attack_data_t *a = AttackData-square;

  for(sq=KSQ(side); sq!=PL_END; sq=PL_NEXT(sq)) {
    if(sq>H8) continue;
    piece = Board[sq];
    if(PieceMask[piece]&a[sq].may_attack) {
      if(!SLIDER(piece)) return 1;
      step = a[sq].step;
      for(tosq=sq+step; Board[tosq]==EMPTY&&tosq!=square; tosq+=step);
      if(tosq==square) return 1;
    }
  }
  return 0;
}

Question1: Why AttackData is offset by 128

Code: Select all

attack_data_t *AttackData = AttackData_+128; 

Question2: Please explain this.

Code: Select all

  attack_data_t *a = AttackData-square;

Question3: Are there any other way to calculated attack table before hand.

PS: For Now I donot want to use bitboard,I know there are magics bitboard which find attack map very quickly,but i donot want it learn now.They are out of scope of my mind.I had also seen qperft by hgm but i could not understand.

First layer of optimisation would be to calculate this incrementally.
Second layer of optimisation is to move your "side" to a constexpr parameter.
Third layer of optimisation would be for you to use bitboards - which are experimentically much much faster than 0x88. Also there is nothing to understand. One uint64_t is like an array (and can be used as such). Also the code is shorter and simpler to read.

The last layer of optimisations is that:
Fastest code is non existing code. Meaning that your "is attacked" is probably fastest if you dont call it at all. Meaning that check testing can be done by sending out rays like a queen and intersecting those with sliders. + Knight + Pawns. If its really needed maintain it incrementally.

[hgm]

When I was doing the mailbox trials, I did not encounter many places where bitboards might help. The point is that an attack map is intrinsically a mailbox data structure, as it requires many bits per square or piece. So generating the new moves of a moved piece in a bitboard, you would still have to extract all the moves, in order to transfer them to the attack map. To my surprise it also turned out there was no benefit in reducing the number of target squares when some of those fell off board; it was faster to always loop over the same number of targets, and treat the off-board targets the same as the others, but diverted to a dummy element of the attack map. Just looping over all possible steps of a leaper requires less overhead than the usual extraction loop of a bitboard.

Scans over the board only occuured for updating the view-distance table after a non-capture. Which happens so infrequently that there isn't much to gain there. All the more since any gains would have to earn back the overhead of updating the occupied bitboard. A problem here is that the view-distance table is really 10x10, although the upstream targets will always ly in a 9x9 subset of it. But I guess one could make a variant of magic bitboard, which masks out the 4 upstream directions (e4 -> e5, f5, f4 and f3) from the normal 8x8 occupied board, and uses the magic hash to index a table that lists the square numbers of the 4 neighbors in those directions. One could then loop over those 4 squares to update the view-distances. The savings would have to earn back the overhead of updating the occupied bitboard, though, which would happen on every move.

[Edit] I guess the number of bits in the relevance mask would be too variable, and rise to a too large value for a1 to do it in the described way, but this could be cured by defining 'upstream' as e4 -> e5, f4, f3 and d3. It would require an 14-bit index, though (but only 4 bytes per stored item).

Code: Select all

. . . . * . . .
. . . . * . . .
. . . . * . . .
. . . . * . . .
. . . . o * * *
. . . * . * . .
. . * . . . * .
. * . . . . . *

[diep]

Probably the fastest incremental attacktables on the planet in C code are in Diep. Note this is for oldschool cpu's without vectorisation. To vectorize things in AVX - well question is whether your time is useful to waste on that instead of build a new robot you can make a billion dollar with instead.

The datastructure in question is not that relevant on paper, but you use precalculated tables for this.
Doing it without precalculated tables most definitely is a lot slower.

In itself how you represent the board is not so relevant there as how you represent the attacktables.

The board representation in itself is more interesting for your evaluation function to not mess up there.

Attacktables would only be really useful to do incremental if your ambition is an evaluation function that is quite huge. Say 10x+ larger than what Stockfish has.

There is a significant slowdown. I would argue it is worth it.

More knowledge always wins provided you can parameter tune every bonus/penalty there is in your evaluation function. With parameter tune i mean of course a perfect parameter tuning. Not the nonsense tuning some beginners posted here.

What works of course you cannot expect to be public. Unlike Diep's datastructure which is not secret at all.

[hgm]

The way I did it in 'the mailbox trials' caused a significant speedup in a virtually evaluationless test. Because it eliminated the need for making a move list, and sorting it. The captures could be directly extracted from the attack table, in the desired order.

How was Diep's attack map organized? I used an array indexed by victim, which would flag all attackers in a way so they would extract in LVA order.