←back to thread

Grandmaster-level chess without search

(github.com)
365 points lawrenceyan | 4 comments | 17 Oct 24 19:13 UTC | HN request time: 0.923s | source
Show context
squidgedcricket ◴[18 Oct 24 02:04 UTC] No.41875758[source]▶
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.

replies(3): >>41875783 #>>41875833 #>>41876086 #
jeremyjh ◴[18 Oct 24 02:21 UTC] No.41875833[source]▶
There are more possible chess games than there are atoms in the universe. It can't be solved by brute force.
replies(1): >>41875944 #
squidgedcricket ◴[18 Oct 24 02:49 UTC] No.41875944[source]▶
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://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.

replies(1): >>41877886 #
jeremyjh ◴[18 Oct 24 10:11 UTC] No.41877886[source]▶
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

replies(1): >>41879139 #
1. Scarblac ◴[18 Oct 24 13:13 UTC] No.41879139[source]▶
But that's not the relevant thing if we're talking about storing a best move per possible position.
replies(1): >>41880162 #
2. jeremyjh ◴[18 Oct 24 15:12 UTC] No.41880162[source]▶
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.
replies(1): >>41886132 #
3. Scarblac ◴[19 Oct 24 06:51 UTC] No.41886132[source]▶
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.
replies(1): >>41888193 #
4. jeremyjh ◴[19 Oct 24 15:04 UTC] No.41888193{3}[source]▶
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?