Ignore the 3-time repetition and 50-move rules. What is the number P of chess positions reachable via a legal game? Finding the exact answer is too hard, but finding good upper & lower bounds is doable. A "position" should know what the pieces are, where they are, who is to move, what are the castling rights, and what the available en passant captures (if any) are. Note that pawns can only be located on ranks 2-6, not 1,8; and that if M pieces and P pawns have been captured, then at most 2*M+3*P promotions could have happened. And many pawn configurations are impossible unless enough captures happened... John Tromp claimed P<=7728772977965919677164873487685453137329736522=2^152.437 as the result of a computer program he has not described, but this is unlikely to be optimal (assuming it is correct). For somebody determined enough: I think it should be possible to determine the answer accurate to 5% by first creating a good encoding scheme, say which proves P<2^155, and then sampling random positions for each deciding if it really would be reachable. Assuming deciding reachability is actually feasible 99.999% of the time, and assuming P>2^144, we would after 2 million random samples find at least about 1000 reachable positions and at most about 20 whose reachability was unknown. This would be good enough for a 5% accurate (Monte Carlo) estimate. If P<2^150, then the proof tree of chess (at least ignoring 50-move rule) would presumably be about 2^75 positions, suggesting chess might actually be feasibly solvable (?!). -- Warren D. Smith