This position seems legal indeed:
The 3 missing black men are enough for the 6 white promotions RBBNNN and then also the 3 black promotions QRN are possible. There must be 1 missing man of the opposing side per 2 promotions on the side with most promotions, so that the pawns can pass towards the promotion square.
This position seems legal too:
Black has promoted QRRBBBN and 4 white men are missing. 7 < 2*4
White has promoted RBN and no black man is missing. 3 < 4
This position is labeled as legal
Black has promoted QRNNNN and 4 white men are missing. 6 < 2*4
White has promoted QBBB and 1 black man is missing. 4 = 4
This seems legal indeed.
> if you could eliminate obviously illegal positions at the source instead of after sampling.
It's not feasible to eliminate the the wrong being in check at the source.
> I guess the real fraction of legal positions will be less than 8% of your present N.
Why would you guess that? My sampling is unbiased, so the true fraction could just as easily be higher than 8%...
Wait and see until you have done your sampling of 1000 and 10000 and you have weeded out all illegal positions. Instead of 1 sample of 10000 I suggest you treat it as 10 samples of 1000 each, so that you get 10 estimates for the fraction of illegal positions. The variation between the 10 samples then gives an idea of the error margin on the obtained fraction.
> The variation between the 10 samples then gives an idea of the error margin on the obtained fraction.
That's quite unnecessary. The confidence interval can be computed directly. See https://en.wikipedia.org/wiki/Binomial_proportion_confidence_interval for details.
> if you could eliminate obviously illegal positions at the source instead of after sampling.
It's not feasible to eliminate the the wrong being in check at the source.
> I guess the real fraction of legal positions will be less than 8% of your present N.
Why would you guess that? My sampling is unbiased, so the true fraction could just as easily be higher than 8%...
He's guessing that because he has an outcome already charted out.
He's hoping you will do a bunch of homework for him and get him out of the 10^20 jam he got himself into in this thread...and this thread ...and this thread 
Hi you geeks, have you ever seen an attempt to estimate the smallest number of moves in which any legal position can be reached? We had fun trying to reach crazy positions and I guess in less than 150 moves you should be able to reach whatever is possible on a chess board. But the 150 is a wild guess. Can you post any links that might give a clue?
Interesting question for sure!
It's like asking for the radius or diameter of chess, the maximum possible shortest distance.
Seeing retrograde problems like number 6 - N. Plaksin's on https://www.janko.at/Retros/Masterworks/Part1.htm
which was constructed to take 50 pawn-less capture-less moves, it seems quite possible that even crazier positions can be constructed that take a few hundred moves to reach...
#12 #13
Is it possible to combine #12 and #13 in a matrix? Columns = 0 to 16 promotions, Rows = 32 to 2 men. By the way 'promotions' is a misnomer: a position with one queen at each side can be an original queen but can also be a promoted queen. The more sensible positions are those with 0, 1, 2 promotions. Bigamy games with 2 queens each do occur, but polygamy games with more than 4 queens are extremely rare. An underpromotion to knight, rook or even bishop occasionally occurs, but 2 or more underpromotions are extremely rare. Your random sample positions seem nearly all with crazy underpromotions.
Is it possible to split #12 in a matrix: rows = number of white men 16 to 1, columns = number of black men 16 to 1. The more relevant positions lie along or near the diagonal.
What is the meaning of the ranking number of a FEN? Is 0 the starting position, 1 to 959 the chess960 starting positions, then the other starting positions, then positions with 32 men, 31 men... until N-1 bare kings?
It's possible to make a 17x31 matrix of counts, but that's pretty low on my list of priorities.
> What is the meaning of the ranking number of a FEN? Is 0 the starting position, 1 to 959 the chess960 starting positions, then the other starting positions, then positions with 32 men, 31 men... until N-1 bare kings?
It's just the result of how I construct the ranking of chess positions:
-- Chess Position Ranking
cpr :: Ranking Position
cpr = sideToMoveRanking `composeURI` (caseRanking `composeRI` wArmyStatRanking `composeURI` bArmyStatRanking `composeRI` guardRanking `composeRI` enPassantRanking `composeURI` epOppRanking `composeURI` sandwichRanking `composeRI` opposeRanking `composeURI` pawnRanking `composeURI` castleRanking `composeURI` wArmyRanking `composeURI` bArmyRanking `composeURI` pieceRanking) $ emptyPos
So I start with all white-to-move positions. Within those, I distinguish the 18 cases that show up in the counting program of the original post. Within each one, I enumerate white and black armies according to their statistics, which include 1) number of men 2) number of pawns (excluding those fixed by enpassant) 3) number of promotions required 4) a value unique to the product of factorials of specific piece counts
The position of rank 0 therefore has white to move, no castling rights or en-passant, and has minimal white and black armies, i.e. just a king each.
The initial position shows up in the case of all castling rights, no en-passant, and maximal armies. I just computed its rank as 4363356584906475725281875852763383495825704796, which is at 49.999999999580193708 % of the ranking.
Btw, a ranking is this simple data type:
-- rank and unrank size items to/from 0..size-1
data Ranking a = Ranking {
size :: Integer,
unrank :: Integer -> a,
rank :: a -> Integer
}
#30
Thanks John for pointing me to the retrograde problem number 6 - N. Plaksin's on https://www.janko.at/Retros/Masterworks/Part1.htm. It took me a few hours to find a sequence of moves to reach this final position. The black king has to move from one side to the other and back in a very restricted way which makes the construction quite long. It took me 82 moves (164 plies) but it is very likely that it can be reached even a few moves faster, because a few of my moves were probably not the quickest. But this legal position could be a starting point for finding a lower boundary for the minimum number of moves to the most complicated legal position. With a more rigorous approach one should quickly arrive at something like 80 as a lower bound. Much more work to do ...
#32
How do you cope with en passant? Positions with say white to move and either no white pawn on the 5th rank, or a white pawn on the 5th rank but no adjacent black pawn on the 5th rank have 2 different FEN with and without the en passant bit enabled for the same position.
I only consider positions to have en-passant if there is an opposite colored pawn adjacent to the pawn that just moved 2 spaces. That is, I only consider en-passant to be relevant if it affects the set of possible next moves. If I had to represent all cases where a pawn just moved 2 spaces, then the counts would be rather larger (~25x on ep=1 counts and +18% overall). To wit:
fixwr=0 fixbr=0 ep=0 4317116501858047620299900728599356147494556640
fixwr=0 fixbr=0 ep=1 797713682412446449194544318760424166045159920
fixwr=0 fixbr=1 ep=0 6922142764395483618137561107749568789790148
fixwr=0 fixbr=1 ep=1 1340451951436822329513335659651326317561196
fixwr=0 fixbr=2 ep=0 136530769984693307040227830128737122354029
fixwr=0 fixbr=2 ep=1 25750593275802123442619111698596068754468
fixwr=1 fixbr=0 ep=0 6922142764395483618137561107749568789790148
fixwr=1 fixbr=0 ep=1 1384609882504094117860726652755665033619956
fixwr=1 fixbr=1 ep=0 11745419798256512510493235052589222172668
fixwr=1 fixbr=1 ep=1 2470059798250807939531494806990899137912
fixwr=1 fixbr=2 ep=0 235958281122206691085936171885340863152
fixwr=1 fixbr=2 ep=1 48393901917830360443544051247040975752
fixwr=2 fixbr=0 ep=0 136530769984693307040227830128737122354029
fixwr=2 fixbr=0 ep=1 27998814907755433016772517921909504307490
fixwr=2 fixbr=1 ep=0 235958281122206691085936171885340863152
fixwr=2 fixbr=1 ep=1 50923696856800114132693024275218785060
fixwr=2 fixbr=2 ep=0 4729971278292293446735355275667009679
fixwr=2 fixbr=2 ep=1 995691937108360833217384994547415494
total positions: 10263482270041599278227190263939167131130941786
I wrote a legality checker that gives the following percentages on a set of 10 million random positions:
59% Both Kings in Check, including 10% Adjacent Kings
17% Side not to move in Check
8% Unsupported Monochromatic Bishops Promotion
3% Illegal Triple Check
3% Illegal Double Check
---
90% definitely illegal
1% Discovered Check
5% Single Check
4% No Checks
---
10% possibly legal
Of the 1000 sample set, 93 are possibly legal, and
of the 10,000 sample set, 921 are.
Both of these sets may be found at https://github.com/tromp/ChessPositionRanking
I look forward to seeing other people run their legality checkers on these sets so we can compare results, and maybe track down bugs...
Kudos. You can make a case for dropping a entire order of magnitude from positions that need to be evaluated to solve chess if you extrapolate this out.
#36
error 404: cannot see the set
Another question is what fraction of positions without excess promotions is legal, that is not necessarily the same fraction as the fraction of all positions.
Can you post an extract of those possible legal FEN from the 10,000 sample set that do not contain excess promotions?
No excess promotions = possible with one regular chess set, i.e. without having to borrow extra promotion pieces from another set
A bit broader: sensible position = possible with one regular chess set with 1 spare queen from each color, such as supplied for high level over the board competitions
'Possibly legal' is a weak qualification.
I will be happy to check possibly legal FEN of sensible positions.
I removed the comma after the github link that was causing problems.
The fraction of positions with no extra promotions is only 0.00022%, so it mostly doesn't occur unless you sample millions.
The fraction of positions with at most 1 extra queen promotion is only 0.00426%.
"Possibly legal" just means I haven't had the chance to manually judge legality yet.
That is all right, but your estimate of the number of legal positions would be more accurate if you could eliminate obviously illegal positions at the source instead of after sampling.
Also the upper bound N is relevant in its own right as well as your resulting 153 bit per FEN.
Anyway, I look forward to your results of sampling 1000 and 10000 positions. I guess the real fraction of legal positions will be less than 8% of your present N.