Position validity

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
rreagan
Posts: 102
Joined: Sun Sep 09, 2007 4:32 am

Position validity

Post by rreagan » Sun May 04, 2014 1:16 am

What are the minimum requirements to have a valid position when loading from FEN? Is it only that there are two kings, a valid side to move, and side-not-to-move is not in check?

Edmund
Posts: 668
Joined: Mon Dec 03, 2007 2:01 pm
Location: Barcelona, Spain
Contact:

Re: Position validity

Post by Edmund » Sun May 04, 2014 2:03 am

rreagan wrote:What are the minimum requirements to have a valid position when loading from FEN? Is it only that there are two kings, a valid side to move, and side-not-to-move is not in check?
According to the specification (http://www6.chessclub.com/help/PGN-spec) all 6 fields are required. Whether there exist certain interfaces, that can interpret shortened versions is another thing.

Some interfaces will also accept empty board FEN strings or positions with more than 2 kings. This part is not regulated in the specification.

User avatar
hgm
Posts: 24228
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Position validity

Post by hgm » Sun May 04, 2014 4:37 pm

What do you mean by 'valid position'?

WinBoard is not pedantic about this; it just sets up what you enter. If you specified a board with 64 white Kings, you get it. Whether the engine accepts it is of course another issue. Fairy-Max would. (But of course both black and white would be stalemated in that position, so it is not a very interesting one.)

In Shogi Tsume problems there is usually no King given for the side that must perform the mate, unless it actively participates.

As far as I am concerned FENs are just a method to encode 2d board setups into a character string. Whether the described position is valid depends on the rules of the game, which is beyond the FEN's jurisdiction.

Sven
Posts: 3830
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: Position validity

Post by Sven » Sun May 04, 2014 8:31 pm

rreagan wrote:What are the minimum requirements to have a valid position when loading from FEN? Is it only that there are two kings, a valid side to move, and side-not-to-move is not in check?
I guess you ask about "position validity" from the chess engine viewpoint, so neither arbitrary chess variants or other games nor invalid FENs are your subject.

There is no precise definition of a "valid position". The FIDE rules define how chess pieces can and must move, and they also define that certain kinds of moving pieces are not allowed (e.g. Art. 1.2: "Leaving one’s own king under attack, exposing one’s own king to attack and also ’capturing’ the opponent’s king are not allowed." or Art. 3.1 "It is not permitted to move a piece to a square occupied by a piece of the same colour.").

So there are positions of which we know they are illegal since they were immediately reached by an illegal move. We can detect this either by knowing the previous move or, in case of setting up a new position from an FEN, by finding an element of the position that proves the previous move, or any of its predecessors, to have been illegal (e.g. if the king of the side not having the move is in check, or if any side does not have exactly one king which would imply either an illegal capture of the king or an illegal promotion to a king).

There are, however, much more cases where we can find out that any of the previous moves must have been illegal, or in other words: that the position is unreachable from the initial chess position by a legal sequence of moves. Here is where we leave the "exact" part of the story. There are a couple of obvious checks that can be made to detect unreachable positions. But it is practically impossible to do a complete (retro) analysis, so in most engines only some basic criteria are applied. Here is a selection of some criteria that I know:

- more than two checks to the enemy king?
- double check given by two pieces that can never give double check (e.g. two pieces of the same type, or bishop with queen on diagonal)?
- pawn on 1st or 8th rank?
- number of pieces definitely resulting from a promotion exceeds (8 - number of friendly pawns)?

You could do many more checks to filter out unreachable positions, e.g. a white bishop on a dark square different from c1 together with white pawns on b2 and d2 (unreachable since the bishop could never have left c1), or white pawns a2, a3, b2 (unreachable since the Pa3 would have captured from b2 to a3 but there is another white pawn on b2), it is up to you where you draw the line. Engines are not forced to reject any kind of illegal resp. unreachable positions. In fact all unreachable positions are also illegal in the context of whole games that started from the initial chess position but often it is hard to prove it.

bob
Posts: 20814
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Position validity

Post by bob » Mon May 05, 2014 9:12 pm

Sven Schüle wrote:
rreagan wrote:What are the minimum requirements to have a valid position when loading from FEN? Is it only that there are two kings, a valid side to move, and side-not-to-move is not in check?
I guess you ask about "position validity" from the chess engine viewpoint, so neither arbitrary chess variants or other games nor invalid FENs are your subject.

There is no precise definition of a "valid position". The FIDE rules define how chess pieces can and must move, and they also define that certain kinds of moving pieces are not allowed (e.g. Art. 1.2: "Leaving one’s own king under attack, exposing one’s own king to attack and also ’capturing’ the opponent’s king are not allowed." or Art. 3.1 "It is not permitted to move a piece to a square occupied by a piece of the same colour.").

So there are positions of which we know they are illegal since they were immediately reached by an illegal move. We can detect this either by knowing the previous move or, in case of setting up a new position from an FEN, by finding an element of the position that proves the previous move, or any of its predecessors, to have been illegal (e.g. if the king of the side not having the move is in check, or if any side does not have exactly one king which would imply either an illegal capture of the king or an illegal promotion to a king).

There are, however, much more cases where we can find out that any of the previous moves must have been illegal, or in other words: that the position is unreachable from the initial chess position by a legal sequence of moves. Here is where we leave the "exact" part of the story. There are a couple of obvious checks that can be made to detect unreachable positions. But it is practically impossible to do a complete (retro) analysis, so in most engines only some basic criteria are applied. Here is a selection of some criteria that I know:

- more than two checks to the enemy king?
- double check given by two pieces that can never give double check (e.g. two pieces of the same type, or bishop with queen on diagonal)?
- pawn on 1st or 8th rank?
- number of pieces definitely resulting from a promotion exceeds (8 - number of friendly pawns)?

You could do many more checks to filter out unreachable positions, e.g. a white bishop on a dark square different from c1 together with white pawns on b2 and d2 (unreachable since the bishop could never have left c1), or white pawns a2, a3, b2 (unreachable since the Pa3 would have captured from b2 to a3 but there is another white pawn on b2), it is up to you where you draw the line. Engines are not forced to reject any kind of illegal resp. unreachable positions. In fact all unreachable positions are also illegal in the context of whole games that started from the initial chess position but often it is hard to prove it.
Your last example is legal. Promote a pawn to a light-squared bishop will do the trick. :)

User avatar
Brunetti
Posts: 112
Joined: Tue Dec 08, 2009 12:37 pm
Location: Milan, Italy
Contact:

Re: Position validity

Post by Brunetti » Thu May 15, 2014 5:36 pm

Sven Schüle wrote:- more than two checks to the enemy king?
- double check given by two pieces that can never give double check (e.g. two pieces of the same type, or bishop with queen on diagonal)?
I dn't think engines or GUIs are checking these conditions. For example, this one is accepted by ChessBase GUI and a lot of engines:
  • 7k/b7/3q4/4pn2/1r1K1r2/8/8/8 w - - 0 1
Anyway, some positions could be tricky and require retro-analysis, that is beyond engine purposes, like these legal ones:
  • 8/8/4kP2/8/3KR1B1/8/8/8 w - - 0 1
    4Q1Q1/8/4k3/8/3K4/8/8/8 w - - 0 1
So, if the game can go on there's no reason to program such a control.
Sven Schüle wrote:- pawn on 1st or 8th rank?
- number of pieces definitely resulting from a promotion exceeds (8 - number of friendly pawns)?
Both these conditions should be checked by most engines, since they often have an impact on data structures. In my engine I also check for correct pawn positions when EP flag is set; king and rooks positions according to castling rights flags; valid 50-move rule count and move number; and, obviously, side not to move in check.
Sven Schüle wrote:You could do many more checks to filter out unreachable positions, e.g. a white bishop on a dark square different from c1 together with white pawns on b2 and d2 (unreachable since the bishop could never have left c1), or white pawns a2, a3, b2 (unreachable since the Pa3 would have captured from b2 to a3 but there is another white pawn on b2), it is up to you where you draw the line. Engines are not forced to reject any kind of illegal resp. unreachable positions. In fact all unreachable positions are also illegal in the context of whole games that started from the initial chess position but often it is hard to prove it.
Agreed, hard to prove and not very useful, if the game can continue.

Alex

Post Reply