Answers.Body: <p>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.</p>
  
  <p>On the other hand, something like the Zobrist hash (see <a href="http://research.cs.wisc.edu/techreports/1970/TR88.pdf" rel="nofollow">this</a> or <a href="http://web.archive.org/web/20070810003508/http://www.seanet.com/~brucemo/topics/zobrist.htm%29" rel="nofollow">this</a>) 
  is a one way hash function considered to perform well in encoding chess position in 64 bits without collisions. </p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2014-03-08T09:21:24.443Z
Answers.LastActivityDate: 2014-03-08T09:21:24.443Z
Answers.UserDisplayName: Tihomir Georgiev
Answers.Body: <p>The total number of possible positions in chess is estimated to be 10^43, so the key would need to be extremely large.</p>
  
  <p>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. </p>
  
  <p>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.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2014-03-07T16:24:25.927Z
Answers.Text: 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.
Answers.UserDisplayName: newshutz
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2014-03-07T16:29:15.993Z
Answers.Text: 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.
Answers.UserDisplayName: Thomas Cleberg
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2014-03-07T19:58:16.523Z
Answers.Text: 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.
Answers.UserDisplayName: newshutz
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2014-03-08T00:07:57.050Z
Answers.Text: I apologize - my mistake was in thinking you had intended for the answer to be new unique positions.
Answers.UserDisplayName: Thomas Cleberg
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2014-03-10T20:36:13.273Z
Answers.Text: Yes, I want to know the number of new positions added by practical play. I have an approximation for total positions in new games.
Answers.UserDisplayName: newshutz
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2014-03-07T13:44:22.277Z
Answers.LastActivityDate: 2014-03-07T13:44:22.277Z
Answers.UserDisplayName: Thomas Cleberg
Body: <p>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. </p>
  
  <p>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?</p>
  
  <p>In probability terms, if the number of new positions added by a game is a random variable, what is the expected value?</p>
  
  <p>The practical result of this answer might be how large a key would a position table need in a database.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-10-17T22:58:52.590Z
Comments.Text: 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.
Comments.UserDisplayName: Sopel
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-10-20T21:25:34.753Z
Comments.Text: @Sopel your comment can be the basis of a real answer to this question. Can you expand please including expected game length etc?
Comments.UserDisplayName: Laska
Tags: <statistics><database>
Title: What is the approximate number of unique positions added by each practical game of chess?
ThreadText: # What is the approximate number of unique positions added by each practical game of chess?
  
  (Asked by: username_0 on 2014-03-06)
  
  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.
  
  **Tags:** statistics, database
  
  > **Comments:**
  > **username_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.  
  > **username_2**: @username_1 your comment can be the basis of a real answer to this question. Can you expand please including expected game length etc?  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_3 on 2014-03-08. Score: 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](http://research.cs.wisc.edu/techreports/1970/TR88.pdf) or [this](http://web.archive.org/web/20070810003508/http://www.seanet.com/~brucemo/topics/zobrist.htm%29))
  is a one way hash function considered to perform well in encoding chess position in 64 bits without collisions.
  
  
  ---
  
  ### Answer by username_4 on 2014-03-07. Score: 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.
  
  > **Comments:**
  > **username_0**: 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.  
  > **username_4**: 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.  
  > **username_0**: 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.  
  > **username_4**: I apologize - my mistake was in thinking you had intended for the answer to be new unique positions.  
  > **username_0**: Yes, I want to know the number of new positions added by practical play. I have an approximation for total positions in new games.  
  
  ---
  
  