search

lichess-org / lila-openingexplorer

Opening explorer for lichess.org that can handle all the variants and trillions of unique positions
http://lichess.org/analysis#explorer
GNU Affero General Public License v3.0
135 stars 34 forks source link

import master games #9

Closed niklasf closed 8 years ago

niklasf commented 8 years ago

@ornicar: Are the master games going to be imported into lichess, so that they have game ids?

ornicar commented 8 years ago

I'd like to that lazily, i.e. import only when a player requests to see the game.

It requires storing the PGN somewhere. Let's discuss that in IRC soon.

niklasf commented 8 years ago

Drawing 3 million IDs at random, there's a good chance some of them will be gone by the time the corresponding game is imported.

ornicar commented 8 years ago

I suck at maths, but...

scala> 3000000 * (1d/math.pow(62,8))
res9: Double = 1.374003182770069E-8

seems unlikely to me?

niklasf commented 8 years ago

However this is the probability for: Pick one id and hold it in your hands. What is the chance any of the 3 million games collides with this particular id? (Rather than any of the millions of games yet to be played.)

niklasf commented 8 years ago

Let's say we draw those 3 million ids. Then someone plays a game. Chance to pick one of the used ids: 3000000/62^8 (neglegible)

Chance not to pick one of the used IDs: 1 - 3000000/62^8 (almost certain)

No collision two times in a row: (1-3000000/62^8)^2

No collision ten times in a row: (1-3000000/62^8)^10

The exponent is key. No collision after 10 million games: (1-3000000/62^8)^10000000 = 87%. And from here on it only gets worse ever faster.

(I ignore that the keyspace gets used up. Doesn't matter in these calculations).

ornicar commented 8 years ago

What I can do is check if an ID exists in the DB before assigning it to a new game. Problem solved.