1

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?

2

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.

3
  • + 1 for the rules of chess (not just how the pieces move) – NWS Jul 4 '13 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. – Ryan Jul 4 '13 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! – KennyZ Jul 5 '13 at 17:12
1

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
}
2
  • 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) – Ryan Jun 30 '13 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 – ratchet freak Jun 30 '13 at 1:16
1

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):
    mymask &= ~square_mask

pieace.addLegalMove(square_mask):
    mymask |= square_mask;

piece.canMove(x, y):
    square_mask = 1 << (x + 8 * y);
    return mymask & square_mask > 0;

But I'm fairly unfamiliar with C#, so I don't know if it handles bit masks. I assume it does.

0

If you're spending your time worrying about the fastest way, you'll never have time to develop a strong program. Computer cycles are cheap. Your cycles are a very limited resource. Optimizing at this level is the very last thing you should do. Literally.

6
  • 3
    This should be a comment at most, because it doesn't answer the question. – Rob W Jun 30 '13 at 8:00
  • @RobW: Sometimes, the best answer is that someone is asking the wrong question. – Bart van Ingen Schenau Jun 30 '13 at 9:02
  • @BartvanIngenSchenau Do you expect the OP to accept this answer and say "Ooh thanks, I didn't know!"? Probably not. I'm perfectly fine with a small note about "premature optimization", but not if the answer stops at that. – Rob W Jun 30 '13 at 9:08
  • 1
    I intended this in the spirit of "you're asking the wrong question, so the answer is to do something different" – ddyer Jun 30 '13 at 18:39
  • It's more of a... technical question than a management question, because there is no deadline the fun is had in the journey of thinking of efficient solutions – Ryan Jul 4 '13 at 17:46
0

Look out how strong chess engines implement this. A good technique is to use bitboards. A lot of work can be saved using pre-calculation. Here is one article: http://www.frayn.net/beowulf/theory.html#bitboards

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.