3 ms·

There are more possible chess games than there are atoms in the universe. It can't be solved by brute force.

squidgedcricket 2y ago
There's a lot of chess configs, but there's a LOT of atoms in the observable universe. I suspect there's a few in the unobservable universe too. Chess configs = 4.8 x 10^44, Atoms > 10^70 https://tromp.github.io/chess/chess.html https://tromp.github.io/chess/chess.html https://physics.stackexchange.com/questions/47941/dumbed-down-explanation-how-scientists-know-the-number-of-atoms-in-the-universe https://physics.stackexchange.com/questions/47941/dumbed-dow... You might be able to pull off a low-resolution lookup table. Take some big but manageable number N (e.g 10^10) and calculate the maximally even distribution of those points over the total space of chessboard configurations. Then make a lookup table for those configs. In play, for configs not in the table, interpolate between nearest points in the table.
- jeremyjh 2y ago
  I didn't say chess positions, I said chess games. That number has a lower-bound of 10^120. https://en.wikipedia.org/wiki/Shannon_number https://en.wikipedia.org/wiki/Shannon_number
  - Scarblac 2y ago
    But that's not the relevant thing if we're talking about storing a best move per possible position.
    - jeremyjh 2y ago
      Unless you’ve calculated every line to a forced win or draw you don’t actually know the objective evaluation of a position and so you can’t determine “best move”. That’s what a tablebase is.
      - Scarblac 2y ago
        Yes, I figured that he would need a tablebase anyway. But that's still a few bits per position, the number of possible games doesn't come in to it.
        jeremyjh 2y ago
        A tablebase does include every possible move from every possible position. There are many transpositions, saving space but still every single possible line from a position is represented in a tablebase. How is that different from every possible game from that position? A 6-piece tablebase is 150GB. A 7 piece is 18TB. An 8 piece is thought to be 2PB, but we don't have one yet. How big do you think a 32-piece tablebase will be?

There's a lot of chess configs, but there's a LOT of atoms in the observable universe. I suspect there's a few in the unobservable universe too. Chess configs = 4.8 x 10^44, Atoms > 10^70 https://tromp.github.io/chess/chess.html https://tromp.github.io/chess/chess.html https://physics.stackexchange.com/questions/47941/dumbed-down-explanation-how-scientists-know-the-number-of-atoms-in-the-universe https://physics.stackexchange.com/questions/47941/dumbed-dow... You might be able to pull off a low-resolution lookup table. Take some big but manageable number N (e.g 10^10) and calculate the maximally even distribution of those points over the total space of chessboard configurations. Then make a lookup table for those configs. In play, for configs not in the table, interpolate between nearest points in the table.

jeremyjh 2y ago
I didn't say chess positions, I said chess games. That number has a lower-bound of 10^120. https://en.wikipedia.org/wiki/Shannon_number https://en.wikipedia.org/wiki/Shannon_number
- Scarblac 2y ago
  But that's not the relevant thing if we're talking about storing a best move per possible position.
  - jeremyjh 2y ago
    Unless you’ve calculated every line to a forced win or draw you don’t actually know the objective evaluation of a position and so you can’t determine “best move”. That’s what a tablebase is.
    - Scarblac 2y ago
      Yes, I figured that he would need a tablebase anyway. But that's still a few bits per position, the number of possible games doesn't come in to it.
      - jeremyjh 2y ago
        A tablebase does include every possible move from every possible position. There are many transpositions, saving space but still every single possible line from a position is represented in a tablebase. How is that different from every possible game from that position? A 6-piece tablebase is 150GB. A 7 piece is 18TB. An 8 piece is thought to be 2PB, but we don't have one yet. How big do you think a 32-piece tablebase will be?