Inspiration:

Ich war stark von der kleinsten Schachbrettkomprimierung inspiriert und entschied mich für einen ähnlichen, aber deutlich anderen Wettbewerb.

tl; dr

Nehmen Sie die Datei Chess_Games.txt und komprimieren Sie sie so weit wie möglich, damit Sie sie auf die Originaldatei erweitern können.

Zielsetzung:

Schreiben Sie einen Algorithmus zum Codieren und Decodieren einer gesamten Schachdatenbank von der Startposition bis zum Ende

Die Codierung muss in der Lage sein, für alle Spiele alle Positionen zu bestimmen:

• Die Lage aller Stücke
• Wessen dran ist es
• Ob der Spieler auf jeder Seite burgieren kann.
• Ob der Spieler einen En-Passanten ausführen kann und wenn ja, welcher seiner Bauern?
• Die vorherige Position

Zusätzlich:

• Jedes Spiel sollte auch enthalten, wer gewonnen hat und wie es endete (verwirkt, unentschieden, Schachmatt, Patt usw.).

Input-Output:

Es sollten 2 Algorithmen zum Komprimieren / Erweitern vorhanden sein, die die folgenden Eigenschaften erfüllen:

• Compress nimmt eine Spieledatei über eine Folge von Zügen in Schachnotation auf und gibt eine komprimierte Datei aus

• Expand macht das Gegenteil, nimmt eine komprimierte Datei auf und gibt die Originaldatei mit allen Spielen in derselben Reihenfolge aus

• Richtigkeit: Erweitern (Komprimieren (Datei)) = Datei für alle ordnungsgemäß erstellten Dateien

Jedes Spiel, das nicht gut geformt ist oder gegen die Schachregeln verstößt, wird als schlecht angesehen. Alle schlechten Spiele können übersprungen werden.

Es muss in der Lage sein, die Notation zu analysieren. Einige Beispiele finden Sie unter chessgames.com und https://database.lichess.org/ .

Ich habe eine Datei der ersten 10000 Spiele von "Mai 2017" in zusammengestellt Chess_Games.txt zusammengestellt

Die Datei sollte wie folgt aussehen:

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
...

Wertung:

Der Gewinner ist der Algorithmus, mit dem die Dateien unter https://database.lichess.org/ so klein wie möglich komprimiert werden können. Die Zieldatenbank ist der "Mai 2017" . Der Gewinner ist derjenige, der die kleinste Datei hat, die ordnungsgemäß erweitert wird.

Die zu verwendende Datei ist Chess_Games.txt. Dies sind die ersten 10000 Spiele aus der Datenbank "Mai 2017" unter https://database.lichess.org/, bei der alle Header-Informationen entfernt wurden. Diese Datei wird als Benchmark verwendet. Es sollte 2.789.897 Bytes mit einem SHA-256-Hash von sein 56b6d2fffc7644bcd126becd03d859a3cf6880fa01a47fa08d4d6a823a4866bc(Pastebin entfernt möglicherweise die letzte neue Zeile nach Spiel 10000).

Naive Lösung:

Verwenden generischer Komprimierungsalgorithmen:

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

Python, Punktzahl = 426508 Bytes

Komprimierungsfunktion: (m + 1) ⋅ log ₂ (b + 1)

m ist die Anzahl der Züge und b ist der Verzweigungsfaktor

Versuch 1:

Ich habe die Frage bei der kleinsten Schachbrettkomprimierung beantwortet, also versuche ich, sie zu reparieren, um sie hier zu posten.

Naiv dachte ich, dass ich jede Bewegung in 12 Bits, 4 Tripletts der Form (Start x, Start y, Ende x, Ende y) codieren kann, wobei jede 3 Bits ist.

Wir würden die Startposition einnehmen und Teile von dort bewegen, wobei Weiß zuerst geht. Die Tafel ist so angeordnet, dass (0, 0) die untere linke Ecke von Weiß ist.

Zum Beispiel das Spiel:

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

Würde verschlüsselt werden als:

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

Dies führt zu einer Codierung von 12 m Bits, wobei m die Anzahl der durchgeführten Bewegungen ist.

Versuch 2:

Mir wurde klar, dass jeder Zug im vorherigen Versuch viele illegale Züge codiert. Deshalb habe ich beschlossen, nur legale Schritte zu kodieren. Wir zählen mögliche Bewegungen wie folgt auf und nummerieren jedes Quadrat so, dass (0, 0) → 0, (1, 0) → 1, (x, y) → x + 8 y. Durchlaufen Sie die Kacheln und prüfen Sie, ob ein Teil vorhanden ist und sich bewegen kann. Wenn ja, fügen Sie die Positionen hinzu, die zu einer Liste führen können. Wählen Sie den Listenindex aus, den Sie verschieben möchten. Addieren Sie diese Zahl zur laufenden Summe der mit 1 gewichteten Züge plus der Anzahl der möglichen Züge.

Beispiel wie oben: Von der Startposition aus kann sich der Ritter auf Feld 1 als erstes bewegen. Er kann sich auf Feld 16 oder 18 bewegen. Fügen Sie diese also zur Liste hinzu [(1,16),(1,18)]. Als nächstes kommt der Ritter auf Feld 6 und fügt seine Züge hinzu. Insgesamt bekommen wir:

[(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)]

Da wir den Zug wollen (12, 28), codieren wir diesen in Basis 20 als 13, da es 20 mögliche Züge gibt.

Jetzt erhalten wir die Spielnummer g ₀ = 13

Als nächstes machen wir dasselbe für Schwarz, außer dass wir die Kacheln umgekehrt nummerieren (um es einfacher zu machen, nicht erforderlich), um die Liste der Züge zu erhalten:

[(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)]

Da wir den Zug (11, 27) wollen, codieren wir diesen in Basis 20 als 11, da es 20 mögliche Züge gibt.

Jetzt erhalten wir die Spielnummer g ₁ = (11 ⋅ 20) + 13 = 233

Als nächstes erhalten wir die folgende Liste von Zügen für Weiß:

[(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)]

Da wir den Zug wollen (6, 21), codieren wir diesen in Basis 29 als 13, da es 29 mögliche Züge gibt.

Jetzt erhalten wir die Spielnummer g ₂ = ((13 ⋅ 20) + 11) 20 + 13 = 5433

Als nächstes erhalten wir die folgende Liste von Zügen für Schwarz: [(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)]

Da wir den Zug wollen (10, 18), codieren wir diesen in Basis 29 als 19, da es 29 mögliche Züge gibt.

Jetzt erhalten wir die Spielnummer g ₃ = (((19 ⋅ 29 + 13) 20) + 11) 20 + 13 = 225833

Und setzen Sie diesen Vorgang für alle verbleibenden Züge fort. Sie können sich g als die Funktion g (x, y, z) = x y + z vorstellen. Somit ist 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)

Um eine Spielnummer g ₀ zu dekodieren , beginnen wir an der Ausgangsposition und zählen alle möglichen Züge auf. Dann berechnen wir g ₁ = g ₀ // l , m ₀ = g ₀ % l , wobei l die Anzahl der möglichen Züge ist, '//' der ganzzahlige Divisionsoperator und '%' der Moduloperator ist. Es sollte gelten, dass g ₀ = g ₁ + m ₀ . Als nächstes machen wir die Bewegung m ₀ und wiederholen.

Aus dem obigen Beispiel, wenn g ₀ = 225833, dann ist g ₁ = 225833 // 20 = 11291 und m ₀ = 225833% 20 = 13. Als nächstes g ₂ = 11291 // 20 = 564 und m ₁ = 11291% 20 = 11. Dann g ₃ = 11291 // 20 = 564 und m ₂ = 11291% 20 = 11. Daher ist g ₄ = 564 // 29 = 19 und_m_ ₃ = 564% 29 = 13. Schließlich ist g ₅ = 19 // 29 = 0 und m ₄ = 19% 29 = 19.

Wie viele Bits werden verwendet, um ein Spiel auf diese Weise zu codieren?

Nehmen wir zur Vereinfachung an, es gibt immer 35 Züge pro Runde ( https://en.wikipedia.org/wiki/Branching_factor ) und im schlimmsten Fall wählen wir immer den größten aus, 34. Die Zahl, die wir erhalten, ist 34 ⋅ 35 ^m + 34 ⋅ 35 ^m-1 + 34 ⋅ 35 ^m-2 + ⋯ + 34 ⋅ 35 + 34 = 35 ^{m + 1} - 1 wobei _m die Anzahl der Züge ist. Um 35 ^{m + 1} - 1 zu codieren, benötigen wir ungefähr log ₂ (35 ^{m + 1} ) Bits, was ungefähr (m + 1) ≤ log ₂ (35) = 5,129 ≤ (m + 1) ist.

Im Durchschnitt ist m = 80 (40 Züge pro Spieler), daher würde die Codierung 416 Bit dauern. Wenn wir viele Spiele aufnehmen würden, würden wir eine universelle Codierung benötigen, da wir nicht wissen, wie viele Bits jede Zahl benötigt

Der schlimmste Fall, wenn m = 11741 ist, würde die Codierung 60229 Bit erfordern.

Zusätzliche Bemerkungen:

Beachten Sie, dass g = 0 ein gültiges Spiel bezeichnet, bei dem sich die Figur auf dem untersten Feld auf das niedrigste Feld bewegt, das sie kann.

Wenn Sie sich auf eine bestimmte Position im Spiel beziehen möchten, müssen Sie möglicherweise den Index codieren. Dies kann entweder manuell hinzugefügt werden, z. B. um den Index zum Spiel zu verketten, oder es kann ein zusätzlicher "End" -Zug als letzter möglicher Zug in jeder Runde hinzugefügt werden. Dies kann nun dazu führen, dass Spieler kassieren oder 2 in Folge, um die Spieler zu kennzeichnen, die einem Unentschieden zugestimmt haben. Dies ist nur erforderlich, wenn das Spiel nicht in einem Schachmatt oder einer Pattsituation aufgrund der Position endete. In diesem Fall ist dies impliziert. In diesem Fall wird die Anzahl der durchschnittlich benötigten Bits auf 419 und im schlimmsten Fall auf 60706 erhöht.

Eine Möglichkeit, Gabeln in einem Was-wäre-wenn-Szenario zu handhaben, besteht darin, das Spiel bis zur Gabel zu codieren und dann jeden Zweig beginnend an der gegabelten Position anstelle der Anfangsposition zu codieren.

Implementierung:

In meinem Github-Repo finden Sie den Code: https://github.com/edggy/ChessCompress

Python, Punktzahl = 418581 Bytes

Dies verwendet eine bijektive Variante asymmetrischer Zahlensysteme . Da es bijektiv ist, können Sie nicht nur eine gültige Liste von Schachspielen in eine Datei komprimieren und wieder auf dieselbe Liste erweitern - Sie können auch jede Datei in eine gültige Liste von Schachspielen erweitern und auf dieselbe Datei zurückkomprimieren! Perfekt, um deine Pornosammlung zu verstecken.

Benötigt Python-Schach . Führen Sie mit python script.py compressoder aus python script.py expand, wobei beide von der Standardeingabe lesen und in die Standardausgabe schreiben.

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]]()