Inspirasi:

Terinspirasi oleh kompresi papan catur terkecil, saya memutuskan untuk membuat kompetisi yang serupa tetapi berbeda.

tl; dr

Ambil file Chess_Games.txt dan kompres sebanyak mungkin sehingga Anda dapat mengembangkannya ke file asli.

Objektif:

Tulis algoritme untuk menyandikan dan mendekode seluruh basis data catur dari posisi awal hingga akhir

Pengkodean harus dapat menentukan untuk semua game semua posisi:

• Lokasi semua bagian
• Giliran siapa itu
• Apakah pemain dapat melakukan kastil di setiap sisi.
• Apakah pemain dapat melakukan en-passant, dan jika demikian, mana dari pion mereka?
• Posisi sebelumnya

Selain itu:

• Setiap permainan juga harus menyertakan siapa yang menang dan bagaimana itu berakhir (kehilangan, menggambar, skakmat, kebuntuan, dll ...)

Input output:

Harus ada 2 algoritma Compress / Expand yang memenuhi properti berikut:

• Compress mengambil file game melalui urutan gerakan melalui notasi catur dan output file terkompresi

• Expand melakukan yang sebaliknya, dengan mengambil file terkompresi dan mengeluarkan file asli dengan semua game dalam urutan yang sama

• Kebenaran: Perluas (Kompres (file)) = file untuk semua file yang terbentuk dengan benar

Game apa pun yang tidak dibentuk dengan baik atau melanggar aturan catur dianggap buruk. Semua game yang buruk dapat dilewati.

Itu harus dapat mengurai notasi sen. Lihatlah chessgames.com dan https://database.lichess.org/ untuk beberapa contoh.

Saya telah menyusun file 10.000 game pertama dari "Mei 2017" di Chess_Games.txt

File tersebut akan terlihat seperti berikut:

e4 d5 exd5 Nf6 d3 Qxd5 Nc3 Qf5 Be2 Bd7 g4 Qe6 g5 Nd5 Ne4 Bc6 Bg4 Qe5 f4 Qd4 Nf3 Qb6 Qe2 e6 Be3 Qa6 O-O Nd7 c4 Ne7 f5 Bxe4 dxe4 exf5 exf5 O-O-O f6 gxf6 gxf6 Nc6 Nd4 Nxd4 Bxd4 Bc5 Bxc5 Rhg8 Be7 Rde8 b4 Qxf6 Bxf6 Rxe2 h3 h5 Kh1 hxg4 Rg1 Nxf6 Rae1 Rxe1 Rxe1 gxh3 Kh2 Ng4+ Kxh3 Nf2+ Kh2 Ng4+ Kg3 f5 Kf4 Nh6 Re7 Rg4+ Ke5 Kd8 Kf6 Ng8+ Kf7 Nxe7 Kf8 f4 c5 f3 c6 f2 cxb7 Nc6 b8=Q+ Nxb8 Kf7 Kd7 0-1
d3 e6 e3 d5 Nf3 Nf6 Be2 Be7 O-O O-O Nc3 Nbd7 Ne1 c5 f3 e5 e4 d4 Nb1 b6 f4 exf4 Rxf4 Qc7 Rf3 Bd6 g3 Ng4 Rf1 Ndf6 Bxg4 Bxg4 Qd2 Rae8 Qf2 Re5 Bf4 Rh5 Bxd6 Qxd6 Nf3 c4 e5 Rxe5 Nxe5 Qxe5 Nd2 cxd3 cxd3 Be2 Rfe1 Qe3 Qxe3 dxe3 Ne4 Bxd3 Nxf6+ gxf6 Rxe3 Bg6 Rae1 Kg7 h4 h5 R1e2 Bf5 Rg2 Bg4 Re4 Kg6 Rge2 f5 Re5 f6 Re6 Rg8 Re7 Rg7 Re8 1-0
d4 d5 e4 dxe4 c4 Nf6 Qc2 Bf5 Nc3 Qxd4 Be3 Qe5 Nge2 e6 Ng3 Bb4 a3 Bxc3+ bxc3 Nc6 Be2 Na5 O-O Nxc4 Bd4 Qb5 Nxf5 exf5 Bxf6 gxf6 Rab1 Nxa3 Qa2 Qxb1 Rxb1 Nxb1 Qxb1 O-O-O Qb3 b6 Ba6+ Kb8 Qb5 Rhe8 Qc6 1-0
e3 c5 d3 d5 Nf3 Nc6 Be2 Nf6 O-O g6 h3 Bg7 Re1 O-O Nbd2 Re8 Nf1 e5 c3 b6 N3h2 Bb7 Qc2 Qc7 b3 Rac8 Bb2 a5 Rac1 a4 Qb1 axb3 axb3 Ba6 d4 Bxe2 Rxe2 exd4 cxd4 Qb8 dxc5 d4 Ree1 dxe3 Rxe3 Nd5 Rxe8+ Rxe8 Bxg7 Kxg7 Re1 Rxe1 Qxe1 bxc5 Qd1 Nd4 Ne3 Nf4 Neg4 Qxb3 Qe1 Qd5 Ne3 Qe6 Qf1 c4 Nhg4 Nde2+ Kh2 c3 g3 c2 gxf4 c1=Q Qxc1 Nxc1 Ng2 Qe4 Kg3 Nd3 f3 Qe2 Nh4 h5 Nh2 Qe1+ Kg2 Nf2 Nf5+ gxf5 Kg3 Qg1+ Kh4 Nxh3 Kxh5 1-0
e4 d5 exd5 Qxd5 Nc3 Qd8 d4 Bf5 Nf3 e6 Nh4 Bg6 Nxg6 hxg6 Be3 Bd6 Bc4 a6 Qf3 c6 O-O-O Nd7 Ne4 Qc7 Nxd6+ Qxd6 Bf4 Qb4 Bb3 Ngf6 Rhe1 O-O-O Bg3 a5 Qf4 Qb6 Re3 Rh5 Bc4 Rf5 Qd6 Ne8 Qa3 Qa7 Red3 b5 Bxb5 cxb5 Rc3+ Kb7 Qe7 b4 Rc5 Rxc5 dxc5 Qxc5 Qxd8 Ndf6 Qb8+ Ka6 Rd8 Qa7 Rxe8 Nxe8 Qxe8 Qc5 Qa8+ Kb5 Qb8+ Ka4 b3+ Ka3 Qf4 Qc3 Qe5 1-0
e4 d5 exd5 Qxd5 Nf3 Qd8 Nc3 e6 Bc4 Nf6 Bb3 Be7 a3 a6 O-O O-O h3 b6 d3 Bb7 Bg5 Nbd7 Ne4 h6 Bh4 Nxe4 Bxe7 Qxe7 dxe4 Bxe4 Re1 Bb7 Ba2 Nf6 b4 Rfd8 Qc1 Qd6 c4 Qc6 Qc2 Rd7 Rac1 Rad8 c5 bxc5 Qxc5 Qb5 Qxb5 axb5 Ne5 Rd2 Bb3 Rb2 Bd1 Rdd2 Re2 Rxe2 Bxe2 Rxe2 Nf3 Ra2 Rxc7 Bd5 Rc8+ Kh7 Ne5 Rxa3 Rf8 Ra1+ Kh2 h5 Rxf7 Kh6 Rf8 Kg5 g3 Kf5 Nd7 Ra2 Nxf6 gxf6 Rg8 Rxf2+ Kg1 Rg2+ Kf1 Rh2 g4+ hxg4 hxg4+ Ke5 Re8 Rh1+ Kf2 Rh2+ Kg3 Rg2+ Kh4 Rf2 Kg3 Rf4 g5 Re4 gxf6 Kxf6 Rf8+ Ke5 Rh8 Re3+ Kf2 Re4 Rh5+ Kd4 Rh6 Rf4+ Kg3 Re4 Rh8 Re3+ 0-1
...

Mencetak:

Untuk membuat sesuatu menjadi objektif, pemenangnya adalah algoritma yang dapat memampatkan file di https://database.lichess.org/ sekecil mungkin. Basis data target adalah "Mei 2017" . Pemenangnya adalah siapa pun yang memiliki file terkecil yang diperluas dengan benar.

File yang akan digunakan adalah Chess_Games.txt yang merupakan 10.000 game pertama dari database "Mei 2017" di https://database.lichess.org/ dengan semua informasi header dihapus. File ini akan menjadi patokan untuk digunakan. Seharusnya 2.789.897 byte dengan hash SHA-256 56b6d2fffc7644bcd126becd03d859a3cf6880fa01a47fa08d4d6a823a4866bc(Pastebin mungkin menghapus baris baru terakhir setelah pertandingan 10000)

Solusi Naif:

Menggunakan algoritma kompresi generik:

• zip: 647.772 byte (76,841%)
• 7z: 652.813 byte (76,661%)
• bz2: 722.158 byte (74,182%)
• xz: 784.980 byte (71,936%)
• rar: 853.482 byte (69,487%)
• gz: 923.474 byte (66,985%)

Python, skor = 426508 byte

Fungsi Kompresi: (m + 1) ⋅ log ₂ (b + 1)

m adalah jumlah gerakan dan b adalah faktor percabangan

Percobaan 1:

Saya menjawab pertanyaan di kompresi papan catur terkecil, jadi saya mencoba memperbaikinya untuk dikirim ke sini.

Secara naif saya berpikir bahwa saya dapat mengkodekan setiap gerakan dalam 12 bit, 4 triplet dari bentuk (mulai x, mulai y, akhir x, akhir y) di mana masing-masing 3 bit.

Kami akan mengasumsikan posisi awal dan memindahkan potongan dari sana dengan putih akan menjadi yang pertama. Papan disusun sedemikian rupa sehingga (0, 0) adalah sudut kiri bawah putih.

Misalnya gim:

  e4    e5
 Nf3    f6
Nxe5  fxe5
...    ...

Akan dikodekan sebagai:

100001 100010 100110 100100
110000 101010 101110 101101
101010 100100 101101 100100
...

Ini mengarah ke pengkodean 12 m bit di mana m adalah jumlah gerakan yang dilakukan.

Percobaan 2:

Saya menyadari bahwa setiap gerakan dalam upaya sebelumnya menyandikan banyak gerakan ilegal. Jadi saya memutuskan untuk hanya menyandikan langkah hukum. Kami menghitung langkah yang mungkin sebagai berikut, beri angka setiap kuadrat sedemikian sehingga (0, 0) → 0, (1, 0) → 1, (x, y) → x + 8 y. Iterasi melalui ubin dan periksa apakah ada potongan di sana dan apakah itu bisa bergerak. Jika demikian, tambahkan posisi yang dapat dituju ke daftar. Pilih indeks daftar yang merupakan langkah yang ingin Anda buat. Tambahkan nomor itu ke total gerakan yang dibobot oleh 1 ditambah jumlah gerakan yang mungkin.

Contoh seperti di atas: Dari posisi awal, potongan pertama yang bisa bergerak adalah ksatria di kotak 1, dapat bergerak ke kotak 16 atau 18, jadi tambahkan itu ke daftar [(1,16),(1,18)]. Berikutnya adalah ksatria di kotak 6, tambahkan gerakannya. Secara keseluruhan kami mendapatkan:

[(1,16),(1,18),(6,21),(6,23),(8,16),(8,24),(9,17),(9,25),(10,18),(10,26),(11,19),(11,27),(12,20),(12,28),(13,21),(13,29),(14,22),(14,30),(15,23),(15,31)]

Karena kami menginginkan gerakan (12, 28), kami menyandikan ini sebagai 13 di basis 20 karena ada 20 kemungkinan gerakan.

Jadi sekarang kita mendapatkan nomor g g = ₀

Selanjutnya kita melakukan hal yang sama untuk hitam kecuali kita memberi nomor ubin secara terbalik (untuk membuatnya lebih mudah, tidak diperlukan) untuk mendapatkan daftar langkah:

[(1,16),(1,18),(6,21),(6,23),(8,16),(8,24),(9,17),(9,25),(10,18),(10,26),(11,19),(11,27),(12,20),(12,28),(13,21),(13,29),(14,22),(14,30),(15,23),(15,31)]

Karena kami menginginkan gerakan (11, 27), kami menyandikan ini sebagai 11 di basis 20 karena ada 20 kemungkinan gerakan.

Jadi sekarang kita mendapatkan nomor g permainan ₁ = (11 ⋅ 20) + 13 = 233

Selanjutnya kita mendapatkan daftar langkah untuk putih:

[(1,16),(1,18),(3,12),(3,21),(3,30),(3,39),(4,12),(5,12),(5,19),(5,26),(5,33),(5,40),(6,12),(6,21),(6,23),(8,16),(8,24),(9,17),(9,25),(10,18),(10,26),(11,19),(11,27)(13,21),(13,29),(14,22),(14,30),(15,23),(15,31)]

Karena kami menginginkan gerakan (6, 21), kami menyandikan ini sebagai 13 di basis 29 karena ada 29 kemungkinan gerakan.

Jadi sekarang kita mendapatkan nomor permainan g ₂ = ((13 ⋅ 20) + 11) 20 + 13 = 5433

Selanjutnya kita mendapatkan daftar langkah untuk hitam: [(1,11),(1,16),(1,18),(2,11),(2,20),(2,29),(2,38),(2,47),(3,11),(4,11),(4,18),(4,25),(4,32),(6,21),(6,23),(8,16),(8,24),(9,17),(9,25),(10,18),(10,26),(12,20),(12,28),(13,21),(13,29),(14,22),(14,30),(15,23),(15,31)]

Karena kami menginginkan gerakan (10, 18), kami menyandikan ini sebagai 19 di basis 29 karena ada 29 kemungkinan gerakan.

Jadi sekarang kita mendapatkan nomor g permainan ₃ = (((19 ⋅ 29 + 13) 20) + 11) 20 + 13 = 225833

Dan lanjutkan proses ini untuk semua gerakan yang tersisa. Anda dapat menganggap g sebagai fungsi g (x, y, z) = x y + z. Jadi g ₀ = g (1, 1, 13), g ₁ = g (g (1, 1, 11), 20, 13), g ₂ = g (g (g (1, 1, 13), 20, 11), 20, 13), g ₃ = g (g (g (g (1, 1, 19), 29, 13), 20, 11), 20, 13)

Untuk memecahkan kode nomor g permainan ₀ , kita mulai dari posisi awal dan menghitung semua gerakan yang mungkin. Kemudian kita menghitung g ₁ = g ₀ // l , m ₀ = g ₀ % l , di mana l adalah jumlah gerakan yang mungkin, '//' adalah operator pembagian integer dan '%' adalah operator modulus. Seharusnya menyatakan bahwa g ₀ = g ₁ + m ₀ . Selanjutnya kita buat langkah m ₀ dan ulangi.

Dari contoh di atas jika g ₀ = 225833 maka g ₁ = 225833 // 20 = 11291 dan m ₀ = 225833% 20 = 13. Selanjutnya g ₂ = 11291 // 20 = 564 dan m ₁ = 11291% 20 = 11. Kemudian g ₃ = 11291 // 20 = 564 dan m ₂ = 11291% 20 = 11. Karena itu g ₄ = 564 // 29 = 19 dan_m_ ₃ = 564% 29 = 13. Akhirnya g ₅ = 19 // 29 = 0 dan m ₄ = 19% 29 = 19.

Jadi berapa banyak bit yang digunakan untuk meng-encode game dengan cara ini?

Untuk kesederhanaan, katakanlah selalu ada 35 gerakan setiap belokan ( https://en.wikipedia.org/wiki/Branching_factor ) dan untuk skenario terburuk kami selalu memilih yang terbesar, 34. Angka yang akan kami dapatkan adalah 34 ⋅ 35 ^m + 34 ⋅ 35 ^m-1 + 34 ⋅ 35 ^m-2 + ⋯ + 34 ⋅ 35 + 34 = 35 ^{m + 1} - 1 di mana _m adalah jumlah gerakan. Untuk mengkodekan 35 ^{m + 1} - 1 kita membutuhkan sekitar log ₂ (35 ^{m + 1} ) bit yang kira-kira (m + 1) ⋅ log ₂ (35) = 5.129 ⋅ (m + 1)

Rata-rata m = 80 (40 gerakan per pemain) sehingga ini akan membutuhkan 416 bit untuk dikodekan. Jika kami merekam banyak permainan, kami akan memerlukan pengodean universal karena kami tidak tahu berapa banyak bit yang dibutuhkan setiap angka

Kasus terburuk ketika m = 11741 jadi ini akan mengambil 60.229 bit untuk dikodekan.

Catatan tambahan:

Perhatikan bahwa g = 0 menunjukkan gim yang valid, gim di mana potongan pada kuadrat terendah bergerak ke kuadrat terendah.

Jika Anda ingin merujuk ke posisi tertentu dalam permainan, Anda mungkin perlu menyandikan indeks. Ini dapat ditambahkan baik secara manual misalnya menggabungkan indeks ke permainan, atau menambahkan gerakan "akhir" tambahan sebagai langkah terakhir yang mungkin dilakukan setiap belokan. Ini sekarang dapat menjelaskan kebobolan pemain, atau 2 berturut-turut untuk menunjukkan bahwa pemain setuju untuk bermain seri. Ini hanya diperlukan jika permainan tidak berakhir dengan skakmat atau kebuntuan berdasarkan posisi, dalam hal ini tersirat. Dalam hal ini ia membawa jumlah bit yang dibutuhkan rata-rata menjadi 419 dan dalam kasus terburuk 60706.

Cara untuk menangani garpu dalam skenario bagaimana-jika adalah untuk menyandikan permainan hingga ke garpu dan kemudian menyandikan setiap cabang mulai dari posisi bercabang alih-alih posisi awal.

Penerapan:

Lihatlah repo github saya untuk kode: https://github.com/edggy/ChessCompress

Python, skor = 418581 byte

Ini menggunakan varian bijective dari sistem angka asimetris . Karena bersifat obyektif, Anda tidak hanya dapat mengompres daftar permainan catur yang valid ke dalam file dan mengembangkannya kembali ke daftar yang sama — Anda juga dapat memperluas file apa saja ke dalam daftar permainan catur yang valid dan mengompresnya kembali ke file yang sama! Sempurna untuk menyembunyikan koleksi porno Anda.

Membutuhkan python-catur . Jalankan dengan python script.py compressatau python script.py expand, keduanya akan membaca dari input standar dan menulis ke output standar.

import chess
import sys

RESULTS = ['1-0\n', '1/2-1/2\n', '0-1\n', '*\n']
BITS = 24

def get_moves(board):
    if board.is_insufficient_material() or not board.legal_moves:
        return [board.result() + '\n']
    else:
        return RESULTS + sorted(
            board.legal_moves,
            key=lambda move: (move.from_square, move.to_square, move.promotion))

def read_bijective():
    buf = bytearray(getattr(sys.stdin, 'buffer', sys.stdin).read())
    carry = 0
    for i in range(len(buf)):
        carry += buf[i] + 1
        buf[i] = carry & 0xff
        carry >>= 8
    if carry:
        buf.append(carry)
    return buf

def write_bijective(buf):
    carry = 0
    for i in range(len(buf)):
        carry += buf[i] - 1
        buf[i] = carry & 0xff
        carry >>= 8
    while carry:
        carry = (carry << 8) + buf.pop() + 1
    getattr(sys.stdout, 'buffer', sys.stdout).write(buf)

def add_carry(buf, carry):
    for i in range(len(buf)):
        if carry == 0:
            break
        carry += buf[i]
        buf[i] = carry & 0xff
        carry >>= 8
    return carry

def do_compress():
    board = chess.Board()
    state = 0
    buf = bytearray()

    games = []
    for sans in sys.stdin:
        game = []
        for san in sans.split(' '):
            move = san if san in RESULTS else board.parse_san(san)
            moves = get_moves(board)
            game.append((len(moves), moves.index(move)))
            if move in RESULTS:
                board.reset()
            else:
                board.push(move)
        games.append(game)

    for game in reversed(games):
        for (n, i) in reversed(game):
            q = ((1 << BITS) - 1 - i) // n + 1
            while state >= q << 8:
                buf.append(state & 0xff)
                state >>= 8
            hi, j = divmod(state, q)
            lo = n * j + i
            state = hi << BITS | lo
        state += add_carry(buf, 1)

    while state:
        buf.append(state & 0xff)
        state >>= 8
    write_bijective(buf)

def do_expand():
    board = chess.Board()
    state = 0
    buf = read_bijective()

    while True:
        while buf and state < 1 << BITS:
            state = state << 8 | buf.pop()
        if state == 0:
            break
        state += add_carry(buf, -1)

        while True:
            moves = get_moves(board)
            while buf and state < 1 << BITS:
                state = state << 8 | buf.pop()
            n = len(moves)
            hi, lo = divmod(state, 1 << BITS)
            j, i = divmod(lo, n)
            q = ((1 << BITS) - 1 - i) // n + 1
            state = j + q * hi
            move = moves[i]
            if move in RESULTS:
                sys.stdout.write(move)
                board.reset()
                break
            else:
                sys.stdout.write(board.san(move).rstrip('+#') + ' ')
                board.push(move)

if __name__ == '__main__':
    {'compress': do_compress, 'expand': do_expand}[sys.argv[1]]()