2 ms·

This is fun. Of course this problem is also a fun way to consider an upper bound on the total number of board states and therefore how hard it is to 'solve' che

by jmward01 10mo ago

This is fun. Of course this problem is also a fun way to consider an upper bound on the total number of board states and therefore how hard it is to 'solve' chess compared to a game like checkers. Hitting the calculator 26 bytes works out to chess being no more than 4.113761393×10⁶² possible states. I'll start my GPU solving that right now! [edit] This made me look for articles estimating this and I found this one [1] which confirms the above is in the right ballpark. Actual study (according to the article) says 4.822 x10^44 is their upper bounds [1] https://chess-grandmaster.com/how-many-possible-chess-positions-exist-the-math-behind-it/ https://chess-grandmaster.com/how-many-possible-chess-positi...

klaff 10mo ago
Wondering if there's a typo or I misunderstand something, but isn't one of these 10^18 bigger than the other? That would be a pretty big ballpark.
- jmward01 10mo ago
  When constraining an entire game being that close as an initial dart throw is pretty good I think. It is also good to use as a check on the plausibility of the author's algorithm. If they had found an encoding that was well below the current estimates for total board states then it likely would have indicated a major flaw (or a major breakthrough worthy of several papers and broader recognition!) At least that is what I meant by 'in the right ballpark'.
Someone 10mo ago
> a fun way to consider an upper bound on the total number of board states and therefore how hard it is to 'solve' chess compared to a game like checkers That and therefore doesn’t follow. As a counterexample, consider a NIM (https://en.wikipedia.org/wiki/Nim https://en.wikipedia.org/wiki/Nim) game starting with a googolplex number of piles of size 1. That has way more board states than chess or go, but is easily solved, as the game is trivial.

klaff 10mo ago

Wondering if there's a typo or I misunderstand something, but isn't one of these 10^18 bigger than the other? That would be a pretty big ballpark.

jmward01 10mo ago
When constraining an entire game being that close as an initial dart throw is pretty good I think. It is also good to use as a check on the plausibility of the author's algorithm. If they had found an encoding that was well below the current estimates for total board states then it likely would have indicated a major flaw (or a major breakthrough worthy of several papers and broader recognition!) At least that is what I meant by 'in the right ballpark'.

Someone 10mo ago

> a fun way to consider an upper bound on the total number of board states and therefore how hard it is to 'solve' chess compared to a game like checkers That and therefore doesn’t follow. As a counterexample, consider a NIM (https://en.wikipedia.org/wiki/Nim https://en.wikipedia.org/wiki/Nim) game starting with a googolplex number of piles of size 1. That has way more board states than chess or go, but is easily solved, as the game is trivial.