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.
qsearch in crafty
Moderators: hgm, Rebel, chrisw
-
- Posts: 117
- Joined: Wed Jul 20, 2011 2:54 pm
- Location: Ottawa, Canada
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: qsearch in crafty
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.stevemulligan wrote: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 (int i = 0; i++ i < 64) for (j = 0; j < ray_count; j++) for (k = 0; k < ray_length; k++) if (square_is_occupied) break; attacks |= rays_square[k];
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...
-
- Posts: 117
- Joined: Wed Jul 20, 2011 2:54 pm
- Location: Ottawa, Canada
Re: qsearch in crafty
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.bob wrote: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...
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.
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: qsearch in crafty
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."stevemulligan wrote: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.bob wrote: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...
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.
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...
-
- Posts: 117
- Joined: Wed Jul 20, 2011 2:54 pm
- Location: Ottawa, Canada
Re: qsearch in crafty
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.bob wrote: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'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;
In your paper you say a rook movers should be (piece & 2).
I'm going to try to figure out the rotated BB approach. Out of curiosity, what is direct computation?Direct computation is not that hard to do if you want a simpler approach.
-
- Posts: 893
- Joined: Mon Jan 15, 2007 11:23 am
- Location: Warsza
Re: qsearch in crafty
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)
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)
Pawel Koziol
http://www.pkoziol.cal24.pl/rodent/rodent.htm
http://www.pkoziol.cal24.pl/rodent/rodent.htm
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: qsearch in crafty
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.stevemulligan wrote: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.bob wrote: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'm stuck on a part in your Swap function though. Around line 60 of swap.c
Why do you check for piece == pawn? It looks like rsliders only contains the occupied squares for rooks & queens.Code: Select all
if (piece == pawn || piece & 4) attacks |= AttacksRook(target, toccupied) & rsliders;
In your paper you say a rook movers should be (piece & 2).
I'm going to try to figure out the rotated BB approach. Out of curiosity, what is direct computation?Direct computation is not that hard to do if you want a simpler approach.
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).
-
- Posts: 117
- Joined: Wed Jul 20, 2011 2:54 pm
- Location: Ottawa, Canada
Re: qsearch in crafty
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.bob wrote:There's an ICGA paper I wrote on the subject.
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 - -