Nicht unbedingt eine Frage, eher ein Rätsel ...

Im Laufe der Jahre war ich an einigen technischen Interviews mit neuen Mitarbeitern beteiligt. Abgesehen von den Standardfragen "Kennst du die X-Technologie?" Habe ich auch versucht, ein Gefühl dafür zu bekommen, wie sie Probleme angehen. Normalerweise sende ich ihnen die Frage am Tag vor dem Interview per E-Mail und erwarte, dass sie am nächsten Tag eine Lösung finden.

Oft waren die Ergebnisse ziemlich interessant - falsch, aber interessant - und die Person erhielt immer noch meine Empfehlung, wenn sie erklären konnte, warum sie einen bestimmten Ansatz gewählt hatte.

Also dachte ich, ich würde eine meiner Fragen an das Stack Overflow-Publikum richten.

Frage: Was ist die platzsparendste Methode, um den Status eines Schachspiels (oder einer Teilmenge davon) zu codieren? Das heißt, wenn ein Schachbrett mit den legal angeordneten Figuren vorhanden ist, codieren Sie sowohl diesen Ausgangszustand als auch alle nachfolgenden legalen Züge, die von den Spielern im Spiel ausgeführt werden.

Für die Antwort ist kein Code erforderlich, nur eine Beschreibung des Algorithmus, den Sie verwenden würden.

EDIT: Wie eines der Poster gezeigt hat, habe ich das Zeitintervall zwischen den Zügen nicht berücksichtigt. Fühlen Sie sich frei, dies auch als optionales Extra zu berücksichtigen :)

EDIT2: Nur zur zusätzlichen Verdeutlichung ... Denken Sie daran, dass der Encoder / Decoder regelbewusst ist. Die einzigen Dinge, die wirklich gespeichert werden müssen, sind die Entscheidungen des Spielers - alles andere kann vom Encoder / Decoder als bekannt angenommen werden.

EDIT3: Es wird schwierig sein, hier einen Gewinner zu ermitteln :) Viele tolle Antworten!

Update: Dieses Thema hat mir so gut gefallen, dass ich Programmierpuzzles, Schachpositionen und Huffman-Codierung geschrieben habe . Wenn Sie dies durchlesen, habe ich festgestellt, dass die einzige Möglichkeit, einen vollständigen Spielstatus zu speichern, darin besteht, eine vollständige Liste der Züge zu speichern. Lesen Sie weiter, warum. Daher verwende ich eine leicht vereinfachte Version des Problems für das Stücklayout.

Das Problem

Dieses Bild zeigt die Startposition Schach. Schach findet auf einem 8x8-Brett statt, wobei jeder Spieler mit einem identischen Satz von 16 Figuren beginnt, die aus 8 Bauern, 2 Türmen, 2 Rittern, 2 Bischöfen, 1 Königin und 1 König bestehen, wie hier dargestellt:

Positionen werden im Allgemeinen als Buchstabe für die Spalte aufgezeichnet, gefolgt von der Nummer für die Zeile, sodass die Königin von Weiß bei d1 liegt. Bewegungen werden meistens in algebraischer Notation gespeichert , die eindeutig ist und im Allgemeinen nur die erforderlichen minimalen Informationen angibt. Betrachten Sie diese Öffnung:

1. e4 e5
2. Sf3 Sc6
3. …

was übersetzt bedeutet:

1. Weiß bewegt den Bauern des Königs von e2 nach e4 (es ist das einzige Stück, das zu e4 gelangen kann, daher „e4“);
2. Schwarz bewegt den Bauern des Königs von e7 auf e5;
3. Weiß bewegt den Ritter (N) auf f3;
4. Schwarz bewegt den Ritter auf c6.
5. …

Das Board sieht so aus:

Eine wichtige Fähigkeit für jeden Programmierer besteht darin , das Problem korrekt und eindeutig spezifizieren zu können .

Was fehlt oder ist nicht eindeutig? Viel, wie sich herausstellt.

Board State vs Game State

Als erstes müssen Sie feststellen, ob Sie den Status eines Spiels oder die Position der Spielsteine ​​auf dem Brett speichern. Es ist eine Sache, einfach die Positionen der Teile zu kodieren, aber das Problem lautet „alle nachfolgenden rechtlichen Schritte“. Das Problem sagt auch nichts darüber aus, die Bewegungen bis zu diesem Punkt zu kennen. Das ist eigentlich ein Problem, wie ich erklären werde.

Rochade

Das Spiel ist wie folgt verlaufen:

1. e4 e5
2. Sf3 Sc6
3. Lb5 a6
4. Ba4 Lc5

Das Board sieht wie folgt aus:

Weiß hat die Möglichkeit zu schlössern . Ein Teil der Anforderungen hierfür ist, dass sich der König und der betreffende Turm niemals bewegt haben können. Ob sich also der König oder einer der Türme jeder Seite bewegt hat, muss gespeichert werden. Wenn sie nicht auf ihren Startpositionen sind, sind sie offensichtlich umgezogen, andernfalls muss dies angegeben werden.

Es gibt verschiedene Strategien, um dieses Problem zu lösen.

Erstens könnten wir zusätzliche 6 Informationsbits speichern (1 für jeden Turm und König), um anzuzeigen, ob sich dieses Stück bewegt hat. Wir könnten dies rationalisieren, indem wir nur ein bisschen für eines dieser sechs Quadrate speichern, wenn das richtige Stück darin ist. Alternativ könnten wir jedes unbewegte Stück als einen anderen Stücktyp behandeln. Anstelle von 6 Stücktypen auf jeder Seite (Bauer, Turm, Ritter, Bischof, Königin und König) gibt es 8 (Hinzufügen von unbewegtem Turm und unbewegtem König).

En Passant

Eine andere eigenartige und oft vernachlässigte Regel im Schach ist En Passant .

Das Spiel ist fortgeschritten.

1. e4 e5
2. Sf3 Sc6
3. Lb5 a6
4. Ba4 Lc5
5. OO b5
6. Bb3 b4
7. c4

Schwarzs Bauer auf b4 hat jetzt die Möglichkeit, seinen Bauern auf b4 nach c3 zu verschieben und den weißen Bauern auf c4 zu nehmen. Dies geschieht nur bei der ersten Gelegenheit, dh wenn Schwarz die Option jetzt weitergibt, kann er sie beim nächsten Zug nicht mehr ausführen. Also müssen wir das speichern.

Wenn wir den vorherigen Schritt kennen, können wir definitiv antworten, ob En Passant möglich ist. Alternativ können wir speichern, ob jeder Bauer auf seinem 4. Rang gerade mit einem doppelten Vorwärtszug dorthin gezogen ist. Oder wir können uns jede mögliche En Passant-Position auf dem Brett ansehen und eine Flagge haben, um anzuzeigen, ob dies möglich ist oder nicht.

Beförderung

Es ist der Schritt von Weiß. Wenn Weiß seinen Bauern auf h7 nach h8 bewegt, kann er zu jeder anderen Figur befördert werden (aber nicht zum König). 99% der Zeit wird es zu einer Königin befördert, aber manchmal nicht, normalerweise, weil dies eine Pattsituation erzwingen kann, wenn Sie sonst gewinnen würden. Dies ist geschrieben als:

56. h8 = Q.

Dies ist bei unserem Problem wichtig, da wir uns nicht darauf verlassen können, dass auf jeder Seite eine feste Anzahl von Teilen vorhanden ist. Es ist durchaus möglich (aber unglaublich unwahrscheinlich), dass eine Seite 9 Königinnen, 10 Türme, 10 Bischöfe oder 10 Ritter hat, wenn alle 8 Bauern befördert werden.

Patt

Wenn Sie sich in einer Position befinden, aus der Sie nicht gewinnen können, versuchen Sie am besten, eine Pattsituation zu erreichen . Die wahrscheinlichste Variante ist, wenn Sie keinen legalen Zug machen können (normalerweise, weil jeder Zug, wenn Sie Ihren König in Schach halten). In diesem Fall können Sie eine Auslosung beantragen. Dieser ist leicht zu bedienen.

Die zweite Variante besteht aus dreifacher Wiederholung . Wenn dieselbe Brettposition in einem Spiel dreimal vorkommt (oder im nächsten Zug ein drittes Mal vorkommt), kann ein Unentschieden beansprucht werden. Die Positionen müssen nicht in einer bestimmten Reihenfolge auftreten (was bedeutet, dass nicht dieselbe Abfolge von Zügen dreimal wiederholt werden muss). Dies erschwert das Problem erheblich, da Sie sich an jede vorherige Boardposition erinnern müssen. Wenn dies eine Anforderung des Problems ist, besteht die einzig mögliche Lösung des Problems darin, jeden vorherigen Zug zu speichern.

Schließlich gibt es die Fünfzig-Zug-Regel . Ein Spieler kann ein Unentschieden beanspruchen, wenn sich in den letzten fünfzig aufeinanderfolgenden Zügen kein Bauer bewegt hat und keine Figur genommen wurde. Daher müssten wir speichern, wie viele Züge seit dem Bewegen eines Bauern oder einer genommenen Figur (die letzte der beiden) erforderlich sind 6 Bits (0-63).

Wer ist dran?

Natürlich müssen wir auch wissen, wer an der Reihe ist, und dies ist eine einzelne Information.

Zwei Probleme

Aufgrund des Pattfalls besteht die einzig mögliche oder sinnvolle Möglichkeit, den Spielstatus zu speichern, darin, alle Bewegungen zu speichern, die zu dieser Position geführt haben. Ich werde dieses eine Problem angehen. Das Problem mit dem Board-Status wird dadurch vereinfacht: Speichern Sie die aktuelle Position aller Teile auf dem Board, ohne Rücksicht auf Rochade, en passant, Patt-Bedingungen und wer an der Reihe ist .

Das Stücklayout kann auf zwei Arten behandelt werden: durch Speichern des Inhalts jedes Quadrats oder durch Speichern der Position jedes Stücks.

Einfacher Inhalt

Es gibt sechs Stückarten (Bauer, Turm, Ritter, Bischof, Königin und König). Jedes Stück kann weiß oder schwarz sein, so dass ein Quadrat eines von 12 möglichen Stücken enthalten kann, oder es kann leer sein, so dass es 13 Möglichkeiten gibt. 13 kann in 4 Bits (0-15) gespeichert werden. Die einfachste Lösung besteht also darin, 4 Bits für jedes Quadrat mal 64 Quadrate oder 256 Bits an Informationen zu speichern.

Der Vorteil dieser Methode ist, dass die Manipulation unglaublich ist einfach und schnell ist. Dies könnte sogar erweitert werden, indem 3 weitere Möglichkeiten hinzugefügt werden, ohne die Speicheranforderungen zu erhöhen: ein Bauer, der in der letzten Runde 2 Felder bewegt hat, ein König, der sich nicht bewegt hat, und ein Turm, der sich nicht bewegt hat, was viel zu bieten hat von zuvor erwähnten Problemen.

Aber wir können es besser machen.

Base 13-Codierung

Es ist oft hilfreich, sich die Vorstandsposition als eine sehr große Zahl vorzustellen. Dies geschieht häufig in der Informatik. Zum Beispiel behandelt das Problem des Anhaltens ein Computerprogramm (zu Recht) als eine große Anzahl.

Bei der ersten Lösung wird die Position als 64-stellige Basis-16-Zahl behandelt. Wie gezeigt, sind diese Informationen jedoch redundant (dies sind die 3 nicht verwendeten Möglichkeiten pro „Ziffer“), sodass wir den Zahlenraum auf 64-Basis-13-Stellen reduzieren können. Natürlich kann dies nicht so effizient durchgeführt werden wie Base 16, aber es spart Speicherbedarf (und die Minimierung des Speicherplatzes ist unser Ziel).

In Basis 10 entspricht die Zahl 234 2 x 10 ² + 3 x 10 ¹ + 4 x 10 ⁰ .

In Basis 16 entspricht die Zahl 0xA50 10 x 16 ² + 5 x 16 ¹ + 0 x 16 ⁰ = 2640 (dezimal).

Wir können also unsere Position als p ₀ x 13 ⁶³ + p ₁ x 13 ⁶² + ... + p ₆₃ x 13 ⁰ codieren, wobei p _i den Inhalt des Quadrats i darstellt .

2 ²⁵⁶ entspricht ungefähr 1,16e77. 13 ⁶⁴ entspricht ungefähr 1,96e71, was 237 Bit Speicherplatz erfordert. Diese Einsparung von nur 7,5% führt zu deutlich erhöhten Manipulationskosten.

Variable Basiskodierung

In juristischen Gremien können bestimmte Teile nicht auf bestimmten Feldern erscheinen. Zum Beispiel können Bauern nicht in der ersten oder achten Reihe auftreten, was die Möglichkeiten für diese Quadrate auf 11 reduziert. Dadurch werden die möglichen Bretter auf 11 ¹⁶ x 13 ⁴⁸ = 1,35e70 (ungefähr) reduziert , was 233 Bit Speicherplatz erfordert.

Das eigentliche Codieren und Decodieren solcher Werte zu und von Dezimal (oder Binär) ist etwas komplizierter, kann jedoch zuverlässig durchgeführt werden und wird dem Leser als Übung überlassen.

Alphabete mit variabler Breite

Die beiden vorhergehenden Methoden können beide als alphabetische Codierung mit fester Breite beschrieben werden . Jedes der 11, 13 oder 16 Mitglieder des Alphabets wird durch einen anderen Wert ersetzt. Jedes „Zeichen“ hat die gleiche Breite, aber die Effizienz kann verbessert werden, wenn Sie bedenken, dass nicht jedes Zeichen gleich wahrscheinlich ist.

Betrachten Sie den Morsecode (siehe Abbildung oben). Zeichen in einer Nachricht werden als Folge von Strichen und Punkten codiert. Diese Striche und Punkte werden (normalerweise) über Funk mit einer Pause zwischen ihnen übertragen, um sie abzugrenzen.

Beachten Sie, dass der Buchstabe E ( der häufigste Buchstabe im Englischen ) ein einzelner Punkt ist, die kürzestmögliche Folge, während Z (der am wenigsten häufige) zwei Striche und zwei Pieptöne enthält.

Ein solches Schema kann die Größe einer erwarteten Nachricht erheblich verringern , geht jedoch zu Lasten der Vergrößerung einer zufälligen Zeichenfolge.

Es sollte beachtet werden, dass Morsecode eine weitere integrierte Funktion hat: Bindestriche sind so lang wie drei Punkte, daher wird der obige Code in diesem Sinne erstellt, um die Verwendung von Bindestrichen zu minimieren. Da 1s und 0s (unsere Bausteine) dieses Problem nicht haben, müssen wir diese Funktion nicht replizieren.

Schließlich gibt es zwei Arten von Pausen im Morsecode. Eine kurze Pause (die Länge eines Punktes) wird verwendet, um zwischen Punkten und Strichen zu unterscheiden. Eine längere Lücke (die Länge eines Strichs) wird verwendet, um Zeichen abzugrenzen.

Wie trifft dies auf unser Problem zu?

Huffman-Codierung

Es gibt einen Algorithmus für den Umgang mit Codes variabler Länge, der als Huffman-Codierung bezeichnet wird . Die Huffman-Codierung erzeugt eine Codesubstitution variabler Länge und verwendet normalerweise die erwartete Häufigkeit der Symbole, um den häufigeren Symbolen kürzere Werte zuzuweisen.

In dem obigen Baum ist der Buchstabe E als 000 (oder links-links-links) und S als 1011 codiert. Es sollte klar sein, dass dieses Codierungsschema eindeutig ist .

Dies ist ein wichtiger Unterschied zum Morsecode. Morsecode hat das Zeichentrennzeichen, so dass es ansonsten eine mehrdeutige Ersetzung durchführen kann (z. B. 4 Punkte können H oder 2 Is sein), aber wir haben nur 1s und 0s, also wählen wir stattdessen eine eindeutige Ersetzung.

Unten ist eine einfache Implementierung:

private static class Node {
  private final Node left;
  private final Node right;
  private final String label;
  private final int weight;

  private Node(String label, int weight) {
    this.left = null;
    this.right = null;
    this.label = label;
    this.weight = weight;
  }

  public Node(Node left, Node right) {
    this.left = left;
    this.right = right;
    label = "";
    weight = left.weight + right.weight;
  }

  public boolean isLeaf() { return left == null && right == null; }

  public Node getLeft() { return left; }

  public Node getRight() { return right; }

  public String getLabel() { return label; }

  public int getWeight() { return weight; }
}

mit statischen Daten:

private final static List<string> COLOURS;
private final static Map<string, integer> WEIGHTS;

static {
  List<string> list = new ArrayList<string>();
  list.add("White");
  list.add("Black");
  COLOURS = Collections.unmodifiableList(list);
  Map<string, integer> map = new HashMap<string, integer>();
  for (String colour : COLOURS) {
    map.put(colour + " " + "King", 1);
    map.put(colour + " " + "Queen";, 1);
    map.put(colour + " " + "Rook", 2);
    map.put(colour + " " + "Knight", 2);
    map.put(colour + " " + "Bishop";, 2);
    map.put(colour + " " + "Pawn", 8);
  }
  map.put("Empty", 32);
  WEIGHTS = Collections.unmodifiableMap(map);
}

und:

private static class WeightComparator implements Comparator<node> {
  @Override
  public int compare(Node o1, Node o2) {
    if (o1.getWeight() == o2.getWeight()) {
      return 0;
    } else {
      return o1.getWeight() < o2.getWeight() ? -1 : 1;
    }
  }
}

private static class PathComparator implements Comparator<string> {
  @Override
  public int compare(String o1, String o2) {
    if (o1 == null) {
      return o2 == null ? 0 : -1;
    } else if (o2 == null) {
      return 1;
    } else {
      int length1 = o1.length();
      int length2 = o2.length();
      if (length1 == length2) {
        return o1.compareTo(o2);
      } else {
        return length1 < length2 ? -1 : 1;
      }
    }
  }
}

public static void main(String args[]) {
  PriorityQueue<node> queue = new PriorityQueue<node>(WEIGHTS.size(),
      new WeightComparator());
  for (Map.Entry<string, integer> entry : WEIGHTS.entrySet()) {
    queue.add(new Node(entry.getKey(), entry.getValue()));
  }
  while (queue.size() > 1) {
    Node first = queue.poll();
    Node second = queue.poll();
    queue.add(new Node(first, second));
  }
  Map<string, node> nodes = new TreeMap<string, node>(new PathComparator());
  addLeaves(nodes, queue.peek(), &quot;&quot;);
  for (Map.Entry<string, node> entry : nodes.entrySet()) {
    System.out.printf("%s %s%n", entry.getKey(), entry.getValue().getLabel());
  }
}

public static void addLeaves(Map<string, node> nodes, Node node, String prefix) {
  if (node != null) {
    addLeaves(nodes, node.getLeft(), prefix + "0");
    addLeaves(nodes, node.getRight(), prefix + "1");
    if (node.isLeaf()) {
      nodes.put(prefix, node);
    }
  }
}

Eine mögliche Ausgabe ist:

         White    Black
Empty          0 
Pawn       110      100
Rook     11111    11110
Knight   10110    10101
Bishop   10100    11100
Queen   111010   111011
King    101110   101111

Für eine Startposition entspricht dies 32 x 1 + 16 x 3 + 12 x 5 + 4 x 6 = 164 Bit.

Zustandsunterschied

Ein anderer möglicher Ansatz besteht darin, den allerersten Ansatz mit der Huffman-Codierung zu kombinieren. Dies basiert auf der Annahme, dass die meisten erwarteten Schachbretter (und nicht zufällig generierte) zumindest teilweise eher einer Startposition ähneln.

Was Sie also tun, ist XOR die aktuelle 256-Bit-Kartenposition mit einer 256-Bit-Startposition und codieren diese dann (unter Verwendung der Huffman-Codierung oder beispielsweise einer Methode zur Lauflängencodierung ). Offensichtlich ist dies zunächst sehr effizient (64 0s entsprechen wahrscheinlich 64 Bit), erhöht jedoch den Speicherbedarf im Verlauf des Spiels.

Stückposition

Wie bereits erwähnt, besteht eine andere Möglichkeit, dieses Problem anzugreifen, darin, die Position jedes Stücks eines Spielers zu speichern. Dies funktioniert besonders gut bei Endspielpositionen, an denen die meisten Quadrate leer sind (beim Huffman-Codierungsansatz verwenden leere Quadrate ohnehin nur 1 Bit).

Jede Seite hat einen König und 0-15 andere Teile. Aufgrund der Beförderung kann die genaue Zusammensetzung dieser Teile so unterschiedlich sein, dass Sie nicht davon ausgehen können, dass die auf den Startpositionen basierenden Zahlen Maxima sind.

Der logische Weg, dies aufzuteilen, besteht darin, eine Position zu speichern, die aus zwei Seiten besteht (Weiß und Schwarz). Jede Seite hat:

• Ein König: 6 Bits für den Ort;
• Hat Bauern: 1 (ja), 0 (nein);
• Wenn ja, Anzahl der Bauern: 3 Bits (0-7 + 1 = 1-8);
• Wenn ja, wird die Position jedes Bauern codiert: 45 Bit (siehe unten);
• Anzahl der Nicht-Bauern: 4 Bits (0-15);
• Für jedes Stück: Typ (2 Bits für Königin, Turm, Ritter, Bischof) und Ort (6 Bits)

Was den Bauernstandort betrifft, können sich die Bauern nur auf 48 möglichen Feldern befinden (nicht auf 64 wie die anderen). Daher ist es besser, nicht die zusätzlichen 16 Werte zu verschwenden, die bei Verwendung von 6 Bits pro Bauer verwendet würden. Wenn Sie also 8 Bauern haben, gibt es 48 ⁸ Möglichkeiten, was 28.179.280.429.056 entspricht. Sie benötigen 45 Bit, um so viele Werte zu codieren.

Das sind 105 Bit pro Seite oder insgesamt 210 Bit. Die Ausgangsposition ist jedoch der schlechteste Fall für diese Methode und wird beim Entfernen von Teilen wesentlich besser.

Es sollte darauf hingewiesen werden, dass es weniger als 48 ⁸ Möglichkeiten gibt, da sich die Bauern nicht alle auf demselben Feld befinden können. Die erste hat 48 Möglichkeiten, die zweite 47 und so weiter. 48 x 47 x… x 41 = 1,52e13 = 44-Bit-Speicher.

Sie können dies weiter verbessern, indem Sie die Felder entfernen, die von anderen Teilen (einschließlich der anderen Seite) belegt werden, sodass Sie zuerst die weißen Nichtbauern, dann die schwarzen Nichtbauern, dann die weißen Bauern und zuletzt die schwarzen Bauern platzieren können. In einer Startposition reduziert dies den Speicherbedarf auf 44 Bit für Weiß und 42 Bit für Schwarz.

Kombinierte Ansätze

Eine weitere mögliche Optimierung besteht darin, dass jeder dieser Ansätze seine Stärken und Schwächen hat. Sie könnten beispielsweise die besten 4 auswählen und dann einen Schemaselektor in den ersten beiden Bits und anschließend den schemaspezifischen Speicher codieren.

Mit dem so geringen Overhead wird dies bei weitem der beste Ansatz sein.

Spielstatus

Ich komme auf das Problem zurück, ein Spiel statt einer Position zu speichern . Aufgrund der dreifachen Wiederholung müssen wir die Liste der Bewegungen speichern, die bis zu diesem Punkt aufgetreten sind.

Anmerkungen

Eine Sache, die Sie feststellen müssen, ist, dass Sie einfach eine Liste von Zügen speichern oder das Spiel mit Anmerkungen versehen. Schachspiele werden oft kommentiert, zum Beispiel:

17. Lb5 !! Sc4?

Der Zug von Weiß wird durch zwei Ausrufezeichen als brillant markiert, während der von Schwarz als Fehler angesehen wird. Siehe Schachpunktion .

Außerdem müssen Sie möglicherweise freien Text speichern, wenn die Bewegungen beschrieben werden.

Ich gehe davon aus, dass die Bewegungen ausreichend sind, damit es keine Anmerkungen gibt.

Algebraische Notation

Wir könnten einfach den Text des Umzugs hier speichern ("e4", "Bxb5" usw.). Einschließlich eines Abschlussbytes sehen Sie ungefähr 6 Bytes (48 Bit) pro Bewegung (schlimmster Fall). Das ist nicht besonders effizient.

Der zweite Versuch besteht darin, den Startort (6 Bit) und den Endort (6 Bit) so zu speichern, dass 12 Bit pro Zug vorhanden sind. Das ist deutlich besser.

Alternativ können wir alle rechtlichen Schritte von der aktuellen Position auf vorhersehbare und deterministische Weise und in dem von uns gewählten Zustand bestimmen. Dies geht dann auf die oben erwähnte variable Basiscodierung zurück. Weiß und Schwarz haben jeweils 20 mögliche Züge beim ersten Zug, mehr beim zweiten und so weiter.

Fazit

Es gibt keine absolut richtige Antwort auf diese Frage. Es gibt viele mögliche Ansätze, von denen die oben genannten nur einige sind.

Was ich an diesem und ähnlichen Problemen mag, ist, dass es Fähigkeiten erfordert, die für jeden Programmierer wichtig sind, wie das Verwendungsmuster zu berücksichtigen, Anforderungen genau zu bestimmen und über Eckfälle nachzudenken.

Schachpositionen als Screenshots vom Schachpositionstrainer .

Es ist am besten, Schachspiele in einem für Menschen lesbaren Standardformat zu speichern.

Die tragbare Spielnotation nimmt eine Standardstartposition ein (obwohl dies nicht erforderlich ist ) und listet nur die Züge nacheinander auf. Ein kompaktes, für Menschen lesbares Standardformat.

Z.B

[Event "F/S Return Match"]
[Site "Belgrade, Serbia Yugoslavia|JUG"]
[Date "1992.11.04"]
[Round "29"]
[White "Fischer, Robert J."]
[Black "Spassky, Boris V."]
[Result "1/2-1/2"]

1. e4 e5 2. Nf3 Nc6 3. Bb5 {This opening is called the Ruy Lopez.} 3... a6
4. Ba4 Nf6 5. O-O Be7 6. Re1 b5 7. Bb3 d6 8. c3 O-O 9. h3 Nb8  10. d4 Nbd7
11. c4 c6 12. cxb5 axb5 13. Nc3 Bb7 14. Bg5 b4 15. Nb1 h6 16. Bh4 c5 17. dxe5
Nxe4 18. Bxe7 Qxe7 19. exd6 Qf6 20. Nbd2 Nxd6 21. Nc4 Nxc4 22. Bxc4 Nb6
23. Ne5 Rae8 24. Bxf7+ Rxf7 25. Nxf7 Rxe1+ 26. Qxe1 Kxf7 27. Qe3 Qg5 28. Qxg5
hxg5 29. b3 Ke6 30. a3 Kd6 31. axb4 cxb4 32. Ra5 Nd5 33. f3 Bc8 34. Kf2 Bf5
35. Ra7 g6 36. Ra6+ Kc5 37. Ke1 Nf4 38. g3 Nxh3 39. Kd2 Kb5 40. Rd6 Kc5 41. Ra6
Nf2 42. g4 Bd3 43. Re6 1/2-1/2

Wenn Sie es verkleinern möchten, schließen Sie es einfach . Job erledigt!

Tolles Puzzle!

Ich sehe, dass die meisten Leute die Position jedes Stücks speichern. Wie wäre es mit einem einfacheren Ansatz und dem Speichern des Inhalts jedes Quadrats ? Das kümmert sich automatisch um Werbung und erbeutete Teile.

Und es ermöglicht die Huffman-Codierung . Tatsächlich ist die anfängliche Häufigkeit der Spielsteine ​​auf dem Brett nahezu perfekt: Die Hälfte der Felder ist leer, die Hälfte der verbleibenden Felder sind Bauern usw.

In Anbetracht der Häufigkeit jedes Stücks habe ich einen Huffman-Baum auf Papier konstruiert , den ich hier nicht wiederholen werde. Das Ergebnis, wobei cfür die Farbe steht (weiß = 0, schwarz = 1):

• 0 für leere Quadrate
• 1c0 für Bauer
• 1c100 für Turm
• 1c101 für Ritter
• 1c110 für Bischof
• 1c1110 für Königin
• 1c1111 für König

Für das gesamte Board in seiner Ausgangssituation haben wir

• leere Quadrate: 32 * 1 Bit = 32 Bit
• Bauern: 16 * 3 Bits = 48 Bits
• Türme / Ritter / Bischöfe: 12 * 5 Bit = 60 Bit
• Königinnen / Könige: 4 * 6 Bits = 24 Bits

Gesamt: 164 Bit für den anfänglichen Kartenstatus. Deutlich weniger als die 235 Bits der derzeit am höchsten bewerteten Antwort. Und es wird im Laufe des Spiels nur noch kleiner (außer nach einer Beförderung).

Ich schaute nur auf die Position der Stücke auf dem Brett; Zusätzlicher Status (dessen Zug, wer Burgen hat, en passant, sich wiederholende Züge usw.) muss separat codiert werden. Vielleicht höchstens noch 16 Bit, also 180 Bit für den gesamten Spielstatus. Mögliche Optimierungen:

• Lassen Sie die weniger häufigen Teile weg und speichern Sie ihre Position separat. Aber das hilft nicht ... Wenn Sie König und Königin durch ein leeres Quadrat ersetzen, werden 5 Bits gespart. Dies sind genau die 5 Bits, die Sie benötigen, um ihre Position auf andere Weise zu codieren.
• "Keine Bauern in der hinteren Reihe" könnte leicht mit einer anderen Huffman-Tabelle für die hinteren Reihen codiert werden, aber ich bezweifle, dass es viel hilft. Sie würden wahrscheinlich immer noch denselben Huffman-Baum haben.
• "Ein weißer, ein schwarzer Läufer" kann codiert werden, indem zusätzliche Symbole eingefügt werden, die nicht über das cBit verfügen. Diese können dann aus dem Quadrat abgeleitet werden, auf dem sich der Bischof befindet. (Bauern, die zu Bischöfen befördert wurden, stören dieses Schema ...)
• Wiederholungen von leeren Quadraten könnten durch Hinzufügen zusätzlicher Symbole für beispielsweise "2 leere Quadrate in einer Reihe" und "4 leere Quadrate in einer Reihe" in Lauflänge codiert werden. Aber es ist nicht so einfach, die Häufigkeit dieser zu schätzen, und wenn Sie etwas falsch machen, wird es eher weh tun als helfen.

Der wirklich große Lookup-Table-Ansatz

Position - 18 Bytes
Geschätzte Anzahl der zulässigen Positionen beträgt 10 ⁴³
Zählen Sie einfach alle auf und die Position kann in nur 143 Bit gespeichert werden. 1 weiteres Bit ist erforderlich, um anzuzeigen, welche Seite als nächstes gespielt werden soll

Die Aufzählung ist natürlich nicht praktikabel, aber dies zeigt, dass mindestens 144 Bits erforderlich sind.

Verschiebt - 1 Byte
Es gibt in der Regel etwa 30-40 rechtliche Schritte für jede Position , aber die Anzahl kann so hoch sein wie 218 Lets enumerate alle rechtlichen Schritte für jede Position. Jetzt kann jede Bewegung in ein Byte codiert werden.

Wir haben noch viel Raum für Spezialbewegungen wie 0xFF, um den Rücktritt darzustellen.

Es würde das Interesse erhöhen, die durchschnittliche Fallgröße für typische Spiele, die von Menschen gespielt werden, anstelle des schlimmsten Falls zu optimieren . (Die Problemstellung sagt nicht, welche; die meisten Antworten gehen von einem Worst-Case aus.)

Lassen Sie für die Bewegungssequenz eine gute Schachmaschine Bewegungen aus jeder Position generieren. Es wird eine Liste von k möglichen Zügen erstellt, geordnet nach der Rangfolge ihrer Qualität. Menschen wählen im Allgemeinen häufiger gute Züge als zufällige Züge. Daher müssen wir von jeder Position in der Liste eine Zuordnung zu der Wahrscheinlichkeit lernen, mit der Menschen einen Zug auswählen, der „gut“ ist. Verwenden Sie diese Wahrscheinlichkeiten (basierend auf einem Korpus von Spielen aus einer Internet-Schachdatenbank), um die Züge mit arithmetischer Codierung zu codieren . (Der Decoder muss dieselbe Schachengine und Zuordnung verwenden.)

Für die Startposition würde Ralus Ansatz funktionieren. Wir könnten es dort auch mit arithmetischer Codierung verfeinern, wenn wir die Auswahl nach Wahrscheinlichkeit gewichten könnten - z. B. erscheinen Teile oft in Konfigurationen, die sich gegenseitig verteidigen, nicht zufällig. Es ist schwieriger, einen einfachen Weg zu finden, um dieses Wissen zu integrieren. Eine Idee: Greifen Sie stattdessen auf die obige Verschiebungscodierung zurück, indem Sie von der Standardöffnungsposition aus beginnen und eine Sequenz finden, die auf der gewünschten Karte endet. (Sie können eine A * -Suche mit einem heuristischen Abstand versuchen, der der Summe der Abstände der Figuren von ihren Endpositionen entspricht, oder etwas in dieser Richtung.) Dies führt zu einer gewissen Ineffizienz bei der Überbestimmung der Bewegungssequenz im Vergleich zur Effizienz beim Ausnutzen des Schachspiels Wissen.

Es ist auch schwierig abzuschätzen, wie viel Einsparungen Sie bei durchschnittlicher Komplexität erzielen würden, ohne Statistiken aus einem tatsächlichen Korpus zu sammeln. Aber der Ausgangspunkt mit allen gleich wahrscheinlichen Zügen würde meiner Meinung nach die meisten Vorschläge hier bereits übertreffen: Die arithmetische Codierung benötigt keine ganzzahlige Anzahl von Bits pro Zug.

Angriff auf ein Teilproblem beim Codieren der Schritte, nachdem eine Anfangsposition codiert wurde. Der Ansatz besteht darin, eine "verknüpfte Liste" von Schritten zu erstellen.

Jeder Schritt im Spiel wird als Paar "alte Position -> neue Position" codiert. Sie kennen die Ausgangsposition zu Beginn des Schachspiels; Durch Durchlaufen der verknüpften Liste von Schritten können Sie den Status erreichen, nachdem sich X bewegt hat.

Für die Codierung jedes Schritts benötigen Sie 64 Werte zum Codieren der Startposition (6 Bit für 64 Quadrate auf der Platine - 8 x 8 Quadrate) und 6 Bit für die Endposition. 16 Bits für 1 Bewegung jeder Seite.

Die Menge an Speicherplatz, die für die Codierung eines bestimmten Spiels benötigt wird, ist dann proportional zur Anzahl der Züge:

10 x (Anzahl der weißen Bewegungen + Anzahl der schwarzen Bewegungen) Bits.

UPDATE: Mögliche Komplikation mit beförderten Bauern. Sie müssen angeben können, zu was der Bauer befördert wird - möglicherweise sind spezielle Bits erforderlich (verwenden Sie dafür grauen Code, um Platz zu sparen, da die Beförderung von Bauern äußerst selten ist).

UPDATE 2: Sie müssen nicht die vollständigen Koordinaten der Endposition codieren. In den meisten Fällen kann sich das zu bewegende Teil nicht mehr als X Stellen bewegen. Zum Beispiel kann ein Bauer an einem bestimmten Punkt maximal 3 Zugoptionen haben. Indem wir die maximale Anzahl von Zügen für jeden Stücktyp realisieren, können wir Bits bei der Codierung des "Ziels" speichern.

Pawn: 
   - 2 options for movement (e2e3 or e2e4) + 2 options for taking = 4 options to encode
   - 12 options for promotions - 4 promotions (knight, biship, rook, queen) times 3 squares (because you can take a piece on the last row and promote the pawn at the same time)
   - Total of 16 options, 4 bits
Knight: 8 options, 3 bits
Bishop: 4 bits
Rook: 4 bits
King: 3 bits
Queen: 5 bits

So wird die räumliche Komplexität pro Bewegung von Schwarz oder Weiß

6 Bits für die Anfangsposition + (variable Anzahl von Bits basierend auf dem Typ des Objekts, das bewegt wird).

Ich habe diese Frage letzte Nacht gesehen und sie hat mich fasziniert, also habe ich im Bett gesessen und mir Lösungen ausgedacht. Meine endgültige Antwort ist der von int3 ziemlich ähnlich.

Grundlösung

Angenommen, Sie haben ein Standardschachspiel und codieren die Regeln nicht (wie Weiß immer zuerst geht), dann können Sie viel sparen, indem Sie nur die Züge codieren, die jede Figur macht.

Insgesamt gibt es 32 Teile, aber bei jedem Zug wissen Sie, welche Farbe sich bewegt, sodass Sie sich nur um 16 Felder sorgen müssen. Dies sind 4 Bits, für die sich dieser Teil in diesem Zug bewegt.

Jedes Stück hat nur ein begrenztes Moveset, das Sie auf irgendeine Weise aufzählen würden.

• Bauer: 4 Optionen, 2 Bits (1 Schritt vorwärts, 2 Schritte vorwärts, 1 pro Diagonale)
• Turm: 14 Optionen, 4 Bits (maximal 7 in jede Richtung)
• Bischof: 13 Optionen, 4 Bits (wenn Sie 7 in einer Diagonale haben, haben Sie nur 6 in der anderen)
• Ritter: 8 Optionen, 3 Bits
• Königin: 27 Optionen, 5 Bits (Turm + Bischof)
• König: 9 Optionen, 4 Bits (8 Ein-Schritt-Züge plus die Castling-Option)

Für die Beförderung stehen 4 Teile zur Auswahl (Turm, Bischof, Ritter, Königin). Bei diesem Zug würden wir 2 Bits hinzufügen, um dies anzugeben. Ich denke, alle anderen Regeln werden automatisch abgedeckt (zB en passant).

Weitere Optimierungen

Nachdem 8 Teile einer Farbe erfasst wurden, können Sie zunächst die Codierung der Teile auf 3 Bit reduzieren, dann auf 2 Bit für 4 Teile und so weiter.

Die Hauptoptimierung besteht jedoch darin, nur die möglichen Züge an jedem Punkt im Spiel aufzulisten. Angenommen, wir speichern die Züge eines Bauern wie {00, 01, 10, 11}für 1 Schritt vorwärts, 2 Schritte vorwärts, diagonal links bzw. diagonal rechts. Wenn einige Bewegungen nicht möglich sind, können wir sie für diesen Zug aus der Codierung entfernen.

Wir kennen den Spielstatus in jeder Phase (indem wir alle Züge verfolgen). Nachdem wir also gelesen haben, welches Stück sich bewegen wird, können wir immer bestimmen, wie viele Bits wir lesen müssen. Wenn wir feststellen, dass die einzigen Bewegungen eines Bauern an diesem Punkt diagonal nach rechts erfasst werden oder eine vorwärts bewegen, wissen wir, dass wir nur 1 Bit lesen müssen.

Kurz gesagt, der oben aufgeführte Bitspeicher für jedes Stück ist maximal . Fast jede Bewegung hat weniger Optionen und oft weniger Bits.

Erhalten Sie an jeder Position die Anzahl aller möglichen Züge.

Der nächste Zug wird als generiert

index_current_move =n % num_of_moves //this is best space efficiency
n=n/num_of_moves

nachweislich beste Raumeffizienz zum Speichern von zufällig generiertem Spiel und benötigt durchschnittlich ca. 5 Bit / Zug, da Sie 30-40 mögliche Züge haben. Beim Zusammenstellen des Speichers wird nur n in umgekehrter Reihenfolge generiert.

Die Speicherposition ist aufgrund der großen Redundanz schwerer zu knacken. (Es können bis zu 9 Königinnen an Bord sein, aber in diesem Fall gibt es keine Bauern und Bischöfe, wenn sie sich auf gegenüberliegenden farbigen Quadraten befinden.) Dies entspricht jedoch im Allgemeinen der Aufbewahrung einer Kombination derselben Teile über den verbleibenden Quadraten.)

BEARBEITEN:

Beim Speichern von Zügen müssen nur der Bewegungsindex gespeichert werden. Anstatt Kc1-c2 zu speichern und zu versuchen, diese Informationen zu reduzieren, sollten wir nur den Bewegungsindex hinzufügen, der vom deterministischen Bewegungsgenerator (Position) generiert wurde.

Bei jeder Bewegung fügen wir Informationen zur Größe hinzu

num_of_moves = get_number_of_possible_moves(postion) ;

im Pool und diese Anzahl kann nicht reduziert werden

Informationspool generieren ist

n=n*num_of_moves+ index_current_move

extra

Wenn nur ein Zug in der Endposition verfügbar ist, speichern Sie die Anzahl der zuvor durchgeführten erzwungenen Züge. Beispiel: Wenn die Startposition 1 erzwungene Züge für jede Seite hat (2 Züge) und wir dies als ein Zugspiel speichern möchten, speichern Sie 1 in Pool n.

Beispiel für die Speicherung im Infopool

Nehmen wir an, wir kennen Startpositionen und machen 3 Züge.

Im ersten Zug sind 5 Züge verfügbar, und wir nehmen den Zugindex 4. Im zweiten Zug sind 6 Züge verfügbar, und wir nehmen den Positionsindex 3, und im dritten Zug stehen 7 Züge für diese Seite zur Verfügung, und er hat sich für den Zugindex entschieden 2.

Vektorform; index = [4,3,2] n_moves = [5,6,7]

Wir codieren diese Informationen rückwärts, also n = 4 + 5 * (3 + 6 * (2)) = 79 (kein Multiplizieren mit 7 erforderlich)

Wie kann man das lösen? Zuerst haben wir eine Position und stellen fest, dass 5 Züge verfügbar sind. So

index=79%5=4
n=79/5=15; //no remainder

Wir nehmen den Bewegungsindex 4 und untersuchen die Position erneut. Ab diesem Punkt stellen wir fest, dass es 6 mögliche Bewegungen gibt.

index=15%6=3
n=15/6=2

Und wir nehmen den Bewegungsindex 3, der uns zu einer Position mit 7 möglichen Zügen bringt.

index=2%7=2
n=2/7=0

Wir machen den letzten Zug Index 2 und erreichen die endgültige Position.

Wie Sie sehen können, ist die Zeitkomplexität O (n) und die Raumkomplexität O (n). Bearbeiten: Die Zeitkomplexität ist tatsächlich O (n ^ 2), da die Zahl, mit der Sie multiplizieren, zunimmt, aber es sollte kein Problem geben, Spiele mit bis zu 10.000 Zügen zu speichern.

Speicherposition

Kann nahezu optimal durchgeführt werden.

Wenn wir Informationen erhalten und Informationen speichern, lassen Sie mich mehr darüber sprechen. Die allgemeine Idee ist, die Redundanz zu verringern (darüber werde ich später sprechen). Nehmen wir an, es gab keine Beförderungen und keine Einnahme, also gibt es 8 Bauern, 2 Türme, 2 Ritter, 2 Bischöfe, 1 König und 1 Königin pro Seite.

Was müssen wir retten: 1. Position jedes Friedens 2. Möglichkeiten der Rochade 3. Möglichkeiten des Passanten 4. Seite, die sich bewegt hat

Nehmen wir an, dass jedes Stück überall stehen kann, aber nicht zwei Stück am selben Ort. Die Anzahl der Möglichkeiten, wie 8 Bauern derselben Farbe an Bord angeordnet werden können, ist C (64/8) (Binomial), was 32 Bit entspricht, dann 2 Türme 2R-> C (56/2), 2B -> C (54/2). , 2N-> C (52/2), 1Q-> C (50/1), 1K -> C (49/1) und dasselbe für andere Stellen, jedoch beginnend mit 8P -> C (48/8) und so weiter .

Wenn wir dies für beide Standorte multiplizieren, erhalten wir die Nummer 4634726695587809641192045982323285670400000, was ungefähr 142 Bit entspricht. Wir müssen 8 für einen möglichen En-Passanten addieren (En-Passant-Bauer kann an einer von 8 Stellen sein), 16 (4 Bits) für Burgling-Einschränkungen und ein Bit für Site, die sich bewegt hat. Am Ende haben wir 142 + 3 + 4 + 1 = 150 Bit

Aber jetzt machen wir uns auf die Suche nach Redundanz auf dem Brett mit 32 Teilen und ohne Einnahme.

1. Beide schwarzen und weißen Bauern befinden sich auf derselben Säule und stehen sich gegenüber. Jeder Bauer steht einem anderen Bauern gegenüber, was bedeutet, dass der weiße Bauer höchstens den 6. Rang erreichen kann. Dies bringt uns 8 * C (6/2) anstelle von C (64/8) * C (48/8), wodurch die Informationen um 56 Bit verringert werden.

2. Die Möglichkeit der Rochade ist ebenfalls überflüssig. Wenn sich keine Türme am Startplatz befinden, gibt es keine Möglichkeit, mit diesem Turm zu basteln. Wir können uns also vorstellen, 4 Felder an Bord hinzuzufügen, um zusätzliche Informationen zu erhalten, wenn mit diesem Turm eine Rochade möglich ist, und 4 Burgenbits entfernen. Anstelle von C (56/2) * C (40/2) * 16 haben wir also C (58/2) * C (42/2) und wir haben 3,76 Bits verloren (fast alle 4 Bits).

3. en-passant: Wenn wir eine von 8 en-passant-Möglichkeiten speichern, kennen wir die Position des schwarzen Bauern und reduzieren die Informationsredindanz (wenn es sich um einen weißen Zug handelt und der 3. Bauer en-passant ist, bedeutet dies, dass der schwarze Bauer auf c5 ist und der weiße Bauer entweder c2, c3 oder c4) von C (6/2) haben wir 3 und wir haben 2,3 Bits verloren. Wir verringern eine gewisse Redundanz, wenn wir die Zahl der Passanten auch auf der Seite speichern, von der aus dies möglich ist (3 Möglichkeiten -> links, rechts, beide), und wir kennen die Möglichkeit eines Bauern, der die Passanten aufnehmen kann. (Zum Beispiel aus dem vorherigen en passant Beispiel mit schwarz auf c5, was links, rechts oder beides sein kann. Wenn es sich an einer Stelle befindet, haben wir 2 * 3 (3 zum Speichern von Psissibiliten und 2 mögliche Züge für schwarzen Bauern auf Rang 7 oder 6 ) anstelle von C (6/2) und wir reduzieren um 1,3 Bit und wenn wir auf beiden Seiten um 4,2 Bit reduzieren. Auf diese Weise können wir um 2,3 + 1,3 = 3 reduzieren.

4. Bischöfe: Bisops können nur auf Opostitfeldern sein, wodurch die Redundanz für jeden Standort um 1 Bit verringert wird.

Wenn wir zusammenfassen, benötigen wir 150-56-4-3.6-2 = 85 Bit zum Speichern der Schachposition, wenn es keine Einnahmen gab

Und wahrscheinlich nicht viel mehr, wenn Einnahmen und Werbeaktionen berücksichtigt werden (aber ich werde später darüber schreiben, wenn jemand diesen langen Beitrag nützlich findet)

Die meisten Leute haben den Board-Status codiert, aber in Bezug auf die Bewegungen selbst. Hier ist eine Beschreibung der Bit-Codierung.

Bits pro Stück:

• Stück-ID: Maximal 4 Bit, um die 16 Teile pro Seite zu identifizieren. Weiß / Schwarz kann abgeleitet werden. Lassen Sie eine Bestellung auf den Stücken definieren. Wenn die Anzahl der Teile unter die jeweiligen Zweierpotenzen fällt, verwenden Sie weniger Bits, um die verbleibenden Teile zu beschreiben.
• Bauer: 3 Möglichkeiten beim ersten Zug, also +2 Bits (vorwärts um ein oder zwei Quadrate, en passant). Nachfolgende Züge erlauben keine Bewegung um zwei vorwärts, daher ist +1 Bit ausreichend. Die Beförderung kann im Dekodierungsprozess abgeleitet werden, indem notiert wird, wann der Bauer den letzten Rang erreicht hat. Wenn bekannt ist, dass der Bauer befördert wird, erwartet der Decoder weitere 2 Bits, die angeben, zu welchem ​​der 4 Hauptstücke er befördert wurde.
• Bischof: +1 Bit für die verwendete Diagonale, Bis zu +4 Bit für den Abstand entlang der Diagonale (16 Möglichkeiten). Der Decoder kann den maximal möglichen Abstand ableiten, um den sich das Stück entlang dieser Diagonale bewegen kann. Wenn es sich also um eine kürzere Diagonale handelt, verwenden Sie weniger Bits.
• Ritter: 8 mögliche Züge, +3 Bits
• Turm: +1 Bit für horizontal / vertikal, +4 Bit für Abstand entlang der Linie.
• König: 8 mögliche Züge, +3 Bits. Zeigen Sie das Rochieren mit einem "unmöglichen" Zug an - da das Rochieren nur möglich ist, während sich der König auf dem ersten Rang befindet, codieren Sie diesen Zug mit einer Anweisung, den König "rückwärts" zu bewegen - dh aus dem Brett.
• Königin: 8 mögliche Richtungen, + 3 Bits. Bis zu +4 mehr Bits für den Abstand entlang der Linie / Diagonale (weniger, wenn die Diagonale kürzer ist, wie im Fall des Bischofs)

Angenommen, alle Teile befinden sich auf dem Brett, dann sind dies die Bits pro Zug: Bauer - 6 Bits beim ersten Zug, 5 anschließend. 7 wenn befördert. Bischof: 9 Bits (max.), Ritter: 7, Turm: 9, König: 7, Königin: 11 (max.).

Ist das Problem, eine Codierung anzugeben, die für typische Schachspiele am effizientesten ist, oder eine, die die kürzeste Codierung im ungünstigsten Fall aufweist?

Für letztere ist der effizienteste Weg auch der undurchsichtigste: Erstellen Sie eine Aufzählung aller möglichen Paare (Anfangstafel, zulässige Reihenfolge der Züge), die mit der dreimal wiederholten Position und nicht mehr als -fünfzig Züge seit den Regeln für den letzten Bauernzug ​​oder die letzte Erfassung sind rekursiv. Dann ergibt der Index einer Position in dieser endlichen Folge die kürzeste Codierung im ungünstigsten Fall, aber auch eine ebenso lange Codierung für typische Fälle und ist, wie ich erwarte, sehr teuer in der Berechnung. Das längstmögliche Schachspiel soll über 5000 Züge umfassen, wobei in der Regel jedem Spieler 20 bis 30 Züge pro Position zur Verfügung stehen (allerdings weniger, wenn nur noch wenige Figuren übrig sind) - dies ergibt ungefähr 40000 Bits, die für diese Codierung benötigt werden.

Die Idee der Aufzählung kann angewendet werden, um eine besser handhabbare Lösung zu erhalten, wie in Henk Holtermans Vorschlag für die Codierung von Bewegungen oben beschrieben. Mein Vorschlag: nicht minimal, aber kürzer als die obigen Beispiele, die ich mir angesehen habe, und vernünftig nachvollziehbar:

1. 64 Bit, um darzustellen, welche Quadrate belegt sind (Belegungsmatrix), plus Liste der Teile in jedem belegten Feld (kann 3 Bit für Bauern und 4 Bit für andere Teile haben): Dies ergibt 190 Bit für die Startposition. Da nicht mehr als 32 Teile an Bord sein können, ist die Codierung der Belegungsmatrix redundant und so können so etwas wie gemeinsame Kartenpositionen codiert werden, beispielsweise als 33 gesetzte Bits plus Index der Karte aus der Liste der gemeinsamen Karten.

2. 1 Bit zu sagen, wer den ersten Schritt macht

3. Code-Bewegungen gemäß Henks Vorschlag: Normalerweise 10 Bits pro Paar Weiß / Schwarz-Züge, obwohl einige Züge 0 Bits benötigen, wenn ein Spieler keine alternativen Züge hat.

Dies schlägt 490 Bit vor, um ein typisches Spiel mit 30 Zügen zu codieren, und wäre eine einigermaßen effiziente Darstellung für typische Spiele.

Abouth Codierung der dreimal wiederholten Draw-on-Position und nicht mehr als fünfzig Züge seit den Regeln für den letzten Bauernzug ​​oder die letzte Eroberung: Wenn Sie die Vergangenheit codieren, bewegen Sie sich zurück zum letzten Bauernzug ​​oder der letzten Eroberung, dann Sie Haben Sie genügend Informationen, um zu entscheiden, ob diese Regeln gelten: Keine Notwendigkeit für die gesamte Spielhistorie.

Die Position auf einer Karte kann in 7 Bits definiert werden (0-63 und 1 Wert, der angibt, dass sie sich nicht mehr auf der Karte befindet). Geben Sie also für jedes Stück auf der Tafel an, wo es sich befindet.

32 Stück * 7 Bit = 224 Bit

EDIT: Wie Cadrian betonte ... haben wir auch den Fall "Bauer zur Königin befördert". Ich schlage vor, dass wir am Ende zusätzliche Bits hinzufügen, um anzuzeigen, welche Bauern befördert wurden.

Für jeden beförderten Bauern folgen wir also den 224 Bits mit 5 Bits, die den Index des beförderten Bauern angeben, und 11111, wenn dies das Ende der Liste ist.

Der minimale Fall (keine Werbeaktionen) beträgt also 224 Bit + 5 (keine Werbeaktionen). Für jeden beförderten Bauern 5 Bits hinzufügen.

EDIT: Wie zotteliger Frosch betont, brauchen wir am Ende noch ein bisschen, um anzuzeigen, wer an der Reihe ist; ^)

Ich würde eine Lauflängencodierung verwenden. Einige Stücke sind einzigartig (oder existieren nur zweimal), daher kann ich die Länge nach ihnen weglassen. Wie Cletus benötige ich 13 eindeutige Zustände, damit ich das Stück mit einem Halbbyte (4 Bit) codieren kann. Das ursprüngliche Board würde dann so aussehen:

White Rook, W. Knight, W. Bishop, W. Queen, W. King, W. Bishop, W. Knight, W. Rook,
W. Pawn, 8,
Empty, 16, Empty, 16
B. Pawn, 8,
B. Rook, B. Knight, B. Bishop, B. Queen, B. King, B. Bishop, B. Knight, B. Rook

Das lässt mich mit 8 + 2 + 4 + 2 + 8 Knabbereien = 24 Knabbereien = 96 Bits. Ich kann 16 nicht mit einem Nibble codieren, aber da "Leer, 0" keinen Sinn ergibt, kann ich "0" als "16" behandeln.

Wenn das Brett leer ist, aber für einen einzelnen Bauern in der oberen linken Ecke, erhalte ich "Bauer, 1, leer, 16, leer, 16, leer 16, leer, 15" = 10 Knabbereien = 40 Bits.

Der schlimmste Fall ist, wenn ich zwischen jedem Stück ein leeres Quadrat habe. Aber für die Codierung des Stücks benötige ich nur 13 von 16 Werten, also kann ich vielleicht einen anderen verwenden, um "Empty1" zu sagen. Dann brauche ich 64 Knabbereien == 128 Bit.

Für die Bewegungen benötige ich 3 Bits für das Stück (die Farbe ergibt sich aus der Tatsache, dass sich Weiß immer zuerst bewegt) plus 5 Bits (0..63) für die neue Position = ein Byte pro Bewegung. Meistens brauche ich die alte Position nicht, da nur ein einziges Stück in Reichweite ist. Für den seltsamen Fall muss ich den einzelnen nicht verwendeten Code verwenden (ich benötige nur 7 Codes, um das Stück zu codieren) und dann 5 Bits für die alte und 5 Bits für die neue Position.

Auf diese Weise kann ich die Rochade in 13 Bissen codieren (ich kann den König in Richtung Turm bewegen, was ausreicht, um zu sagen, was ich beabsichtige).

[BEARBEITEN] Wenn Sie einen intelligenten Encoder zulassen, benötige ich 0 Bits für die Ersteinrichtung (da er in keiner Weise codiert werden muss: Es ist statisch) plus ein Byte pro Zug.

[EDIT2] Was die Bauernumwandlung verlässt. Wenn ein Bauer die letzte Reihe erreicht, kann ich ihn verschieben, um "Transformationen" zu sagen, und dann die 3 Bits für das Stück hinzufügen, durch das er ersetzt wird (Sie müssen keine Königin verwenden; Sie können den Bauern durch irgendetwas ersetzen aber der König).

So wie sie Spiele auf Büchern und Papieren codieren: Jedes Stück hat ein Symbol; Da es sich um ein "legales" Spiel handelt, muss Weiß zuerst ziehen - Weiß oder Schwarz müssen nicht separat codiert werden. Zählen Sie einfach die Anzahl der Züge, um festzustellen, wer sich bewegt hat. Außerdem wird jede Bewegung als (Stück, Endposition) codiert, wobei die „Endposition“ auf die geringste Anzahl von Symbolen reduziert wird, mit denen Mehrdeutigkeiten erkannt werden können (kann Null sein). Die Länge des Spiels bestimmt die Anzahl der Züge. Man kann die Zeit auch bei jedem Schritt in Minuten (seit dem letzten Zug) codieren.

Die Codierung des Stücks kann entweder durch Zuweisen eines Symbols zu jedem (insgesamt 32) oder durch Zuweisen eines Symbols zur Klasse erfolgen. Verwenden Sie die Endposition, um zu verstehen, welches Stück verschoben wurde. Zum Beispiel hat ein Bauer 6 mögliche Endpositionen; Im Durchschnitt stehen jedoch nur ein paar auf Schritt und Tritt zur Verfügung. Statistisch gesehen ist die Codierung nach Endposition für dieses Szenario möglicherweise am besten.

Ähnliche Codierungen werden für Spike-Züge in der Computational Neuroscience (VRE) verwendet.

Nachteile: Sie müssen das gesamte Spiel wiederholen, um den aktuellen Status zu erreichen und eine Teilmenge zu generieren, ähnlich wie beim Durchlaufen einer verknüpften Liste.

Es gibt 64 mögliche Platinenpositionen, sodass Sie 6 Bits pro Position benötigen. Es gibt 32 Anfangsstücke, also haben wir bisher insgesamt 192 Bits, wobei alle 6 Bits die Position des gegebenen Stücks angeben. Wir können die Reihenfolge, in der die Teile erscheinen, vorbestimmen, sodass wir nicht sagen müssen, welche welche ist.

Was ist, wenn ein Stück vom Brett ist? Nun, wir können ein Stück an der gleichen Stelle wie ein anderes Stück platzieren, um anzuzeigen, dass es nicht auf dem Brett ist, da dies sonst illegal wäre. Wir wissen aber auch nicht, ob das erste Stück auf dem Brett sein wird oder nicht. Also addieren wir 5 Bits, die angeben, welches Stück das erste ist (32 Möglichkeiten = 5 Bits, um das erste Stück darzustellen). Dann können wir diesen Punkt für nachfolgende Teile verwenden, die vom Brett sind. Das bringt uns auf insgesamt 197 Bit. Es muss mindestens ein Stück auf dem Brett sein, damit das funktioniert.

Dann brauchen wir ein Bit, für das wir an der Reihe sind - bringt uns auf 198 Bits .

Was ist mit Bauernförderung? Wir können es schlecht machen, indem wir 3 Bits pro Bauer hinzufügen und 42 Bits hinzufügen. Aber dann können wir feststellen, dass Bauern die meiste Zeit nicht befördert werden.

Für jeden Bauern, der sich auf dem Brett befindet, zeigt das Bit '0' an, dass er nicht befördert wird. Wenn ein Bauer nicht auf dem Brett ist, brauchen wir überhaupt kein bisschen. Dann können wir Bitfolgen variabler Länge verwenden, für welche Promotion er hat. Am häufigsten wird es eine Königin sein, also kann "10" KÖNIGIN bedeuten. Dann bedeutet "110" Turm, "1110" bedeutet Bischof und "1111" bedeutet Ritter.

Der Anfangszustand dauert 198 + 16 = 214 Bits , da alle 16 Bauern auf dem Brett sind und nicht befördert werden. Ein Endspiel mit zwei beförderten Bauernköniginnen kann ungefähr 198 + 4 + 4 dauern, was bedeutet, dass 4 lebende und nicht beförderte Bauern und 2 Dame-Bauern insgesamt 206 Bit haben . Scheint ziemlich robust!

===

Die Huffman-Codierung wäre, wie andere betont haben, der nächste Schritt. Wenn Sie einige Millionen Spiele beobachten, werden Sie feststellen, dass jedes Stück viel wahrscheinlicher auf bestimmten Feldern liegt. Zum Beispiel bleiben die Bauern die meiste Zeit in einer geraden Linie oder einer nach links / einer nach rechts. Der König bleibt normalerweise in der Nähe der Heimatbasis.

Entwickeln Sie daher ein Huffman-Codierungsschema für jede einzelne Position. Bauern nehmen wahrscheinlich nur durchschnittlich 3-4 Bits statt 6. Der König sollte auch einige Bits nehmen.

Schließen Sie auch in diesem Schema "genommen" als mögliche Position ein. Dies kann auch sehr robust mit Burgen umgehen - jeder Turm und König hat einen zusätzlichen Zustand "ursprüngliche Position, bewegt". Auf diese Weise können Sie auch en passant in den Bauern codieren - "ursprüngliche Position, can en passant".

Mit genügend Daten sollte dieser Ansatz wirklich gute Ergebnisse liefern.

Ich würde versuchen, die Huffman-Codierung zu verwenden . Die Theorie dahinter ist - in jedem Schachspiel gibt es einige Figuren, die sich viel bewegen, und einige, die sich nicht viel bewegen oder früh eliminiert werden. Wenn in der Ausgangsposition bereits einige Teile entfernt wurden - umso besser. Das gleiche gilt für Quadrate - einige Quadrate sehen alle Aktionen, während andere nicht sehr berührt werden.

Somit hätte ich zwei Huffman-Tische - einen für Stücke, einen für Quadrate. Sie werden durch Betrachten des tatsächlichen Spiels erzeugt. Ich könnte einen großen Tisch für jedes Stück-Quadrat-Paar haben, aber ich denke, das wäre ziemlich ineffizient, da sich nicht viele Instanzen desselben Stücks wieder auf demselben Quadrat bewegen.

Jedes Stück hätte eine zugewiesene ID. Da es 32 verschiedene Teile gibt, würde ich nur 5 Bits für die Stück-ID benötigen. Die Stück-IDs ändern sich nicht von Spiel zu Spiel. Gleiches gilt für quadratische IDs, für die ich 6 Bits benötigen würde.

Die Huffman-Bäume würden codiert, indem jeder Knoten aufgeschrieben wird, wenn sie in der richtigen Reihenfolge durchlaufen werden (dh zuerst wird der Knoten ausgegeben, dann seine untergeordneten Knoten von links nach rechts). Für jeden Knoten gibt es ein Bit, das angibt, ob es sich um einen Blattknoten oder einen Verzweigungsknoten handelt. Wenn es sich um einen Blattknoten handelt, folgen die Bits mit der ID.

Die Startposition wird einfach durch eine Reihe von Stück-Ort-Paaren angegeben. Danach gibt es für jede Bewegung ein Stück-Ort-Paar. Sie finden das Ende des Startpositionsdeskriptors (und den Anfang des Bewegungsdeskriptors) einfach, indem Sie das erste Stück finden, das zweimal erwähnt wird. Falls ein Bauer befördert wird, gibt es 2 zusätzliche Bits, die angeben, was er wird, aber die Stück-ID ändert sich nicht.

Um die Möglichkeit zu berücksichtigen, dass ein Bauer zu Beginn des Spiels befördert wird, gibt es auch eine "Beförderungstabelle" zwischen den Huffman-Bäumen und den Daten. Zuerst gibt es 4 Bits, die angeben, wie viele Bauern aufgerüstet werden. Dann gibt es für jeden Bauern seine Huffman-codierte ID und 2 Bits, die angeben, was er geworden ist.

Die Huffman-Bäume werden unter Berücksichtigung aller Daten (sowohl der Startposition als auch der Bewegungen) und der Beförderungstabelle generiert. Obwohl normalerweise die Promotion-Tabelle leer ist oder nur wenige Einträge enthält.

Um es grafisch zusammenzufassen:

<Game> := <Pieces huffman tree> <squares huffman tree> <promotion table> <initial position> (<moves> | <1 bit for next move - see Added 2 below>)

<Pieces huffman tree> := <pieces entry 1> <pieces entry 2> ... <pieces entry N>
<pieces entry> := "0" | "1" <5 bits with piece ID>

<squares huffman tree> := <squares entry 1> <squares entry 2> ... <squares entry N>
<Squares entry> := "0" | "1" <6 bits with square ID>

<promotion table> := <4 bits with count of promotions> <promotion 1> <promotion 2> ... <promotion N>
<promotion> := <huffman-encoded piece ID> <2 bits with what it becomes>

<initial position> := <position entry 1> <position entry 2> ... <position entry N>
<moves> := <position entry 1> <position entry 2> ... <position entry N>
<position entry> := <huffman-encoded piece ID> <huffman-encoded squre ID> (<2 bits specifying the upgrade - optional>)

Hinzugefügt: Dies könnte noch optimiert werden. Jedes Stück hat nur wenige rechtliche Schritte. Anstatt einfach das Zielquadrat zu codieren, könnte man 0-basierte IDs für die möglichen Bewegungen jedes Stücks angeben. Dieselben IDs würden für jedes Stück wiederverwendet, sodass insgesamt nicht mehr als 21 verschiedene IDs vorhanden wären (die Königin kann höchstens 21 verschiedene mögliche Bewegungsoptionen haben). Legen Sie dies in eine Huffman-Tabelle anstelle der Felder.

Dies würde jedoch eine Schwierigkeit bei der Darstellung des ursprünglichen Zustands darstellen. Man könnte eine Reihe von Zügen erzeugen, um jedes Stück an seinen Platz zu bringen. In diesem Fall wäre es notwendig, das Ende des Anfangszustands und den Beginn der Bewegungen irgendwie zu markieren.

Alternativ können sie mithilfe unkomprimierter 6-Bit-Quadrat-IDs platziert werden.

Ob dies insgesamt zu einer Größenverringerung führen würde - weiß ich nicht. Wahrscheinlich, sollte aber ein bisschen experimentieren.

Hinzugefügt 2: Ein weiterer Sonderfall. Wenn der Spielstatus KEINE Züge hat, ist es wichtig zu unterscheiden, wer sich als nächstes bewegt. Fügen Sie dazu am Ende noch ein Bit hinzu. :) :)

[bearbeitet, nachdem die Frage richtig gelesen wurde] Wenn Sie davon ausgehen, dass jede Rechtsposition von der Ausgangsposition aus erreicht werden kann (was eine mögliche Definition von "legal" ist), kann jede Position als die Reihenfolge der Bewegungen von Anfang an ausgedrückt werden. Ein Spielausschnitt, der von einer nicht standardmäßigen Position ausgeht, kann ausgedrückt werden als die Abfolge von Bewegungen, die zum Erreichen des Starts erforderlich sind, ein Schalter zum Einschalten der Kamera, gefolgt von nachfolgenden Bewegungen.

Nennen wir den anfänglichen Kartenstatus das Einzelbit "0".

Bewegungen von jeder Position aus können durch Nummerieren der Quadrate und Ordnen der Bewegungen nach (Start, Ende) aufgezählt werden, wobei der herkömmliche 2-Quadrat-Sprung die Rochade anzeigt. Es ist nicht erforderlich, illegale Züge zu kodieren, da die Brettposition und die Regeln immer bereits bekannt sind. Die Flagge zum Einschalten der Kamera kann entweder als spezielle In-Band-Bewegung oder sinnvoller als Out-of-Band-Bewegungsnummer ausgedrückt werden.

Es gibt 24 Öffnungsbewegungen für jede Seite, die jeweils in 5 Bits passen. Nachfolgende Bewegungen erfordern möglicherweise mehr oder weniger Bits, aber die zulässigen Bewegungen sind immer aufzählbar, sodass die Breite jeder Bewegung glücklich wachsen oder sich erweitern kann. Ich habe nicht berechnet, aber ich stelle mir vor, 7-Bit-Positionen wären selten.

Mit diesem System könnte ein 100-Half-Move-Spiel in ungefähr 500 Bit codiert werden. Es kann jedoch ratsam sein, ein Eröffnungsbuch zu verwenden. Angenommen, es enthält eine Million Sequenzen. Dann gibt eine anfängliche 0 einen Start von der Standardplatine an, und eine 1 gefolgt von einer 20-Bit-Zahl zeigt einen Start von dieser Öffnungssequenz an. Spiele mit etwas konventionellen Eröffnungen können um beispielsweise 20 halbe Züge oder 100 Bit verkürzt werden.

Dies ist nicht die größtmögliche Komprimierung, aber (ohne das Eröffnungsbuch) wäre es sehr einfach zu implementieren, wenn Sie bereits ein Schachmodell haben, von dem die Frage ausgeht.

Um weiter zu komprimieren, möchten Sie die Bewegungen eher nach der Wahrscheinlichkeit als nach einer beliebigen Reihenfolge ordnen und die wahrscheinlichen Sequenzen in weniger Bits codieren (z. B. mit Huffman-Token, wie bereits erwähnt).

Wenn die Rechenzeit kein Problem darstellt, können Sie einen deterministischen möglichen Positionsgenerator verwenden, um einer bestimmten Position eindeutige IDs zuzuweisen.

Generieren Sie von einer bestimmten Position aus zunächst eine Anzahl möglicher Positionen in einem deterministischen Herrenhaus, z. B. von links unten nach rechts oben. Das bestimmt, wie viele Bits Sie für den nächsten Zug benötigen. In einigen Situationen kann es nur eine sein. Wenn der Umzug ausgeführt wird, speichern Sie nur die eindeutige ID für diesen Umzug.

Beförderung und andere Regeln zählen einfach als gültige Züge, solange sie deterministisch gehandhabt werden, z. B. zur Königin, zum Turm, zum Bischof. Jeder Zählimpuls wird als separater Zug gezählt.

Die Anfangsposition ist am schwierigsten und könnte ungefähr 250 Millionen mögliche Positionen erzeugen (glaube ich), die ungefähr 28 Bit plus ein zusätzliches Bit erfordern würden, um zu bestimmen, um welche Bewegung es sich handelt.

Angenommen, wir wissen, wer an der Reihe ist (jede Runde wechselt von weiß nach schwarz), würde der deterministische Generator ungefähr so ​​aussehen:

for each row
    for each column
        add to list ( get list of possible moves( current piece, players turn) )

'Liste der möglichen Züge abrufen' würde ungefähr Folgendes bewirken:

if current piece is not null 
    if current piece color is the same as the players turn
        switch( current piece type )
            king - return list of possible king moves( current piece )
            queen - return list of possible queen moves( current piece )
            rook - return list of possible rook moves( current piece )
            etc.

Wenn der König in Schach ist, gibt jede 'Liste möglicher xxx Züge' nur gültige Züge zurück, die die Kontrollsituation ändern.

Die meisten Antworten übersehen die dreifache Wiederholung. Leider müssen Sie für eine dreifache Wiederholung alle bisher gespielten Positionen speichern ...

Bei dieser Frage mussten wir platzsparend speichern, damit wir die Position wirklich nicht speichern müssen, solange wir sie aus der Liste der Züge erstellen können (vorausgesetzt, wir haben eine Standardstartposition). Wir können PGN optimieren und fertig. Balg ist ein einfaches Schema.

Es gibt 64 Felder auf dem Brett, 64 = 2 ^ 6. Wenn wir nur das Anfangs- und Endfeld jedes Zuges speichern, würde dies 12 Bit dauern (die Beförderung wird später angegangen). Beachten Sie, dass dieses Schema bereits Spieler zum Bewegen, Hervorheben, Erfassen von Stücken, Burgen usw. abdeckt. Ab diesen kann nur die Wiedergabe der Verschiebungsliste erstellt werden.

Für die Promotion können wir ein separates Array von Vektoren behalten, die "bei Bewegung N Promotion zu Piece XYZ" sagen würden. wir können einen Vektor von (int, byte) behalten.

Es ist verlockend, auch den Vektor (To, From) zu optimieren, da viele dieser Vektoren (To, From) im Schach nicht möglich sind. z.B. Es wird keinen Wechsel von e1 zu d8 usw. geben. Aber ich konnte mir kein Schema einfallen lassen. Weitere Ideen sind sehr willkommen.

Ich habe lange darüber nachgedacht (+ - 2 Stunden). Und es gibt keine offensichtlichen Antworten.

Angenommen:

1. Zeitstatus ignorieren (Ein Spieler hatte früher kein Zeitlimit und konnte daher ein Unentschieden erzwingen, indem er nicht spielte.)
2. Wann wurde das Spiel gespielt?!? Dies ist wichtig, da sich die Regeln im Laufe der Zeit geändert haben (daher wird im folgenden Punkt ein modernes Spiel von einem modernen Spiel ausgehen ...). Bitte beziehen Sie sich zum Beispiel auf die Regel für tote Bauern (Wikipedia hat ein sehr berühmtes Problem, das dies anzeigt), und wenn Sie möchten Um in die Vergangenheit zu reisen, bewegte sich der Bischof immer nur langsam und es wurden Würfel verwendet. lol.

... so aktuell sind moderne Regeln. Zuerst unabhängig von der Wiederholung und Verschieben der Wiederholungsgrenze.

-C 25 Bytes gerundet (64b + 32 * 4b + 5b = 325b)

= 64 Bit (etwas / nichts) + 32 * 4 Bit [1 Bit = Farbe {schwarz / mit}} + 3 Bit = Art des Stücks {König, Königin, Bischof, Nacht, Turm, Bauer, MovedPawn} NB: Moved Pawn ... zB wenn es der letzte bewegte Bauer in der vorherigen Runde war, der anzeigt, dass ein "en passant" machbar ist. ] + 5bit für den tatsächlichen Zustand (wer ist an der Reihe, en passant, Möglichkeit des Rookings oder nicht auf jeder Seite)

So weit, ist es gut. Kann wahrscheinlich verbessert werden, aber dann wäre eine variable Länge und Promotion zu berücksichtigen!?

Die folgenden Regeln gelten nur, wenn sich ein Spieler für ein Unentschieden bewirbt. ES IST NICHT automatisch! Bedenken Sie also, dass diese 90 Züge ohne Eroberung oder Bauernzug ​​möglich sind, wenn kein Spieler ein Unentschieden fordert! Das bedeutet, dass alle Bewegungen aufgezeichnet werden müssen ... und verfügbar sind.

-D Wiederholung der Position ... zB Zustand des Bretts wie oben erwähnt (siehe C) oder nicht ... (siehe unten bezüglich der FIDE-Regeln) -E Damit bleibt das komplexe Problem der 50-Zug-Erlaubnis ohne Eroberung oder Bauernbewegung dort a Zähler ist notwendig ... Allerdings.

Wie gehst du damit um? ... Nun, wirklich, es gibt keinen Weg. Weil keiner der Spieler ziehen oder erkennen möchte, dass es passiert ist. Für den Fall, dass E ein Zähler ausreicht ... aber hier ist der Trick und sogar das Lesen der FIDE-Regeln (http://www.fide.com/component/handbook/?id=124&view=article) kann ich nicht finden Antwort ... was ist mit dem Verlust der Fähigkeit zum Rooking? Ist das eine Wiederholung? Ich denke nicht, aber dann ist dies ein verschwommenes Thema, das nicht angesprochen, nicht geklärt wird.

Also hier sind zwei Regeln, die zwei komplex oder undefiniert sind, selbst um zu versuchen, sie zu kodieren ... Prost.

Die einzige Möglichkeit, ein Spiel wirklich zu kodieren, besteht darin, alles von Anfang an aufzuzeichnen ... was dann mit der Frage "Board State" in Konflikt steht (oder nicht?).

Hoffe diese Hilfe ... nicht zu viel Mathe :-) Nur um zu zeigen, dass einige Fragen nicht so einfach sind, zu offen für Interpretation oder Vorkenntnisse, um richtig und effizient zu sein. Keines, das ich für ein Interview in Betracht ziehen würde, da es zu viel Dose Wurm öffnet.

Mögliche Verbesserung der Ausgangsposition in Yacobys Lösung

Keine Rechtsposition hat mehr als 16 Stück jeder Farbe. Die Anzahl der Möglichkeiten, bis zu 16 schwarze und 16 weiße Teile auf 64 Quadraten zu platzieren, beträgt ca. 3,63e27. Log2 (3.63e27) = 91.55. Dies bedeutet, dass Sie die Position und Farbe aller Teile in 92 Bit codieren können. Dies ist weniger als die 64 Bit für Position + bis zu 32 Bit für Farbe, die Yacobys Lösung benötigt. Sie können im schlimmsten Fall 4 Bit auf Kosten einer erheblichen Komplexität bei der Codierung sparen.

Auf der anderen Seite wird die Größe für Positionen erhöht, bei denen 5 oder mehr Teile fehlen. Diese Positionen machen nur <4% aller Positionen aus, aber sie sind wahrscheinlich die Mehrheit der Fälle, in denen Sie eine andere Startposition als die Anfangsposition aufzeichnen möchten.

Dies führt zur vollständigen Lösung

1. Codieren Sie die Position und Farbe der Teile gemäß der obigen Methode. 92 Bit .
2. Verwenden Sie einen Huffman-Code, um den Typ jedes Stücks anzugeben: Bauer: '0', Turm: '100', Ritter: '101', Bischof: '110', Königin: '1110', König: '1111'. Dies erfordert (16 * 1 + 12 * 3 + 4 * 4) = 68 Bit für einen vollständigen Satz von Teilen. Die Vollplatinenposition kann in maximal 92 + 68 = 160 Bit codiert werden .
3. Zusätzlicher Spielstatus sollte hinzugefügt werden: Zug: 1 Bit, welches Castling möglich ist: 4 Bit, "en passant" möglich: bis zu 4 Bit (1 Bit sagt, dass dies der Fall ist und 3 Bit sagen, welches). Die Startposition ist in = 160 + 9 = 169 Bit codiert
4. Zählen Sie für die Liste der Züge alle möglichen Züge für eine bestimmte Position auf und speichern Sie die Position des Zuges in der Liste. Die Liste der Züge enthält alle Sonderfälle (Rochade, en passant und Rücktritt). Verwenden Sie nur so viele Bits wie nötig, um die höchste Position zu speichern. Im Durchschnitt sollte es 7 Bits pro Zug nicht überschreiten (durchschnittlich 16 mögliche Stücke und 8 legale Züge pro Stück). In einigen Fällen benötigt ein erzwungener Zug nur 1 Bit (Zug oder Rücktritt).

Es gibt 32 Stück auf dem Brett. Jedes Stück hat eine Position (eines von 64 Quadraten). Sie brauchen also nur 32 positive ganze Zahlen.

Ich weiß, dass 64 Positionen in 6 Bits gehalten werden, aber das würde ich nicht tun. Ich würde die letzten Teile für ein paar Flaggen behalten (fallengelassenes Stück, Bauer mit Königin)

Cletus 'Antwort ist gut, aber er hat vergessen, auch zu kodieren, an der Reihe ist. Es ist Teil des aktuellen Status und erforderlich, wenn Sie diesen Status verwenden, um einen Suchalgorithmus (wie ein Alpha-Beta-Derivat) zu steuern.

Ich bin kein Schachspieler, aber ich glaube, es gibt noch einen weiteren Eckfall: Wie viele Züge wurden wiederholt? Sobald jeder Spieler dreimal den gleichen Zug macht, ist das Spiel ein Unentschieden, nicht wahr? Wenn ja, müssen Sie diese Informationen im Status speichern, da der Status nach der dritten Wiederholung jetzt terminal ist.

Wie mehrere andere bereits erwähnt haben, können Sie für jedes der 32 Teile speichern, auf welchem ​​Quadrat sie sich befinden. Wenn sie sich auf dem Brett befinden oder nicht, ergibt dies 32 * (log2 (64) + 1) = 224 Bits.

Die Bischöfe können jedoch nur die schwarzen oder weißen Quadrate besetzen, sodass Sie für diese nur log2 (32) Bits für die Position benötigen, was 28 * 7 + 4 * 6 = 220 Bits ergibt.

Und da die Bauern nicht hinten anfangen und sich nur vorwärts bewegen können, sondern nur auf 56, sollte es möglich sein, diese Einschränkung zu verwenden, um die Anzahl der für die Bauern benötigten Bits zu verringern.

Eine Tafel hat 64 Quadrate und kann durch 64 Bits dargestellt werden, die anzeigen, ob ein Quadrat leer ist oder nicht. Wir brauchen nur Stückinformationen, wenn ein Quadrat ein Stück hat. Da der Spieler + Stück 4 Bits benötigt (wie oben gezeigt), können wir den aktuellen Status in 64 + 4 * 32 = 192 Bits erhalten. Werfen Sie die aktuelle Runde und Sie haben 193 Bits.

Wir müssen jedoch auch die rechtlichen Schritte für jedes Stück kodieren. Zuerst berechnen wir die Anzahl der legalen Züge für jedes Stück und fügen so viele Bits nach der Stückkennung eines vollen Quadrats hinzu. Ich habe wie folgt berechnet:

Bauer: Vorwärts, zuerst zwei vorwärts drehen, en passant * 2, Beförderung = 7 Bits. Sie können die erste Vorwärtsbewegung und die Beförderung zu einem einzigen Bit kombinieren, da sie nicht von derselben Position aus erfolgen können. Sie haben also 6. Turm: 7 vertikale Quadrate, 7 horizontale Quadrate = 14 Bit Ritter: 8 Quadrate = 8 Bit Bischof: 2 Diagonalen * 7 = 14 Bit Königin: 7 vertikal, 7 horizontal, 7 diagonal, 7 diagonal = 28 Bit König: 8 umgebende Quadrate

Dies bedeutet immer noch, dass Sie die Zielquadrate basierend auf der aktuellen Position abbilden müssten, aber es sollte (sollte) eine einfache Berechnung sein.

Da wir 16 Bauern, 4 Türme / Ritter / Bischöfe und 2 Königinnen / Könige haben, sind dies 16 * 6 + 4 * 14 + 4 * 8 + 4 * 14 + 2 * 28 + 2 * 8 = 312 weitere Bits die Summe auf 505 Bit insgesamt.

Was die Anzahl der Bits betrifft, die pro Stück für mögliche Züge benötigt werden, könnten einige Optimierungen hinzugefügt und die Anzahl der Bits wahrscheinlich verringert werden. Ich habe nur einfache Zahlen verwendet, um damit zu arbeiten. Zum Beispiel könnten Sie für Schiebeteile speichern, wie weit sie sich bewegen könnten, dies würde jedoch zusätzliche Berechnungen erfordern.

Lange Rede, kurzer Sinn: Speichern Sie zusätzliche Daten (Stück usw.) nur, wenn ein Quadrat belegt ist, und speichern Sie nur die Mindestanzahl von Bits für jedes Stück, um seine legalen Bewegungen darzustellen.

EDIT1: Vergessen Sie die Rochade und Bauernförderung für jedes Stück. Dies könnte die Summe mit expliziten Positionen auf 557 Züge bringen (3 weitere Bits für Bauern, 2 für Könige)

Jedes Stück kann durch 4 Bits dargestellt werden (Bauer an König, 6 Typen), schwarz / weiß = 12 Werte

Jedes Quadrat auf der Tafel kann durch 6 Bits (x-Koordinate, y-Koordinate) dargestellt werden.

Anfangspositionen erfordern maximal 320 Bit (32 Teile, 4 + 6 Bit)

Jede nachfolgende Bewegung kann durch 16 Bits dargestellt werden (von Position zu Position, Stück).

Das Castling würde zusätzliche 16 Bit erfordern, da es sich um einen Doppelzug handelt.

Dame-Bauern könnten durch einen der 4 Ersatzwerte von 4 Bits dargestellt werden.

Ohne die Mathematik im Detail durchzuführen, beginnt dies nach dem ersten Zug Platz zu sparen, verglichen mit dem Speichern von 32 * 7 Bit (vordefinierte Anordnung von Teilen) oder 64 * 4 Bit (vordefinierte Zuordnung von Quadraten).

Nach 10 Zügen auf beiden Seiten beträgt der maximal benötigte Speicherplatz 640 Bit

... aber andererseits, wenn wir jedes Stück eindeutig identifizieren (5 Bits) und ein sechstes Bit zum Markieren von Bauern mit Königinnen hinzufügen, brauchen wir nur Stück-ID + Position für jeden Zug. Dies ändert die Berechnung in ...

Anfangspositionen = max. 384 Bit (32 Teile, 6 + 6 Bit) Jede Bewegung = 12 Bit (zu Position, Stück-ID)

Nach 10 Zügen auf jeder Seite beträgt der maximal benötigte Platz 624 Bit

Wie Robert G würde ich PGN eher verwenden, da es Standard ist und von einer Vielzahl von Tools verwendet werden kann.

Wenn ich jedoch eine Schach-KI spiele, die sich auf einer entfernten Raumsonde befindet, und daher jedes bisschen wertvoll ist, würde ich dies für die Züge tun. Ich werde später mit der Kodierung des Ausgangszustands beginnen.

Die Bewegungen müssen keinen Status aufzeichnen. Der Decoder kann den Status sowie die Bewegungen verfolgen, die zu einem bestimmten Zeitpunkt zulässig sind. Es muss lediglich aufgezeichnet werden, welche der verschiedenen rechtlichen Alternativen gewählt wird. Da sich die Spieler abwechseln, muss bei einem Zug die Spielerfarbe nicht aufgezeichnet werden. Da ein Spieler nur seine eigenen Farbstücke bewegen kann, ist die erste Wahl, welche Figur der Spieler bewegt (ich werde später auf eine Alternative zurückkommen, die eine andere Wahl verwendet). Bei höchstens 16 Stück sind dafür höchstens 4 Bit erforderlich. Wenn ein Spieler Steine ​​verliert, verringert sich die Anzahl der Auswahlmöglichkeiten. Ein bestimmter Spielzustand kann auch die Auswahl der Teile einschränken. Wenn sich ein König nicht bewegen kann, ohne sich selbst in Schach zu halten, wird die Anzahl der Auswahlmöglichkeiten um eins verringert. Wenn ein König in Schach ist, ist jedes Stück, das den König nicht aus der Kontrolle bringen kann, keine brauchbare Wahl.

Sobald das Stück angegeben ist, hat es nur noch eine bestimmte Anzahl legaler Ziele. Die genaue Anzahl hängt stark vom Brettlayout und der Spielhistorie ab, aber wir können bestimmte Maxima und erwartete Werte herausfinden. Für alle außer dem Ritter und während der Rochade kann sich ein Stück nicht durch ein anderes Stück bewegen. Dies wird eine große Quelle für Bewegungslimits sein, aber es ist schwer zu quantifizieren. Ein Stück kann sich nicht vom Brett entfernen, was auch die Anzahl der Ziele stark einschränkt.

Wir codieren das Ziel der meisten Teile, indem wir Quadrate entlang der Linien in der folgenden Reihenfolge nummerieren: W, NW, N, NE (schwarze Seite ist N). Eine Linie beginnt auf dem Quadrat, das am weitesten in der angegebenen Richtung liegt, zu der es legal ist, sich zu bewegen, und verläuft in Richtung der. Für einen unbelasteten König lautet die Liste der Züge W, E, NW, SE, N, S, NE, SW. Für den Ritter beginnen wir mit 2W1N und fahren im Uhrzeigersinn fort; Ziel 0 ist das erste gültige Ziel in dieser Reihenfolge.

• Bauern: Ein unbewegter Bauer hat 2 verschiedene Ziele und benötigt daher 1 Bit. Wenn ein Bauer einen anderen entweder normal oder en passant erfassen kann (was der Decoder bestimmen kann, da er den Status verfolgt), hat er auch zwei oder drei Züge zur Auswahl. Davon abgesehen kann ein Bauer nur eine Wahl haben und benötigt keine Bits. Wenn ein Bauer in seinem 7 - ^ten Rang, heften wir auch auf der Förderung Wahl. Da Bauern normalerweise zu Königinnen befördert werden, gefolgt von Rittern, kodieren wir die Auswahlmöglichkeiten wie folgt:
  • Königin: 0
  • Ritter: 10
  • Bischof: 110
  • Turm: 111
• Bischof: höchstens 13 Ziele bei {d, e} {4,5} für 4 Bits.
• Turm: höchstens 14 Ziele, 4 Bit.
• Ritter: höchstens 8 Ziele, 3 Bits.
• Könige: Wenn das Rochieren eine Option ist, hat der König es zurück zu S und kann sich nicht nach unten bewegen. Dies ergibt insgesamt 7 Ziele. In der restlichen Zeit hat ein König höchstens 8 Züge, was maximal 3 Bits ergibt.
• Königin: Wie Auswahl für Bischof oder Turm, für insgesamt 27 Auswahlmöglichkeiten, was 5 Bit entspricht

Da die Anzahl der Auswahlmöglichkeiten nicht immer eine Zweierpotenz ist, verschwendet das Obige immer noch Bits. Angenommen, die Anzahl der Auswahlmöglichkeiten ist C und die bestimmte Auswahl ist mit c nummeriert und n = Ceil (lg ( C )) (die Anzahl der Bits, die zum Codieren der Auswahl erforderlich sind). Wir nutzen diese ansonsten verschwendeten Werte, indem wir das erste Bit der nächsten Wahl untersuchen. Wenn es 0 ist, nichts tun. Wenn es 1 ist und c + C <2 ⁿ , dann füge C zu c hinzu . Das Dekodieren einer Zahl kehrt dies um: Wenn das empfangene c > = C ist , subtrahieren Sie C und setzen Sie das erste Bit für die nächste Zahl auf 1. Wenn c<2ⁿ - C , dann setze das erste Bit für die nächste Zahl auf 0. Wenn 2 ⁿ - C <= c < C , dann tue nichts. Nennen Sie dieses Schema "Sättigung".

Eine andere mögliche Art der Wahl, die die Kodierung verkürzen könnte, ist die Auswahl eines zu erfassenden Gegenstücks. Dies erhöht die Anzahl der Auswahlmöglichkeiten für den ersten Teil eines Zuges, wobei eine Figur ausgewählt wird, höchstens für ein zusätzliches Bit (die genaue Anzahl hängt davon ab, wie viele Figuren der aktuelle Spieler bewegen kann). Dieser Auswahl folgt eine Auswahl der Eroberungsstücke, die wahrscheinlich viel kleiner ist als die Anzahl der Züge für eine der gegebenen Spielerstücke. Eine Figur kann nur von einer Figur aus einer beliebigen Himmelsrichtung plus den Rittern für insgesamt höchstens 10 angreifende Figuren angegriffen werden. Dies ergibt insgesamt maximal 9 Bit für eine Erfassungsbewegung, obwohl ich durchschnittlich 7 Bit erwarten würde. Dies wäre besonders vorteilhaft für Gefangennahmen durch die Königin, da es häufig einige legale Ziele gibt.

Bei Sättigung bietet die Capture-Codierung wahrscheinlich keinen Vorteil. Wir könnten beide Optionen berücksichtigen und im Ausgangszustand angeben, welche verwendet werden. Wenn die Sättigung nicht verwendet wird, kann die Spielcodierung auch nicht verwendete Auswahlnummern ( C <= c <2 ⁿ ) verwenden, um die Optionen während des Spiels zu ändern. Jedes Mal, wenn C eine Zweierpotenz ist, konnten wir die Optionen nicht ändern.

Thomas hat den richtigen Ansatz für die Codierung der Karte. Dies sollte jedoch mit dem Ansatz von ralu zum Speichern von Zügen kombiniert werden. Machen Sie eine Liste aller möglichen Bewegungen und schreiben Sie die Anzahl der Bits auf, die erforderlich sind, um diese Anzahl auszudrücken. Da der Decoder dieselbe Berechnung durchführt, weiß er, wie viele möglich sind und wie viele Bits zu lesen sind. Es werden keine Längencodes benötigt.

Somit erhalten wir 164 Bits für die Teile, 4 Bits für die Casting-Informationen (vorausgesetzt, wir speichern ein Fragment eines Spiels, andernfalls kann es rekonstruiert werden), 3 Bits für en passant-Berechtigungsinformationen - speichern Sie einfach die Spalte, in der der Umzug stattgefunden hat ( Wenn en passant nicht möglich ist, speichern Sie eine Spalte dort, wo dies nicht möglich ist (solche Spalten müssen vorhanden sein) und 1 für die Person, die verschoben werden soll.

Bewegungen dauern normalerweise 5 oder 6 Bit, können jedoch von 1 bis 8 variieren.

Eine zusätzliche Verknüpfung: Wenn die Codierung mit 12 1 Bit beginnt (eine ungültige Situation - nicht einmal ein Fragment hat zwei Könige auf einer Seite), brechen Sie die Decodierung ab, wischen das Brett ab und richten ein neues Spiel ein. Das nächste Bit wird ein Bewegungsbit sein.

Der Algorithmus sollte alle möglichen Ziele bei jeder Bewegung deterministisch auflisten. Anzahl der Ziele:

• 2 Bischöfe zu je 13 Zielen = 26
• 2 Türme, jeweils 14 Ziele = 28
• 2 Ritter, je 8 Ziele = 16
• Königin, 27 Ziele
• König, 8 Ziele

8 Pfoten könnten im schlimmsten Fall (in Bezug auf die Aufzählung) alle zu Königinnen werden, wodurch die größte Anzahl möglicher Ziele 9 * 27 + 26 + 28 + 16 + 8 = 321 erreicht wird. Somit können alle Ziele für jede Bewegung durch eine 9-Bit-Zahl aufgezählt werden.

Die maximale Anzahl von Zügen beider Parteien beträgt 100 (wenn ich mich nicht irre, kein Schachspieler). Somit konnte jedes Spiel in 900 Bit aufgezeichnet werden. Plus Anfangsposition jedes Stück kann mit 6-Bit-Nummern aufgezeichnet werden, was 32 * 6 = 192 Bit ergibt. Plus ein Bit für den Datensatz "Wer bewegt sich zuerst?". Somit kann jedes Spiel mit 900 + 192 + 1 = 1093 Bits aufgezeichnet werden.

Speichern des Board-Status

Der einfachste Weg, an den ich gedacht habe, ist, zuerst ein Array von 8 * 8 Bits zu haben, die die Position jeder Figur darstellen (also 1, wenn es eine Schachfigur gibt, und 0, wenn es keine gibt). Da dies eine feste Länge ist, benötigen wir keinen Terminator.

Stellen Sie als nächstes jede Schachfigur in der Reihenfolge ihrer Position dar. Bei Verwendung von 4 Bits pro Stück werden 32 * 4 Bits (insgesamt 128) benötigt. Welches ist wirklich sehr, sehr verschwenderisch.

Mit einem binären Baum können wir einen Bauern in einem Byte, einen Ritter und einen Turm und einen Bischof in 3 und einen König und eine Königin in 4 darstellen. Da wir auch die Farbe des Stücks speichern müssen, das ein zusätzliches Byte benötigt, endet es as (verzeihen Sie mir, wenn dies falsch ist, ich habe mir die Huffman-Codierung noch nie im Detail angesehen):

• Bauer: 2
• Turm: 4
• Ritter: 4
• Bischof: 4
• König: 5
• Königin: 5

Angesichts der Gesamtzahlen:

2*16 + 4*4 + 4*4 + 4*4 + 2*5 + 2*5 = 100

Welches schlägt mit einem Satz von Bits fester Größe um 28 Bits.

Die beste Methode, die ich gefunden habe, ist es, sie in einem 8 ² + 100-Bit-Array zu speichern

8*8 + 100 = 164

Speichern von Moves
Das erste, was wir wissen müssen, ist, welches Stück sich wohin bewegt. Da sich maximal 32 Teile auf dem Brett befinden und wir wissen, was jedes Teil ist, anstatt eine Ganzzahl, die das Quadrat darstellt, können wir eine Ganzzahl haben, die den Teilversatz darstellt, was bedeutet, dass wir nur 32 mögliche Werte anpassen müssen, um a darzustellen Stück.

Leider gibt es verschiedene Sonderregeln, wie das Rochieren oder Stürzen des Königs und das Bilden einer Republik (Terry Pratchett-Referenz). Bevor wir das zu bewegende Stück aufbewahren, benötigen wir ein einzelnes Bit, das angibt, ob es sich um einen Sonderzug handelt oder nicht.

Für jede normale Bewegung haben wir also die notwendigen 1 + 5 = 6Bits. (1 Bit Typ, 5 Bit für das Stück)

Nachdem die Stücknummer dekodiert wurde, kennen wir den Stücktyp und jedes Stück sollte seine Bewegung auf die effizienteste Weise darstellen. Zum Beispiel (wenn meine Schachregeln auf dem neuesten Stand sind) hat ein Bauer insgesamt 4 mögliche Züge (links nehmen, rechts nehmen, einen vorwärts bewegen, zwei vorwärts bewegen).
Um einen Bauernzug ​​darzustellen, benötigen wir '6 + 2 = 8' Bits. (6 Bit für den anfänglichen Verschiebungsheader, 2 Bit für welchen Zug)

Das Bewegen für die Königin wäre komplexer, da es am besten wäre, eine Richtung (8 mögliche Richtungen, also 3 Bits) und insgesamt 8 mögliche Quadrate für jede Richtung (also weitere 3 Bits) zu haben. Um die Bewegung einer Königin darzustellen, wären 6 + 3 + 3 = 12Bits erforderlich .

Das Letzte, was mir einfällt, ist, dass wir speichern müssen, welche Spieler an der Reihe sind. Dies sollte ein einzelnes Bit sein (Weiß oder Schwarz, um sich als nächstes zu bewegen)

Resultierendes Format Das Dateiformat würde also ungefähr
so aussehen

[64 Bit] Anfangsstückpositionen
[max. 100 Bit] Anfangsstücke [1 Bit] Spielerzug
[n Bit] Zieht

Wo ein Move ist
[1 Bit] Move-Typ (speziell oder normal)
[n Bit] Move Detail

Wenn es sich bei der Verschiebung um eine normale Bewegung handelt, sieht das Verschiebungsdetail ungefähr wie eine
[5 Bit] Stück
[n Bit] spezifische Stückbewegung aus (normalerweise im Bereich von 2 bis 6 Bit].

Wenn es sich um einen Spezialzug handelt,
sollte er einen ganzzahligen Typ und dann zusätzliche Informationen haben (z. B. wenn es sich um eine Rochade handelt). Ich kann mich nicht an die Anzahl der Spezialbewegungen erinnern, daher kann es in Ordnung sein, nur anzuzeigen, dass es sich um eine Spezialbewegung handelt (wenn es nur eine gibt).

Beachten Sie im Basisfall des ersten Boards plus nachfolgender Züge Folgendes.

Verwenden Sie ein Schachprogramm, um allen möglichen Zügen Wahrscheinlichkeiten zuzuweisen. Zum Beispiel 40% für e2-e4, 20% für d2-d4 und so weiter. Wenn einige Schritte legal sind, aber von diesem Programm nicht berücksichtigt werden, geben Sie ihnen eine geringe Wahrscheinlichkeit. Verwenden Sie die arithmetische Codierung, um zu speichern, welche Auswahl getroffen wurde. Dies ist eine Zahl zwischen 0 und 0,4 für den ersten Zug, 0,4 und 0,6 für den zweiten und so weiter.

Machen Sie dasselbe für die andere Seite. Wenn beispielsweise eine 50% ige Chance von e7-e5 als Antwort auf e2-e4 besteht, liegt die codierte Zahl zwischen 0 und 0,2. Wiederholen, bis das Spiel beendet ist. Das Ergebnis ist ein möglicherweise sehr kleiner Bereich. Finden Sie den binären Bruch mit der kleinsten Basis, die in diesen Bereich passt. Das ist arithmetische Codierung.

Dies ist besser als Huffman, da es als fraktionierte Bitcodierung angesehen werden kann (plus einige am Ende des Spiels, um auf ein ganzes Bit aufzurunden).

Das Ergebnis sollte kompakter sein als Huffman, und es gibt keine Sonderfälle für Beförderung, en passant, den 50-Regel-Zug und andere Details, da diese vom Schachbewertungsprogramm behandelt werden.

Verwenden Sie zum Wiederholen erneut das Schachprogramm, um das Brett zu bewerten und jedem Zug alle Wahrscheinlichkeiten zuzuweisen. Verwenden Sie den arithmetisch codierten Wert, um zu bestimmen, welcher Zug tatsächlich gespielt wurde. Wiederholen, bis fertig.

Wenn Ihr Schachprogramm gut genug ist, können Sie mit einem Zwei-Zustands-Encoder eine bessere Komprimierung erzielen, bei der die Wahrscheinlichkeiten basierend auf den Bewegungen für Schwarz und Weiß definiert werden. Im extremsten Fall von mehr als 200 Staaten codiert dies den gesamten Satz aller möglichen Schachspiele und ist daher nicht durchführbar.

Dies ist eine ziemlich andere Art zu sagen, was Darius bereits geschrieben hat, nur mit einem kleinen Beispiel dafür, wie arithmetische Codierung funktionieren könnte, und einem realen Beispiel für die Verwendung eines vorhandenen Schachprogramms, um die Wahrscheinlichkeit der nächsten Züge zu bewerten.