Hacker News Reader

Comment by civilized | Hacker News Reader

Why do they make such a big deal out of having numbered the positions? That's kind of a basic thing about a countable set, you can enumerate its elements if you want. We already knew the set of legal chess positions was countable.

View on HN

Because it's very hard to make a numbering that's both:

1. compact, in that it uses a relatively narrow range of numbers.

2. efficiently computable, in that you can quickly map numbers (or preferably, thousands of them) to positions, and back.

The combination of these is what allows for estimating the number of legal positions.

Thanks, that is helpful! Let me ask a more specific question. Combinatorics gives us lots of ways to calculate the sizes of sets, and in my experience, they rarely if ever involve an explicit enumeration. Why then is an explicit enumeration an important milestone in this particular problem? To a combinatorialist, it would be more interesting to see the more-easily-countable-structure you're presumably mapping these positions to/from.

This chess position ranking wouldn't be possible without making use of such combinatorics, as you can see with the use [1] [2] of the multinomial ranking [3].

You're right that counting is much easier than ranking. That's reflected in my Haskell counting program [4] being MUCH simpler and MUCH faster than the ranking program. But counting is only good for upper bounding and doesn't let you draw a random sample to determine the fraction of legal ones, as needed for estimation.

[1] https://github.com/tromp/ChessPositionRanking/blob/main/src/...

[2] https://github.com/tromp/ChessPositionRanking/blob/main/src/...

[3] https://github.com/tromp/ChessPositionRanking/blob/main/src/...

[4] https://github.com/tromp/ChessPositionRanking/blob/main/src/...

So at a high level, you need the ranking because you need to do computations on individual elements of the set (e.g. random samples) to refine the estimate. Which is not necessary in a lot of ordinary combinatorics problems, but is here because this one is so hard. Cool, thank you!

I can imagine this project being of interest in the seminar of the right university department.

> Combinatorics gives us lots of ways to calculate the sizes of sets, and in my experience, they rarely if ever involve an explicit enumeration.

I don't think that this is true. I think that explicit enumerations are rarer than exact size computations, which are themselves rarer than asymptotic size estimations, for presumably obvious reasons; but a bijective proof (https://en.wikipedia.org/wiki/Bijective_proof) is still regarded as the gold standard in combinatorics, and as a desideratum.

A bijective proof isn't the same as an enumeration, which is a bijection to the set 1,2,3...

Of course you can derive an enumeration by bijection to a set with an existing enumeration, but the point is that that's usually not of interest.

I've experimented with using factoradic (mixed radix) numbers to index into the combinatorial gamestates for Magic the Gathering.

I think the knowledge that the set is countable and can thus be counted is, as you say, quite obvious. However, actually counting it or generating the complete set is terrifically hard in practice. There are many more illegal positions than legal ones (I suspect, would be curious to know if this is actually the case). Moreover each legal position may be the result of thousands of games played legally or thousands of games played illegally. Computers historically haven't been able to enumerate this set, or judge from a position if it is conclusively legal or illegal since the complexity of that question is immense. We're on the cusp of being able to do that and I think that's what makes this project more than a trivial exercise in counting countable things.

Reply on news.ycombinator.com