Hi David,
Not sure if you still need this but here is an example in c# that I use
Determining From squares
Moderators: hgm, Rebel, chrisw
-
- Posts: 117
- Joined: Wed Jul 20, 2011 2:54 pm
- Location: Ottawa, Canada
-
- Posts: 153
- Joined: Fri Sep 30, 2011 7:48 am
Re: Determining From squares
I wrote some code for a SAN to LAN (Long algebra notation e.g. e2e4) ages ago for my gui, then later I wrote a LAN to SAN converter to create SAN representation for the moves entered by the user. The rooks routine can be complex if you don't know the best way to start ...
using a board represented by an array of characters is one easy method,
Useful functions to implement are
bool IsFileSpanBlocked( int x1, int x2, int y)
bool IsRankSpanBlocked( int x, int y1, int y2)
so you can call the function
bool CanRookReachSquare(...)
and then you need
bool IsPiecePinned( Piece &p, int fromX, int fromY )
because you need to handle the case when the rook is capturing the pinning piece, i.e. another rook.
I basically sat up one night with a load of snacks etc and wrote the whole SAN to LAN in one night, then I had the pleasure of debugging the next day.
using a board represented by an array of characters is one easy method,
Useful functions to implement are
bool IsFileSpanBlocked( int x1, int x2, int y)
bool IsRankSpanBlocked( int x, int y1, int y2)
so you can call the function
bool CanRookReachSquare(...)
and then you need
bool IsPiecePinned( Piece &p, int fromX, int fromY )
because you need to handle the case when the rook is capturing the pinning piece, i.e. another rook.
I basically sat up one night with a load of snacks etc and wrote the whole SAN to LAN in one night, then I had the pleasure of debugging the next day.
-
- Posts: 153
- Joined: Fri Sep 30, 2011 7:48 am
Re: Determining From squares
Bitboards are much faster than looping over all the rooks/promoted rooks and calling these functions though. Also it is better to generate all legal moves in the long run because then you can easily detect mate and stalemate etc. (i didn't read the earlier post).
-
- Posts: 85
- Joined: Sun May 29, 2011 11:56 pm
- Location: San Diego
Re: Determining From squares
Thank u for the link. The code looks interesting. Ill check it out more detail for sure. Thanks much.
David
David
-
- Posts: 85
- Joined: Sun May 29, 2011 11:56 pm
- Location: San Diego
Re: Determining From squares
Hi David,
I actually had the light bulb turn on earlier today and Ive actually converted my piece list to use bitboard approach. I now have routines to generate all possible goto squares for rooks bishops and knights for all starting squares. Im actually doing my occupied squares a bit differently. Lets take WhiteRooks. This is basically a Dictionary<string,ulong> with the key being a square like "c3" and the value will be a ulong value of all squares this piece can move to freely, essentially the attack squares. This dictionary is updated as moves are made. So whenever I get a move like "Rc3" I can do an AND of the values of whiterooks and the square. A bit more involved but thats the jist of it.
I wouldnt consider this a complete bitboard but maybe a hybrid. It behaves pretty nicely. Im really thankful for all the help.
Thanks for the reply.
David
I actually had the light bulb turn on earlier today and Ive actually converted my piece list to use bitboard approach. I now have routines to generate all possible goto squares for rooks bishops and knights for all starting squares. Im actually doing my occupied squares a bit differently. Lets take WhiteRooks. This is basically a Dictionary<string,ulong> with the key being a square like "c3" and the value will be a ulong value of all squares this piece can move to freely, essentially the attack squares. This dictionary is updated as moves are made. So whenever I get a move like "Rc3" I can do an AND of the values of whiterooks and the square. A bit more involved but thats the jist of it.
I wouldnt consider this a complete bitboard but maybe a hybrid. It behaves pretty nicely. Im really thankful for all the help.
Thanks for the reply.
David
-
- Posts: 85
- Joined: Sun May 29, 2011 11:56 pm
- Location: San Diego
Re: Determining From squares
Thank u for the link. The code looks interesting. Ill check it out more detail for sure. Thanks much.
David
David
-
- Posts: 778
- Joined: Sat Jul 01, 2006 7:11 am
Re: Determining From squares
The problem is when there are two rooks that could move to c3 and one is pinned.bob wrote:Not sure how that is simpler. In Crafty, my idea would be:jwes wrote:Or just generate rook moves and ensure that exactly one legal move goes to c3. Thiis will probably use nearly all existing code.bob wrote:For bitboards, take the rook bitboard (because of the R in Rc3) and AND that with rook attacks FROM c3. You will get exactly one bit set, assuming your SAN output is correct (Rc3 is not ambiguous, and not impossible).whittenizer wrote:Hi all,
I'm looking for an efficient algorithm to determine the "from" square given a move such as "Rc3". In this case only one rook can move to this square. There could have been another rook that otherwise could have gone to c3 but it was blocked by another piece. I've implemented something that works but it is very clunky, and I'm not happy with it. I'm thinking I could use bitwise operators but no idea how to even start.
Any hints to get started would be greatly appreciated.
Thanks so much,
David
from = MSB(white_rooks & RookAttacks(c3))
That's about as simple as it gets...
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Determining From squares
Add a simple bit of code.jwes wrote:The problem is when there are two rooks that could move to c3 and one is pinned.bob wrote:Not sure how that is simpler. In Crafty, my idea would be:jwes wrote:Or just generate rook moves and ensure that exactly one legal move goes to c3. Thiis will probably use nearly all existing code.bob wrote:For bitboards, take the rook bitboard (because of the R in Rc3) and AND that with rook attacks FROM c3. You will get exactly one bit set, assuming your SAN output is correct (Rc3 is not ambiguous, and not impossible).whittenizer wrote:Hi all,
I'm looking for an efficient algorithm to determine the "from" square given a move such as "Rc3". In this case only one rook can move to this square. There could have been another rook that otherwise could have gone to c3 but it was blocked by another piece. I've implemented something that works but it is very clunky, and I'm not happy with it. I'm thinking I could use bitwise operators but no idea how to even start.
Any hints to get started would be greatly appreciated.
Thanks so much,
David
from = MSB(white_rooks & RookAttacks(c3))
That's about as simple as it gets...
If PopCnt(white_rooks & RookAttacks(c3)) == 1
from = MSB(white_rooks & RookAttacks(c3))
else
{here you do a MSB loop checking to see if each from square is legal (not pinned on king) }
-
- Posts: 85
- Joined: Sun May 29, 2011 11:56 pm
- Location: San Diego
Re: Determining From squares
Hey all,
I've come up with a routine to get this done. I'm using some generic lists and doing some ANDing to get the desired effect. Here's the jist of my routine:
There's really not too much to it. I do need to hook in "pin" type checking but that shouldn't be too bad. I'm using Dictionaries for some of the lists but the Board, WhiteRooks, etc... are ulong variables. I call this a hyrbid compared to the full blown bitboard. This way it keeps with my current structure and still takes advantage of the bitwise operators.
The code will be more gereric and will pass in the mask being used and the Indexes you see. Just did this to show the rook moves.
I've finally gotten around to getting my site up. Nothing there yet but I will post some code samples later this weekend to explain what I'm doing in more detail. It's a Silverlight project using C#.
I do use some of StockFishes syntax in a few places as this helped me out after looking over some of the code. I've placed comments to include anything related to StockFish.
My url is: http://www.whittenizer.com
Enjoy, and thanks again all.
David
I've come up with a routine to get this done. I'm using some generic lists and doing some ANDing to get the desired effect. Here's the jist of my routine:
Code: Select all
int indexToMoves = this.Squares[toSquare];
List<ulong> mask = this.RMask[indexToMoves];
int i = 0;
int index = 0;
ulong p = 0;
for (int j = 0; j < 4; j++)
{
index = this.RIndexes[indexToMoves, j];
for (int k = 0; k < this.RIndexes[indexToMoves, j]; k++)
{
p = mask[i];
if ((p & this.Board) > 0)
{
if ((p & this.WhiteRooks) == 0)
{
break;
}
else
{
//-- We have our piece :-)
return p;
}
}
i++;
index--;
}
i += index;
}
return p;
The code will be more gereric and will pass in the mask being used and the Indexes you see. Just did this to show the rook moves.
I've finally gotten around to getting my site up. Nothing there yet but I will post some code samples later this weekend to explain what I'm doing in more detail. It's a Silverlight project using C#.
I do use some of StockFishes syntax in a few places as this helped me out after looking over some of the code. I've placed comments to include anything related to StockFish.
My url is: http://www.whittenizer.com
Enjoy, and thanks again all.
David
-
- Posts: 85
- Joined: Sun May 29, 2011 11:56 pm
- Location: San Diego
Re: Determining From squares
Here is the routine I came up with to build up the masks and the indexes:
I've tested the heck out of it and it seems to work for every case. Any comments in how I've implemented this would be warmly welcomed.
Thanks,
David
Code: Select all
private void InitSlidingSquares(int[,] deltas, bool isbishop)
{
IDictionary<int, List<ulong>> mask = (isbishop) ? this.BMask : this.RMask;
int[,] indexes = (isbishop) ? this.BIndexes : this.RIndexes;
int count = 0;
int rank = 0;
int file = 0;
int index = 0;
int delta0 = 0;
int delta1 = 0;
int delta2 = 0;
List<ulong> values = null;
for (int i = 0; i < 64; i++)
{
values = new List<ulong>();
for (int j = 0; j < 4; j++)
{
delta0 = deltas[j, 0];
delta1 = deltas[j, 1];
delta2 = deltas[j, 2];
file = i % 8;
rank = i / 8;
if (isbishop)
{
index = i;
}
count = 0;
while ((file + delta1) >= 0 && (file + delta1) <= 7 && (rank + delta2) >= 0 && (rank + delta2) <= 7)
{
file += delta1;
rank += delta2;
count++;
if (isbishop)
{
index += delta0;
}
else
{
index = (rank * 8) + file;
}
values.Add(1UL << index);
}
indexes[i, j] = count;
}
mask[i] = values;
}
}
Thanks,
David