A question about writing big arrays of static variables

[Uri Blass]

Strelka has many big arrays
This program does not include a program to calculate the arrays but
only values of many 64 bit numbers that are xored by a single random number in the beginning of the program and never being changed later.

I understood the meaning of many of these arrays and
wrote a program to calculate them and my problem is how to use this program without strelka to rewrite the arrays as const without spending much time.

I want to use LineMask that is calculated by a special function that I wrote in order to write an array of 4*64*64 64 bits numbers and I want to do it for many arrays.

That array that has 4*64*64 numbers has many lines of code and start with:

static unsigned __int64 LineMask[4][64][64] = {
{{0x2AE711874E578EAD,


How much time do you need to do it and what is the best way to do it.
Is the best way to write a program that simply write the content of the array into a file and later use copy and paste or there is a better way.

Note that with small array of constants or array of small constants that were written as integers my solution to this problem was simple and I simply wrote a program to print the constants into the screen by printf and later copied the data from the screen but with big constants and big arrays this solution is not possible because the screen does not show me the first numbers and running the program many times is not efficient.

I can write a program that writes the content of arrays to a file but I see no reason to do it in case that there is an available program that does it
and I think that if you want to translate many arrays to arrays of constants after you have some program to generate the numbers then it is not efficient to run different program for every array.

Uri

[Harald Johnsen]

You don't need to copy and paste, just ouput the results in a source C file.
You generate something like :

int myarray[] = {......};

see http://chessdb.cvs.sourceforge.net/ches ... iew=markup function MTBWriter::Write (FILE * fp)

HJ.

[Tord Romstad]

Hello Uri,

What's the point? Computing such arrays during program initialization takes almost no time, and I don't see why you would want to include them as huge constant arrays in the source code.

In any case, I found an old rotated bitboard version of Glaurung on my hard disk. Here is the code for initializing the sliding attack bitboards (called LineMask[][][] in Strelka, and SlidingAttackBBArray[][][] in Glaurung), modified to a complete program which does nothing more than initializing the array and writing it as an array in C syntax to a file tables.c. It is not particularly elegant or clever, but it works.

Code: Select all

#include <stdio.h>

typedef unsigned long long bitboard_t;

enum {HORIZ_DIR, VERT_DIR, DIAG_DIR, XDIAG_DIR};

bitboard_t SlidingAttackBBArray[4][64][64];

int bit_is_set(bitboard_t b, int bit) {
  return b & (1ULL << bit);
}

int slide(int x, int v, int d) {
  x += d;
  if(x < 0 || x > 7) return 0;
  if(v & (1<<x)) return 1<<x;
  return (1<<x) | slide(x, v, d);
}

int fill(int x, int v) {
  return slide(x, v, 1) | slide(x, v, -1);
}

bitboard_t place_bitvector(int bitvector, int square, int direction) {
  int i, r=square>>3, f=square&7, d=(r-f)&7, x=(r+f)&7;
  bitboard_t result = 0ULL;
  int d_mask[16] = {255, 127, 63, 31, 15, 7, 3, 1,
                    0, 128, 192, 224, 240, 248, 252, 254};
  int xd_mask[16] = {1, 3, 7, 15, 31, 63, 127, 255,
                     254, 252, 248, 240, 224, 192, 128, 0};
  if(direction == DIAG_DIR) bitvector &= d_mask[(r-f)&15];
  else if(direction == XDIAG_DIR) bitvector &= xd_mask[(r+f)&15];
  for(i=0; i<8; i++) {
    if(bitvector&(1<<i))
      switch(direction) {
      case HORIZ_DIR: result |= (1ULL<<(r*8+i)); break;
      case VERT_DIR: result |= (1ULL<<(i*8+f)); break;
      case DIAG_DIR: result |= (1ULL<<(i+8*((d+i)&7))); break;
      case XDIAG_DIR: result |= (1ULL<<(i+8*((x-i)&7))); break;
      }
  }
  return result;
}

void init_attacks(void) {
  int i, j, k;
  for(i = 0; i < 64; i++)
    for(j = 0; j < 256; j++)
      for(k = HORIZ_DIR; k <= XDIAG_DIR; k++)
        SlidingAttackBBArray[k][i][(j >> 1) & 63] =
          place_bitvector(fill((k == 1)? (i>>3) : (i&7), j), i, k);
}

int main(void) {
  FILE *f;
  int i, j, k, l;

  init_attacks();
  f = fopen("tables.c", "w");
  fprintf(f, "const bitboard_t LineMask[4][64][64] = \n{\n");
  for(i = 0; i < 4; i++) {
    fprintf(f, "  {\n");
    for(j = 0; j < 64; j++) {
      fprintf(f, "    {\n");
      for(k = 0; k < 16; k++) {
        fprintf(f, "      ");
        for(l = 0; l < 4; l++)
          fprintf(f, "0x%llxULL%s", SlidingAttackBBArray[i][j][k*4+l],
                  (k == 15 && l == 3)? "" : ", ");
        fprintf(f, "\n");
      }
      fprintf(f, "    }%s", (j < 63)? ",\n" : "\n");
    }
    fprintf(f, "  }%s", (i < 3)? ",\n" : "\n");
  }
  fprintf(f, "};\n");
  fclose(f);
 
  return 0;
}


Tord

[Uri Blass]

Hello Tord,
Thanks for your code.

Edit:After looking at your code I see that your code clearly solve the problem of writing a file with consts and not only calculate the array so I delete part of my comments that are not relevant.

I already have my functions to calculate LineMask but it seems that your code is simpler
Speed is not the reason
I simply wanted to understand how the constants numbers were generated without spending a lot of time.

The only reason that I may consider to calculate arrays in initializiation is not speed but protecting possible secrets of future programs.

For the record here is my code to calculate linemask.

Note that I used xxx and later did comparison with the array after xoring without xxx to verify that my code is correct.

Code: Select all

unsigned __int64 LineMaskxxx[4][64][64];
int max_possible_7(int i,int j,int h)
{
   int score=h;
   int k=0;
   h=h-7;
   while (h>i)
   {
      if (j&(1<<k))
      {
         //there is a piece in h
         score=h;
      }
      k++;
      h=h-7;

   }
   return score;
   ////example i=E4 h=A8 l=A1
   //j&1 mean not A8 score=B7
   //j&2 mean not B7 score=C6
   //j&4 mean not C6 score=D5
   //otherwise everything is possible in the diagnol
   //j&16 mean square=F3
}
int min_possible_7(int i,int j,int h,int l)
{
   int score=l;
   int k=rank0(h)-rank0(l)-2;
   l+=7;
   while (l<i)
   {
      if (j&(1<<k))
         score=l;
      k--;
      l+=7;
   }
   return score;
   //example i=E4 h=A8 l=A1
   //k=
}
int min_possible_9(int i,int j,int l)
{
   int score=l;
   int k=0;
   l+=9;
   while (l<i)
   {
      if (j&(1<<k))
         score=l;
      k++;
      l+=9;
   }
   return score;

}
int max_possible_9(int i,int j,int h,int l)
{
   int score=h;
   int k=rank0(h)-rank0(l)-2;
   h-=9;
   while (h>i)
   {
      if (j&(1<<k))
         score=h;
      k--;
      h-=9;
   }
   return score;


}
int min_possible_1(int i,int j)
{
   int score=rank0(i)*8;
   int k=0;
   int l=score+1;
   while (l<i)
   {
      if (j&(1<<k))
         score=l;
      k++;
      l++;
   }
   return score;

}
int max_possible_1(int i,int j)
{
   int score=rank0(i)*8+7;
   int h=score-1;
   int k=5;
   while (h>i)
   {
      if (j&(1<<k))
         score=h;
      h--;
      k--;
   }
   return score;

}
int min_possible_8(int i,int j)
{
   int score=fil0(i);
   int k=5;
   int l=score+8;
   while (l<i)
   {
      if (j&(1<<k))
         score=l;
      k--;
      l+=8;
   }
   return score;

}
int max_possible_8(int i,int j)
{
   int score=fil0(i)+56;
   int h=score-8;
   int k=0;
   while (h>i)
   {
      if (j&(1<<k))
         score=h;
      h-=8;
      k++;
   }
   return score;

}

void calculate_line_mask()
{
   int i,j,l,h,k;
   for (i=0;i<64;i++)
      for(j=0;j<64;j++)
      {
         LineMaskxxx[0][i][j]=0;
         l=fil0(i)+rank0(i);
         if (l>=8)
            l+=7*(l-7);
         h=fil0(l)*8+rank0(l);
         if (h>l)
         for (k=min_possible_7(i,j,h,l);k<=max_possible_7(i,j,h);k+=7)
         {
               if (k!=i)
                  LineMaskxxx[0][i][j]|=setmask[k];
            }
            LineMaskxxx[1][i][j]=0;
            if (rank0(i)>fil0(i))
            {
               l=i-9*fil0(i);
               h=l+9*(7-rank0(l));
            }
            else
            {
               l=i-9*rank0(i);
               h=l+9*(7-fil0(l));
            }
            for (k=min_possible_9(i,j,l);k<=max_possible_9(i,j,h,l);k+=9)
            {
               if (k!=i)
                  LineMaskxxx[1][i][j]|=setmask[k];
            }
            LineMaskxxx[2][i][j]=0;
            for (k=min_possible_1(i,j);k<=max_possible_1(i,j);k++)
            {
               if (k!=i)
                  LineMaskxxx[2][i][j]|=setmask[k];
            }
            LineMaskxxx[3][i][j]=0;
            
            for (k=min_possible_8(i,j);k<=max_possible_8(i,j);k+=8)
            {
               if (k!=i)
                  LineMaskxxx[3][i][j]|=setmask[k];
            }
            

      
          
         }
}

[Uri Blass]

Note that I forgot 3 definitions that my code need to be compiled
and I forgot the initialization of setmask that is based on the following 2 lines

for (j=0;j<64;j++)
setmask[j]=((unsigned __int64)1<<(unsigned __int64)j);

#define fil0(i) ((i)&7)
#define rank0(i) ((i)>>3)
unsigned __int64 setmask[64];

[Uri Blass]

I can say that your code is extremely short.

Your code have the following advantages relative to my code that make it shorter:
1)Having recursive functions
2)not having many functions for similiar tasks.

The disadvantage of your code is that there are no comments to explain
what you do but I learned from your code and changed my code to be shorter.

Note that part of the reason that your code is shorter is the fact that you simply has some tricks that make is shorter instead of easier to understand and I find if then else easier to understand then ?

My opinion about it is that it is better to have a short code but not code that is too short.

Not having many functions to do similiar tasks is important when there are 8 similiar tasks for all directions but not when there are only 2 functions and I think that simply having 2 functions instead of your slide
function when one is for right and one is for left is better because I do not see how slide is useful for |d|!=1

I also used different names for these functions because the names that you used did not seem to me significant and the function is function that give possible places of squares that piece can move to.

int left_move_vector(int vector,int place)

int right_move_vector(int vector,int place)



Uri

[Onno Garms]

What do the arrays LineMask (or SlidingAttackBBArray) do?
Is the Strelka source publically available?

[Uri Blass]

What do the arrays LineMask (or SlidingAttackBBArray) do?
Is the Strelka source publically available?

These array simply have 64 bit numbers that represent set of squares that piece can go in a line based on 3 parameters:

parameter 1 is the line of the piece(0,1,2,3 for every line based on the direction)
when 2 numbers are for lines of the rook (same file or same rank) and 2 numbers are for lines of the bishop.

parameter 2 is the square that the piece start from (0-63)

parameter 3 is the vector of enemy pieces in the same line when you ignore the minimal and the maximal square(again 0-63)

An example:

suppose that you have a bishop at E4 and the line that you look is H1-A8

This mean direction=0 based on strelka definition and square=36

suppose that there are pieces at B7 C6 H1 and there are no pieces in other squares

This means that the relevant vector of pieces is

B7-1 *2^0
C6-1 *2^1
D5-0 *2^2
E4-0 *2^3
F3-0 *2^4
G2-0 *2^5

and this means that the vector of pieces is 2+4=6

The bishop At E4 can goto D5 F3 G2 and capture C6 and H1.

This give 64 bit number that is setmask[D5]+setmask[F3]+setmask[G2]+
setmask[C6]+setmask[H1] when setmask is an array of powers of 2 and
D5 F3 G2 C6 H1 are numbers 0-63 (every square is translated to a number).

For your second question strelka is not free source code(I was lucky to get it) but Tord told me that this idea is also used in Crafty so I decided that I can post about this specific array.

Uri

[Tord Romstad]

The disadvantage of your code is that there are no comments to explain
what you do but I learned from your code and changed my code to be shorter.

Note that part of the reason that your code is shorter is the fact that you simply has some tricks that make is shorter instead of easier to understand and I find if then else easier to understand then ?

My opinion about it is that it is better to have a short code but not code that is too short.

You are right, the code was not written with readability in mind. Because the technique was already widely known and used, I just implemented it in the shortest and simplest way I could see, without bothering to write comments or explanations.

Tord

[Tord Romstad]

What do the arrays LineMask (or SlidingAttackBBArray) do?

It's a technique for computing attack bitboards for sliding pieces, known as "rotated bitboards". It was originally invented by Bob Hyatt (I think), and described in this paper. For some reason I have never been able to figure out, Bob uses four different arrays (rook_attacks_r0, rook_attacks_rl90, bishop_attacks_rl45 and bishop_attacks_rr45) instead of a single array for all directions.

Rotated bitboards were very popular until a year or two ago, but don't seem to be very fashionable at the moment. I currently don't use them in chess, but I use a similar technique in shogi.

Is the Strelka source publically available?

No, it is not.

Tord

[Ron Murawski]

My opinion about it is that it is better to have a short code but not code that is too short.

Uri

"Everything should be made as simple as possible, but not simpler."
-- Albert Einstein

[bob]

What do the arrays LineMask (or SlidingAttackBBArray) do?

It's a technique for computing attack bitboards for sliding pieces, known as "rotated bitboards". It was originally invented by Bob Hyatt (I think), and described in this paper. For some reason I have never been able to figure out, Bob uses four different arrays (rook_attacks_r0, rook_attacks_rl90, bishop_attacks_rl45 and bishop_attacks_rr45) instead of a single array for all directions.

Rotated bitboards were very popular until a year or two ago, but don't seem to be very fashionable at the moment. I currently don't use them in chess, but I use a similar technique in shogi.

Is the Strelka source publically available?

No, it is not.

Tord

The reason for the four arrays is easy. The pieces of code were developed one at a time, and for a while, they changed frequently. It avoided dealing with the difficulty of changing part of an array while leaving the other (functional) parts alone...

I also try to avoid multi-dimensional arrays to eliminate multiplies and extra register usage for address calculation, which was another consideration.

[Michael Sherwin]

What do the arrays LineMask (or SlidingAttackBBArray) do?
Is the Strelka source publically available?

These array simply have 64 bit numbers that represent set of squares that piece can go in a line based on 3 parameters:

parameter 1 is the line of the piece(0,1,2,3 for every line based on the direction)
when 2 numbers are for lines of the rook (same file or same rank) and 2 numbers are for lines of the bishop.

parameter 2 is the square that the piece start from (0-63)

parameter 3 is the vector of enemy pieces in the same line when you ignore the minimal and the maximal square(again 0-63)

An example:

suppose that you have a bishop at E4 and the line that you look is H1-A8

This mean direction=0 based on strelka definition and square=36

suppose that there are pieces at B7 C6 H1 and there are no pieces in other squares

This means that the relevant vector of pieces is

B7-1 *2^0
C6-1 *2^1
D5-0 *2^2
E4-0 *2^3
F3-0 *2^4
G2-0 *2^5

and this means that the vector of pieces is 2+4=6

The bishop At E4 can goto D5 F3 G2 and capture C6 and H1.

This give 64 bit number that is setmask[D5]+setmask[F3]+setmask[G2]+
setmask[C6]+setmask[H1] when setmask is an array of powers of 2 and
D5 F3 G2 C6 H1 are numbers 0-63 (every square is translated to a number).

For your second question strelka is not free source code(I was lucky to get it) but Tord told me that this idea is also used in Crafty so I decided that I can post about this specific array.

Uri

I have been wondering about the strelka source code issue for awhile, ever since you gave indication that you possed it. I admit that I am extreamly jealous and am having a hard time making sense of the fairness of it. As long as Movei does not go commercial then I suppose that I can live with such an unfairness. However, if you now, ever make Movei commercial like you have indicated that you were going to do then I believe that I would become angry. IMHO the honorable thing to have done would be to have refused to look at the strelka sources unless your peers could also look at it.

Thanks for being honest and admitting that you posses the sources, but you should realize that it would be morally wrong to benifit from them if others can not.

Sorry, I do not mean to cause you any trouble. For fairness the author of Strelka should now release the source code under the GPL so all can benifit.

Practically forcing the author of Strelka to give his source code out to a few individuals to quell cloning accusations was IMO a crime against the author and now a crime against computer chess and its devotees as well. Nothing good has come of it. Uri, you should at least at this time say whether or not you recieved the sources from the original author of Strelka or not.

$.02

[Uri Blass]

I recieved the source from author of smarthink sergei markof and not from the original author.

I do not know if the original author gave permission to sergei to send me the code.

Uri

[Aleks Peshkov]

Thanks for being honest and admitting that you posses the sources, but you should realize that it would be morally wrong to benifit from them if others can not.

Sorry, I do not mean to cause you any trouble. For fairness the author of Strelka should now release the source code under the GPL so all can benifit.

I disagree, Michael. Strelka's author says and does strange things before, and free to continue to do strange things further for his own strange reasons. Uri got his Strelka source copy by occasion but without any doubt legally. I know that Strelka's evaluation (and successor program named Belka, http://en.wikipedia.org/wiki/Soviet_space_dogs) is discussing now in Russian computer chess forum, so probably suspicious Uri's forum postings about Strelka's internals are also ok. Just my personal opinion.

[Uri Blass]

Note that it is possible to say that everything that I do is unfair.

In case of deciding to refuse to look at strelka the author of smarthink could have the advantage of having strelka.

I simply see the code as a gift that I got.
I do not know how much it is going to help me to have a better program later and it may even be counter productive because it is possible that without looking at the code I could get better progress in movei.

Uri

[Michael Sherwin]

Note that it is possible to say that everything that I do is unfair.

In case of deciding to refuse to look at strelka the author of smarthink could have the advantage of having strelka.

I simply see the code as a gift that I got.
I do not know how much it is going to help me to have a better program later and it may even be counter productive because it is possible that without looking at the code I could get better progress in movei.

Uri

The point is, is that you have the option and the rest of us do not.

You would not have the option either if the computer chess community (of wich you played a major role of accuser) had not attacked the author of Strelka in the first place.

"I think that your program Movei is a clone." Now, send the source code out to ... so that I may recieve the gift of it.

[Uri Blass]

Note that I never accused strelka of being a fruit clone and I was asked to give opinion about that.

I had the opinion that it has parts of rybka based on comparing analysis of positions and not based on other things.

This opinion is unchanged.

Uri

[Michael Sherwin]

Note that I never accused strelka of being a fruit clone and I was asked to give opinion about that.

I had the opinion that it has parts of rybka based on comparing analysis of positions and not based on other things.

This opinion is unchanged.

Uri

So if B steals from A it is okay for C to steal from B what B stole from A?

Thanks, I did not realize this.

Things are much better now!

Do not sweat it, as I am not going to let it bother me anymore or give it any more thought.

[Uri Blass]

Note that I never accused strelka of being a fruit clone and I was asked to give opinion about that.

I had the opinion that it has parts of rybka based on comparing analysis of positions and not based on other things.

This opinion is unchanged.

Uri

So if B steals from A it is okay for C to steal from B what B stole from A?

Thanks, I did not realize this.

Things are much better now!

Do not sweat it, as I am not going to let it bother me anymore or give it any more thought.

1)I did not claim that Juri Osipov stole something and I think that stealing is the wrong word in this case.

2)I did not experess an opinion if what he did is illegal

3)I do not plan to do a similiar program to strelka(like the programmer of strelka did to rybka) but only to learn strelka
in the hope thst it is going to help me to write a better program.

I can promise you that there is not going to be copy and paste from strelka in future movei.

Uri