4 ms·

Would it be feasible to create a complete lookup table of 'best' moves for all given board configurations? I'm not sure how to determine the total number of co

Would it be feasible to create a complete lookup table of 'best' moves for all given board configurations? I'm not sure how to determine the total number of configurations. Not the same as a tablebase, just a single next move rather than sequence to checkmate. It wouldn't be competitive against top tier players and AI, but I wouldn't be surprised if it could beat me. 'Instantly' knowing the next move would be a cool trick.

k2xl 2y ago
The amount of data that would be required for a lookup table for all best moves for every board configuration would be infeasible. They have managed to create one for 7 pieces. Last update on trying to get to 8 piece database: https://www.chess.com/blog/Rocky64/eight-piece-tablebases-a-progress-update-and-some-results https://www.chess.com/blog/Rocky64/eight-piece-tablebases-a-...
- squidgedcricket 2y ago
  Yup, and it looks like a complete tablebase from the start of the game won't ever be feasible. > From May to August 2018 Bojun Guo generated 7-piece tables. The 7-piece tablebase contains 423,836,835,667,331 unique legal positions in about 18 Terabytes.
- andrelaszlo 2y ago
  Almost halfway there ;)
  - jeremyjh 2y ago
    There are 32 pieces on the board at the start of the game.
jeremyjh 2y ago
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.
roenxi 2y ago
That is basically what a neural network based chess engine is. The function the neural network is encoding is logically equivalent to "probability this move is the best for this board state". The resolution isn't great, and adding search to that can be used to develop an implicit measure of how accurate the function is (ie, probability the move suggested in a position remains unchanged after searching the move tree for better alternatives).

k2xl 2y ago

The amount of data that would be required for a lookup table for all best moves for every board configuration would be infeasible. They have managed to create one for 7 pieces. Last update on trying to get to 8 piece database: https://www.chess.com/blog/Rocky64/eight-piece-tablebases-a-progress-update-and-some-results https://www.chess.com/blog/Rocky64/eight-piece-tablebases-a-...

squidgedcricket 2y ago
Yup, and it looks like a complete tablebase from the start of the game won't ever be feasible. > From May to August 2018 Bojun Guo generated 7-piece tables. The 7-piece tablebase contains 423,836,835,667,331 unique legal positions in about 18 Terabytes.
andrelaszlo 2y ago
Almost halfway there ;)
- jeremyjh 2y ago
  There are 32 pieces on the board at the start of the game.

jeremyjh 2y ago

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.

roenxi 2y ago

That is basically what a neural network based chess engine is. The function the neural network is encoding is logically equivalent to "probability this move is the best for this board state". The resolution isn't great, and adding search to that can be used to develop an implicit measure of how accurate the function is (ie, probability the move suggested in a position remains unchanged after searching the move tree for better alternatives).