Hacker News Reader

Comment by Sesse__ | Hacker News Reader

We can do a rough estimate.

There are (_very_) roughly half as many squares in 6x6 as there are in 8x8. This means that for every piece you add, you can expect (again very roughly) a 50% bonus to your branching factor. Now look at the best tablebases currently available (Syzygy):

Up to 5 pieces: 1GB Up to 6 pieces: 151GB Up to 7 pieces: 17277GB

So, let's assume the factor of 140 per extra piece; of course this doesn't hold perfectly, but still:

Up to 8 pieces: 2418TB Up to 9 pieces: 338PB Up to 10 pieces: 47320PB

Now divide that last number by our 2^10 bonus. That leaves 46PB for 10-piece tablebases. We were asked for 24-piece. This is unlikely to go down well.

Of course, there will be some small additional bonus for the fact that fewer positions are possible (easier to be in check), double-pawn-push doesn't apply, no en passant or castling to worry about, and fewer piece types. Still, it honestly doesn't look that good. :-)

View on HN

Your analysis would pretty similarly apply to 5x5 Gardner's chess which has been weakly solved. Simple tree search can be quite effective as the branching factor is cut down a significant amount (2x in the starting position). Gardner's chess was completely solved without any tablebases.

It is only an argument against building a complete tablebase. Additionally because the extra space is reduced the high piece count version is likely the be much smaller than this would predict because pieces cannot overlap.

Just looking at the piece positions without regard to the types shows a better than 2x relationship for tablebase size.

(64 choose 7) / (64 choose 8) ~ 10% whereas (36 choose 7) / (36 choose 8) ~ 25%

Additionally, because the tablebase would need to go past 18, the possible piece positions would actually shrink. To be clear, the tablebase would not shrink because of the piece types.

I'm not sure if you can call it “completely solved” if it's only weakly solved, but sure. It's a different goal (and my answer was a response to a “can't we just build a tablebase” comment).

I'm really only interested in weakly solved, i.e. "forced draw from starting position" like the 5x5 variant, not a perfect play tablebase from all possible positions.

Given that 5x5 is (weakly) solved, even though your rough estimates would put its 20-piece 5x5 starting position outside the realm of possibility, I don't think you're discounting accurately how much a reduced board/piece/ruleset can affect those exploding permutations for 6x6 as well.

Well, it helps if you can meet-in-the-middle, roughly. And it helps a _lot_ to do a weak solve, i.e., you don't care about winning won positions, only showing a draw with perfect play.

Note that the number of possible legal positions will likely be largest with fewer than 24 pieces. For regular chess, I've calculated that there are most legal positions for 29 pieces: https://github.com/lechmazur/ChessCounter?tab=readme-ov-file...

It doesn't really matter, since every position with 24 pieces can change into one with fewer. So you need the sum of all of those values.

For a more sophisticated estimation of the number of legal positions, taking into account _true_ legality (a legal position must be reachable by a sequence of legal moves from the starting position, however dumb), see https://github.com/tromp/ChessPositionRanking. You can probably filter their sample by number of pieces to gain pretty accurate estimations for number of 29-piece positions if you wish.

This matters in the context of your statement of "factor of 140 per extra piece," which doesn't hold when the number of pieces nears the maximum.

> For regular chess, I've calculated that there are most legal positions for 29 pieces

Improved counting shows the maximum to occur at 28 pieces [1] (also see the issue I filed on your github repo).

[1] https://www.chess.com/forum/view/general/on-the-number-of-ch...

I don't have time to go through the thread at this time but I see that in the first post of this thread you just confirmed the number I calculated (8.7E+45) instead of your earlier estimate of 4.5E+46?

Your page only mentions

> Upper bound estimate of possible legal chess position (counts en passant, castling, sides to move, allows underpromotions): 8.7E+45.

But how exactly is this number determined? Is this a sampling based estimate?

My 8726713169886222032347729969256422370854716254 is an exact upperbound on the number of so-called urpositions, and is not sampling based.

In any case it will be easier to continue this discussion at https://github.com/lechmazur/ChessCounter/issues/1

Reply on news.ycombinator.com