According to my calculations there are 72,224,643,857,443,120,117,642,452,381,178,066,698,624 ways to arrange any subset of the starting chess pieces on the board, assuming that the subset contains both kings and there are no pawns on the first or eighth rank.

Obviously, these are not all legal positions. My idea was to take a stratified random sample of these positions, check them for legality, and then use that to estimate the number of legal positions that can be made with just the starting pieces. The idea is to get a count not of all legal positions, but a specific subset of legal positions representing the positions you are likely to encounter.

So what I need now is an algorithm that can check the legality of a position. Another way to look at it is that I need a list of things that make a position illegal. Here is what I've got so far:

• One player's bishops on the same color square (I am assuming underpromotion to bishops is unlikely).
• Kings next to each other.
• Both players in check.
• Doubled pawns with the lead pawn too far from the open file.
• Pawns moved off file without capturing pieces
• Back rank pieces that have moved without pawns getting out of the way.

What else should be added to that list?

Edits: added items from posts 2 and 6

You'll want to watch the rule you use for doubled pawns -- the distance from the open file needs to be measured in terms of missing pieces from the opposing side and should be considered for all out of position pawns simultaneously.

When you put the original number together did you consider all of the positions that can arise as the result of promotions?  Each pawn can also be one of four other pieces.  The same configuration should also be considered a different position depending on who's move it is.

I also think I'd replace the rule that both kings cannot be in check with one that says the side with the move cannot already be checking the opposing king.

Good point on the missing pieces for out of file pawns.

I am not really considering promotion because of the likelihood constraint. You may want to promote to a knight on rare occasions, but in how many of those cases will it be your third knight? Same with a bishop, but how often will that be the same color as a your current bishop? The only thing I am  concerned about is two queens, which seems reasonably likely, but I'm holding off on that until I get just positions with the starting pieces.

Does it really matter whose move it is?

I guess it depends on the application -- some positions will be legal for one side to move and not another, and some positions will be legal for both.

En passant and castling rights can also make two identical positions technically different, as can the number of moves since the last capture or pawn move.  I think you'd be safe to ignore these as well on the assumption that they're also quite rare.

It absolutely matters, as was pointed out a week or so ago in another thread, the initial startimg position is only legal with White to move, there is no way you can reach that position with Black to move.

And there will be many more positions which is only legal for one side, for eg, if the Black King is in check, it can oly be Black's move.

How about a check for freed bishops that can't have escaped because the two blocking pawns have not moved-- again, it could technically be a legal position that resulted from an underpromotion to bishop but very unlikely.  You can also do a similar check for escaped Queens where no pawn has moved and escaped Rooks where no pawn has moved past the thirdrank or made a capture (noting that two adjacent pawns on the third rank could both have captured to arrive in that configuration so long as there are at least two missing opposing pieces).

 But if I'm just trying to determine if the position is legal, how does it matter? Take the check situation. The position is legal (in terms of check) as long as both players aren't in check. If both players aren't in check, it doesn't matter (in terms of check) if one of them is, so I don't need to worry about whose move it is. If both players are in check, it's illegal for both players, so I don't need to worry about whose move it is.

What is a position where I need to worry about whose move it is? If it's the one in the other thread, can you link to it so I can check it out?

Well, the starting position, only legal if it's white to move:

IMO, the same position, where both sides are able to move, would be 2 positions?

I tend to agree, but again, it depends on the intended application of the result set.

I was temporarily convinced I could maneuver the Knights to arrive back at the starting position with Black to move, but it just can't be done.  Because Knights change colours every move it takes an even number of moves.  I looked at swapping the Knights gets around this, but because you're now maneuvering two Knights, it also ends up taking an even number of moves.  Waiting moves by the rooks also end up taking an even number of moves.

It simply can't be done.

I always knew chess was better.

Okay, look at the starting position from the algorithm's perspective:

• Bishops are on different colors
• Kings are not next to each other
• It is not the case that both players are in check
• There are no doubled pawns, so don't need to check distance/captures
• No back rank pieces have moved through pawns.

So the position is legal, and we don't have to worry about whether or not it's white's move. There's a difference between positions that are only legal if it is a certain color's move and positions you cannot determine the legality of without knowing whose move it is.

I am thinking of a legal position as a position that could be reached by a sequence of legal chess moves. In that case it's one position even if it could be legal for both black and white.

And Grobe, if you keep talking about the "intended application" I'm going to have to assume you're suffering under the delusion that I'm actually going to do something with this number once I generate it. What's the fun in generating a number that can actually be used for something?

I guess the question, then, is how large a proportion of the legal positions are only legal for one side to move and is it material enough to consider it relevant.  I suspect the answer is no.  Perhaps more accurate would be to call it a legal board configuration rather than a legal position.

As for any intended applications, I hope that at a minimum you intend to share this useless number here.

What does the "likelihood" of a position - due, say, to underpromotion to a Bishop - have to do with its "legality" in this calculation?

Ooh, yes, with a complete list of FEN's, please, so I can catalogue them...

It's a trade off between the materiality of the impact of excluding them with the simplicity of the calculation.  It's an approximation, after all, and spending 99% of the time and effort on the exceptions to get the remaining 1% of the accuracy doesn't make a lot of sense. 

 I see it as a matter of practicality. There are a huge number of legal positions where one side has three rooks, three knights, three bishops, and two queens. They are all legal in the sense that they could be reached by making legal moves from the starting position. But who cares? Have you ever seen that in a game? Do you think you would ever see that in a serious game? It seems to me that such a set of pieces indicates that somebody is screwing around. Screwing around is fine if you're having fun, but there is a difference between screwing around and a "serious" game. It just seemed to me that the number of practical positions from "serious" games was a more interesting number, and one that is easier to calculate.

The promotion to a same color bishop is on the border-line. It is something you might do in a serious game. But it is again incredibly unlikely that you would do it. So is it a practical set of positions to enumerate?

But, I think if you start examining games that fit your criteria, the vast majority of them would also be highly unlikely? It is not only promotion to pieces already existing that make positions unlikely...

I'd be interested to see what kind of coverage a database of master games might have across the resulting legal positions from the sample set that you pull.  You should be able to get a rough idea how many of the legal positions have actually been realized in game play.

It's not the unlikelihood alone that's the issue -- its the unlikelihood combined with the substantial incremental complexity that considering these positions would add.  The rest of the unlikely positions are easy to deal with, these are not, so it's easier to exclude them on the assumption that they don't impact the result all that much anyway. 

 Ooh, that's a very interesting idea. Come to think of it, that would be easier to program. I already have a pgn reader, and I know where to get a ton of pgn games, so I could just have it read through the games and spit out the positions. Sort or hash the results and remove duplicates. It would take a lot of time and a fair chunk of storage. I'll have to try a test of that. It would also give me a chance to see just how unlikely it is to underpromote to a double-color bishop.