What does HackerNews think of ChessPositionRanking?

How to store a legal chess position in log_2(8726713169886222032347729969256422370854716254) ~ 152.6 bits ~ 19.1 bytes using rankings:

https://github.com/tromp/ChessPositionRanking

But the major point of this project is to allow for random sampling of positions with a decent likelihood of getting a legal one, which allows for accurate estimation of the number of legal positions.

The permutation ranking algorithm described in the article can be generalized to a so-called multinomial ranking, one of several rankings implemented in Haskell [1]. E.g.

   > let r = multinomialRanking (zip "abc" [1..3])
   > size r
   60
   > unrank r 42
   "cbcabc"
   > rank r "cbcabc"
   42

Various types of rankings, together with combinators to build up more complex ones, were implemented as part of the chess position ranking project [2] which aims to rank a subset of all chess positions that includes all legal ones:

    > let cpr = sideToMoveRanking `composeURI` (caseRanking `composeRI` wArmyStatRanking `composeURI` bArmyStatRanking `composeRI` guardRanking `composeRI` enPassantRanking `composeURI` epOppRanking `composeURI` sandwichRanking `composeRI` opposeRanking `composeURI` pawnRanking `composeURI` castleRanking `composeURI` wArmyRanking `composeURI` bArmyRanking `composeURI` pieceRanking) $ emptyURPosition
    > size cpr
    8726713169886222032347729969256422370854716254
    > writeFEN . toPosition . unrank cpr $ 2389124290426577024216048831051262280148947032
    "1r6/1qrRPk2/1rn1Rn1n/1RQRR2R/3P4/3b2BN/1Knn1b1b/1BR5 w - - 0 1"
    > rank cpr . fromPosition . readFEN $ "1r6/1qrRPk2/1rn1Rn1n/1RQRR2R/3P4/3b2BN/1Knn1b1b/1BR5 w - - 0 1"
    2389124290426577024216048831051262280148947032

Position data includes side to move, castling status, and en-passant status. This ranking allows one to sample millions of random such positions, determine how many are legal, and thus obtain an accurate estimate of 4.8 * 10^44 legal chess positions.

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

[2] https://github.com/tromp/ChessPositionRanking

I recently wrote a Haskell module [1] for computing with so-called Rankings, which I formalize as a triple consisting of a size, an unrank function that maps integers in the range 0..size-1 to objects, and a rank function that maps objects to integers.

A similar Haskell module [2] was written by Brent Yorgey.

The multinomialRanking function in my module generalizes the binomial rankings considered in the article, as well as permutations. By composing all kinds of rankings together, some very interesting classes of objects can be enumerated.

Even very densely coded chess positions; by nesting 14 different rankings, I obtained a ranking of size ~ 8.7x10^45 that includes all legal chess positions. Sampling millions of random chess positions [3] and determining their legality [4] allowed us to estimate the number of legal chess positions as ~ 4.8 * 10^44.

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

[2] https://hackage.haskell.org/package/simple-enumeration-0.2/d...

[3] https://github.com/tromp/ChessPositionRanking

[4] https://github.com/peterosterlund2/texel/blob/master/doc/pro...

The number of legal chess positions has now been estimated with 2 digits of accuracy as ~ 4.8 x 10^44: https://github.com/tromp/ChessPositionRanking For the game of Go, we know all 171 digits of the number: https://tromp.github.io/go/legal.htm

I programmed my Chess Position Ranking [1], used to accurately estimate the number of chess positions, in Haskell because of the ease of building powerful abstractions like a Ranking [2].

[1] https://github.com/tromp/ChessPositionRanking

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