7

The average number of moves in a game of chess is about 40. This would be an average of about 80 positions in each game, but many positions are shared between games. More sharing occurs at the beginning and end of the game.

New positions arise as games are played. As we add new games to the database of chess games, how many new positions will be added by each game?

In probability terms, if the number of new positions added by a game is a random variable, what is the expected value?

The practical result of this answer might be how large a key would a position table need in a database.

Improve this question
2
  • 1
    With ~3M low level lichess games it's around 85% of unique (distinct) positions at 3M games. I did some tests and the fitting function is very close to 1.06-0.0128*ln(num_games). So ~3% relative increase after 10 times more games. For higher level games there is probably less unique positions at least at lower plies.
    – Sopel
    Commented Oct 17, 2019 at 22:58
  • @Sopel your comment can be the basis of a real answer to this question. Can you expand please including expected game length etc?
    – Laska
    Commented Oct 20, 2019 at 21:25

2 Answers 2

Reset to default
2

The total number of possible positions in chess is estimated to be 10^43, so the key would need to be extremely large.

As to how many new positions you could expect from an incremental game load, that would depend highly on the current state of the database. For example: the first game would necessarily be all new positions, the second would share at least one position with the first (the starting position) and could otherwise either completely duplicate the first game or deviate entirely.

What seems certain is that as your n rises for positions, the expected value of new positions from an incrementally loaded game would decrease heavily. If you had somehow loaded every game of chess ever played (recorded or otherwise), the expectation of a new position occurring in the next loaded game would be very small indeed.

Improve this answer
5
  • The number of practical positions is quite smaller than 10^43. The question is about the growth of new positions as actual games are added to a database.
    – newshutz
    Commented Mar 7, 2014 at 16:24
  • I understand- even if the proportion is as small as one out of a million possible positions as a practical consideration, the key would still require the ability to handle up to 10^38 unique positions.
    – Thomas Cleberg
    Commented Mar 7, 2014 at 16:29
  • Currently, the large databases have millions of games, 10^7 x 10^2 positions per game for 10^9 positions. TWIC in 2013 had a little over 200,000 games, which worse case would add about 2x10^7 positions.
    – newshutz
    Commented Mar 7, 2014 at 19:58
  • I apologize - my mistake was in thinking you had intended for the answer to be new unique positions.
    – Thomas Cleberg
    Commented Mar 8, 2014 at 0:07
  • Yes, I want to know the number of new positions added by practical play. I have an approximation for total positions in new games.
    – newshutz
    Commented Mar 10, 2014 at 20:36
2

Typical large databases like chessbase, chess-db.com, etc. contain up to 10 million chess games in total, which is roughly about 500 millions positions. Thus, if you want to encode/enumerate them in some way it would require at least 32 bit key.

On the other hand, something like the Zobrist hash (see this or this) is a one way hash function considered to perform well in encoding chess position in 64 bits without collisions.

Improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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