Hacker News Reader

Comment by alexpotato | Hacker News Reader

> What does that mean? 250,000+ new accounts are being created each day. People are playing games (16,000 chess moves per second on average)

I remember reading how Dropbox and other file sharing sites used hashing to create single instances of popular files and then just used pointers from accounts with that file to save disk space.

I would imagine a LOT of chess games probably start out the same and you can therefore store a pointer to where the game is on a subset of potential game starts and then write the difference as you branch out.

I may be underestimating the possible start conditions and/or the metadata storage cost (e.g. time in the game of each move doesn't go away).

View on HN

you probably can encode a whole board in a small-ish string, something you can put in a url hash. But chess game is also a history of moves.

Pretty sure you could fit it in a 64 bit int/bitmap.

Potentially some SIMD optimisations could be done in this direction

I have played chess maybe 5 times in my life.. so I have no idea but..

Maybe you could store all the moves in an array of 2 byte ints. I doubt you can have more than 32k moves in a chess game.

Assume 10kb per game in memory. You can run 1 million games on 10gb.

Store the moves in the end, run your analysis, etc.

Or am I missing something?

I don't play chess, but my finger in the air estimate is that the whole record of the game weighs a few kb at most. I'd venture a guess that all players data and their avatars take more space. Or maybe less, but not much.

Think of it this way. Every move is from 1 position on a 64 location board to another (therefore most moves could be stored in about 12 total bits). There might be a couple more bits to represent enpassant and promotion, and my simple representation could easily be compressed, but for a regular game (generally less than 100 moves), you can store it < 1kb. (You still need the names of the participants, and maybe some other metadata, but my point is that the game compresses easily without too much thinking at all.)

The game gets even more compact in that not all source and destination squares are possible at every move, etc. But, you're dead on in your estimate.

Depends, if it’s pgn that’s just plaintext.

SCID uses 1 byte per move which is close to optimal (it splits it into 2^4 for piece and 2^4 for direction, with some edge cases).

SCID vs PC is a fantastic tool for chess players, I maintain a massive database of master games using it.

Reply on news.ycombinator.com