Chess: Getting All Legal Chess Moves

Question

I am making the game chess, and have gotten virtually everything but one thing: I need to make it so that it is impossible for a player to move a piece into check. I am having trouble on how to tackle this problem.

What I have right now in pseudocode to generate valid moves is: Class getMoveLocations (I defined a location to be one of those squares in chess): If this location is in bounds, and the piece at this location is that of an enemy's, AND the simulated move does not cause the board to be in check, then add this location to the possible locations the piece can move to.

The problem with this is how I check if a chessboard is "in check". In my code, it considers a chessboard to be in "check" by gathering all enemies' move locations, and seeing if any of those enemy move locations overlap with the king's location.

Unfortunately, this is where the infinite loop starts; in order to gather all enemies' movie locations, each enemy's possible move locations needs to make sure its moves will not cause it to be in check. In order to make sure none of enemy's locations are in check, it has to gather all of the allies' potential move locations, etc. etc..

I'm stumped on how to get a working algorithm. Although my code "theoretically" makes logical sense, it can't be implemented. I'm interested in A)a more efficient way of implementing a way to check all legal moves, or B)a way to fix this infinite loop

Answer 1

There's a much more efficient method of determining whether a side is in check: you simply scan outwards from the king and see if you find pieces that can attack it. For example, from the king's position, check if any enemy bishops are along a diagonal, etc. You do not need to generate a move list at all, so recursion is not necessary. Here's some pseudocode:

function leftInCheck(board, sideToCheck) {

   // one of the four rays for bishop/queen attacks
   d := 0
   while (king rank + d, king file + d) is on the board
      piece := board[king rank + d][king file + d]
      if piece is an enemy bishop or queen
         return true
      if piece is not an empty square   // a piece blocks any potential
         break                          // attack behind it so we can stop
      d := d + 1

   // do this for all the other forms of attack
   ...

   return false
}

As you can see there's some code repetition, but you can make it shorter. I left it as is so it's simple to understand. You can generate legal moves by generating the pseudo-legal moves as you're doing now, making each one, and omitting the ones that leave you in check with the above subroutine. This has the additional advantage of en passant naturally. Here's some pseudocode:

function legalMoves(board, sideToMove) {
   moveList := empty
   for each move in pseudoLegalMoves()
      make(move)
      if not leftInCheck(board, sideToMove)
         moveList.add(move)
      unmake(move) // you may not need this
   return moveList
}

For castling you will still have to check if there are attacks on the squares between the king and rook. Fortunately this is easy as you can extend the subroutine above to work for squares other than the king's.

I assume you are not using bitboards or 0x88, but instead with a simple array representation. This makes it a bit difficult to implement legal move generation (with no intermediate pseudo-legal moves), as it requires generating attack maps very fast to determine pinned pieces. If you're ambitious, this is a possibility.

As an additional note, I'm somewhat disappointed by the other answers here. And I wouldn't even recommend my own answer to anyone who wants to write a good move generator (it's only intended for those unfamiliar with chess programming). This is a topic that has been thoroughly examined and has well known solutions, yet is eliciting original ideas. Of course there is nothing wrong with this, but why reinvent the wheel, and worse? Look into well established methods of move generation.