Gibt es neben der FEN-Notation noch andere kompaktere bekannte Schachpositionsnotationen? Eine, die natürlich auch Burgenrechte und en passant Möglichkeiten mit sich bringen würde. Ein wirklich fehlendes Bit im FEN ist die Tatsache, dass es keine Informationen darüber enthält, ob die Position einem Schachmatt entspricht oder ob dies überprüft wird. Natürlich kann man die Position immer auf die Tafel setzen und sehen, ob es sich um ein Schachmatt handelt oder nicht, aber es ist nicht direkt aus der Notation ableitbar. Eine solche Eigenschaft wäre daher auch für die Unterscheidung möglicher Notationen von Bedeutung (abgesehen von Kompaktheit usw.).

Wenn es hilft, wird dies aus praktischen und effizienten Gründen bei der Programmierung angefordert. Vielen Dank für alle Vorschläge.

Da es sich um Programmierung handelt, suchen Sie vermutlich nach einem Speicherschema, das im Computerspeicher kompakter ist als FEN. Neben der Untersuchung, wie es in großen Tischgestellen gemacht wird, fallen mir sofort zwei Möglichkeiten ein.

Normales FEN

Für diese Diskussion ist "normales" FEN nur eine typische Textzeichenfolge, die mit 1-Byte-Zeichen (8-Bit) dargestellt wird. Schauen wir uns einen vereinfachten Worst-Case an :

r1b1k1n1/1p1p1p1p/p1p1p1p1/1n1q1b1r/R1B1P1N1/1P1P1P1P/P1P1K1P1/1N1Q1B1R w KQkq e3 999 999

Dies ist natürlich kein gültiger FEN, aber es ist eine effektive Obergrenze für unsere Komplexität. Es gibt acht Zeichen pro Rang sowie sieben Schrägstriche, fünf Leerzeichen und dreizehn zusätzliche Zeichen, die die verbleibenden Felder bilden. Das sind 89 Zeichen bei einer Gesamtgröße von 712 Bit .

Komprimiertes FEN

Diese Version verwendet lediglich eine FEN-Darstellung und verwendet einige grundlegende Beobachtungen, um die Anzahl der zum Speichern erforderlichen Bits zu verringern. Hier sind unsere Beobachtungen:

1. Die Schrägstriche sind für die Maschinenlagerung nicht erforderlich. Jeder Rang muss einfach "zu 8 addieren". So können wir Schrägstriche in unserer internen Darstellung beseitigen.
2. Die verbleibenden möglichen Zeichen (im ersten Abschnitt) sind : kK qQ rR bB nN pP 12345678. Die Unterscheidung zwischen 20 Zeichen passt in fünf Bits. In unserem vereinfachten Worst-Case haben wir also fünf Bits mal acht Dateien mal acht Ränge, was 320 Bits für den ersten Teil entspricht.
3. Wir brauchen keine Leerzeichen; wieder sind sie eine Annehmlichkeit für Menschen. Das spart uns fünf Zeichen.
4. "Wer hat den Zug" ist ein bisschen: Weiß oder Schwarz.
5. Die Verfügbarkeit von Castling beträgt vier Bits: Verfügbar / Nicht verfügbar für jeden von KQkq.
6. En passant ist normalerweise nicht verfügbar und kann viel Platz einnehmen (sechs Bits, um alle Quadrate darzustellen). Verschieben Sie es also zum Ende und machen Sie es optional: Wenn en passant Bits vorhanden sind, ist es verfügbar, aber wenn es nicht verfügbar ist, können wir Beenden Sie einfach die Darstellung nach den Verschiebungs- und Halbverschiebungsbits, um Platz zu sparen.
7. Der Einfachheit halber ordne ich jedem Zug- und Halbbewegungszähler nur zehn Bits zu. Dies bedeutet, dass Spiele, die in diesem Format dargestellt werden, 1023 Züge nicht überschreiten dürfen (halbe Züge seit dem letzten Eroberungs- oder Bauernvorschub).

Unser Vollformat sieht folgendermaßen aus (in einem vereinfachten Worst-Case mit en passant verfügbar):

<position><whose move><castling><half moves><full moves><en passant>
 320 bits  1 bit       4 bits    10 bits     10 bits     6 bits

Dies ergibt eine Gesamtgröße von 351 Bit in unserem unmöglichen schlimmsten Fall, etwas weniger als die Hälfte der Größe unseres Startpunkts.

µFEN

Wenn wir FEN für das Fleisch der Darstellung ganz aufgeben, können wir es etwas weiter verkleinern. Betrachten Sie ein einzelnes beliebiges Quadrat. Dieses Quadrat kann leer sein oder ein Stück darauf haben. Wenn es ein Stück hat, kann es entweder weiß oder schwarz sein, und es kann ein König, eine Königin, ein Turm, ein Bischof, ein Ritter oder ein Bauer sein. Das sind insgesamt dreizehn verschiedene Zustände, die wir in vier Bits darstellen können; etwas wie das:

0000: empty square
0001: White Pawn
0010: White Knight
0011: White Bishop
0100: White Rook
0101: White Queen
0110: White King
0111: unused
1000: unused
1001: Black Pawn
1010: Black Knight
1011: Black Bishop
1100: Black Rook
1101: Black Queen
1110: Black King
1111: unused

Offensichtlich gibt es einige nicht verwendete "Teilbits", so dass dieses Schema mit ziemlicher Sicherheit von jemandem mit mehr Kenntnissen über Komprimierungstechniken oder einfach einer sorgfältigeren Abbildung der verschiedenen Zustände weiter verbessert werden könnte. Auch in der Praxis kann dies größer sein als das oben beschriebene komprimierte FEN , da keine Komprimierung zusammenhängender Leerzeichen erfolgt. Es repräsentiert jedoch die gesamte Karte in konstanten 256 Bit (4 Bit * 64 Quadrate), was im schlimmsten Fall eine Verbesserung von 20% darstellt.

Der Einfachheit halber markieren wir nur die zweite Hälfte des komprimierten FEN , um die Darstellung zu vervollständigen. Das Format sieht also so aus:

<position><whose move><castling><half moves><full moves><en passant>
 256 bits  1 bit       4 bits    10 bits     10 bits     6 bits

Dies ergibt einen Platzbedarf im ungünstigsten Fall von 287 Bit . Nicht so schlecht!

Anmerkung 1: Denken Sie daran, dies ist alles nur eine Worst-Case-Analyse, da ich einen Informatik-Hintergrund habe. Standard-FEN schneidet normalerweise viel besser ab, als ich es beschrieben habe, da normale Positionen nicht das Szenario sind, das ich hier für Vergleiche verwendet habe. Die prozentualen Verbesserungen sind also wahrscheinlich etwas niedriger als ich tatsächlich dargestellt habe, aber der Trend hält wahrscheinlich immer noch an, zumindest für die komprimierte FEN-Darstellung. Es würde mich sehr interessieren, wenn jemand eine probabilistische Durchschnittsfallanalyse für Standard-FEN durchführen möchte (und im weiteren Sinne die oben vorgeschlagene komprimierte Version)!

Hinweis 2: Denken Sie daran, dass sich die Geschwindigkeitskompromisse beim Umgang mit komprimierten Formaten für Ihre Anwendungen möglicherweise lohnen oder nicht! Je nachdem , welche Sprache Sie verwenden und das Niveau der Kontrolle haben Sie über einzelne Bits, können Sie diese einfach finden FEN schneller ist deutlich zu verwenden , auch wenn es mehr Platz benötigt!

Hinweis 3: Wenn Sie einer der neuen vorgeschlagenen Notationen einen Indikator "check / checkmate / no-check" hinzufügen möchten, sind es zwei zusätzliche Bits, um die drei zusätzlichen Zustände darzustellen. Wirf es einfach vor die en passant Anzeige.

Extended Position Description ( EPD ) fügt FEN "Operationen" hinzu. Diese Operationen umfassen unter anderem die beste Bewegung, die Anzahl der Wiederholungen und die vorhergesagte Bewegung. Es ist offensichtlich nicht kompakter, aber es macht mehr.

Es sei denn, mir fehlt etwas Offensichtliches, die Darstellung

0      empty
100    white pawn
101    black pawn
110xxx any piece except Rook
111x   Rook

codiert ein volles Haus (dh vor jeder Erfassung) in 32 * 1 + 16 * 3 + 12 * 6 + 4 * 4 = 168 Positionsbits. Plus natürlich 4 Burgbits, 3 en passant Bits und 7 oder 8 50-Bewegungsregelbits.

Der schlimmste Fall (8 Bauern wurden durch die Kosten für das Erobern von 8 anderen Bauern gefördert, was zu 20 Teilen + 4 Türmen an Bord führte) erfordert 40 * 1 + 20 * 6 + 4 * 4 = 176 Positionsbits.

Es ist möglich, die Karte und alle Informationen (außer der 50-Bewegungsregel) in einfach zu handhabende 256 Bit zu integrieren. Ich würde folgendes vorschlagen. 64 Quadrate und 4 Bits pro Quadrat ermöglichen 16 mögliche Zustände. 0 würde das leere Quadrat darstellen. Dann haben wir 6 Stück, aber ich würde ein 7. Stück für den "bewegten Turm" reservieren, damit die Möglichkeit einer Rochade bestimmt werden kann. Ein Bit für Weiß oder Schwarz. Wir verwenden 15 Zustände und haben noch 1 weiteren Zustand: Wert 8 (1000 binär). Es stellt auch ein emotionales Quadrat dar, aber wir können dieses auf dem 3. oder 6. Rang verwenden, um anzuzeigen, dass der Bauer vor ihm 2 Felder verschoben hat und "en passant" gefangen genommen werden muss. Schließlich verwenden wir diesen Wert auch, um die zu bewegende Seite anzugeben. Finde das erste Empy-Quadrat in der unteren Hälfte des Bretts, um anzuzeigen, dass es weiß ist, um sich zu bewegen. In der oberen Hälfte für Schwarz.

Sie haben gefragt: Ein wirklich fehlendes Bit im FEN ist die Tatsache, dass es keine Informationen darüber enthält, ob die Position einem Schachmatt entspricht oder ob dies überprüft wird. Natürlich kann man die Position immer auf die Tafel setzen und sehen, ob es sich um ein Schachmatt handelt oder nicht, aber es ist nicht direkt aus der Notation ableitbar.

An dieser Stelle könnte es eine gute Frage sein, wenn man eine rechnerisch komplexe Information in eine Beschreibung einbetten möchte.

Dasselbe gilt für Bewegungsnotationen - zum Beispiel zwischen: algebraischer Notation (e2e4 b1c3) und SAN (e4 Nc3) - die letztere erfordert eine Engine, um die TO-Position jeder Bewegung zu berechnen, und ist rechnerisch komplex zu dekodieren, während die erstere Es ist nicht erforderlich, einen ganzen Bewegungsgenerator zu schreiben, um die abgeleitete TO-Position zu bestimmen - was von Vorteil sein kann.