qsearch in crafty

[stevemulligan]

I found this Avoiding Rotated Bitboards with Direct Lookup

Looks like it will be under 10 megs, should be easier for me to implement than mbb's.

[bob]

heh, Magic bit boards seem a bit complicated for me at this stage. I'm trying to understand kindergarden bb's and I gotta say, whoever choose that name is making me feel really dumb right now :p

Would a lookup table without any rotations or hashing be too big (under 10Megs?) I know it would give terrible performance compared to MBB's but it would be way faster than what I'm using now to generate attacks.

Code: Select all

 for &#40;int i = 0; i++ i < 64&#41;
   for &#40;j = 0; j < ray_count; j++)
     for &#40;k = 0; k < ray_length; k++)
       if &#40;square_is_occupied&#41;
         break;
       attacks |= rays_square&#91;k&#93;;

It would be impossible, because you need a 64 bit "index". I don't think you can find that much memory on planet earth, much less in one computer.

If you want to do some work to extract a specific rank, or file, or diagonal, you might make it work, but it will be very slow...

[stevemulligan]

If you want to do some work to extract a specific rank, or file, or diagonal, you might make it work, but it will be very slow...

Well, after reading that paper I'm still stuck. And if I'm going to use bb's for move generation I might as well try to do it without a big array of c# dictionaries - so I'd like to try to figure out how rotated bit boards work.

Is there a rotated bit board tutorial for dummies? I'm stuck right at the beginning, I don't know how to extract the 8 bits of the rank I'm looking at from the 64bit board representation.

[bob]

If you want to do some work to extract a specific rank, or file, or diagonal, you might make it work, but it will be very slow...

Well, after reading that paper I'm still stuck. And if I'm going to use bb's for move generation I might as well try to do it without a big array of c# dictionaries - so I'd like to try to figure out how rotated bit boards work.

Is there a rotated bit board tutorial for dummies? I'm stuck right at the beginning, I don't know how to extract the 8 bits of the rank I'm looking at from the 64bit board representation.

There's an ICGA paper I wrote on the subject. There is also an online copy at www.cis.uab.edu/hyatt... scroll down until you see "online technical papers" and click that, then click "rotated bitmaps."

Direct computation is not that hard to do if you want a simpler approach. It will be slower, but we are not talking 2x slower or anything like that and it is certainly easier to implement. If you want an explanation, let me know...

[stevemulligan]

There's an ICGA paper I wrote on the subject. There is also an online copy at www.cis.uab.edu/hyatt... scroll down until you see "online technical papers" and click that, then click "rotated bitmaps."

I think I saw that a few months ago and thought it was waaay to complicated for me. However, I'm trying my best to figure it out. I think I making progress because I have working AttacksBishop & AttacksRook now.

I'm stuck on a part in your Swap function though. Around line 60 of swap.c

Code: Select all

if (piece == pawn || piece & 4)
       attacks |= AttacksRook(target, toccupied) & rsliders;

Why do you check for piece == pawn? It looks like rsliders only contains the occupied squares for rooks & queens.

In your paper you say a rook movers should be (piece & 2).

Direct computation is not that hard to do if you want a simpler approach.

I'm going to try to figure out the rotated BB approach. Out of curiosity, what is direct computation?

[PK]

for direct computation, start from here:

chessprogramming.wikispaces.com/Dumb7Fill

I guess one cannot make it simpler, yet this is enough for the beginning. later You can replace fill procedures with OccludedFill (also described on chesprogramming wiki)

[bob]

There's an ICGA paper I wrote on the subject. There is also an online copy at www.cis.uab.edu/hyatt... scroll down until you see "online technical papers" and click that, then click "rotated bitmaps."

I think I saw that a few months ago and thought it was waaay to complicated for me. However, I'm trying my best to figure it out. I think I making progress because I have working AttacksBishop & AttacksRook now.

I'm stuck on a part in your Swap function though. Around line 60 of swap.c

Code: Select all

if (piece == pawn || piece & 4)
       attacks |= AttacksRook(target, toccupied) & rsliders;

Why do you check for piece == pawn? It looks like rsliders only contains the occupied squares for rooks & queens.

In your paper you say a rook movers should be (piece & 2).

Direct computation is not that hard to do if you want a simpler approach.

I'm going to try to figure out the rotated BB approach. Out of curiosity, what is direct computation?

The == pawn is for a special case. I use Swap() to test the "safety" of any move, including pawn pushes. Which means that if I move a rook or queen (piece & 4 where R=4, Q=5) or if I move a pawn) I need to expand the attacks for any sliders behind that piece. But that is only for the move passed in. There can be no pawn advances in the SEE sequence itself as a pawn push is not a capture.

If you look at the loop that only considers captures, if piece & 1 is non-zero, I look for sliders behind the piece I just used, and this is true if piece = pawn, bishop or queen (pawn=1, bishop=3, queen=5).

[stevemulligan]

There's an ICGA paper I wrote on the subject.

I just wanted to post a thank you to Bob et alia. for the help on this subject. It took me almost two months but I did finally get my c# engine to use the rotated bit boards described in Bob's paper. The pawn move generation was probably the most difficult for me.

My engine still isn't as fast as Gaviota for instance but it's a lot better than what I had before. I was getting about 2K nodes per sec on a perft before and now with RBB's I get about 500K. Still a long piece away from 3 million like gaviota gets but I'm a lot happier! My final qnode count from my original post dropped down to 44k with SEE.

I think I still have a move ordering issue to sort out because a test position I found takes me about 5 million nodes on the 8th ply where as Gaviota takes 100k nodes.

3r1k2/4npp1/1ppr3p/p6P/P2PPPP1/1NR5/5K2/2R5 w - -