4 ms·

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

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.

tromp 5y ago
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.
- civilized 5y ago
  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.
  - tromp 5y ago
    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/Chess/Position/Ranking.hs#L412 https://github.com/tromp/ChessPositionRanking/blob/main/src/... [2] https://github.com/tromp/ChessPositionRanking/blob/main/src/Chess/Position/Ranking.hs#L424 https://github.com/tromp/ChessPositionRanking/blob/main/src/... [3] https://github.com/tromp/ChessPositionRanking/blob/main/src/Data/Ranking.hs#L14-L37 https://github.com/tromp/ChessPositionRanking/blob/main/src/... [4] https://github.com/tromp/ChessPositionRanking/blob/main/src/CountChess.hs https://github.com/tromp/ChessPositionRanking/blob/main/src/...
    - civilized 5y ago
      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.
  - JadeNB 5y ago
    > 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 https://en.wikipedia.org/wiki/Bijective_proof) is still regarded as the gold standard in combinatorics, and as a desideratum.
    - civilized 5y ago
      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.
- emidln 5y ago
  I've experimented with using factoradic (mixed radix) numbers to index into the combinatorial gamestates for Magic the Gathering.
academia_hack 5y ago
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.

tromp 5y ago

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.

civilized 5y ago
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.
- tromp 5y ago
  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/Chess/Position/Ranking.hs#L412 https://github.com/tromp/ChessPositionRanking/blob/main/src/... [2] https://github.com/tromp/ChessPositionRanking/blob/main/src/Chess/Position/Ranking.hs#L424 https://github.com/tromp/ChessPositionRanking/blob/main/src/... [3] https://github.com/tromp/ChessPositionRanking/blob/main/src/Data/Ranking.hs#L14-L37 https://github.com/tromp/ChessPositionRanking/blob/main/src/... [4] https://github.com/tromp/ChessPositionRanking/blob/main/src/CountChess.hs https://github.com/tromp/ChessPositionRanking/blob/main/src/...
  - civilized 5y ago
    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.
- JadeNB 5y ago
  > 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 https://en.wikipedia.org/wiki/Bijective_proof) is still regarded as the gold standard in combinatorics, and as a desideratum.
  - civilized 5y ago
    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.
emidln 5y ago
I've experimented with using factoradic (mixed radix) numbers to index into the combinatorial gamestates for Magic the Gathering.

academia_hack 5y ago

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.