Determining From squares

[whittenizer]

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

[JuLieN]

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.

[sje]

I'm looking for an efficient algorithm to determine the "from" square given a move such as "Rc3".

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.

Why do you need this?

[whittenizer]

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

[sje]

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.

Let's define some common terms.

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.

[whittenizer]

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.

[Aleks Peshkov]

Why it need to be efficient? In most cases better to aim for simplicity.

[jhaglund]

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

What I did was pretty much similar to what is being described with the array of moves.

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

[sje]

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.

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.

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.

[mcostalba]

Let me add that to get the Move->SAN encoder working

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.

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