Some questions from a beginner

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
The_Algebraist
Posts: 11
Joined: Tue Mar 29, 2016 12:47 pm
Location: Munich, Germany

Re: Some questions from a beginner

Post by The_Algebraist » Tue Apr 05, 2016 9:07 pm

Thanks for your detailed explanations, Gerd! And also to you Sven!
This really helps me a lot! I'm looking forward to reimplementing the slider attacks with the magics

I just fed my move generation with the 218-move-position and the engine found them all :)
Gerd Isenberg wrote: And yes, you can compute the magics on the fly while startup ...
Isn't that what most engines do, that use magic bitboards?

wgarvin
Posts: 838
Joined: Thu Jul 05, 2007 3:03 pm
Location: British Columbia, Canada

Re: Some questions from a beginner

Post by wgarvin » Wed Apr 06, 2016 1:49 am

The_Algebraist wrote:Thanks for your detailed explanations, Gerd! And also to you Sven!
This really helps me a lot! I'm looking forward to reimplementing the slider attacks with the magics

I just fed my move generation with the 218-move-position and the engine found them all :)
Gerd Isenberg wrote: And yes, you can compute the magics on the fly while startup ...
Isn't that what most engines do, that use magic bitboards?
I think some engines use a pre-computed list of magics, but then generate the actual tables from them at startup time.

Mincho Georgiev
Posts: 454
Joined: Sat Apr 04, 2009 4:44 pm
Location: Bulgaria
Contact:

Re: Some questions from a beginner

Post by Mincho Georgiev » Wed Apr 06, 2016 5:10 am

The_Algebraist wrote:Thanks for your detailed explanations, Gerd! And also to you Sven!
This really helps me a lot! I'm looking forward to reimplementing the slider attacks with the magics

I just fed my move generation with the 218-move-position and the engine found them all :)
Gerd Isenberg wrote: And yes, you can compute the magics on the fly while startup ...
Isn't that what most engines do, that use magic bitboards?
I use them statically, but I intentionally left my code in the branch, even not connected to the cmd line interface, so I can show how the numbers have been generated. I will strongly recommend you read Kannan's papers first, so you can clear everything out for yourself. Also Reul's thesis would be great for you.

Code: Select all

const unsigned int b_bits[64] =
{ 6, 5, 5, 5, 5, 5, 5, 6, 
  5, 5, 5, 5, 5, 5, 5, 5, 
  5, 5, 7, 7, 7, 7, 5, 5, 
  5, 5, 7, 9, 9, 7, 5, 5, 
  5, 5, 7, 9, 9, 7, 5, 5, 
  5, 5, 7, 7, 7, 7, 5, 5, 
  5, 5, 5, 5, 5, 5, 5, 5, 
  6, 5, 5, 5, 5, 5, 5, 6
};

const unsigned int r_bits[64] =
{ 12, 11, 11, 11, 11, 11, 11, 12, 
  11, 10, 10, 10, 10, 10, 10, 11, 
  11, 10, 10, 10, 10, 10, 10, 11, 
  11, 10, 10, 10, 10, 10, 10, 11, 
  11, 10, 10, 10, 10, 10, 10, 11, 
  11, 10, 10, 10, 10, 10, 10, 11, 
  11, 10, 10, 10, 10, 10, 10, 11, 
  12, 11, 11, 11, 11, 11, 11, 12
};

//magic multipliers generation
#define MAX_TRIALS 10000

void print_magics(uint64 *m)
{
  int i,j;
  FILE *f;
	
  f = fopen("magics.txt", "a");
  j = 1;
  for&#40;i = 0; i < 64; i++)
  &#123; fprintf&#40;f, "\t%#.16llx%s, ", m&#91;i&#93;,"ULL");
    if&#40;++j > 4&#41;
    &#123; j = 1;
      fprintf&#40;f, "%s", "\n");
    &#125;
  &#125;	
  fprintf&#40;f, "%s", "\n\n");
  fclose&#40;f&#41;;
&#125;

uint64 rand64_1bits&#40;int bitcount&#41;
&#123;
  int i;
  uint64 pos, rnum = 0ULL;

  for&#40;i = 0; i < bitcount; i++)
  &#123; for&#40;;;)
    &#123; pos = 1ULL << &#40;rand&#40;) % 63&#41;;
      if&#40;!&#40;pos & rnum&#41;)
      &#123; rnum |= pos;
        break;
      &#125;
    &#125;
  &#125;
  return &#40;rnum&#41;;
&#125;

uint64 gen_multiplier&#40;int sq, bitboard_t mask, int bits, int *mbits, int *ibits, int rook&#41;
&#123;
  int fail,b;
  int trials;
  int bit_trials;
  uint64 magic;
  uint64 index;
  bitboard_t x, blockers&#91;4096&#93;, solution&#91;4096&#93;, used&#91;4096&#93;;
	
  for&#40;x = 0ULL; x < &#40;1ULL << bits&#41;; x++)
  &#123; blockers&#91;x&#93; = get_blockers&#40;x, mask&#41;;
    solution&#91;x&#93; = &#40;rook&#41; ? &#40;get_rook_atk&#40;sq,blockers&#91;x&#93;)) &#58; 
      &#40;get_bishop_atk&#40;sq, blockers&#91;x&#93;));
  &#125;
	
  trials = 0; bit_trials = 1;
  for&#40;;;)
  &#123; ibits&#91;sq&#93; = 0;
    magic = rand64_1bits&#40;bit_trials&#41;;
    for&#40;x = 0ULL; x < &#40;1ULL << bits&#41;; x++) used&#91;x&#93; = 0;
    fail = 0;
    for&#40;x = 0ULL; x < &#40;1ULL << bits&#41;; x++)
    &#123; index = &#40;blockers&#91;x&#93; * magic&#41; >> &#40;64 - bits&#41;;
      if&#40;used&#91;index&#93; == 0&#41; 
      &#123; used&#91;index&#93; = solution&#91;x&#93;;
        b = popcnt&#40;blockers&#91;x&#93; * magic&#41;;
        if&#40;ibits&#91;sq&#93; < b&#41; ibits&#91;sq&#93; = b;
      &#125;
      else if&#40;used&#91;index&#93; != solution&#91;x&#93;)
      &#123; fail = 1;
        break;
      &#125;
    &#125;
    if&#40;!fail&#41;
    &#123; mbits&#91;sq&#93; = bit_trials;
      return magic;
    &#125;
    trials++;
    if&#40;&#40;trials > MAX_TRIALS&#41; && &#40;bit_trials < bits&#41;)
    &#123; bit_trials++;
      trials = 0;
    &#125;
  &#125;
&#125;

void generate_magics&#40;)
&#123;
  int i,j,h,m,s;
  uint64 magics&#91;64&#93;;
  int magic_bits&#91;64&#93;;
  int index_bits&#91;64&#93;;
  time_t t1,t2;

  srand&#40;&#40;uint32&#41;time&#40;0&#41;);
  time&#40;&t1&#41;;
	
  printf&#40;"generating magic numbers\n\nprogress&#58;\n");
  for&#40;i = 0; i < 64; i++)
  &#123; magics&#91;i&#93; = gen_multiplier&#40;i, b_mask&#91;i&#93;, b_bits&#91;i&#93;, magic_bits, index_bits, 0&#41;;
    printf&#40;".");
  &#125;
  print_magics&#40;magics&#41;;
  printf&#40;"\n\nused bits in bishop magic numbers by %d trials&#58;\n\n",MAX_TRIALS&#41;;
  for&#40;i = 0,j = 1; i < 64; i++,j++)
  &#123; printf&#40;"%d, ",magic_bits&#91;i&#93;);
    if&#40;j >= 8&#41; 
    &#123; printf&#40;"\n");
      j = 0;
    &#125;
  &#125;
  printf&#40;"\n\nmax. multiplication bits for bishop by %d trials&#58;\n\n",MAX_TRIALS&#41;;
  for&#40;i = 0,j = 1; i < 64; i++,j++)
  &#123; printf&#40;"%d, ",index_bits&#91;i&#93;);
    if&#40;j >= 8&#41; 
    &#123; printf&#40;"\n");
      j = 0;
    &#125;
  &#125;	
  printf&#40;"\n\nprogress&#58;\n");
  for&#40;i = 0; i < 64; i++)
  &#123; magics&#91;i&#93; = gen_multiplier&#40;i, r_mask&#91;i&#93;, r_bits&#91;i&#93;, magic_bits, index_bits, 1&#41;;
    printf&#40;".");
  &#125;
  print_magics&#40;magics&#41;;
  printf&#40;"\n\nused bits in rook magic numbers by %d trials&#58;\n\n",MAX_TRIALS&#41;;
  for&#40;i = 0,j = 1; i < 64; i++,j++)
  &#123; printf&#40;"%d, ",magic_bits&#91;i&#93;);
    if&#40;j >= 8&#41; 
    &#123; printf&#40;"\n");
      j = 0;
    &#125;
  &#125;
  printf&#40;"\n\nmax. multiplication bits for rook by %d trials&#58;\n\n",MAX_TRIALS&#41;;
  for&#40;i = 0,j = 1; i < 64; i++,j++)
  &#123; printf&#40;"%d, ",index_bits&#91;i&#93;);
    if&#40;j >= 8&#41; 
    &#123; printf&#40;"\n");
      j = 0;
    &#125;
  &#125;
  printf&#40;"\n\n");
	
  time&#40;&t2&#41;;
  s = &#40;int&#41;&#40;t2-t1&#41;; 
  h = &#40;s / 3600&#41;; m = &#40;s / 60&#41; % 60; s %= 60;
  printf&#40;"time&#58; %dh&#58;%dm&#58;%ds\n\n", h, m, s&#41;;
&#125;
generate_magics() is the "interface" function.

The_Algebraist
Posts: 11
Joined: Tue Mar 29, 2016 12:47 pm
Location: Munich, Germany

Re: Some questions from a beginner

Post by The_Algebraist » Thu Apr 07, 2016 4:12 pm

Thanks for all your help and tips!
You guys a really great and make it much easier to get into programming a chess engine.

Thanks Mincho for your code sample, I will definitely look into that closely once I come back to replace the classical approach with the magic bitboards.


I finished the move generator of my engine now. Then I ran all the positions suggested on the perft test page of the cpw. After fixing some minor bugs, I get correct results for all of them now.

At least until like depth 4 or 5. If I go deeper, it not only takes veeeery long, but it starts messing up my computer. Everything slows down and after a while the program crashes.

I looked over the code and didn't find anything that catched my eye, but my time of c++ programming is a little while ago and I've become a bit rusty with c++. So I guess there is something wrong somewhere, maybe a memory leak or anyting similar.

Have any of you had a similar problem?
How did you try to find the root of the problem?
I have many asserts for pretty much everything all over the code and it is running in debug mode.

The_Algebraist
Posts: 11
Joined: Tue Mar 29, 2016 12:47 pm
Location: Munich, Germany

Re: Some questions from a beginner

Post by The_Algebraist » Thu Apr 07, 2016 7:34 pm

I found it! 1 missing delete... That got out of hand really fast though.
But now it runs smoothly, yet not very fast.

I only get 7M nodes per sec. Is this only due to the classical approach approach I used instead of the magic bitboards, or must there be some sloppy technique somewhere?

kbhearn
Posts: 411
Joined: Thu Dec 30, 2010 3:48 am

Re: Some questions from a beginner

Post by kbhearn » Thu Apr 07, 2016 8:47 pm

The_Algebraist wrote:I found it! 1 missing delete... That got out of hand really fast though.
But now it runs smoothly, yet not very fast.

I only get 7M nodes per sec. Is this only due to the classical approach approach I used instead of the magic bitboards, or must there be some sloppy technique somewhere?
well the fact that there was a delete missing indicates you're engaged in one cardinal sin: dynamic memory allocation. You should be able to get a fair bit of speed by reusing preallocated objects or creating objects on the stack (local variables) instead of new and delete.

That said, if 7M nodes per second is 7M makes and unmakes you're doing pretty good. If you're bulk counting at the leaves (rather than make and unmake the final ply just tallying the number of legal moves) it's a bit slow, but the algorithm shouldn't be the problem.

Also regardless it's not so slow as to prevent you from continuing to make your engine play chess and then come back to it later.

The_Algebraist
Posts: 11
Joined: Tue Mar 29, 2016 12:47 pm
Location: Munich, Germany

Re: Some questions from a beginner

Post by The_Algebraist » Thu Apr 07, 2016 8:53 pm

kbhearn wrote:well the fact that there was a delete missing indicates you're engaged in one cardinal sin: dynamic memory allocation. You should be able to get a fair bit of speed by reusing preallocated objects or creating objects on the stack (local variables) instead of new and delete.
There aren't too many new and delete in the code, but maybe I can try to eliminate them. I will have a look at that tomorrow! Thanks for your suggestion Kevin!

kbhearn wrote:That said, if 7M nodes per second is 7M makes and unmakes you're doing pretty good. If you're bulk counting at the leaves (rather than make and unmake the final ply just tallying the number of legal moves) it's a bit slow, but the algorithm shouldn't be the problem.
It is indeed 7M make and unmake.
It just seems so slow. I was running stockfish in another console to compare the results, and they were so much faster, at over 100M nodes on my laptop.

Don't they make/unmake the moves? So are they filtering the illegal moves already during move generation?

kbhearn
Posts: 411
Joined: Thu Dec 30, 2010 3:48 am

Re: Some questions from a beginner

Post by kbhearn » Thu Apr 07, 2016 9:01 pm

They do bulk counting of the leaves in perft (just looked at their routine) which is much faster (and would allow you to do higher perft ply numbers as such) but less indicative of how much your move generation/make/unmake will affect the search (that said perft isn't a great way to test that anyways).

Post Reply