3 ms·
Seems like longest chess game is about less than 300 turns, there are 64 cells, and even if you don't know chess, and even without efficiently coded there are
by malkia 6y ago
Seems like longest chess game is about less than 300 turns, there are 64 cells, and even if you don't know chess, and even without efficiently coded there are max of 128bits per turn (a lot of them not valid, and probably space that can be explored better) - e.g. it feels like not only the current position, but the history can be recorded in small amount of data in an URL.
- malkia 6y agoFor example, instead of using 64-bits for specifying from where the chess figure was moved, it can be the enumeration of the first chess figure for the given player, starting from top/down - so since there are max of 16 figures - it's only 16 bits. So this goes to 64+16 bits only per move. I guess you can go further...
- malkia 6y agoactually the final position is given by the type of figure - queen, king, etc. - and they have limited positions possible (not all 64) - even queen would have at the best - how many? like 27-28 possible - so 16+28 bits only now per move, and it can go lower. Replaying these moves should be almost instant (not much really)
- malkia 6y agoeven further - since the first part says what figure is moved, based on the current state - it can tell what are the possible states (in bits), and only expect that amount of bits that follow. - at the end it'll be just bag of bytes, that need to be URL encoded. Probably something that can fit in a long URL (max 2048 chars?)
- recursivecaveat 6y agoYou can get under one byte per move actually. There are less than 256 moves possible from any given chess position, so you just have an algorithm to order them, and index into that. You can do even better with variable length compression and move ordering. Here's a post from lichess about their system: https://lichess.org/blog/Wqa7GiAAAOIpBLoY/developer-update-275-improved-game-compression https://lichess.org/blog/Wqa7GiAAAOIpBLoY/developer-update-2...
- Yajirobe 6y agowhy 128bits?
- thom 6y agoYou may find this a fun read: https://lichess.org/blog/Wqa7GiAAAOIpBLoY/developer-update-275-improved-game-compression https://lichess.org/blog/Wqa7GiAAAOIpBLoY/developer-update-2...
- Someone 6y agoIn practice, 300 moves is about right. In theory, way more than 300 moves. https://www.chess.com/blog/kurtgodden/the-lo https://www.chess.com/blog/kurtgodden/the-lo ngest-possible-chess-game claims 5,870½. Picking 16 out of thin air as the average number of possible moves per turn because it is ‘about right (tm)’ and simplifies the math, that would be just over 2,435 bytes (yes, even assuming that ‘16’ is the average, that math is broken, but who cares?)