Take the 2-minute tour ×
Chess Stack Exchange is a question and answer site for serious players and enthusiasts of chess. It's 100% free, no registration required.

I am doing a personal project, where at one point I need to validate the FEN position, I started with some basics checks, such as check if there are kings and making sure there aren't any extra rows or columns, and that kind of things.

But what other checks should I do to completely make sure a FEN is legal?

share|improve this question
add comment

3 Answers

up vote 9 down vote accepted

Here is a well organized list that should validate 99.99%+ of common positions:

Board:

  • There are exactly 8 cols
  • The row sum of the empty squares and pieces add to 8

Kings:

  • See if there is exactly one w_king and one b_king
  • Make sure kings are separated 1 square apart

Checks:

  • Non-active color is not in check
  • Active color is checked less than 3 times; in case of 2 that it is never pawn+(pawn, bishop, knight), bishop+bishop, knight+knight

Pawns:

  • There are no more than 8 pawns from each color
  • There aren't any pawns in first or last rows
  • In case of en passant square; see if it was legally created (e.g it must be on the x3 or x6 row, there must be a pawn (from the correct color) in front of it, and the en passant square and the one behind it are empty)
  • Prevent having more promoted pieces than missing pawns (e.g extra_pieces = Math.max(0, num_queens-1) + Math.max(0, num_rooks-2)... and then extra_pieces <= (8-num_pawns)), also you should do special calculations for bishops, If you have two (or more) bishops from the same square color, these can only be created through pawn promotion and you should include this information to the formula above somehow
  • The pawn formation is possible to reach (e.g in case of multiple pawns in a single col, there must be enough enemy pieces missing to make that formation), here are some useful rules:
    1. it is impossible to have more than 6 pawns in a single column (because pawns can't exist in the first and last ranks)
    2. it is impossible to have more than 5 pawns in a or h columns
    3. the minimum number of enemy missing pieces to reach a multiple pawn in a single col B to G 2=1, 3=2, 4=4, 5=6, 6=9 ___ A and H 2=1, 3=3, 4=6, 5=10, 6=impossible, for example, if you see 5 pawns in A or H, the other player must be missing at least 10 pieces from his 15 captureable pieces
    4. if there are white pawns in a2 and a3, there can't legally be one in b2, and this idea can be further expanded to cover more possibilities

Castling:

  • If the king or rooks are not in their starting position; the castling ability for that side is lost (in the case of king, both are lost)

Bishops:

  • Look for bishops in the first and last rows trapped by pawns that haven't moved, for example:
    1. a bishop (any color) trapped behind 3 pawns
    2. a bishop trapped behind 2 non-enemy pawns (not by enemy pawns because we can reach that position by underpromoting pawns, however if we check the number of pawns and extra_pieces we could determine if this case is possible or not)

Non-jumpers:

  • If there are non-jumpers enemy pieces in between the king and rook and there are still some pawns without moving; check if these enemy pieces could have legally gotten in there. Also, ask yourself: was the king or rook needed to move to generate that position? (if yes, we need to make sure the castling abilities reflect this)
  • If all 8 pawns are still in the starting position, all the non-jumpers must not have left their initial rank (also non-jumpers enemy pieces can't possibly have entered legally), there are other similar ideas, like if the white h-pawn moved once, the rooks should still be trapped inside the pawn formation, etc.

Half/Full move Clocks:

  • In case of an en passant square, the half move clock must equal to 0
  • HalfMoves <= ((FullMoves-1)*2)+(if BlackToMove 1 else 0), the +1 or +0 depends on the side to move
  • The HalfMoves must be x >= 0 and the FullMoves x >= 1

Other:

  • Make sure the FEN contains all the parts that are needed (e.g active color, castling ability, en passant square, etc)

Note: there is no need to make the 'players should not have more than 16 pieces' check because the points 'no more than 8 pawns' + 'prevent extra promoted pieces' + the 'exactly one king' should already cover this point

Note2: these rules are intended to validate positions arising from the starting position of normal chess, some of the rules will invalidate some positions from Chess960 (exception if started from arrangement Nº518) and generated puzzles.

share|improve this answer
1  
You can also check the pawn structure, for example white pawns could never be on a2, a3, and b2; there is no way a pawn could be on both a3 and b2. –  Akavall Nov 3 '12 at 14:19
    
Is that to say FEN positions should only be achievable from the initial position? What if I wanted to have puzzle positions represented by a FEN? Sometimes they are created in a way impossible to reach in an actual game... –  tbischel Jun 24 '13 at 18:45
    
@tbischel I making these rules from the normal chess perspective (not intended for Chess960 or other generated positions), thanks I might point this somewhere to make it clearer –  ajax333221 Jun 24 '13 at 19:27
    
Even for normal chess, you may not want to do all of these checks. You end up with a program that can't represent an illegal position as FEN. But they do happen in practice -- illegal moves are sometimes only noticed after the game. Should it be impossible to show diagrams from such games, and so on? –  RemcoGerlich Sep 17 '13 at 19:51
add comment
\s*([rnbqkpRNBQKP1-8]+\/){7}([rnbqkpRNBQKP1-8]+)\s[bw-]\s(([a-hkqA-HKQ]{1,4})|(-))\s(([a-h][36])|(-))\s\d+\s\d+\s*

Here's a regular expression that I use to ensure that a FEN string is actually valid. It doesn't do any testing for a legal/illegal position, but it's a good starting point.

share|improve this answer
    
I think the active color is a must (you are allowing -) and half/full clocks are sometimes optional I think. Also I didn't understand the a-h part on castling ability, I rewrote it to /^\s*([rnbqkpRNBQKP1-8]+\/){7}([rnbqkpRNBQKP1-8]+)\s[bw]\s(-|K?Q?k?q?)\s(-|[a-h‌​][36])/ –  ajax333221 Mar 7 '13 at 23:55
    
I just noted we can do the "no pawns in promotion ranks" test with something starting like ([rnbqkRNBQK1-8]+\/)([rnbqkpRNBQKP1-8]+\/){6}([rnbqkRNBQK1-8]+) .... –  ajax333221 Jul 4 '13 at 17:48
    
also for the clocks this might be good (0|[1-9][0-9]*)\s([1-9][0-9]*) as moves can't have leading zeros and full move can't be or start with 0, (code credit) –  ajax333221 Sep 16 '13 at 19:48
add comment

Here is a simple backtracking algorithm, provided that you have a function that can check reverse legal moves at every board state (also known as position):

function is_legal_state(state,move)

   //Terminate if a starting state was found. This immediately implies there
   //was a legal game that generated this state, in fact the backtracking
   //can tell you precisely such a game       
   if (state in starting board state)
     return true

   //Apply some move to get to a new state, state is a persistent object
   apply_reverse_move(state,move)

   //Generate all legal "reverse" moves, that is, moves that could have
   //been performed to get to the current state from another position,
   //provided the previous position was valid. You do not have to check the
   //validness of the previous state, you just have to make sure the
   //transitioning move was valid
   legalmoves = enumerate_all_reverse_moves( state )

   for local_move in legalmoves:
     return is_legal_state(state,local_move)

   //Reverse the move that was previously applied so backtracking can
   //work properly 
   reverse_reverse_move(state,move)

   return false
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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