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
Determining From squares
Moderators: hgm, Rebel, chrisw
-
- Posts: 85
- Joined: Sun May 29, 2011 11:56 pm
- Location: San Diego
-
- Posts: 2949
- Joined: Mon May 05, 2008 12:16 pm
- Location: Bordeaux (France)
- Full name: Julien Marcel
Re: Determining From squares
Hello David. I think you need to tell us about your data structures (for instance how you code a move) in order to allow us to give you any meaningful suggestion.
"The only good bug is a dead bug." (Don Dailey)
[Blog: http://tinyurl.com/predateur ] [Facebook: http://tinyurl.com/fbpredateur ] [MacEngines: http://tinyurl.com/macengines ]
[Blog: http://tinyurl.com/predateur ] [Facebook: http://tinyurl.com/fbpredateur ] [MacEngines: http://tinyurl.com/macengines ]
-
- Posts: 4675
- Joined: Mon Mar 13, 2006 7:43 pm
Re: Determining From squares
There may not be a unique from-square, and there probably won't be one in most cases. The best that can be done is to calculate a list of possible squares, and that will take a retro-generator routine.whittenizer wrote:I'm looking for an efficient algorithm to determine the "from" square given a move such as "Rc3".
Why do you need this?
-
- Posts: 85
- Joined: Sun May 29, 2011 11:56 pm
- Location: San Diego
Re: Determining From squares
Hi there,
I have this pgn parsing routine which puts the moves in a generic list. This is C# so I have something like this: List<Move> moves...
So "Move" would have a Move.From and Move.To. When I add to the move list, I have to know what the from and to sqaures are given a move from the pgn. So, if we take "Rc3", I'd have to check all possibles rooks that could go to this square but in this case only one will work. Let's just say I have an array of two rooks that could go to c3 but only one of those rooks can legally move there. I could get lucky and pic the first one but we all know thats not going to work. The way I did it was for each square a rook can be on, I calculate which squares the rook can go to, and this is put into a Dictionary like: Dictionary<string, List<string>> so this would be something like: "a1", {"b1","c1","d1","e1","f1","g1","h1","a2","a3","a4","a5","a6","a7","a8"} and this repeats for all combinations of squares. The same is done for bishops. This to me seems clunky, and not efficient. I was thinking I could use bitwise operators like load the square values like 1<<8, 1<<16, etc and put those values in a long[64] array and use combinations of ^, & what have ya to get my desired effect but not sure how to get started.
I'm going to make a stab and the bitwise way but certainly welcome any advice.
Thanks so much,
David
I have this pgn parsing routine which puts the moves in a generic list. This is C# so I have something like this: List<Move> moves...
So "Move" would have a Move.From and Move.To. When I add to the move list, I have to know what the from and to sqaures are given a move from the pgn. So, if we take "Rc3", I'd have to check all possibles rooks that could go to this square but in this case only one will work. Let's just say I have an array of two rooks that could go to c3 but only one of those rooks can legally move there. I could get lucky and pic the first one but we all know thats not going to work. The way I did it was for each square a rook can be on, I calculate which squares the rook can go to, and this is put into a Dictionary like: Dictionary<string, List<string>> so this would be something like: "a1", {"b1","c1","d1","e1","f1","g1","h1","a2","a3","a4","a5","a6","a7","a8"} and this repeats for all combinations of squares. The same is done for bishops. This to me seems clunky, and not efficient. I was thinking I could use bitwise operators like load the square values like 1<<8, 1<<16, etc and put those values in a long[64] array and use combinations of ^, & what have ya to get my desired effect but not sure how to get started.
I'm going to make a stab and the bitwise way but certainly welcome any advice.
Thanks so much,
David
-
- Posts: 4675
- Joined: Mon Mar 13, 2006 7:43 pm
Re: Determining From squares
Let's define some common terms.whittenizer wrote:I have this pgn parsing routine which puts the moves in a generic list. This is C# so I have something like this: List<Move> moves...
So "Move" would have a Move.From and Move.To. When I add to the move list, I have to know what the from and to sqaures are given a move from the pgn.
SAN = string of characters from 2 up te 7 characters in length (this is what appears in PGN move text).
Move = structure of numeric data with components including from-man, from-square, to-man, to-square, etc.
My guess is that you want to read PGN, extract the SAN sequence, and generate a list of Move structures.
Is this right? If so, you are going to need a position-to-List<Move> generator and a Move-to-SAN encoder.
-
- Posts: 85
- Joined: Sun May 29, 2011 11:56 pm
- Location: San Diego
Re: Determining From squares
Yes, basically this is what I need. As I said before I have a routine that works but its clunky and seems inefficient. Given what youve provided, maybe I need to refactor my code a bit. Ill play around with a few things and see how it goes.
Thanks for the reply.
Thanks for the reply.
-
- Posts: 892
- Joined: Sun Nov 19, 2006 9:16 pm
- Location: Russia
Re: Determining From squares
Why it need to be efficient? In most cases better to aim for simplicity.
-
- Posts: 173
- Joined: Sun May 11, 2008 7:43 am
Re: Determining From squares
What I did was pretty much similar to what is being described with the array of moves.whittenizer wrote:Hi there,
I have this pgn parsing routine which puts the moves in a generic list. This is C# so I have something like this: List<Move> moves...
So "Move" would have a Move.From and Move.To. When I add to the move list, I have to know what the from and to sqaures are given a move from the pgn. So, if we take "Rc3", I'd have to check all possibles rooks that could go to this square but in this case only one will work. Let's just say I have an array of two rooks that could go to c3 but only one of those rooks can legally move there. I could get lucky and pic the first one but we all know thats not going to work. The way I did it was for each square a rook can be on, I calculate which squares the rook can go to, and this is put into a Dictionary like: Dictionary<string, List<string>> so this would be something like: "a1", {"b1","c1","d1","e1","f1","g1","h1","a2","a3","a4","a5","a6","a7","a8"} and this repeats for all combinations of squares. The same is done for bishops. This to me seems clunky, and not efficient. I was thinking I could use bitwise operators like load the square values like 1<<8, 1<<16, etc and put those values in a long[64] array and use combinations of ^, & what have ya to get my desired effect but not sure how to get started.
I'm going to make a stab and the bitwise way but certainly welcome any advice.
Thanks so much,
David
I generated all of the moves for all pieces to all squares, just over 4k, and have them turn on|off with another array flag to all the possible moves, using the from square with conditions met|not met.
The example for pieces:
http://www.talkchess.com/forum/viewtopi ... ht=#426565
http://www.talkchess.com/forum/viewtopi ... ht=#384753
http://talkchess.com/forum/viewtopic.ph ... 11&t=35595
Personally, I think you need to stick to your guns, and keep what you have. Maybe clean it up, but make sure it retains flexibility && is expandable for new ideas IMO.
Joshua D. Haglund
-
- Posts: 4675
- Joined: Mon Mar 13, 2006 7:43 pm
Re: Determining From squares
Let me add that to get the Move->SAN encoder working, you'll need not just a move generator, but also routines for move execute, move retract, and move disambiguation.whittenizer wrote:Yes, basically this is what I need. As I said before I have a routine that works but its clunky and seems inefficient. Given what youve provided, maybe I need to refactor my code a bit. Ill play around with a few things and see how it goes.
Fortunately this has all been done long ago.
I seem to recall an ANSI C "SAN Kit" source from the early 1990s which had all of this. And surely there have been better examples written more recently.
-
- Posts: 2684
- Joined: Sat Jun 14, 2008 9:17 pm
Re: Determining From squares
I think he needs the opposite: given the input in SAN notation (he is parsing a PGN) he needs to decode to from-to (UCI) notation.sje wrote: Let me add that to get the Move->SAN encoder working
Anyhow, in case you really need a "move to SAN" encoder then take a look at move_to_san() function in:
https://github.com/mcostalba/Stockfish/ ... c/move.cpp
This is by far the best you can find around