Hacker News Reader

Comment by tromp | Hacker News Reader

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.

View on HN

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

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.

Reply on news.ycombinator.com