Aktualisierung: Dieses Thema hat mir so gut gefallen, dass ich geschrieben habe Programmierpuzzles, Schachstellungen und Huffman-Kodierung . Wenn Sie dies durchlesen, habe ich festgestellt, dass die nur Der beste Weg, einen vollständigen Spielstand zu speichern, ist die Speicherung einer vollständigen Liste von Zügen. Lesen Sie weiter, um zu erfahren, warum. Ich verwende also eine leicht vereinfachte Version des Problems für das Figurenlayout.
Das Problem
Dieses Bild zeigt die Ausgangsstellung beim Schach. Schach findet auf einem 8x8 Brett statt, wobei jeder Spieler mit einem identischen Satz von 16 Figuren beginnt, bestehend aus 8 Bauern, 2 Türmen, 2 Springern, 2 Läufern, 1 Dame und 1 König, wie hier dargestellt:
![starting chess position]()
Die Stellungen werden in der Regel mit einem Buchstaben für die Spalte und einer Zahl für die Reihe angegeben, so dass die Dame von Weiß auf d1 steht. Züge werden am häufigsten gespeichert in algebraische Schreibweise die eindeutig ist und im Allgemeinen nur die minimal notwendigen Informationen enthält. Betrachten Sie diese Öffnung:
- e4 e5
- Nf3 Nc6
was übersetzt soviel heißt wie:
- Weiß zieht den Königsbauern von e2 nach e4 (er ist die einzige Figur, die nach e4 gelangen kann, daher "e4");
- Schwarz zieht den Königsbauern von e7 nach e5;
- Weiß zieht den Springer (N) nach f3;
- Schwarz zieht den Springer nach c6.
Die Tafel sieht wie folgt aus:
![early opening]()
Eine wichtige Fähigkeit für jeden Programmierer ist es, in der Lage zu sein das Problem korrekt und unmissverständlich zu beschreiben .
Was fehlt also oder ist unklar? Eine Menge, wie sich herausstellt.
Brettstatus vs. Spielstatus
Als Erstes müssen Sie festlegen, ob Sie den Zustand eines Spiels oder die Position der Figuren auf dem Brett speichern wollen. Einfach nur die Positionen der Figuren zu kodieren ist eine Sache, aber das Problem sagt "alle nachfolgenden legalen Züge". Das Problem sagt auch nichts darüber aus, ob man die Züge bis zu diesem Punkt kennt. Das ist tatsächlich ein Problem, wie ich noch erklären werde.
Rochade
Das Spiel ist wie folgt verlaufen:
- e4 e5
- Nf3 Nc6
- Bb5 a6
- Ba4 Bc5
Die Tafel sieht wie folgt aus:
![later opening]()
Weiß hat die Möglichkeit Rochade . Zu den Voraussetzungen dafür gehört, dass der König und der betreffende Turm nie gezogen haben dürfen, so dass gespeichert werden muss, ob der König oder einer der Türme jeder Seite gezogen hat. Wenn sie sich nicht auf ihren Ausgangspositionen befinden, haben sie sich offensichtlich bewegt, andernfalls muss dies angegeben werden.
Es gibt mehrere Strategien, die zur Lösung dieses Problems eingesetzt werden können.
Erstens könnten wir 6 zusätzliche Informationsbits speichern (1 für jeden Turm und König), um anzuzeigen, ob die Figur gezogen hat. Wir könnten dies vereinfachen, indem wir nur ein Bit für eines dieser sechs Felder speichern, wenn sich die richtige Figur auf diesem Feld befindet. Alternativ könnten wir jede unbewegte Figur als eine weitere Figurenart behandeln, so dass es statt der 6 Figurenarten auf jeder Seite (Bauer, Turm, Springer, Läufer, Dame und König) 8 gibt (wenn man den unbewegten Turm und den unbewegten König hinzurechnet).
En Passant
Eine weitere eigenartige und oft vernachlässigte Regel im Schach ist En Passant .
![en passant]()
Das Spiel hat sich weiterentwickelt.
- e4 e5
- Nf3 Nc6
- Bb5 a6
- Ba4 Bc5
- O-O b5
- Bb3 b4
- c4
Der schwarze Bauer auf b4 hat nun die Möglichkeit, seinen Bauern auf b4 nach c3 zu ziehen und den weißen Bauern auf c4 zu schlagen. Dies geschieht nur bei der ersten Gelegenheit, d.h. wenn Schwarz diese Möglichkeit jetzt auslässt, kann er sie im nächsten Zug nicht wahrnehmen. Wir müssen dies also speichern.
Wenn wir den vorherigen Zug kennen, können wir definitiv beantworten, ob En Passant möglich ist. Alternativ können wir speichern, ob jeder Bauer auf seinem 4. Rang gerade mit einem Doppelzug vorwärts gezogen ist. Oder wir können uns jede mögliche En-Passant-Stellung auf dem Brett ansehen und mit einer Flagge anzeigen, ob sie möglich ist oder nicht.
Förderung
![pawn promotion]()
Es ist der Zug von Weiß. Wenn Weiß seinen Bauern auf h7 nach h8 zieht, kann er zu jeder anderen Figur (aber nicht zum König) befördert werden. In 99% der Fälle wird der Bauer zur Dame umgewandelt, manchmal aber auch nicht, weil dies ein Patt erzwingen kann, wenn man sonst gewinnen würde. Dies wird geschrieben als:
- h8=Q
Das ist für unser Problem wichtig, denn es bedeutet, dass wir uns nicht darauf verlassen können, dass es auf jeder Seite eine feste Anzahl von Stücken gibt. Es ist durchaus möglich (aber sehr unwahrscheinlich), dass eine Seite am Ende 9 Damen, 10 Türme, 10 Läufer oder 10 Springer hat, wenn alle 8 Bauern befördert werden.
Pattsituation
Wenn Sie sich in einer Position befinden, aus der Sie nicht gewinnen können, ist Ihre beste Taktik, zu versuchen, eine Pattsituation . Die wahrscheinlichste Variante ist, dass Sie keinen legalen Zug machen können (normalerweise weil jeder Zug Ihren König ins Schach setzt). In diesem Fall können Sie ein Remis verlangen. Diese Variante ist leicht zu erreichen.
Die zweite Variante ist von dreifache Wiederholung . Wenn dieselbe Brettstellung in einer Partie dreimal vorkommt (oder im nächsten Zug ein drittes Mal vorkommen wird), kann ein Remis beansprucht werden. Die Stellungen müssen nicht in einer bestimmten Reihenfolge auftreten (d. h. es muss nicht dieselbe Zugfolge dreimal wiederholt werden). Dies verkompliziert das Problem erheblich, da man sich jede vorherige Brettstellung merken muss. Wenn dies eine Voraussetzung für das Problem ist, besteht die einzig mögliche Lösung darin, jeden vorherigen Zug zu speichern.
Schließlich gibt es noch die Fünfzig-Züge-Regel . Ein Spieler kann ein Unentschieden beanspruchen, wenn in den letzten fünfzig aufeinanderfolgenden Zügen kein Bauer gezogen und keine Figur geschlagen wurde; wir müssen also speichern, wie viele Züge seit dem Ziehen eines Bauern oder dem Schlagen einer Figur vergangen sind (der letzte der beiden Züge). Dies erfordert 6 Bits (0-63).
Wer ist dran?
Natürlich müssen wir auch wissen, wer an der Reihe ist, und das ist eine einzige Information.
Zwei Probleme
Wegen des Patt-Falles ist die einzige machbare oder sinnvolle Art, den Spielstand zu speichern, alle Züge zu speichern, die zu dieser Stellung geführt haben. Ich werde dieses eine Problem angehen. Das Problem des Brettzustandes wird vereinfacht dargestellt: die aktuelle Position aller Figuren auf dem Brett zu speichern, wobei Rochade, en passant, Pattbedingungen und die Frage, wer am Zug ist, ignoriert werden .
Die Anordnung der Spielsteine kann auf zwei Arten gehandhabt werden: durch Speicherung des Inhalts jedes Quadrats oder durch Speicherung der Position jedes Steins.
Einfache Inhalte
Es gibt sechs Figurenarten (Bauer, Turm, Springer, Läufer, Dame und König). Jede Figur kann weiß oder schwarz sein, so dass ein Feld eine von 12 möglichen Figuren enthalten kann oder leer sein kann, so dass es 13 Möglichkeiten gibt. 13 können in 4 Bits (0-15) gespeichert werden. Die einfachste Lösung ist also, 4 Bits für jedes Feld mal 64 Felder oder 256 Bits an Informationen zu speichern.
Der Vorteil dieser Methode ist, dass die Manipulation unglaublich einfach und schnell. Dies könnte sogar noch um 3 weitere Möglichkeiten erweitert werden, ohne den Speicherbedarf zu erhöhen: ein Bauer, der im letzten Zug 2 Felder gezogen hat, ein König, der sich nicht bewegt hat, und ein Turm, der sich nicht bewegt hat, was viele der zuvor erwähnten Probleme lösen wird.
Aber wir können es besser machen.
Base 13 Kodierung
Es ist oft hilfreich, sich die Position des Vorstands als eine sehr große Zahl vorzustellen. Das wird in der Informatik oft gemacht. Zum Beispiel kann die Halteproblem behandelt ein Computerprogramm (zu Recht) als eine große Zahl.
Bei der ersten Lösung wird die Position als 64-stellige Zahl zur Basis 16 behandelt, aber wie gezeigt, gibt es Redundanz in dieser Information (die 3 ungenutzten Möglichkeiten pro "Ziffer"), so dass wir den Zahlenraum auf 64 Ziffern zur Basis 13 reduzieren können. Natürlich ist dies nicht so effizient wie bei der Basis 16, aber es spart Speicherplatz (und die Minimierung des Speicherplatzes ist unser Ziel).
Zur Basis 10 ist die Zahl 234 gleich 2 x 10 2 + 3 x 10 1 + 4 x 10 0 .
Zur Basis 16 ist die Zahl 0xA50 gleich 10 x 16 2 + 5 x 16 1 + 0 x 16 0 \= 2640 (dezimal).
Wir können also unsere Position als p kodieren 0 x 13 63 + p 1 x 13 62 + ... + p 63 x 13 0 wobei p i steht für den Inhalt des Quadrats i .
2 256 entspricht etwa 1,16e77. 13 64 entspricht etwa 1,96e71, was 237 Bit Speicherplatz erfordert. Diese Einsparung von nur 7,5 % geht einher mit einem Preis von deutlich erhöhte Manipulationskosten.
Variable Grundkodierung
Bei legalen Brettern können bestimmte Figuren nicht auf bestimmten Feldern stehen. Zum Beispiel können Bauern nicht auf der ersten oder achten Reihe stehen, was die Möglichkeiten für diese Felder auf 11 reduziert. Damit reduziert sich die Zahl der möglichen Bretter auf 11 16 x 13 48 \= 1,35e70 (ungefähr), was 233 Bits an Speicherplatz erfordert.
Die eigentliche Kodierung und Dekodierung solcher Werte in und aus dem Dezimalsystem (oder Binärsystem) ist etwas komplizierter, kann aber zuverlässig durchgeführt werden und wird dem Leser als Übung überlassen.
Alphabete mit variabler Breite
Die beiden vorangegangenen Methoden können wie folgt beschrieben werden Alphabetische Kodierung mit fester Breite . Jedes der 11, 13 oder 16 Glieder des Alphabets wird durch einen anderen Wert ersetzt. Jedes "Zeichen" hat die gleiche Breite, aber die Effizienz kann verbessert werden, wenn man bedenkt, dass nicht jedes Zeichen gleich wahrscheinlich ist.
![morse code]()
Erwägen Sie Morsezeichen (oben abgebildet). Die Zeichen in einer Nachricht werden als eine Folge von Strichen und Punkten kodiert. Diese Striche und Punkte werden (in der Regel) über Funk mit einer Pause dazwischen übertragen, um sie voneinander abzugrenzen.
Beachten Sie, dass der Buchstabe E ( der häufigste Buchstabe im Englischen ) ist ein einzelner Punkt, die kürzest mögliche Sequenz, während Z (die am wenigsten häufige) aus zwei Strichen und zwei Pieptönen besteht.
Ein solches Schema kann die Größe einer Datenbank erheblich reduzieren. erwartet Nachricht, allerdings um den Preis, dass die Größe einer zufälligen Zeichenfolge zunimmt.
Es sei darauf hingewiesen, dass der Morsecode noch eine weitere Eigenschaft hat: Bindestriche sind so lang wie drei Punkte, so dass der obige Code unter Berücksichtigung dieser Tatsache erstellt wurde, um die Verwendung von Bindestrichen zu minimieren. Da 1en und 0en (unsere Bausteine) dieses Problem nicht haben, müssen wir diese Eigenschaft nicht nachbilden.
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 Pause (die Länge eines Bindestrichs) wird zur Abgrenzung von Zeichen verwendet.
Was bedeutet das nun für unser Problem?
Huffman-Kodierung
Es gibt einen Algorithmus für den Umgang mit Codes variabler Länge namens Huffman-Kodierung . Bei der Huffman-Kodierung wird ein Code mit variabler Länge erstellt, der in der Regel die erwartete Häufigkeit der Symbole verwendet, um den häufigeren Symbolen kürzere Werte zuzuweisen.
![Huffman code tree]()
Im obigen Baum ist der Buchstabe E als 000 (oder links-links-links) kodiert und S ist 1011. Es sollte klar sein, dass dieses Kodierungsschema unzweideutig .
Dies ist ein wichtiger Unterschied zum Morsealphabet. Beim Morsen gibt es den Zeichentrenner, so dass eine mehrdeutige Ersetzung möglich ist (z. B. können 4 Punkte ein H oder 2 Is sein), aber wir haben nur 1en und 0en, so dass wir stattdessen eine eindeutige Ersetzung wählen.
Nachfolgend finden Sie eine einfache Umsetzung:
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(), "");
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 Bits.
Staatliche Differenz
Ein weiterer möglicher Ansatz ist die Kombination des ersten Ansatzes mit der Huffman-Kodierung. Dies beruht auf der Annahme, dass die meisten erwarteten Schachbretter (und nicht die zufällig erzeugten) zumindest teilweise einer Ausgangsstellung ähneln.
Sie müssen also die aktuelle 256-Bit-Position der Karte mit einer 256-Bit-Startposition XOR-verknüpfen und diese dann kodieren (mit Huffman-Kodierung oder, sagen wir, einer Methode der Lauflängenkodierung ). Natürlich wird dies zu Beginn sehr effizient sein (64 0s entsprechen wahrscheinlich 64 Bits), aber der benötigte Speicherplatz wird mit dem Fortschreiten des Spiels zunehmen.
Stück Position
Wie bereits erwähnt, kann man dieses Problem auch dadurch lösen, dass man stattdessen die Stellung jeder Figur, die ein Spieler hat, speichert. Dies funktioniert besonders gut bei Endspielpositionen, bei denen die meisten Felder leer sind (aber bei der Huffman-Kodierung wird für leere Felder ohnehin nur 1 Bit verwendet).
Jede Seite hat einen König und 0-15 andere Figuren. Wegen der Beförderung kann die genaue Zusammensetzung dieser Figuren so stark variieren, dass man nicht davon ausgehen kann, dass die Zahlen, die auf den Startpositionen basieren, Maximalwerte sind.
Die logische Art und Weise, dies aufzuteilen, ist das Speichern einer Position, die aus zwei Seiten (Weiß und Schwarz) besteht. Jede Seite hat:
- Ein König: 6 Bits für den Standort;
- Hat Bauern: 1 (ja), 0 (nein);
- Wenn ja, Anzahl der Bauern: 3 Bits (0-7+1 = 1-8);
- Wenn ja, wird der Standort jedes Bauern verschlüsselt: 45 Bits (siehe unten);
- Anzahl der Nicht-Bauern: 4 Bits (0-15);
- Für jede Figur: Typ (2 Bits für Dame, Turm, Springer, Läufer) und Ort (6 Bits)
Was die Lage der Bauern betrifft, so können sie nur auf 48 möglichen Feldern stehen (nicht auf 64 wie bei den anderen). Daher ist es besser, die zusätzlichen 16 Werte nicht zu verschwenden, die bei Verwendung von 6 Bits pro Bauer benötigt würden. Wenn Sie also 8 Bauern haben, gibt es 48 8 Möglichkeiten, die 28.179.280.429.056 entsprechen. Man braucht 45 Bits, um so viele Werte zu kodieren.
Das sind 105 Bits pro Seite oder 210 Bits insgesamt. Die Ausgangsposition ist jedoch der ungünstigste Fall für diese Methode, und sie wird wesentlich besser, wenn Sie Teile entfernen.
Es ist darauf hinzuweisen, dass es weniger als 48 8 Möglichkeiten, weil die Bauern nicht alle auf demselben Feld stehen können. Der erste hat 48 Möglichkeiten, der zweite 47 und so weiter. 48 x 47 x x 41 = 1,52e13 = 44 Bits Speicherplatz.
Man kann dies weiter verbessern, indem man die Felder eliminiert, die von anderen Figuren besetzt sind (einschließlich der anderen Seite), so dass man zuerst die weißen Nicht-Bauern, dann die schwarzen Nicht-Bauern, dann die weißen Bauern und zuletzt die schwarzen Bauern aufstellen könnte. In der Ausgangsstellung reduziert sich der Speicherbedarf dadurch auf 44 Bits für Weiß und 42 Bits 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. Man könnte z. B. die besten 4 auswählen und dann einen Schema-Selektor in den ersten beiden Bits und danach die schema-spezifische Speicherung kodieren.
Bei einem so geringen Aufwand ist dies bei weitem der beste Ansatz.
Zustand des Spiels
Ich komme zurück auf das Problem der Speicherung einer Spiel und nicht eine Position . Wegen der dreifachen Wiederholung müssen wir die Liste der bis zu diesem Punkt erfolgten Züge speichern.
Anmerkungen
Eine Sache, die Sie bestimmen müssen, ist, ob Sie einfach eine Liste von Zügen speichern oder ob Sie die Partie kommentieren. Schachpartien werden zum Beispiel oft mit Anmerkungen versehen:
- Bb5! Nc4?
Der Zug von Weiß wird mit zwei Ausrufezeichen als brillant bezeichnet, während der von Schwarz als Fehler gewertet wird. Siehe Interpunktion im Schach .
Darüber hinaus müssen Sie möglicherweise auch freien Text speichern, wenn die Züge beschrieben werden.
Ich gehe davon aus, dass die Züge ausreichend sind, so dass es keine Anmerkungen geben wird.
Algebraische Notation
Wir könnten hier einfach den Text des Zuges speichern ("e4", "Bxb5", usw.). Einschließlich eines Abschlussbytes sind das im schlimmsten Fall etwa 6 Bytes (48 Bit) pro Zug. Das ist nicht besonders effizient.
Die zweite Möglichkeit ist, die Startposition (6 Bits) und die Endposition (6 Bits) zu speichern, also 12 Bits pro Zug. Das ist deutlich besser.
Alternativ dazu können wir alle legalen Züge von der aktuellen Position aus auf vorhersehbare und deterministische Weise bestimmen und angeben, welche wir gewählt haben. Dies führt zurück zu der oben erwähnten variablen Grundkodierung. Weiß und Schwarz haben in ihrem ersten Zug jeweils 20 mögliche Züge, im zweiten Zug mehr und so weiter.
Schlussfolgerung
Auf diese Frage gibt es keine absolut richtige Antwort. Es gibt viele mögliche Ansätze, von denen die oben genannten nur einige sind.
Was mir an diesem und ähnlichen Problemen gefällt, ist, dass es Fähigkeiten erfordert, die für jeden Programmierer wichtig sind, wie z. B. die Berücksichtigung des Nutzungsmusters, die genaue Bestimmung der Anforderungen und das Nachdenken über Eckfälle.
Schachstellungen als Bildschirmfotos aus Schachstellungstrainer .
