11

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

4
  • You could run the recursive part only for those moves that would create a check (to make sure they are valid) but not the others (it does not matter if they are invalid). That should prevent infinite recursion.
    – assylias
    May 29, 2013 at 1:08
  • Did you make a class called getMoveLocations!? May 29, 2013 at 1:08
  • 1
    You are searching for possible moves "If I move here and the opponent moves there then if I move there after the opponent moves here.....will I be in check?"? Imagine making a game where you have a ball bouncing against the wall and the ball is controllable by the player, you would not limit his movement to the N paths that will not lead to collision with a wall (huge search), you would let him move in any one direction UNTILL He collides with the wall. Likewise only check if a move will put you in check when making the move, not considering all the possible moves by a piece (huge search)
    – arynaq
    May 29, 2013 at 1:13
  • The way I have set it up is that it displays all possible moves. I feel that it would lose some of its readability if when you try to move, a message box pops up and says "illegal move!". Anyhow, this makes getting possible moves more efficient but it doesn't really fix the infinite loop.
    – Mike
    May 29, 2013 at 1:19

5 Answers 5

9

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.

6
  • He also has to handling castling specially too. The King may not cross over a space under attack, so the poster needs also to check f1 or f8 for King-side castling, and d1 or d8 for Queen-side castling. May 29, 2013 at 1:30
  • Yes, and en passant. Quite complicated to do fully legal generation. All of these are handled easily if he evaluates for checks after pseudo-legal generation, though it's a bit slower.
    – Zong
    May 29, 2013 at 1:31
  • But only with castling must the poster check 2 squares; the destination, and the intermediate space. May 29, 2013 at 1:33
  • Looking at moves from the perspective of the king is a nice idea. However, it's a slight bit more complicated than you describe. For instance, an enemy bishop needs to be along the diagonal with no intervening pieces (or consider a diagonal to end at the first piece).
    – Ted Hopp
    May 29, 2013 at 1:37
  • Yes, you're right. I was thinking about how en passant can reveal blocked ray attacks.
    – Zong
    May 29, 2013 at 1:38
2

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.

8
  • By doing this, isn't there still a possibility that a move is considered invalid, when in fact it is valid?
    – Mike
    May 29, 2013 at 1:16
  • @user2430625 - I don't think so. If, as a result of a move of yours, the opponent can immediately take your king (even if its by moving a piece that would put the opponent in check), then you cannot make that move. Can you provide an example that shows otherwise?
    – Ted Hopp
    May 29, 2013 at 1:20
  • I don't think this method works for complicated positions with MANY pinned pieces. You can have circular relationships between the pinned pieces.
    – Zong
    May 29, 2013 at 1:30
  • 3
    @ZongLi - If you can immediately capture the opposing king by moving a piece, then the opposing king is in check whether or not the piece is pinned. Why would the number of pinned pieces or the complexity of the position make any difference at all? The whole point is that to test whether you are in check, you only need to test whether the opponent can capture your king in the next move.
    – Ted Hopp
    May 29, 2013 at 1:34
  • 1
    I see now, you're right, I didn't fully comprehend what you were implying. Now that I do, I have to say this requires an additional 2 plies of unnecessary move generation. This is INCREDIBLY slow (with branching factor of 36 that's possibly over 1000 times slower). As a chess programmer I'm simply stunned.
    – Zong
    May 29, 2013 at 1:41
2

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.

1

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.

5
  • If your algorithm accepts the logic of this answer, this would be a simpler and potentially less expensive evaluation to make than all the enemy's valid moves. It could be a fairly straightforward boolean operation for the king's move: if the space is a valid move for ChessPiece.KING && not under attack by the enemy's remaining pieces, then it is a valid move. If the ChessPiece.KING is under attack && has no valid moves, then the game ends in a loss.
    – scottb
    May 29, 2013 at 23:59
  • What is the difference between being able to move there and being able to attack there besides castling, en passant, and pawn advances? This is almost exactly the same as what the OP is already doing.
    – Zong
    May 30, 2013 at 1:20
  • I've never actually written a chess engine, but I've done a sizeable amount of research in this, and I think this is the best way to do it. My main concern is that the OP is using Java for a chess engine apparently they don't care about performance too much...
    – Andrew W
    May 30, 2013 at 1:22
  • 1
    @Zong Li being able to "attack" there (as I used it) means it could move their if no other rules were in place. You will want this for the evaluator eg. you protect your pieces by being able to "attack" them.
    – Andrew W
    May 30, 2013 at 1:28
  • I don't think they are too concerned about performance either, but Java can be quite fast. And while I understand what you are saying, I don't see how this offers any advantage for the OP. How would you do this faster than move generation without using bitboards or 0x88? And even then, generating the attack map is quite expensive and I don't think many engines do so. It's also not as simple to code as it is to describe it as a high level concept.
    – Zong
    May 30, 2013 at 1:36
0

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.

enter image description here enter image description here

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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