10 ms·

The number of legal chess positions estimated at 4.5x10^44 – proof games wanted

133 points by tromp 5y ago

ctmcdo 5y ago
Cool project!
civilized 5y ago
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.
Waterluvian 5y ago
Are there any intelligent approaches to automating proof games? Can I just play the position backwards, unwinding it with a bias to returning pieces to their home positions? Also isn’t this relatively easy if you can just waste turns (pointless moves by a Queen) while returning pieces back home? This is fascinating because on the surface it seems very do-able but I bet the devil is in the details.
- galdosdi 5y ago
  Great question. This was foreseen long ago (1500s?); the turn wasting thing is limited by the fifty move rule. A game ends in a draw if no pawn is moved or piece captured for 50 moves. Since pieces can only be removed not added and pawns can only move forward, never backward, this proves that cycles are not possible in chess (they certainly would be without this rule of course) See https://en.m.wikipedia.org/wiki/Fifty-move_rule https://en.m.wikipedia.org/wiki/Fifty-move_rule
  - nextaccountic 5y ago
    The rule says a player can claim a draw, but they are not obligated to do. So, if you're a player and want to exhaust the search space, this only helps you if you seek a draw; but perhaps there would be a guaranteed win somewhere if you kept playing (and the opponent didn't claim their draw).
    - PeterisP 5y ago
      There's the usual limits where one may claim a draw (threefold repetition or 50 moves without capture or pawn move), but there also are limits where a draw is automatic and should be enforced by the arbiter even if players do not request it (fivefold repetition or 75 moves without capture or pawn move).
  - pedrosorio 5y ago
    Wouldn’t the 3-fold repetition rule also prevent cycles? https://en.m.wikipedia.org/wiki/Threefold_repetition https://en.m.wikipedia.org/wiki/Threefold_repetition
agalunar 5y ago
Somewhat relatedly, François Labelle has some great pages on chess statistics and problems: https://wismuth.com/chess/statistics-games.html https://wismuth.com/chess/statistics-games.html https://wismuth.com/chess/statistics-positions.html https://wismuth.com/chess/statistics-positions.html https://wismuth.com/chess/chess.html https://wismuth.com/chess/chess.html
- tromp 5y ago
  I in fact corresponded with Francois in the past 2 weeks about the possibility of using his retrograde analysis program jacobi [1] for finding proof games, which he was kind enough to explore. It turned out to be infeasible, even when providing the program with a sequence of requires pawn captures and promotions. [1] https://wismuth.com/jacobi/ https://wismuth.com/jacobi/
GoodJokes 5y ago
You nerds needs to leave chess alone and learn how to have fun without putting your fun through a computer.
beckerdo 5y ago
"They're all legal. That is, reachable from the starting position in a valid game of chess." Help me out on the legality of some of these boards. I see excess pieces on many boards (for example, 2 or more queens, 4 or more knights of one color). Are these considered legal by pawn conversion?
- aliceryhl 5y ago
  Pawn promotions are legal moves, yes.
- syoc 5y ago
  Yes. You do not need to choose a queen when the pawn reaches the opposite side.
  - ctdonath 5y ago
    Were redundant choices culled? No point in tracking all variations of pawn > queen/rook/bishop when one includes the moves of the others.
    - tromp 5y ago
      There is sometimes a point when you need to avoid giving stalement, like in the famous Savedraa study [1] or the vastly more intricate Babson task [2]. [1] https://en.wikipedia.org/wiki/Saavedra_position https://en.wikipedia.org/wiki/Saavedra_position [2] https://en.wikipedia.org/wiki/Babson_task https://en.wikipedia.org/wiki/Babson_task
    - CrazyStat 5y ago
      Sometimes the queen having both rook and bishop moves is a liability. There are positions (real positions from real games, not merely hypothetical ones) where promoting to a queen results in immediate stalemate, while promoting to a rook wins the game. So those choices are not redundant.
  - retrac 5y ago
    There are even times when this is the right move. Sometimes you can put them in check by promoting to a knight, for example, where a queen would not. Common in beginner puzzles.
marcodiego 5y ago
About the same order of magnitude of the number of air molecules in Earth's atmosphere.
- tromp 5y ago
  Curiously, a similar observation (but just for carbon dioxide molecules) was made back in 2008 by Eric Holcomb in http://www.nwchess.com/articles/misc/chessic_coincidence.htm http://www.nwchess.com/articles/misc/chessic_coincidence.htm
JoeAltmaier 5y ago
I'd call some board positions irrelevant, if a win situation had to be traversed to get there.
- tromp 5y ago
  Can you define "win situation" ?
  - derac 5y ago
    I assume he means a forced win. Meaning if the winning side makes the correct moves, the losing side cannot win.
    - UncleMeat 5y ago
      We don't know whether the game is already a forced win for white before a single move is made. It could be. So this system is not workable because we don't know what positions are not forced wins.
      - retsibsi 5y ago
        AFAIK it's also unproven that it's not a forced win for black. (Not trying to correct you, I just think it's an interesting addition.)
- marcusbuffett 5y ago
  Do you mean like if a mate in 2 was passed over? Seems strange to dismiss that since even great players will miss a winning position sometimes.
- spicybright 5y ago
  I think the goal is estimating all legal moves, not all you'd find in a typical game. It would be interesting to define parameters for a "good move" and see how many there are, though!
thom 5y ago
So at only 10 seconds per game, we could annotate all these positions with Stockfish in a mere 10^38 years. We might even be done before all the stars go out!
- 8bitsrule 5y ago
  Don't count on those stars! They might go out in a lot less years, if those guys in Tibet keep chanting all of those names.
Fang_ 5y ago
> Black to move, and in the final position, the pawn at h4 can be captured en-passant. > They're all legal. But then, looking at the final position[1], black is in check by the knight on b2. If white's pawn can be captured en passant, this implies the knight was not the most recent move, so the black king was in check on the previous turn as well. It's obviously not legal to remain in check. What am I missing? [1] https://raw.githubusercontent.com/tromp/ChessPositionRanking/72608cf14906b989753024810fc642142605cca5/img/8686186724060380137654941364776065067846290128.png https://raw.githubusercontent.com/tromp/ChessPositionRanking...
- tromp 5y ago
  To quote from Seinfeld: "It's not you. It's me" I missed something, and clearly misclassified this position, leaving only 51 legal in the 1k set (and only 537 in the 10k set). Oops. It's embarrassing since I did pay attention to the en-passant positions in the 919-93 positions not from the smaller 1k sample, such as this one: https://github.com/tromp/ChessPositionRanking/issues/916 https://github.com/tromp/ChessPositionRanking/issues/916 I'll have to make some changes to my README. Meanwhile, congratulations on spotting the error. And I'll be sure to mention you in the eventual publication. This underscores the need to back up my classification with proof games...
  - tromp 5y ago
    As I went to look for the corresponding issue, I was surprised to not find the position among the open issues. In fact it was closed as https://github.com/tromp/ChessPositionRanking/issues/915 https://github.com/tromp/ChessPositionRanking/issues/915 So I had classified it correctly, but only AFTER making the diagrams for the 1k sample. That means the 538 count for the 10k sample still stands. Good. Less things to fix on the README :-)
  - tromp 5y ago
    A misclassified issue was found by Github user 1pab42 at https://github.com/tromp/ChessPositionRanking/issues/878 https://github.com/tromp/ChessPositionRanking/issues/878 That changes the prospective number of legal positions to 539...
TheDudeMan 5y ago
This is pretty interesting, too. Linked in the README: Number of legal Go positions https://tromp.github.io/go/legal.html https://tromp.github.io/go/legal.html
nickdrozd 5y ago
Question for Tromp: do you prefer working with computable big numbers or uncomputable big numbers?
- tromp 5y ago
  I'm assuming you're refering to the number of legal Go positions versus the number of legal chess positions. Obviously the former is more fun, since you feel like you scaled the summit when you determine the exact count in all its glory. When you can only estimate, you cannot reach the summit, only reach a little higher than the previous explorer by spending much more effort on your estimation climb. I do feel some satisfaction in having established base camp though:-)
  - nickdrozd 5y ago
    No, I mean the number of legal Go and chess positions vs Busy Beaver numbers. BB sequences don't have much in the way of summits, but they do allow for establishing basecamps more precisely.
    - tromp 5y ago
      I very much enjoyed determining functional busy beaver numbers [1]. Maybe somewhere in between the enjoyment from the computable numbers of Go and chess. There is no estimation involved there. Although there are lower bounds. The other difference being that it's a much more esoteric subject (on account of the prevalence of the Turing Machine based definition) with a much more limited audience. [1] https://oeis.org/A333479 https://oeis.org/A333479
cartesius13 5y ago
Absolutely awesome project. I will definitely try to contribute as I can in finding proof games. Though, I want to understand the problem and all the methods and mathematics used a bit better. Do you have any recommendations of resources? Hell, even if you just list topics I should look into it'd be helpful.
- tromp 5y ago
  You could check out all the references at the bottom of the README. The ranking implementation was heavily inspired by Brent Yorgey's Data.Enumeration.Invertible [1] that he blogged about at [2]. [1] https://hackage.haskell.org/package/simple-enumeration-0.2/docs/Data-Enumeration-Invertible.html https://hackage.haskell.org/package/simple-enumeration-0.2/d... [2] https://byorgey.wordpress.com/2019/07/05/lightweight-invertible-enumerations-in-haskell https://byorgey.wordpress.com/2019/07/05/lightweight-inverti...

133 points by tromp 5y ago

Cool project!

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.

Waterluvian 5y ago

Are there any intelligent approaches to automating proof games? Can I just play the position backwards, unwinding it with a bias to returning pieces to their home positions? Also isn’t this relatively easy if you can just waste turns (pointless moves by a Queen) while returning pieces back home? This is fascinating because on the surface it seems very do-able but I bet the devil is in the details.

galdosdi 5y ago
Great question. This was foreseen long ago (1500s?); the turn wasting thing is limited by the fifty move rule. A game ends in a draw if no pawn is moved or piece captured for 50 moves. Since pieces can only be removed not added and pawns can only move forward, never backward, this proves that cycles are not possible in chess (they certainly would be without this rule of course) See https://en.m.wikipedia.org/wiki/Fifty-move_rule https://en.m.wikipedia.org/wiki/Fifty-move_rule
- nextaccountic 5y ago
  The rule says a player can claim a draw, but they are not obligated to do. So, if you're a player and want to exhaust the search space, this only helps you if you seek a draw; but perhaps there would be a guaranteed win somewhere if you kept playing (and the opponent didn't claim their draw).
  - PeterisP 5y ago
    There's the usual limits where one may claim a draw (threefold repetition or 50 moves without capture or pawn move), but there also are limits where a draw is automatic and should be enforced by the arbiter even if players do not request it (fivefold repetition or 75 moves without capture or pawn move).
- pedrosorio 5y ago
  Wouldn’t the 3-fold repetition rule also prevent cycles? https://en.m.wikipedia.org/wiki/Threefold_repetition https://en.m.wikipedia.org/wiki/Threefold_repetition

agalunar 5y ago

Somewhat relatedly, François Labelle has some great pages on chess statistics and problems: https://wismuth.com/chess/statistics-games.html https://wismuth.com/chess/statistics-games.html https://wismuth.com/chess/statistics-positions.html https://wismuth.com/chess/statistics-positions.html https://wismuth.com/chess/chess.html https://wismuth.com/chess/chess.html

tromp 5y ago
I in fact corresponded with Francois in the past 2 weeks about the possibility of using his retrograde analysis program jacobi [1] for finding proof games, which he was kind enough to explore. It turned out to be infeasible, even when providing the program with a sequence of requires pawn captures and promotions. [1] https://wismuth.com/jacobi/ https://wismuth.com/jacobi/

GoodJokes 5y ago

You nerds needs to leave chess alone and learn how to have fun without putting your fun through a computer.

beckerdo 5y ago

"They're all legal. That is, reachable from the starting position in a valid game of chess." Help me out on the legality of some of these boards. I see excess pieces on many boards (for example, 2 or more queens, 4 or more knights of one color). Are these considered legal by pawn conversion?

aliceryhl 5y ago
Pawn promotions are legal moves, yes.
syoc 5y ago
Yes. You do not need to choose a queen when the pawn reaches the opposite side.
- ctdonath 5y ago
  Were redundant choices culled? No point in tracking all variations of pawn > queen/rook/bishop when one includes the moves of the others.
  - tromp 5y ago
    There is sometimes a point when you need to avoid giving stalement, like in the famous Savedraa study [1] or the vastly more intricate Babson task [2]. [1] https://en.wikipedia.org/wiki/Saavedra_position https://en.wikipedia.org/wiki/Saavedra_position [2] https://en.wikipedia.org/wiki/Babson_task https://en.wikipedia.org/wiki/Babson_task
  - CrazyStat 5y ago
    Sometimes the queen having both rook and bishop moves is a liability. There are positions (real positions from real games, not merely hypothetical ones) where promoting to a queen results in immediate stalemate, while promoting to a rook wins the game. So those choices are not redundant.
- retrac 5y ago
  There are even times when this is the right move. Sometimes you can put them in check by promoting to a knight, for example, where a queen would not. Common in beginner puzzles.

marcodiego 5y ago

About the same order of magnitude of the number of air molecules in Earth's atmosphere.

tromp 5y ago
Curiously, a similar observation (but just for carbon dioxide molecules) was made back in 2008 by Eric Holcomb in http://www.nwchess.com/articles/misc/chessic_coincidence.htm http://www.nwchess.com/articles/misc/chessic_coincidence.htm

JoeAltmaier 5y ago

I'd call some board positions irrelevant, if a win situation had to be traversed to get there.

tromp 5y ago
Can you define "win situation" ?
- derac 5y ago
  I assume he means a forced win. Meaning if the winning side makes the correct moves, the losing side cannot win.
  - UncleMeat 5y ago
    We don't know whether the game is already a forced win for white before a single move is made. It could be. So this system is not workable because we don't know what positions are not forced wins.
    - retsibsi 5y ago
      AFAIK it's also unproven that it's not a forced win for black. (Not trying to correct you, I just think it's an interesting addition.)
marcusbuffett 5y ago
Do you mean like if a mate in 2 was passed over? Seems strange to dismiss that since even great players will miss a winning position sometimes.
spicybright 5y ago
I think the goal is estimating all legal moves, not all you'd find in a typical game. It would be interesting to define parameters for a "good move" and see how many there are, though!

thom 5y ago

So at only 10 seconds per game, we could annotate all these positions with Stockfish in a mere 10^38 years. We might even be done before all the stars go out!

8bitsrule 5y ago
Don't count on those stars! They might go out in a lot less years, if those guys in Tibet keep chanting all of those names.

Fang_ 5y ago

> Black to move, and in the final position, the pawn at h4 can be captured en-passant. > They're all legal. But then, looking at the final position[1], black is in check by the knight on b2. If white's pawn can be captured en passant, this implies the knight was not the most recent move, so the black king was in check on the previous turn as well. It's obviously not legal to remain in check. What am I missing? [1] https://raw.githubusercontent.com/tromp/ChessPositionRanking/72608cf14906b989753024810fc642142605cca5/img/8686186724060380137654941364776065067846290128.png https://raw.githubusercontent.com/tromp/ChessPositionRanking...

tromp 5y ago
To quote from Seinfeld: "It's not you. It's me" I missed something, and clearly misclassified this position, leaving only 51 legal in the 1k set (and only 537 in the 10k set). Oops. It's embarrassing since I did pay attention to the en-passant positions in the 919-93 positions not from the smaller 1k sample, such as this one: https://github.com/tromp/ChessPositionRanking/issues/916 https://github.com/tromp/ChessPositionRanking/issues/916 I'll have to make some changes to my README. Meanwhile, congratulations on spotting the error. And I'll be sure to mention you in the eventual publication. This underscores the need to back up my classification with proof games...
- tromp 5y ago
  As I went to look for the corresponding issue, I was surprised to not find the position among the open issues. In fact it was closed as https://github.com/tromp/ChessPositionRanking/issues/915 https://github.com/tromp/ChessPositionRanking/issues/915 So I had classified it correctly, but only AFTER making the diagrams for the 1k sample. That means the 538 count for the 10k sample still stands. Good. Less things to fix on the README :-)
- tromp 5y ago
  A misclassified issue was found by Github user 1pab42 at https://github.com/tromp/ChessPositionRanking/issues/878 https://github.com/tromp/ChessPositionRanking/issues/878 That changes the prospective number of legal positions to 539...

TheDudeMan 5y ago

This is pretty interesting, too. Linked in the README: Number of legal Go positions https://tromp.github.io/go/legal.html https://tromp.github.io/go/legal.html

nickdrozd 5y ago

Question for Tromp: do you prefer working with computable big numbers or uncomputable big numbers?

tromp 5y ago
I'm assuming you're refering to the number of legal Go positions versus the number of legal chess positions. Obviously the former is more fun, since you feel like you scaled the summit when you determine the exact count in all its glory. When you can only estimate, you cannot reach the summit, only reach a little higher than the previous explorer by spending much more effort on your estimation climb. I do feel some satisfaction in having established base camp though:-)
- nickdrozd 5y ago
  No, I mean the number of legal Go and chess positions vs Busy Beaver numbers. BB sequences don't have much in the way of summits, but they do allow for establishing basecamps more precisely.
  - tromp 5y ago
    I very much enjoyed determining functional busy beaver numbers [1]. Maybe somewhere in between the enjoyment from the computable numbers of Go and chess. There is no estimation involved there. Although there are lower bounds. The other difference being that it's a much more esoteric subject (on account of the prevalence of the Turing Machine based definition) with a much more limited audience. [1] https://oeis.org/A333479 https://oeis.org/A333479

cartesius13 5y ago

Absolutely awesome project. I will definitely try to contribute as I can in finding proof games. Though, I want to understand the problem and all the methods and mathematics used a bit better. Do you have any recommendations of resources? Hell, even if you just list topics I should look into it'd be helpful.

tromp 5y ago
You could check out all the references at the bottom of the README. The ranking implementation was heavily inspired by Brent Yorgey's Data.Enumeration.Invertible [1] that he blogged about at [2]. [1] https://hackage.haskell.org/package/simple-enumeration-0.2/docs/Data-Enumeration-Invertible.html https://hackage.haskell.org/package/simple-enumeration-0.2/d... [2] https://byorgey.wordpress.com/2019/07/05/lightweight-invertible-enumerations-in-haskell https://byorgey.wordpress.com/2019/07/05/lightweight-inverti...