Interesting. I'll have to look into this then.
Thanks for the reply.
Determining From squares
Moderators: hgm, Rebel, chrisw
-
- Posts: 85
- Joined: Sun May 29, 2011 11:56 pm
- Location: San Diego
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Determining From squares
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
-
- Posts: 778
- Joined: Sat Jul 01, 2006 7:11 am
Re: Determining From squares
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
-
- Posts: 85
- Joined: Sun May 29, 2011 11:56 pm
- Location: San Diego
Re: Determining From squares
Hi Robert,
Thanks for the reply. The rook attacks seems like they have to be continously updated as moves are played. I don't know C/C++ too well but can follow it enough I think. I can't upload images so here is a position. Please excuse the crude board
__ __ __ __ __ __ __ __
__ __ __ __ __ __ __ __
__ __ __ __ __ __ __ __
__ __ __ __ __ __ __ __
__ __ __ __ __ __ __ __
R __ __ __ __ n __ R
__ __ __ __ __ __ __ __
__ __ __ __ __ __ __ __
Ok, in this position, the rook on a3 can only go to c3. The rook on h3 could but its blocked. So if I do the ANDing as you say, rookattacks wouldnt have the rook on h3 in it then? If it doesn;t have it, then it would be updated as we make moves. Lets say we have the two rooks without the knight there then next move the knight jumps to f3. Would this take the rook on h3 out of the picture for potential c3 squares?
Thanks so much for the reply.
David
Thanks for the reply. The rook attacks seems like they have to be continously updated as moves are played. I don't know C/C++ too well but can follow it enough I think. I can't upload images so here is a position. Please excuse the crude board
__ __ __ __ __ __ __ __
__ __ __ __ __ __ __ __
__ __ __ __ __ __ __ __
__ __ __ __ __ __ __ __
__ __ __ __ __ __ __ __
R __ __ __ __ n __ R
__ __ __ __ __ __ __ __
__ __ __ __ __ __ __ __
Ok, in this position, the rook on a3 can only go to c3. The rook on h3 could but its blocked. So if I do the ANDing as you say, rookattacks wouldnt have the rook on h3 in it then? If it doesn;t have it, then it would be updated as we make moves. Lets say we have the two rooks without the knight there then next move the knight jumps to f3. Would this take the rook on h3 out of the picture for potential c3 squares?
Thanks so much for the reply.
David
-
- Posts: 411
- Joined: Thu Dec 30, 2010 4:48 am
Re: Determining From squares
You'd calculate it on the fly. basically you'd plop an imaginary rook down on c3 and see what it attacks. The rook that it attacks is the rook that can move to c3. If it attacks more than one rook then the SAN is usually ambiguous. So bitboard RAttacks(c3,occupied) & WhiteRooks gives you the answer most of the time. This however does not deal with cases where it's unambiguous due to a pin, so as simple as it is, it's not a sufficient solution unfortunately. If it comes back ambiguous, you would need to test each possible rook origin for pins.
-
- Posts: 85
- Joined: Sun May 29, 2011 11:56 pm
- Location: San Diego
Re: Determining From squares
Hi Kevin,
Thats what I was thinking. Ok, this makes sense. I keep track of the FEN positions for each move so if Rc3 happens to be be move 15, I'll have a corresponding FEN position and can then do my occupied check at that point. I just need to figure out a nice routine for the occupied check. I already have some nice routines to get all possible squares that bishops, rooks and knights can go to given a starting square. I can use that to help with the occupied routine
Anyways, my project is early in development. Its a silverlight app written in C# so this forum is really helping me out alot learning little things as I go.
Thanks for the reply.
David
Thats what I was thinking. Ok, this makes sense. I keep track of the FEN positions for each move so if Rc3 happens to be be move 15, I'll have a corresponding FEN position and can then do my occupied check at that point. I just need to figure out a nice routine for the occupied check. I already have some nice routines to get all possible squares that bishops, rooks and knights can go to given a starting square. I can use that to help with the occupied routine
Anyways, my project is early in development. Its a silverlight app written in C# so this forum is really helping me out alot learning little things as I go.
Thanks for the reply.
David
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Determining From squares
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
No, rook_attacks from c3 would be blocked at f3 and would not make it to the h3 rook. When you and the rooks attacks with the white rook attacks, you only get the a3 rook. I do this with a magic multiply...whittenizer wrote:Hi Robert,
Thanks for the reply. The rook attacks seems like they have to be continously updated as moves are played. I don't know C/C++ too well but can follow it enough I think. I can't upload images so here is a position. Please excuse the crude board
__ __ __ __ __ __ __ __
__ __ __ __ __ __ __ __
__ __ __ __ __ __ __ __
__ __ __ __ __ __ __ __
__ __ __ __ __ __ __ __
R __ __ __ __ n __ R
__ __ __ __ __ __ __ __
__ __ __ __ __ __ __ __
Ok, in this position, the rook on a3 can only go to c3. The rook on h3 could but its blocked. So if I do the ANDing as you say, rookattacks wouldnt have the rook on h3 in it then? If it doesn;t have it, then it would be updated as we make moves. Lets say we have the two rooks without the knight there then next move the knight jumps to f3. Would this take the rook on h3 out of the picture for potential c3 squares?
Thanks so much for the reply.
David
-
- Posts: 1334
- Joined: Sun Jul 17, 2011 11:14 am
Re: Determining From squares
David,
[D]8/8/8/8/8/R4n1R/8/8 w - - 0 1
That should do...
Matthew:out
[D]8/8/8/8/8/R4n1R/8/8 w - - 0 1
That should do...
Matthew:out
Some believe in the almighty dollar.
I believe in the almighty printf statement.
I believe in the almighty printf statement.
-
- Posts: 85
- Joined: Sun May 29, 2011 11:56 pm
- Location: San Diego
Re: Determining From squares
Hi all,
Just wanted to say thank you to all who put their input in. I have a really good idea now how I want to proceed. I realize that what I have now as a routine is not as bad as what I was thinking. I will modify it a bit though to incorporate some of the ANDing techniques some of you had mentioned. Instead of having a piece list I think I can change it to a HashTable or Dictionary with a string key and a ulong value. The key will be the square like "a3" and the ulong value will hold the possible square values.
Anyways, I'll keep you all posted.
Thanks again everyone,
David
Just wanted to say thank you to all who put their input in. I have a really good idea now how I want to proceed. I realize that what I have now as a routine is not as bad as what I was thinking. I will modify it a bit though to incorporate some of the ANDing techniques some of you had mentioned. Instead of having a piece list I think I can change it to a HashTable or Dictionary with a string key and a ulong value. The key will be the square like "a3" and the ulong value will hold the possible square values.
Anyways, I'll keep you all posted.
Thanks again everyone,
David