0
$\begingroup$

Assuming that a database entry schema contains two 64-bit hash IDs generated via the algorithm explained here, in the section "Generating Hash Keys for Chess Boards", and simply a score that's a 32-bit integer, how many bytes would the database need to be to guarantee that it can store every possible game state of chess?

$\endgroup$
  • $\begingroup$ Better asked on a chess site. But have you thought about the problem? $\endgroup$ – gnasher729 Jul 5 '17 at 6:58
2
$\begingroup$

Claude Shannon indicated that the State Space Complexity (number of legal positions reachable from the initial position in chess) has a lower bound of approximately $10^{43}$. If each entry consists of $20$ bytes, as indicated in your question. The total number of bytes for your database would have a lower bound of $2 * 10^{44}$ which is a very large number indeed.

I would suggest reading Section 2: General Considerations of Shannon's paper, Relevant quote:

Another (equally impractical) method is to have a "dictionary" of all possible positions of the chess pieces. For each possible position there is an entry giving the correct move (either calculated by the above process or supplied by a chess master.) At the machine's turn to move it merely looks up the position and makes the indicated move. The number of possible positions, of the general order of $64! / 32!(8!)^2(2!)^6$ , or roughly $10^{43}$, naturally makes such a design unfeasible.

References:

$\endgroup$
  • $\begingroup$ Thank you, I'm not sure why I never got a notification for this answer. That is an incredibly large amount of memory. $\endgroup$ – Patrick Roberts Jul 10 '17 at 4:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.