# What would be the fastest way of storing or calculating legal move sets for chess pieces?

For example if a move is attempted I could just loop through a list of legal moves and compare the x,y but I have to write logic to calculate those at least every time the piece is moved.

Or, I can store in an array [,] and then check if x and y are not 0 then it is a legal move and then I save the data like this [0][1][0][0] etc etc for each row where 1 is a legal move, but I still have to populate it.

I wonder what the fastest way to store and read a legal move on a piece object for calculation.

I could use matrix math as well I suppose but I don't know.

Basically I want to persist the rules for a given piece so I can assign a piece object a little template of all it's possible moves considering it is starting from it's current location, which should be just one table of data. But is it faster to loop or write LINQ queries or store arrays and matrices?

``````public class Move
{
public int x;
public int y;
}

public class ChessPiece : Move
{
private List<Move> possibleMoves { get; set; }

public bool LegalMove(int x, int y){
foreach(var p in possibleMoves)
{
if(p.x == x && p.y == y)
{  return true;  }
}
}
}
``````

Anyone know?

Figuring out the legal moves available for a particular piece on a chess board in a particular chess position is very situational, especially when considering pawns...1 space except when it is on its starting position, then two, and then throw in captures and en passant captures...so building an array of moves that are "mechanically" possible is a bit hairy to start. In the case of en passant, you even need to know whether the opponents last move enabled en passant, as the move is only valid for one move after the opponent made a move to enable it.

Then it gets further complicated by other situational considerations. Does the move expose the player's king to check? For castling, will the king have to move through check (whether final position results in check or not)? If the king is already in check, does the move counter the check?

I think you would be best off to set up rules for each piece including special considerations, direction and distance, rather than an array to step through, since you literally have to determine where the piece is designed to go, then examine whether the position after it goes there will be legal.

• + 1 for the rules of chess (not just how the pieces move)
– NWS
Jul 4, 2013 at 9:28
• I was going to have the board manage square to square but the piece object will be aware of its own legal moves pre calculated as if x,y was zero. Jul 4, 2013 at 17:44
• @ioSamurai -- I see your point. Just don't lose sight of the fact that any pre-calculated array of "legal moves" will then have to be parsed to see if any particular move results in a legal position! Jul 5, 2013 at 17:12

the easiest way would be to have the `LegalMove(Move)` use custom code for each different piece

that way you just need to check that `abs(x-m.x)==abs(y-m.y)` for a bishop for example (not counting blocking pieces)

or if you have a reference to the board and position in the piece then some custom logic would be (again for bishop):

``````IEnumerable LegalMoves(){
for(int xl = x+1,yl = y+1; yl<8 && xl<8; xl++,yl++){
if(board[xl][yl].isFree())
yield return Move(xl,yl);
else if(board[xl][yl].HasEnemy()){
yield return Move(xl,yl);
break;//can't jump over enemy
}else break;//can't jump over own pieces
}
//mirror it for each of the 4 sides
}
``````
• I wonder if there is a way that I can only have to run that LegalMoves function one time and it will store what that move is based on the x and y input (which would always be the current location of the piece) Jun 30, 2013 at 0:50
• @ioSamurai remember that the legal moves depend on other pieces on the board, besides the most amount of moves for a single piece will be 28 (queen in one of the center squares unblocked by anything) so unless you this is a real bottle neck focus on other stuff Jun 30, 2013 at 1:16

The fastest way, I think, would be to keep an array of legal moves for every piece. When you move a piece, you update the legal moves of the other pieces. For the square that you left, you add new moves to the pieces that can now move there. For the new square, you remove legal moves from the pieces that could move there before.

So (in pseudo code):

``````move piece from X0,Y0 to X1,Y1
with X0,Y0:
check surrounding squares for king/pawn moves, add legal move where appropriate
check the knight positions, add legal move where appropriate
check horizontal/vertical lines for rook/queen, add legal move where appropriate
check diagonal lines for queen/bishops, add legal move where appropriate
with X1,Y1:
same checks, but now remove legal move
``````

Of course, checks along lines should stop when they encounter another piece that is blocking the path.

It might be handy to keep some flag on the squares, so that you know if special reachability rules apply to the pawns or king/rook.

Somewhere along the line, when pieces get removed, this will get slower than just checking legal moves for the pieces themselves. At that point you might switch to a straight-forward check for the moving piece itself, abandoning updating the other pieces.

As for how to store it, a 64-bit mask would be enough to encode an 8x8 board.

``````piece.removeLegalMove(square_mask):

piece.canMove(x, y):
square_mask = 1 << (x + 8 * y);