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

Based on the title: Chess: Getting All Legal Chess Moves.

I would like to expose the approach that works well for me.

This require a way to validate a pgn file, i am using pgn-extract, but it works similary with an UCI engine and other tools.

sudo apt install pgn-extract

This can works only by starting from a valid PGN, and not a simple FEN string.

At any given round, regardless pieces, there is no more than 8⁴ = 4096 combinations, menus 64 impossible (eq: c4c4 won't ever be valid).

In fact it's way less, but that doesn't matter we are testing them all, without parsing the type piece.

By generating an array of the whole combinations:

array(4032) {
  [0]=>
  string(4) "a1a2"
  [1]=>
  string(4) "a1a3"
  [2]=>
  string(4) "a1a4"
  [3]=>
  (...) 

And pushing each entry as last move in the PGN file. If the validation failed, the move was invalid.

This works pretty well, all specials moves are taking into account, no moves are valid if checkmate, etc.

This is of course very brutal, it takes a couple of seconds.

Example code is php.

#!/usr/bin/php
<?php
$cp = file_get_contents("SINGLE_GAME-FILE.pgn");
$M = [];$ALL = [];$a = "a";
for ($i = 0;$i < 8;$i++){
  for ($j = 1;$j < 9;$j++){
    $M[] = $a.$j;
  }
  $a++; 
}
$t=0;
for ($i = 0;$i < count($M);$i++){
  for ($j = 0;$j < count($M);$j++){
    if ($M[$i]  != $M[$j]){
      $move = $M[$i].$M[$j];
      $ALL[] = $move;
      $pgn = explode("\n",$cp);
      $g =   explode(" ",end($pgn));
      $pgn[count($pgn)-1] = "";
      $g[count($g)-1] = $move;$g[]= "*";
      file_put_contents("mgen.pgn",implode("\n",$pgn).implode(" ",$g));
      system("pgn-extract -r mgen.pgn 2> .gentest.fen");
      if (!preg_match_all('~\b(Failed|Unknown|Missing)\b~i',file_get_contents(".gentest.fen"))){
        // Valid move
        echo "$move ";$t++;
      }
    }
  }
}
echo "\nFOUND $t LEGAL MOVES\n"; 

Example pgn

Answer 2

It appears that some posters don't understand chess engines sufficiently so please read carefully and research before attempting to argue:

Instead of checking to see if they can move there, check whether they can attack there. You will probably want that later for your evaluation function anyways...

I don't know if how many engines do this, but I know that Stockfish does (see evaluate.cpp in the src folder), so I assume it's fairly standard among the GOOD engines. If it needs to be done for evaluation anyways, you may as well use it in the movement generation.

Answer 3

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.

Answer 4

A move places your side in check (and thus is not allowed) if making the move permits an enemy piece to be able to make an attacking move onto your king.

Note that placing yourself in check is DIFFERENT from placing your opponent in check - when you place your opponent in check, they have a turn to respond. If you could place yourself in check, you would have 0 opportunity to respond. They'd be able to capture your king and it would always be the correct move to make, no matter how bad of a position they'd be put in, or even if they would "be in check" - they've won! There's nothing left after that.

So to see if making a move would place yourself in check, see if any enemy piece could make an attack move onto your king. That's it. You're not recursively resolving future checks or anything like that - if they can attack the king NOW, it's invalid.

Answer 5

Modify your getMoveLocations procedure to accept a flag that indicates whether to worry about moving into check. For instance, if a piece is pinned, it can still move to capture the opposing king. If the flag is set to ignore check risks, then skipping the check test will break the recursion.

Alternatively (and equivalently) write a separate method for generating moves that ignores the problem of moving into check. Use that procedure as part of your "cause the board to be in check" test.