To represent chess games as strings, portable game notation (PGN) can be used. It looks like this: [Event "?"] [Site "?"] [Date "????.??.??"] [Round "?"] [White "?"] [Black "?"] [Result "0-1"] 1. e4 d5 2. exd5 Qxd5 3. c4 Qe5+ 4. Be2 g6 5. Nf3 Qe6 6. d4 c6 7. d5 cxd5 8. cxd5 Qe4 9. Nc3 Qf5 10. O-O Nf6 11. Bb5+ Bd7 12. a4 Nc6 13. Nh4 Qe5 14. dxc6 Bxc6 15. Re1 Ne4 16. f3 Bxb5 17. Nxb5 Rd8 18. Qb3 e6 19. Rxe4 Bc5+ 20. Kf1 Qxh2 21. Rxe6+ Kf8 22. Bh6+ Kg8 23. Qc3 Qg1+ 24. Ke2 Qf2# 0-1 A chess game under current standard constraints should not exceed 5,899 moves (source). The longest recorded and rated chess game in history was 269 moves (source). I have been coding in Python and experimenting with PGNs as strings, potentially to use in a web app with the GET method. Supposing I strip PGN headers except the result and limit the length of a game the string will represent to 500 moves showing only the main line: What is a very efficient and reversible way to shrink these strings down? I've seen solutions using zlib and base64 but they don't necessarily seem optimized for my particular situation. Is my best course to custom code a function to shrink the string, based on my described constraints? How big is the smallest possible URL-safe string, given a theoretical 500-move PGN string? I'll weakly attempt to answer my own questions as an amateur/autodidact here but I'll fully expect the StackOverflow gurus to swoop in and school me inside 5 minutes. Show no mercy, gang – I'll be fine. The PGN example above is the main line of a game that lasted 24 turns. The portions representing moves in the game are about 287 characters. This simple ratio expanded to 500 moves would yield a string perhaps 6,500 characters long. The character set for PGN strings looks limited to: ([, ], ", ?, +, #, -, ., *, /, [0-9], a, B, b, c, d, e, f, g, h, K, k, N, n, Q, q, R, r) The URL-safe character set is: ([0-9], [Aa-Zz], -, _, ., ~) This could get me places. I'm not concerned about security in any way. This is strictly encoding and compressing, not encrypting. But a few aspects take optimization beyond my abilities and intuitions. Legal opening moves in chess make for a discrete set of minimum-length strings. Given above constraints, the strings would all begin with the header for an open game: [Result "*"]\n\n A draw or resignation after a single move would alter the beginning of the string but also add 2 characters for a win/loss: [Result "1-0"]\n\n and a draw, "1/2-1/2", would add more characters yet. We will consider invalid any PGN string that contains a result but no moves. So one variation of the shortest possible string to be passed would be: [Result "*"]\n\n1. a3 * Also the data naturally conforms to other patterns and constraints, but I'm not sure how to leverage them for more efficient compression/encoding. I'm willing to do the work, but could any experts/pros help point me in a productive direction here? Please/thanks! Continue reading...
