Pas strictement une question, plus un puzzle ...

Au fil des ans, j'ai participé à quelques entretiens techniques de nouveaux employés. En plus de poser les questions standard «connaissez-vous la technologie X», j'ai également essayé de comprendre comment ils abordent les problèmes. En règle générale, je leur enverrais la question par e-mail la veille de l'entretien et je m'attendais à ce qu'ils trouvent une solution le lendemain.

Souvent, les résultats seraient très intéressants - faux, mais intéressants - et la personne recevrait toujours ma recommandation si elle pouvait expliquer pourquoi elle a adopté une approche particulière.

J'ai donc pensé que je poserais une de mes questions au public de Stack Overflow.

Question: Quelle est la manière la plus économe en espace que vous puissiez imaginer pour encoder l'état d'une partie d'échecs (ou d'un sous-ensemble de celle-ci)? Autrement dit, étant donné un échiquier avec les pièces disposées légalement, encodez à la fois cet état initial et tous les mouvements légaux ultérieurs pris par les joueurs dans la partie.

Aucun code requis pour la réponse, juste une description de l'algorithme que vous utiliseriez.

EDIT: Comme l'une des affiches l'a souligné, je n'ai pas tenu compte de l'intervalle de temps entre les mouvements. N'hésitez pas à en tenir compte également en option :)

EDIT2: Juste pour une clarification supplémentaire ... N'oubliez pas que l'encodeur / décodeur est conscient des règles. Les seules choses qui doivent vraiment être stockées sont les choix du joueur - tout le reste peut être considéré comme connu par l'encodeur / décodeur.

EDIT3: Il va être difficile de choisir un gagnant ici :) Beaucoup de bonnes réponses!

Mise à jour: J'ai tellement aimé ce sujet que j'ai écrit des puzzles de programmation, des positions d'échecs et du codage Huffman . Si vous lisez ceci, j'ai déterminé que le seul façon de stocker un état de jeu complet est de stocker une liste complète des coups. Lisez la suite pour savoir pourquoi. J'utilise donc une version légèrement simplifiée du problème pour la disposition des pièces.

Le problème

Cette image illustre la position de départ des échecs. Les échecs se produisent sur un plateau 8x8 avec chaque joueur commençant par un ensemble identique de 16 pièces composé de 8 pions, 2 tours, 2 chevaliers, 2 évêques, 1 reine et 1 roi comme illustré ici:

Les positions sont généralement enregistrées sous la forme d'une lettre pour la colonne suivie du numéro de la ligne, de sorte que la reine des blancs est à d1. Les déplacements sont le plus souvent stockés en notation algébrique , qui est sans ambiguïté et ne spécifie généralement que les informations minimales nécessaires. Considérez cette ouverture:

1. e4 e5
2. Nf3 Nc6
3. …

ce qui se traduit par:

1. Les blancs déplacent le pion du roi de e2 à e4 (c'est la seule pièce qui peut atteindre e4 d'où «e4»);
2. Le noir déplace le pion du roi de e7 à e5;
3. Blanc déplace le chevalier (N) vers f3;
4. Le noir déplace le chevalier vers c6.
5. …

Le tableau ressemble à ceci:

Une capacité importante pour tout programmeur est de pouvoir spécifier correctement et sans ambiguïté le problème .

Alors, qu'est-ce qui manque ou est ambigu? Beaucoup comme il se trouve.

État du plateau vs état du jeu

La première chose que vous devez déterminer est de savoir si vous stockez l'état d'un jeu ou la position des pièces sur le plateau. Encoder simplement les positions des pièces est une chose mais le problème dit «tous les coups légaux ultérieurs». Le problème ne dit rien non plus sur la connaissance des mouvements jusqu'à ce point. C'est en fait un problème comme je vais l'expliquer.

Roque

Le jeu s'est déroulé comme suit:

1. e4 e5
2. Nf3 Nc6
3. Bb5 a6
4. Ba4 Bc5

Le tableau ressemble à ceci:

Le blanc a la possibilité de roquer . Une partie des exigences pour cela est que le roi et la tour concernée ne peuvent jamais avoir bougé, donc si le roi ou l'une des tours de chaque camp a bougé, il faudra stocker. Évidemment, s'ils ne sont pas sur leurs positions de départ, ils ont déménagé sinon il faut le préciser.

Il existe plusieurs stratégies qui peuvent être utilisées pour résoudre ce problème.

Premièrement, nous pourrions stocker 6 bits d'informations supplémentaires (1 pour chaque tour et roi) pour indiquer si cette pièce avait bougé. Nous pourrions rationaliser cela en ne stockant qu'un peu pour l'un de ces six carrés si la bonne pièce s'y trouve. Alternativement, nous pourrions traiter chaque pièce non déplacée comme un autre type de pièce, donc au lieu de 6 types de pièces de chaque côté (pion, tour, chevalier, évêque, reine et roi), il y en a 8 (en ajoutant la tour non déplacée et le roi immobile).

En passant

Une autre règle particulière et souvent négligée dans les échecs est En Passant .

Le jeu a progressé.

1. e4 e5
2. Nf3 Nc6
3. Bb5 a6
4. Ba4 Bc5
5. OO b5
6. Bb3 b4
7. c4

Le pion noir sur b4 a maintenant la possibilité de déplacer son pion sur b4 vers c3 en prenant le pion blanc sur c4. Cela ne se produit qu'à la première opportunité, ce qui signifie que si le noir passe l'option maintenant, il ne peut pas la prendre au prochain coup. Nous devons donc stocker cela.

Si nous connaissons le mouvement précédent, nous pouvons certainement répondre si En Passant est possible. Alternativement, nous pouvons stocker si chaque pion de son 4ème rang vient de s'y déplacer avec un double mouvement en avant. Ou nous pouvons regarder chaque position possible de En Passant sur le plateau et avoir un drapeau pour indiquer si c'est possible ou non.

Promotion

C'est le geste de White. Si Blanc déplace son pion de h7 à h8, il peut être promu à n'importe quelle autre pièce (mais pas le roi). 99% du temps, elle est promue reine, mais parfois ce n'est pas le cas, généralement parce que cela peut forcer une impasse alors que vous gagneriez autrement. Ceci s'écrit:

56. h8 = Q

C'est important dans notre problème car cela signifie que nous ne pouvons pas compter sur un nombre fixe de pièces de chaque côté. Il est tout à fait possible (mais incroyablement improbable) qu'un camp se retrouve avec 9 reines, 10 tours, 10 évêques ou 10 chevaliers si les 8 pions sont promus.

Impasse

Lorsque vous êtes dans une position à partir de laquelle vous ne pouvez pas gagner, votre meilleure tactique est d'essayer une impasse . La variante la plus probable est celle où vous ne pouvez pas effectuer de mouvement légal (généralement parce que tout mouvement met votre roi en échec). Dans ce cas, vous pouvez réclamer un tirage au sort. Celui-ci est facile à gérer.

La deuxième variante est par triple répétition . Si la même position sur le plateau se produit trois fois dans une partie (ou se produira une troisième fois au coup suivant), un match nul peut être réclamé. Les positions n'ont pas besoin de se produire dans un ordre particulier (ce qui signifie qu'il n'est pas nécessaire de suivre la même séquence de mouvements répétés trois fois). Celui-ci complique grandement le problème car vous devez vous souvenir de chaque position précédente au conseil d'administration. Si cela est une exigence du problème, la seule solution possible au problème est de stocker chaque mouvement précédent.

Enfin, il y a la règle des cinquante coups . Un joueur peut réclamer un tirage si aucun pion n'a bougé et qu'aucune pièce n'a été prise dans les cinquante mouvements consécutifs précédents, nous aurions donc besoin de stocker le nombre de mouvements depuis qu'un pion a été déplacé ou une pièce prise (le dernier des deux. Cela nécessite 6 bits (0 à 63).

A qui le tour?

Bien sûr, nous avons également besoin de savoir à qui appartient le tour et ceci est une simple information.

Deux problèmes

En raison du cas d'impasse, la seule façon faisable ou raisonnable de stocker l'état du jeu est de stocker tous les mouvements qui ont conduit à cette position. Je vais m'attaquer à ce problème. Le problème de l'état du plateau sera simplifié à ceci: stocker la position actuelle de toutes les pièces sur le plateau en ignorant les conditions de roque, en passant, d'impasse et à qui appartient le tour .

La disposition des pièces peut être gérée globalement de deux manières: en stockant le contenu de chaque carré ou en stockant la position de chaque pièce.

Contenu simple

Il existe six types de pièces (pion, tour, chevalier, évêque, reine et roi). Chaque pièce peut être blanche ou noire donc un carré peut contenir l'une des 12 pièces possibles ou il peut être vide donc il y a 13 possibilités. 13 peut être stocké en 4 bits (0-15) La solution la plus simple est donc de stocker 4 bits pour chaque carré multiplié par 64 carrés ou 256 bits d'information.

L'avantage de cette méthode est que la manipulation est incroyablement simple et rapide. Cela pourrait même être prolongé en ajoutant 3 possibilités supplémentaires sans augmenter les exigences de stockage: un pion qui a bougé de 2 cases au dernier tour, un roi qui n'a pas bougé et une tour qui n'a pas bougé, ce qui en fera beaucoup. des problèmes mentionnés précédemment.

Mais nous pouvons faire mieux.

Encodage Base 13

Il est souvent utile de considérer la position du conseil comme un très grand nombre. Cela se fait souvent en informatique. Par exemple, le problème d'arrêt traite (à juste titre) un programme informatique comme un grand nombre.

La première solution traite la position comme un nombre à 64 chiffres en base 16 mais comme démontré il y a une redondance dans cette information (étant les 3 possibilités inutilisées par «chiffre») afin que nous puissions réduire l'espace numérique à 64 base 13 chiffres. Bien sûr, cela ne peut pas être fait aussi efficacement que la base 16, mais cela permettra d'économiser sur les besoins de stockage (et minimiser l'espace de stockage est notre objectif).

En base 10, le nombre 234 équivaut à 2 x 10 ² + 3 x 10 ¹ + 4 x 10 ⁰ .

En base 16, le nombre 0xA50 équivaut à 10 x 16 ² + 5 x 16 ¹ + 0 x 16 ⁰ = 2640 (décimal).

Nous pouvons donc encoder notre position comme p ₀ x 13 ⁶³ + p ₁ x 13 ⁶² + ... + p ₆₃ x 13 ⁰ où p _i représente le contenu du carré i .

2 ²⁵⁶ équivaut à environ 1,16e77. 13 ⁶⁴ équivaut à environ 1,96e71, ce qui nécessite 237 bits d'espace de stockage. Cette économie de seulement 7,5% entraîne une augmentation significative des coûts de manipulation.

Encodage de base variable

Dans les planches légales, certaines pièces ne peuvent pas apparaître dans certaines cases. Par exemple, les pions ne peuvent pas apparaître au premier ou au huitième rang, réduisant les possibilités pour ces carrés à 11. Cela réduit les planches possibles à 11 ¹⁶ x 13 ⁴⁸ = 1,35e70 (environ), ce qui nécessite 233 bits d'espace de stockage.

En fait, le codage et le décodage de telles valeurs vers et à partir de décimal (ou binaire) est un peu plus compliqué, mais cela peut être fait de manière fiable et est laissé comme un exercice au lecteur.

Alphabets à largeur variable

Les deux méthodes précédentes peuvent toutes deux être décrites comme un codage alphabétique à largeur fixe . Chacun des 11, 13 ou 16 membres de l'alphabet est remplacé par une autre valeur. Chaque «caractère» a la même largeur, mais l'efficacité peut être améliorée si l'on considère que chaque caractère n'est pas également probable.

Considérez le code Morse (photo ci-dessus). Les caractères d'un message sont codés sous la forme d'une séquence de tirets et de points. Ces tirets et points sont transférés par radio (généralement) avec une pause entre eux pour les délimiter.

Remarquez que la lettre E (la lettre la plus courante en anglais ) est un seul point, la séquence la plus courte possible, tandis que Z (la moins fréquente) est composée de deux tirets et de deux bips.

Un tel schéma peut réduire considérablement la taille d'un message attendu mais se fait au prix de l'augmentation de la taille d'une séquence de caractères aléatoires.

Il convient de noter que le code Morse a une autre fonctionnalité intégrée: les tirets sont aussi longs que trois points, donc le code ci-dessus est créé dans cet esprit pour minimiser l'utilisation des tirets. Puisque les 1 et les 0 (nos blocs de construction) n'ont pas ce problème, ce n'est pas une fonctionnalité que nous devons répliquer.

Enfin, il existe deux types de repos en code Morse. Un court repos (la longueur d'un point) est utilisé pour distinguer les points et les tirets. Un espace plus long (la longueur d'un tiret) est utilisé pour délimiter les caractères.

Alors, comment cela s'applique-t-il à notre problème?

Codage Huffman

Il existe un algorithme pour traiter les codes de longueur variable appelé codage Huffman . Le codage Huffman crée une substitution de code de longueur variable, utilise généralement la fréquence attendue des symboles pour attribuer des valeurs plus courtes aux symboles les plus courants.

Dans l'arborescence ci-dessus, la lettre E est codée comme 000 (ou gauche-gauche-gauche) et S est 1011. Il doit être clair que ce schéma de codage est sans ambiguïté .

C'est une distinction importante avec le code Morse. Le code Morse a le séparateur de caractères, donc il peut faire une substitution ambiguë (par exemple, 4 points peuvent être H ou 2 Is) mais nous n'avons que des 1 et des 0 donc nous choisissons une substitution non ambiguë à la place.

Voici une implémentation simple:

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; }
}

avec des données statiques:

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);
}

et:

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);
    }
  }
}

Une sortie possible est:

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

Pour une position de départ, cela équivaut à 32 x 1 + 16 x 3 + 12 x 5 + 4 x 6 = 164 bits.

Différence d'état

Une autre approche possible consiste à combiner la toute première approche avec le codage Huffman. Ceci est basé sur l'hypothèse que la plupart des échiquiers attendus (plutôt que ceux générés aléatoirement) sont plus susceptibles qu'improbables, au moins en partie, de ressembler à une position de départ.

Donc, ce que vous faites est XOR la ​​position actuelle de la carte de 256 bits avec une position de départ de 256 bits, puis encodez cela (en utilisant le codage Huffman ou, par exemple, une méthode de codage de longueur d'exécution ). Evidemment cela sera très efficace au départ (64 0s correspondant probablement à 64 bits) mais augmentera le stockage requis au fur et à mesure que le jeu progresse.

Position de la pièce

Comme mentionné, une autre manière d'attaquer ce problème est de stocker à la place la position de chaque pièce d'un joueur. Cela fonctionne particulièrement bien avec les positions de fin de partie où la plupart des carrés seront vides (mais dans l'approche de codage de Huffman, les carrés vides n'utilisent de toute façon que 1 bit).

Chaque camp aura un roi et 0 à 15 autres pièces. En raison de la promotion, la composition exacte de ces pièces peut varier suffisamment pour que vous ne puissiez pas supposer que les chiffres basés sur les positions de départ sont des maxima.

La manière logique de diviser ceci est de stocker une position composée de deux côtés (blanc et noir). Chaque côté a:

• Un roi: 6 bits pour l'emplacement;
• A des pions: 1 (oui), 0 (non);
• Si oui, nombre de pions: 3 bits (0-7 + 1 = 1-8);
• Si oui, l'emplacement de chaque pion est codé: 45 bits (voir ci-dessous);
• Nombre de non-pions: 4 bits (0-15);
• Pour chaque pièce: type (2 bits pour reine, tour, chevalier, évêque) et emplacement (6 bits)

Quant à l'emplacement des pions, les pions ne peuvent être que sur 48 cases possibles (pas 64 comme les autres). En tant que tel, il vaut mieux ne pas gaspiller les 16 valeurs supplémentaires que l'utilisation de 6 bits par pion utiliserait. Donc, si vous avez 8 pions, il y a 48 ⁸ possibilités, soit 28 179 280 429 056. Vous avez besoin de 45 bits pour encoder autant de valeurs.

Cela représente 105 bits par côté ou 210 bits au total. La position de départ est cependant le pire des cas pour cette méthode et elle s'améliorera considérablement à mesure que vous retirerez des pièces.

Il faut préciser qu'il y a moins de 48 ⁸ possibilités car les pions ne peuvent pas tous être dans la même case Le premier a 48 possibilités, le second 47 et ainsi de suite. 48 x 47 x… x 41 = 1,52e13 = stockage de 44 bits.

Vous pouvez encore améliorer cela en éliminant les cases qui sont occupées par d'autres pièces (y compris l'autre côté) afin que vous puissiez d'abord placer les non-pions blancs puis les non-pions noirs, puis les pions blancs et enfin les pions noirs. En position de départ, cela réduit les besoins de stockage à 44 bits pour le blanc et à 42 bits pour le noir.

Approches combinées

Une autre optimisation possible est que chacune de ces approches a ses forces et ses faiblesses. Vous pouvez, par exemple, choisir les 4 meilleurs, puis encoder un sélecteur de schéma dans les deux premiers bits, puis le stockage spécifique au schéma après cela.

Avec des frais généraux aussi faibles, ce sera de loin la meilleure approche.

État du jeu

Je reviens sur le problème du stockage d'un jeu plutôt que d'une position . En raison de la triple répétition, nous devons stocker la liste des mouvements qui se sont produits jusqu'à présent.

Annotations

Une chose que vous devez déterminer est de stocker simplement une liste de coups ou d'annoter le jeu? Les parties d'échecs sont souvent annotées, par exemple:

17. Bb5 !! Nc4?

Le coup de White est marqué par deux points d'exclamation comme brillant alors que celui de Black est considéré comme une erreur. Voir Ponctuation des échecs .

De plus, vous pourriez également avoir besoin de stocker du texte libre au fur et à mesure que les mouvements sont décrits.

Je suppose que les mouvements sont suffisants, il n'y aura donc pas d'annotations.

Notation algébrique

Nous pourrions simplement stocker le texte du mouvement ici («e4», «Bxb5», etc.). Y compris un octet de fin, vous regardez environ 6 octets (48 bits) par déplacement (pire des cas). Ce n'est pas particulièrement efficace.

La deuxième chose à essayer est de stocker l'emplacement de départ (6 bits) et l'emplacement de fin (6 bits) donc 12 bits par déplacement. C'est nettement mieux.

Alternativement, nous pouvons déterminer tous les mouvements légaux à partir de la position actuelle d'une manière prévisible et déterministe et l'état que nous avons choisi. Cela revient ensuite au codage de base variable mentionné ci-dessus. Les Blancs et les Noirs ont 20 coups possibles chacun sur leur premier coup, plus sur le second et ainsi de suite.

Conclusion

Il n'y a pas de réponse absolument correcte à cette question. Il existe de nombreuses approches possibles dont celles ci-dessus ne sont que quelques-unes.

Ce que j'aime dans ce problème et dans des problèmes similaires, c'est qu'il exige des capacités importantes pour tout programmeur, telles que la prise en compte du modèle d'utilisation, la détermination précise des exigences et la réflexion sur les cas secondaires.

Positions d'échecs prises comme captures d'écran de Chess Position Trainer .

Il est préférable de stocker les parties d'échecs dans un format standard lisible par l'homme.

La notation de jeu portable suppose une position de départ standard (bien que ce ne soit pas obligatoire ) et répertorie simplement les mouvements, tour par tour. Un format standard compact et lisible par l'homme.

Par exemple

[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

Si vous voulez le réduire, il vous suffit de le compresser . Travail accompli!

Grand puzzle!

Je vois que la plupart des gens mémorisent la position de chaque pièce. Que diriez-vous d'adopter une approche plus simple et de stocker le contenu de chaque carré ? Cela prend en charge la promotion et les pièces capturées automatiquement.

Et cela permet l' encodage Huffman . En fait, la fréquence initiale des pièces sur le plateau est presque parfaite pour cela: la moitié des cases sont vides, la moitié des cases restantes sont des pions, etc.

Compte tenu de la fréquence de chaque pièce, j'ai construit un arbre de Huffman sur papier, que je ne répéterai pas ici. Le résultat, où creprésente la couleur (blanc = 0, noir = 1):

• 0 pour les carrés vides
• 1c0 pour pion
• 1c100 pour tour
• 1c101 pour chevalier
• 1c110 pour l'évêque
• 1c1110 pour la reine
• 1c1111 pour le roi

Pour l'ensemble du conseil dans sa situation initiale, nous avons

• carrés vides: 32 * 1 bit = 32 bits
• pions: 16 * 3 bits = 48 bits
• tours / chevaliers / évêques: 12 * 5 bits = 60 bits
• reines / rois: 4 * 6 bits = 24 bits

Total: 164 bits pour l' état initial de la carte. Significativement moins que les 235 bits de la réponse actuellement la plus votée. Et cela ne fera que diminuer au fur et à mesure que le jeu progressera (sauf après une promotion).

Je n'ai regardé que la position des pièces sur le plateau; les états supplémentaires (dont le tour, qui a roque, en passant, répéter les coups, etc.) devront être codés séparément. Peut-être encore 16 bits au plus, donc 180 bits pour tout l'état du jeu. Optimisations possibles:

• Laisser de côté les pièces les moins fréquentes et stocker leur position séparément. Mais cela n'aidera pas ... le remplacement du roi et de la reine par un carré vide économise 5 bits, qui sont exactement les 5 bits dont vous avez besoin pour coder leur position d'une autre manière.
• "Aucun pion sur la rangée arrière" pourrait facilement être encodé en utilisant une table de Huffman différente pour les rangées arrière, mais je doute que cela aide beaucoup. Vous vous retrouveriez probablement toujours avec le même arbre Huffman.
• «Un évêque blanc, un évêque noir» peut être encodé en introduisant des symboles supplémentaires qui n'ont pas le cbit, qui peuvent ensuite être déduits de la case sur laquelle se trouve l'évêque. (Les pions promus évêques perturbent ce schéma ...)
• Les répétitions de carrés vides pourraient être codées en longueur d'exécution en introduisant des symboles supplémentaires pour, par exemple, «2 carrés vides dans une ligne» et «4 carrés vides dans une ligne». Mais il n'est pas si facile d'estimer la fréquence de ceux-ci, et si vous vous trompez, cela fera mal plutôt que d'aider.

La très grande approche de table de consultation

Position - 18 octets
Le nombre estimé de positions légales est de 10 ⁴³
Il suffit de les énumérer toutes et la position peut être stockée en seulement 143 bits. 1 bit supplémentaire est nécessaire pour indiquer le côté à jouer ensuite

L'énumération n'est bien sûr pas pratique, mais cela montre qu'au moins 144 bits sont nécessaires.

Se déplace - 1 octet
Il y a généralement environ 30 à 40 coups légaux pour chaque position, mais le nombre peut être aussi élevé que 218 Permet d'énumérer tous les mouvements légaux pour chaque position. Maintenant, chaque mouvement peut être encodé en un octet.

Nous avons encore beaucoup de place pour des mouvements spéciaux tels que 0xFF pour représenter la démission.

Cela ajouterait de l'intérêt d'optimiser la taille moyenne des cas pour les jeux typiques joués par des humains, au lieu du pire des cas. (L'énoncé du problème ne dit pas lequel; la plupart des réponses supposent le pire des cas.)

Pour la séquence de mouvements, demandez à un bon moteur d'échecs de générer des mouvements à partir de chaque position; il produira une liste de k coups possibles, classés en fonction de leur classement de leur qualité. Les gens choisissent généralement les bons coups plus souvent que les mouvements aléatoires, nous devons donc apprendre une cartographie de chaque position de la liste à la probabilité que les gens choisissent un mouvement qui est «bon». En utilisant ces probabilités (basées sur un corpus de jeux d'une base de données d'échecs Internet), encodez les coups avec un codage arithmétique . (Le décodeur doit utiliser le même moteur d'échecs et la même cartographie.)

Pour la position de départ, l'approche de ralu fonctionnerait. Nous pourrions l'affiner avec un codage arithmétique là aussi, si nous avions un moyen de pondérer les choix par probabilité - par exemple, les pièces apparaissent souvent dans des configurations se défendant les unes les autres, et non au hasard. Il est plus difficile de voir un moyen facile d'incorporer ces connaissances. Une idée: utilisez plutôt le codage de mouvement ci-dessus, en partant de la position d'ouverture standard et en trouvant une séquence qui se termine dans la carte souhaitée. (Vous pouvez essayer une recherche A * avec une distance heuristique égale à la somme des distances des pièces par rapport à leurs positions finales, ou quelque chose du genre.) Cela écarte une certaine inefficacité due à une sur-spécification de la séquence de mouvements par rapport à l'efficacité du fait de profiter du jeu d'échecs. connaissance.

Il est également un peu difficile d'estimer les économies que cela vous apporterait en complexité moyenne, sans recueillir des statistiques à partir d'un corpus réel. Mais le point de départ avec tous les mouvements également probables, je pense, battrait déjà la plupart des propositions ici: le codage arithmétique n'a pas besoin d'un nombre entier de bits par mouvement.

Attaquer un sous-problème de codage des étapes après qu'une position initiale a été codée. L'approche consiste à créer une «liste chaînée» d'étapes.

Chaque étape du jeu est codée comme la paire «ancienne position -> nouvelle position». Vous connaissez la position initiale au début de la partie d'échecs; en parcourant la liste chaînée d'étapes, vous pouvez accéder à l'état après le déplacement de X.

Pour encoder chaque étape, vous avez besoin de 64 valeurs pour encoder la position de départ (6 bits pour 64 carrés sur la carte - 8x8 carrés) et 6 bits pour la position finale. 16 bits pour 1 mouvement de chaque côté.

La quantité d'espace que l'encodage d'un jeu donné prendrait est alors proportionnelle au nombre de coups:

10 x (nombre de coups blancs + nombre de coups noirs) bits.

MISE À JOUR: complication potentielle avec les pions promus. Besoin de pouvoir indiquer à quoi le pion est promu - peut avoir besoin de bits spéciaux (utiliserait un code gris pour économiser de l'espace, car la promotion de pion est extrêmement rare).

MISE À JOUR 2: Vous n'avez pas à encoder les coordonnées complètes de la position finale. Dans la plupart des cas, la pièce qui est déplacée ne peut pas se déplacer à plus de X endroits. Par exemple, un pion peut avoir un maximum de 3 options de déplacement à un moment donné. En réalisant ce nombre maximum de coups pour chaque type de pièce, nous pouvons enregistrer des bits sur le codage de la "destination".

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

Ainsi, la complexité spatiale par mouvement de noir ou de blanc devient

6 bits pour la position initiale + (nombre variable de bits en fonction du type de l'objet déplacé).

J'ai vu cette question la nuit dernière et cela m'a intrigué alors je me suis assis dans mon lit en pensant à des solutions. Ma réponse finale est en fait assez similaire à celle d'int3.

Solution basique

En supposant une partie d'échecs standard et que vous n'encodez pas les règles (comme le blanc passe toujours en premier), alors vous pouvez économiser beaucoup en encodant uniquement les mouvements que chaque pièce fait.

Il y a 32 pièces au total, mais à chaque mouvement, vous savez quelle couleur se déplace, il n'y a donc que 16 carrés à s'inquiéter, soit 4 bits pour lesquels la pièce se déplace ce tour-ci.

Chaque pièce n'a qu'un moveet limité, que vous énuméreriez d'une manière ou d'une autre.

• Pion: 4 options, 2 bits (1 pas en avant, 2 pas en avant, 1 de chaque diagonale)
• Tour: 14 options, 4 bits (maximum de 7 dans chaque direction)
• Bishop: 13 options, 4 bits (si vous en avez 7 dans une diagonale, vous n'en avez que 6 dans l'autre)
• Chevalier: 8 options, 3 bits
• Reine: 27 options, 5 bits (Rook + Bishop)
• Roi: 9 options, 4 bits (8 mouvements en une étape, plus l'option de roque)

Pour la promotion, vous avez le choix entre 4 pièces (tour, évêque, chevalier, reine), donc nous ajouterions 2 bits pour le spécifier. Je pense que toutes les autres règles sont couvertes automatiquement (par exemple en passant).

Optimisations supplémentaires

Tout d'abord, une fois que 8 morceaux d'une couleur ont été capturés, vous pouvez réduire le codage des morceaux à 3 bits, puis 2 bits pour 4 morceaux et ainsi de suite.

L'optimisation principale est cependant de n'énumérer que les mouvements possibles à chaque point du jeu. Supposons que nous stockions les mouvements d'un pion comme {00, 01, 10, 11}pour 1 pas en avant, 2 pas en avant, respectivement en diagonale à gauche et en diagonale à droite. Si certains mouvements ne sont pas possibles, nous pouvons les supprimer de l'encodage pour ce tour.

Nous connaissons l'état du jeu à chaque étape (en suivant tous les mouvements), donc après avoir lu quelle pièce va bouger, nous pouvons toujours déterminer combien de bits nous devons lire. Si nous réalisons que les seuls mouvements d'un pion à ce stade sont la capture en diagonale à droite ou en avancer d'un, nous savons qu'il ne faut lire qu'un bit.

En bref, le stockage de bits indiqué ci-dessus pour chaque pièce n'est qu'un maximum . Presque chaque mouvement aura moins d'options et souvent moins de bits.

À chaque position, obtenez le nombre de tous les coups possibles.

le coup suivant est généré comme

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

la meilleure efficacité d'espace prouvée pour stocker le jeu généré aléatoirement et a besoin d'environ 5 bits / coup en moyenne puisque vous avez 30 à 40 coups possibles. L'assemblage du stockage génère simplement n dans l'ordre inverse.

La position de stockage est plus difficile à craquer, en raison d'une grande redondance. (Il peut y avoir jusqu'à 9 reines à bord pour un site, mais dans ce cas, il n'y a pas de pions, et les évêques si sur le plateau sont sur des carrés de couleurs opposées) mais c'est généralement comme stocker une combinaison des mêmes pièces sur les carrés restants.)

ÉDITER:

Le point dans la sauvegarde des mouvements est de stocker uniquement l'index du mouvement. Au lieu de stocker Kc1-c2 et d'essayer de réduire cette information, nous devrions ajouter uniquement l'index du mouvement généré à partir du générateur de mouvement déterministe (position)

A chaque mouvement nous ajoutons des informations de taille

num_of_moves = get_number_of_possible_moves(postion) ;

en piscine et ce nombre ne peut être réduit

générer un pool d'informations est

n=n*num_of_moves+ index_current_move

supplémentaire

S'il n'y a qu'un seul coup disponible en position finale, enregistrez le nombre de mouvements forcés déjà effectués. Exemple: si la position de départ a 1 coups forcés pour chaque côté (2 coups) et que nous voulons enregistrer cela comme un jeu de coups, stockez 1 dans le pool n.

exemple de stockage dans le pool d'informations

Supposons que nous ayons des positions de départ connues et que nous effectuions 3 coups.

Au premier coup, il y a 5 coups disponibles, et nous prenons l'indice de mouvement 4. Dans le second coup, il y a 6 coups disponibles et nous prenons l'indice de position 3 et au 3ème coup il y a 7 coups disponibles pour ce côté et il a choisi de choisir l'indice de mouvement 2.

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

Nous encodons cette information à l'envers, donc n = 4 + 5 * (3 + 6 * (2)) = 79 (aucune multiplication par 7 n'est nécessaire)

Comment déverrouiller ça? Nous avons d'abord la position et nous découvrons qu'il y a 5 coups disponibles. Alors

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

Nous prenons l'indice de mouvement 4 et examinons à nouveau la position et à partir de ce point, nous découvrons qu'il y a 6 mouvements possibles.

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

Et nous prenons l'indice de mouvement 3 qui nous amène à une position avec 7 mouvements possibles.

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

Nous faisons le dernier mouvement de l'indice 2 et nous atteignons la position finale.

Comme vous pouvez le voir, la complexité temporelle est O (n) et la complexité spatiale est O (n). Edit: la complexité temporelle est en fait O (n ^ 2) car le nombre que vous multipliez par augmente, mais il ne devrait y avoir aucun problème pour stocker des parties jusqu'à 10 000 coups.

position de sauvegarde

Peut être fait près de l'optimum.

Lorsque nous découvrons des informations et que nous les stockons, laissez-moi en parler davantage. L'idée générale est de diminuer la redondance (j'en parlerai plus tard). Supposons qu'il n'y ait eu aucune promotion et aucune prise, donc il y a 8 pions, 2 tours, 2 chevaliers, 2 évêques, 1 roi et 1 reine par côté.

Que devons-nous sauvegarder: 1. position de chaque paix 2. posibilités de roque 3. possibilités d'en-passant 4. côté qui a bougé disponible

Supposons que chaque pièce puisse se tenir n'importe où mais pas 2 pièces au même endroit. Le nombre de façons dont 8 pions de même couleur peuvent être disposés à bord est C (64/8) (binôme) qui est de 32 bits, puis 2 tours 2R-> C (56/2), 2B -> C (54/2) , 2N-> C (52/2), 1Q-> C (50/1), 1K -> C (49/1) et même pour un autre site mais en commençant par 8P -> C (48/8) et ainsi de suite .

En multipliant cela pour les deux sites, nous obtenons le numéro 4634726695587809641192045982323285670400000 qui est d'environ 142 bits, nous devons ajouter 8 pour un possible en-passant (le pion en-passant peut être dans l'un des 8 endroits), 16 (4 bits) pour les limitations de roque et un peu pour le site qui a déménagé. On se retrouve avec 142 + 3 + 4 + 1 = 150bits

Mais maintenant, partons à la recherche de la redondance sur le plateau avec 32 pièces et sans prise.

1. les pions noirs et blancs sont sur la même colonne et se font face. Chaque pion fait face à un autre pion, ce qui signifie que le pion blanc peut être au plus au 6e rang. Cela nous apporte 8 * C (6/2) au lieu de C (64/8) * C (48/8) qui diminue l'information de 56 bits.

2. la possibilité de roque est également redondante. Si les tours ne sont pas au point de départ, il n'y a aucune possibilité de roque avec cette tour. Nous pouvons donc imaginer ajouter 4 carrés à bord pour obtenir les informations supplémentaires si le roque avec cette tour est possible et supprimer 4 bits de roque. Donc au lieu de C (56/2) * C (40/2) * 16, nous avons C (58/2) * C (42/2) et nous avons perdu 3,76 bits (presque tous de 4 bits)

3. en-passant: Lorsque nous stockons l'une des 8 possibilités en passant, nous connaissons la position du pion noir et réduisons la redondance informationnelle (s'il s'agit d'un mouvement blanc et qu'il a un 3ème pion en passant, cela signifie que le pion noir est sur c5 et le pion blanc est soit c2, c3 ou c4) donc insted de C (6/2) nous avons 3 et nous avons perdu 2,3 ​​bits. Nous diminuons une certaine redondance si nous stockons le numéro en passant aussi du côté duquel peut être fait (3 possibilités-> gauche, droite, les deux) et nous connaissons la possibilité de pion qui peut prendre en passant. (par exemple de l'exemple précédent en passant whit noir sur c5 ce qui peut être à gauche, à droite ou les deux. s'il est sur un site, nous avons 2 * 3 (3 pour stocker les psissibilites et 2 coups possibles pour le pion noir au 7ème ou 6ème rang ) insted de C (6/2) et nous réduisons de 1,3 bits et si des deux côtés nous réduisons de 4,2 bits, nous pouvons ainsi réduire de 2,3 + 1,3 = 3.

4. évêques: les bisops ne peuvent être que sur des carrés opposés, ce qui réduit la redondance de 1 bit pour chaque site.

Si nous résumons, nous avons besoin de 150-56-4-3,6-2 = 85 bits pour stocker la position d'échecs s'il n'y avait pas de prise

Et probablement pas beaucoup plus s'il y a des recettes et des promotions prises en compte (mais j'écrirai à ce sujet plus tard si quelqu'un trouvera ce long article utile)

La plupart des gens ont encodé l'état de la carte, mais en ce qui concerne les mouvements eux-mêmes.

Bits par pièce:

• ID de pièce: 4 bits maximum pour identifier les 16 pièces par côté. Le blanc / noir peut être déduit. Faites définir une commande sur les pièces. Lorsque le nombre de pièces tombe en dessous des puissances respectives de deux, utilisez moins de bits pour décrire les pièces restantes.
• Pion: 3 possibilités sur le premier coup, donc +2 bits (avancer d'un ou deux carrés, en passant.) Les coups suivants ne permettent pas d'avancer de deux, donc +1 bit suffit. La promotion peut être déduite dans le processus de décodage en notant quand le pion a atteint le dernier rang. Si le pion est connu pour être promu, le décodeur attendra 2 bits supplémentaires indiquant à laquelle des 4 pièces principales il a été promu.
• Bishop: +1 bit pour la diagonale utilisée, jusqu'à +4 bits pour la distance le long de la diagonale (16 possibilités). Le décodeur peut déduire la distance maximale possible à laquelle la pièce peut se déplacer le long de cette diagonale, donc s'il s'agit d'une diagonale plus courte, utilisez moins de bits.
• Chevalier: 8 coups possibles, +3 bits
• Tour: +1 bit pour horizontal / vertical, +4 bits pour la distance le long de la ligne.
• Roi: 8 coups possibles, +3 bits. Indiquez le roque avec un mouvement «impossible» - puisque le roque n'est possible que lorsque le roi est au premier rang, encodez ce mouvement avec une instruction pour déplacer le roi «en arrière» - c'est-à-dire hors du plateau.
• Reine: 8 directions possibles, + 3 bits. Jusqu'à +4 bits de plus pour la distance le long de la ligne / diagonale (moins si la diagonale est plus courte, comme dans le cas de l'évêque)

En supposant que toutes les pièces sont sur le plateau, ce sont les bits par coup: Pion - 6 bits au premier coup, 5 par la suite. 7 si promu. Évêque: 9 bits (max), Chevalier: 7, Tour: 9, Roi: 7, Reine: 11 (max).

Le problème est-il de donner un encodage qui soit le plus efficace pour les parties d'échecs typiques, ou celui qui a le pire encodage le plus court?

Pour ce dernier, le moyen le plus efficace est aussi le plus opaque: créer une énumération de toutes les paires possibles (plateau initial, séquence légale de coups), ce qui, avec le tirage-sur-trois fois-répété-position et pas-plus-que -fifty-moves depuis les règles du dernier pion-mouvement-ou-capture, est récursif. Ensuite, l'indice d'une position dans cette séquence finie donne le codage le plus court dans le pire des cas, mais aussi un codage tout aussi long pour les cas typiques, et est, je suppose, très coûteux à calculer. La partie d'échecs la plus longue possible est censée compter plus de 5000 coups, avec en général 20 à 30 coups disponibles dans chaque position pour chaque joueur (mais moins lorsqu'il reste peu de pièces) - cela donne quelque chose comme 40000 bits nécessaires pour cet encodage.

L'idée d'énumération peut être appliquée pour donner une solution plus traitable, comme décrit dans la suggestion de Henk Holterman pour l'encodage des mouvements ci-dessus. Ma suggestion: pas minime, mais plus courte que les exemples ci-dessus que j'ai examinés, et raisonnablement traitable:

1. 64 bits pour représenter les carrés occupés (matrice d'occupation), plus la liste des pièces dans chaque carré occupé (peut avoir 3 bits pour les pions et 4 bits pour les autres pièces): cela donne 190 bits pour la position de départ. Puisqu'il ne peut pas y avoir plus de 32 pièces à bord, le codage de la matrice d'occupation est redondant et donc quelque chose comme des positions de carte communes peut être codé, par exemple sous la forme de 33 bits définis plus l'indice de la carte à partir de la liste des cartes communes.

2. 1 bit pour dire qui fait le premier pas

3. Le code se déplace selon la suggestion de Henk: généralement 10 bits par paire de mouvement blanc / noir, bien que certains mouvements prennent 0 bits, lorsqu'un joueur n'a pas de mouvements alternatifs.

Cela suggère 490 bits pour coder un jeu typique de 30 coups, et serait une représentation raisonnablement efficace pour les jeux typiques.

A propos de l'encodage des règles de tirage sur trois fois répétées et pas plus de cinquante coups depuis le dernier pion-mouvement-ou-capture: si vous encodez le passé revient au dernier mouvement ou capture de pion, alors vous avoir suffisamment d'informations pour décider si ces règles s'appliquent: pas besoin de l'historique complet du jeu.

La position sur une carte peut être définie en 7 bits (0-63, et 1 valeur indiquant qu'elle n'est plus sur la carte). Donc, pour chaque pièce sur le plateau, spécifiez où elle se trouve.

32 pièces * 7 bits = 224 bits

EDIT: comme Cadrian l'a souligné ... nous avons également le cas du `` pion promu à la reine ''. Je suggère que nous ajoutions des bits supplémentaires à la fin pour indiquer quel pion a été promu.

Donc pour chaque pion qui a été promu, nous suivons les 224 bits avec 5 bits qui indiquent l'indice du pion qui a été promu, et 11111 si c'est la fin de la liste.

Le cas minimal (pas de promotions) est donc de 224 bits + 5 (pas de promotions). Pour chaque pion promu, ajoutez 5 bits.

EDIT: Comme le souligne Shaggy Frog, il nous faut encore un peu à la fin pour indiquer à qui c'est le tour; ^)

J'utiliserais un encodage de longueur d'exécution. Certaines pièces sont uniques (ou n'existent que deux fois), je peux donc omettre la longueur après elles. Comme cletus, j'ai besoin de 13 états uniques, donc je peux utiliser un quartet (4 bits) pour encoder la pièce. Le tableau initial ressemblerait alors à ceci:

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

ce qui me laisse avec 8 + 2 + 4 + 2 + 8 nibbles = 24 nibbles = 96 bits. Je ne peux pas encoder 16 avec un quartet mais comme "Vide, 0" n'a pas de sens, je peux traiter "0" comme "16".

Si le plateau est vide mais pour un seul pion dans le coin supérieur gauche, j'obtiens "Pion, 1, Vide, 16, Vide, 16, Vide 16, Vide, 15" = 10 nibbles = 40 bits.

Le pire des cas, c'est quand j'ai un carré vide entre chaque pièce. Mais pour l'encodage du morceau, j'ai juste besoin de 13 valeurs sur 16, donc je peux peut-être en utiliser une autre pour dire "Empty1". Ensuite, j'ai besoin de 64 nibbles == 128 bits.

Pour les mouvements, j'ai besoin de 3 bits pour la pièce (la couleur est donnée par le fait que le blanc se déplace toujours en premier) plus 5 bits (0..63) pour la nouvelle position = un octet par mouvement. La plupart du temps, je n'ai pas besoin de l'ancienne position car une seule pièce sera à portée. Pour le cas étrange, je dois utiliser le code unique inutilisé (j'ai juste besoin de 7 codes pour encoder la pièce) puis 5 bits pour l'ancien et 5 bits pour la nouvelle position.

Cela me permet d'encoder le roque en 13 bouchées (je peux déplacer le roi vers la tour ce qui suffit à dire ce que je compte).

[EDIT] Si vous autorisez un encodeur intelligent, alors j'ai besoin de 0 bits pour la configuration initiale (car il ne doit pas être encodé de quelque manière que ce soit: c'est statique) plus un octet par mouvement.

[EDIT2] Ce qui laisse la transformation du pion. Si un pion atteint la dernière ligne, je peux le mettre en place pour dire "transforme" puis ajouter les 3 bits pour la pièce par laquelle il est remplacé (vous n'avez pas besoin d'utiliser une reine; vous pouvez remplacer le pion par quoi que ce soit mais le roi).

Tout comme ils encodent des jeux sur des livres et des papiers: chaque pièce a un symbole; puisqu'il s'agit d'un jeu "légal", les blancs se déplacent en premier - pas besoin d'encoder le blanc ou le noir séparément, il suffit de compter le nombre de coups pour déterminer qui a bougé. De plus, chaque mouvement est codé comme (pièce, position de fin) où la «position de fin» est réduite au moindre nombre de symboles qui permet de discerner les ambiguïtés (peut être zéro). La durée du jeu détermine le nombre de coups. On peut également encoder le temps en minutes (depuis le dernier mouvement) à chaque étape.

L'encodage de la pièce peut être effectué soit en attribuant un symbole à chacun (32 au total), soit en attribuant un symbole à la classe, et utiliser la position de fin pour comprendre laquelle de la pièce a été déplacée. Par exemple, un pion a 6 positions de fin possibles; mais en moyenne, seul un couple est disponible à chaque tournant. Donc, statistiquement, l'encodage par position de fin pourrait être le meilleur pour ce scénario.

Des codages similaires sont utilisés pour les trains de pointes en neurosciences computationnelles (AER).

Inconvénients: vous devez rejouer l'intégralité du jeu pour obtenir l'état actuel et générer un sous-ensemble, un peu comme parcourir une liste chaînée.

Il y a 64 positions de carte possibles, vous avez donc besoin de 6 bits par position. Il y a 32 pièces initiales, donc nous avons un total de 192 bits jusqu'à présent, où tous les 6 bits indiquent la position de la pièce donnée. Nous pouvons prédéterminer l'ordre dans lequel les pièces apparaissent, donc nous n'avons pas à dire laquelle est laquelle.

Et si un morceau est hors du plateau? Eh bien, nous pouvons placer une pièce au même endroit qu'une autre pièce pour indiquer qu'elle est hors du plateau, car ce serait illégal autrement. Mais nous ne savons pas non plus si la première pièce sera sur le plateau ou non. On ajoute donc 5 bits indiquant quelle pièce est la première (32 possibilités = 5 bits pour représenter la première pièce). Ensuite, nous pouvons utiliser cet endroit pour les pièces suivantes qui sont hors du plateau. Cela nous amène à 197 bits au total. Il doit y avoir au moins une pièce sur le tableau, donc cela fonctionnera.

Ensuite, nous avons besoin d'un bit pour le tour de qui c'est - nous amène à 198 bits .

Et la promotion des pions? Nous pouvons le faire mal en ajoutant 3 bits par pion, en ajoutant 42 bits. Mais alors on peut remarquer que la plupart du temps, les pions ne sont pas promus.

Ainsi, pour chaque pion qui est sur le plateau, le bit «0» indique qu'il n'est pas promu. Si un pion n'est pas sur le plateau, nous n'en avons pas besoin du tout. Ensuite, nous pouvons utiliser des chaînes de bits de longueur variable pour lesquelles il bénéficie de la promotion. Le plus souvent, ce sera une reine, donc "10" peut signifier REINE. Alors "110" signifie tour, "1110" signifie évêque et "1111" signifie chevalier.

L'état initial prendra 198 + 16 = 214 bits , puisque les 16 pions sont sur le plateau et sans promotion. Une fin de partie avec deux pions-reines promues peut prendre quelque chose comme 198 + 4 + 4, ce qui signifie 4 pions vivants et non promus et 2 pions reine, pour un total de 206 bits . Semble assez robuste!

===

Le codage Huffman, comme d'autres l'ont souligné, serait la prochaine étape. Si vous observez quelques millions de parties, vous remarquerez que chaque pièce est beaucoup plus susceptible d'être sur certaines cases. Par exemple, la plupart du temps, les pions restent en ligne droite, ou un à gauche / un à droite. Le roi restera généralement autour du port d'attache.

Par conséquent, concevez un schéma de codage Huffman pour chaque position distincte. Les pions ne prendront probablement en moyenne que 3-4 bits au lieu de 6. Le roi devrait également prendre quelques bits.

Également dans ce schéma, incluez «pris» comme position possible. Cela peut aussi très bien gérer le roque - chaque tour et chaque roi auront un état supplémentaire de "position d'origine, déplacé". Vous pouvez également encoder en passant dans les pions de cette façon - "position d'origine, peut en passant".

Avec suffisamment de données, cette approche devrait donner de très bons résultats.

J'essaierais d'utiliser l' encodage Huffman . La théorie derrière cela est - dans chaque partie d'échecs, il y aura des pièces qui bougeront beaucoup, et d'autres qui ne bougeront pas beaucoup ou seront éliminées tôt. Si certaines pièces de la position de départ ont déjà été retirées, tant mieux. Il en va de même pour les carrés - certains carrés peuvent voir toute l'action, tandis que d'autres ne sont pas beaucoup touchés.

Ainsi, j'aurais deux tables Huffman - une pour les pièces, l'autre pour les carrés. Ils seront générés en regardant le jeu réel. Je pourrais avoir une grande table pour chaque paire pièce-carré, mais je pense que ce serait assez inefficace car il n'y a pas beaucoup d'exemples de la même pièce se déplaçant à nouveau sur le même carré.

Chaque pièce aurait un identifiant attribué. Puisqu'il y a 32 pièces différentes, je n'aurais besoin que de 5 bits pour l'identifiant de pièce. Les identifiants des pièces ne changent pas d'une partie à l'autre. Il en va de même pour les identifiants carrés, pour lesquels j'aurais besoin de 6 bits.

Les arbres de Huffman seraient encodés en écrivant chaque nœud au fur et à mesure qu'ils sont traversés dans l'ordre (c'est-à-dire que le nœud est d'abord sorti, puis ses enfants de gauche à droite). Pour chaque nœud, il y aura un bit spécifiant s'il s'agit d'un nœud feuille ou d'un nœud de branche. S'il s'agit d'un nœud feuille, il sera suivi des bits donnant l'ID.

La position de départ sera simplement donnée par une série de paires pièce-emplacement. Après cela, il y aura une paire pièce-emplacement pour chaque mouvement. Vous pouvez trouver la fin du descripteur de position de départ (et le début du descripteur de coups) simplement en trouvant la première pièce mentionnée deux fois. Dans le cas où un pion est promu, il y aura 2 bits supplémentaires spécifiant ce qu'il devient, mais l'ID de pièce ne changera pas.

Pour tenir compte de la possibilité qu'un pion soit promu au début du jeu, il y aura également une "table de promotion" entre les arbres de Huffman et les données. Au début, il y aura 4 bits spécifiant le nombre de pions mis à niveau. Ensuite, pour chaque pion, il y aura son ID encodé par Huffman et 2 bits spécifiant ce qu'il est devenu.

Les arbres de Huffman seront générés en tenant compte de toutes les données (à la fois la position de départ et les coups) et la table de promotion. Bien que normalement la table de promotion soit vide ou ne contienne que quelques entrées.

Pour résumer en termes graphiques:

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

Ajouté: cela pourrait encore être optimisé. Chaque pièce n'a que quelques coups légaux. Au lieu de simplement encoder le carré cible, on pourrait donner des ID basés sur 0 pour les mouvements possibles de chaque pièce. Les mêmes identifiants seraient réutilisés pour chaque pièce, donc au total, il n'y aurait pas plus de 21 identifiants différents (la reine peut avoir au plus 21 options de déplacement différentes). Mettez ceci dans une table Huffman au lieu des champs.

Cela présenterait cependant une difficulté pour représenter l'état d'origine. On pourrait générer une série de mouvements pour remettre chaque pièce à sa place. Dans ce cas, il serait nécessaire de marquer d'une manière ou d'une autre la fin de l'état initial et le début des mouvements.

Ils peuvent également être placés en utilisant des ID carrés de 6 bits non compressés.

Si cela présenterait une diminution globale de la taille - je ne sais pas. Probablement, mais devrait expérimenter un peu.

Ajouté 2: Un autre cas spécial. Si l'état du jeu n'a AUCUN mouvement, il devient important de distinguer qui se déplace ensuite. Ajoutez un peu plus à la fin pour cela. :)

[édité après avoir lu la question correctement] Si vous supposez que chaque position légale peut être atteinte à partir de la position initiale (qui est une définition possible de «légal»), alors n'importe quelle position peut être exprimée comme la séquence de mouvements depuis le début. Un extrait de jeu partant d'une position non standard peut être exprimé comme la séquence de mouvements nécessaires pour atteindre le départ, un interrupteur pour allumer la caméra, suivi des mouvements suivants.

Appelons donc l'état initial de la carte le bit unique "0".

Les mouvements à partir de n'importe quelle position peuvent être énumérés en numérotant les carrés et en ordonnant les mouvements par (début, fin), le saut classique à 2 carrés indiquant le roque. Il n'est pas nécessaire d'encoder les coups illégaux, car la position du plateau et les règles sont toujours déjà connues. Le drapeau pour allumer la caméra pourrait soit être exprimé comme un mouvement spécial dans la bande, soit plus raisonnablement comme un numéro de mouvement hors bande.

Il y a 24 mouvements d'ouverture pour chaque côté, qui peuvent tenir dans 5 bits chacun. Les mouvements suivants peuvent nécessiter plus ou moins de bits, mais les mouvements légaux sont toujours énumérables, de sorte que la largeur de chaque mouvement peut augmenter ou s'étendre. Je n'ai pas calculé, mais j'imagine que les positions 7 bits seraient rares.

En utilisant ce système, un jeu de 100 demi-coups pourrait être encodé en environ 500 bits. Cependant, il peut être judicieux d'utiliser un livre d'ouverture. Supposons qu'il contienne un million de séquences. Laissez alors, un 0 initial indique un départ de la carte standard, et un 1 suivi d'un nombre de 20 bits indique un départ à partir de cette séquence d'ouverture. Les jeux avec des ouvertures quelque peu conventionnelles pourraient être raccourcis par exemple 20 demi-coups ou 100 bits.

Ce n'est pas la meilleure compression possible, mais (sans le livre d'ouverture) elle serait très facile à implémenter si vous avez déjà un modèle d'échecs, ce que suppose la question.

Pour compresser davantage, vous voudrez ordonner les mouvements selon la probabilité plutôt que dans un ordre arbitraire, et encoder les séquences probables en moins de bits (en utilisant par exemple les jetons Huffman comme les gens l'ont mentionné).

Si le temps de calcul n'est pas un problème, vous pouvez utiliser un générateur de position possible déterministe pour affecter des identifiants uniques à une position donnée.

À partir d'une position donnée, commencez par générer un nombre de positions possibles dans un manoir déterministe, par exemple en commençant en bas à gauche en passant en haut à droite. Cela détermine le nombre de bits dont vous aurez besoin pour le prochain mouvement, dans certaines situations, cela pourrait être aussi petit qu'un. Ensuite, lorsque le mouvement est effectué, stockez simplement l'identifiant unique de ce mouvement.

La promotion et les autres règles comptent simplement comme des coups valides tant qu'ils sont traités de manière déterministe, par exemple pour reine, tour, évêque, chacun compte comme un coup séparé.

La position initiale est la plus difficile et pourrait générer environ 250 millions de positions possibles (je pense), ce qui nécessiterait environ 28 bits plus un bit supplémentaire pour déterminer de qui il s'agit.

En supposant que nous sachions à qui c'est le tour (chaque tour passe du blanc au noir), le générateur déterministe ressemblerait à quelque chose comme:

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

'obtenir la liste des mouvements possibles' ferait quelque chose comme:

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.

Si le roi est en échec, chaque «liste de mouvements xxx possibles» ne renvoie que des coups valides qui changent la situation de vérification.

La plupart des réponses ont négligé la répétition triple. malheureusement pour la répétition 3 fois vous devez stocker toutes les positions jouées jusqu'à présent ...

La question nous obligeait à stocker de manière efficace dans l'espace, donc nous n'avons vraiment pas besoin de stocker la position tant que nous pouvons la construire à partir de la liste des mouvements (à condition que nous ayons une position de départ standard). Nous pouvons optimiser PGN et c'est terminé. Ci-dessous est un schéma simple.

Il y a 64 carrés sur le plateau, 64 = 2 ^ 6. Si nous ne stockons que le carré initial et final de chaque coup, cela prendrait 12 bits (la promotion sera abordée plus tard). Notez que ce schéma couvre déjà le joueur à déplacer, emphassant, pièce capturée, roque, etc. comme de ceux-ci peuvent être construits à partir de la simple relecture de la liste de coups.

pour la promotion, nous pouvons conserver un tableau séparé de vecteurs qui dirait "au mouvement N promouvoir vers la pièce XYZ". on peut garder un vecteur de (int, byte).

Il est tentant d'optimiser également le vecteur (Vers, De), puisque beaucoup de ces vecteurs (Vers, De) ne sont pas possibles aux échecs. par exemple. il n'y aura pas de passage de e1 à d8, etc. Mais je n'ai pas pu trouver de schéma. Toute autre idée est la bienvenue.

J'y ai pensé pendant longtemps (+ - 2 heures). Et il n'y a pas de réponses évidentes.

En supposant:

1. Ignorer l'état du temps (un joueur n'a pas utilisé pour avoir une limite de temps donc pourrait forcer un match nul en ne jouant pas)
2. Quand le jeu a-t-il été joué?!? C'est important parce que les règles ont changé au fil du temps (donc supposera un jeu moderne dans le point suivant un jeu moderne ...) Veuillez vous référer à la règle du pion mort par exemple (wikipedia a un problème très connu pour le montrer), et si vous le souhaitez pour remonter dans le temps, l'évêque de bonne chance ne se déplaçait que lentement et les dés étaient utilisés. lol.

... si à jour des règles modernes. Indépendamment de la répétition et de la limite de répétition du mouvement.

-C 25 octets arrondis (64b + 32 * 4b + 5b = 325b)

= 64 bits (quelque chose / rien) + 32 * 4 bits [1bit = couleur {noir / blanc} + 3 bits = type de pièce {King, Queen, Bishop, kNight, Rook, Pawn, MovedPawn} NB: pion déplacé ... Par exemple, si c'était le dernier pion déplacé au tour précédent, indiquant qu'un «en passant» est faisable. ] + 5 bits pour l'état actuel (qui est au tour, en passant, possibilité de tour ou non de chaque côté)

Jusqu'ici tout va bien. Peut probablement être amélioré, mais il y aurait alors une durée et une promotion variables à prendre en compte !?

Désormais, les règles suivantes ne sont applicables que LORSQUE un joueur s'inscrit pour un match nul, CE N'EST PAS automatique! Considérez donc que 90 coups sans capture ou un mouvement de pion est faisable si aucun joueur ne demande un tirage au sort! Cela signifie que tous les mouvements doivent être enregistrés ... et disponibles.

-D répétition de position ... par exemple état du plateau comme mentionné ci-dessus (voir C) ou non ... (voir ci-dessous concernant les règles de la FIDE) -E Cela laisse le problème complexe de 50 coups sans capture ou mouvement de pion compteur est nécessaire ... Cependant.

Alors, comment gérez-vous cela? ... En fait, il n'y a aucun moyen. Parce qu'aucun joueur ne peut vouloir dessiner ou se rendre compte que cela s'est produit. Maintenant, dans le cas E, un compteur pourrait suffire ... mais voici l'astuce et même en lisant les règles de la FIDE (http://www.fide.com/component/handbook/?id=124&view=article) je ne trouve pas de réponse ... qu'en est-il de la perte de capacité de recrue. Est-ce une répétition? Je ne pense pas mais là c'est un sujet flou non abordé, pas clarifié.

Voici donc deux règles qui sont deux complexes ou indéfinies même pour essayer d'encoder ... Cheers.

Donc, la seule façon de vraiment encoder un jeu est de tout enregistrer depuis le début ... ce qui entre alors en conflit (ou pas?) Avec la question "état du plateau".

J'espère que cette aide ... pas trop de maths :-) Juste pour montrer que certaines questions ne sont pas aussi faciles, trop ouvertes pour que l'interprétation ou la pré-connaissance soit correcte et efficace. Pas un que je considérerais pour une interview car il ouvre trop de boîte de ver.

Amélioration possible de la position de départ dans la solution de Yacoby

Aucune position légale n'a plus de 16 pièces de chaque couleur. Le nombre de façons de placer jusqu'à 16 pièces noires et 16 blanches sur 64 carrés est d'environ 3,63e27. Log2 (3,63e27) = 91,55. Cela signifie que vous pouvez encoder la position et la couleur de toutes les pièces en 92 bits. C'est moins que les 64 bits pour la position + jusqu'à 32 bits pour la couleur que la solution de Yacoby requiert. Vous pouvez enregistrer 4 bits dans le pire des cas au détriment d'une complexité considérable dans l'encodage.

D'autre part, il augmente la taille des positions avec 5 pièces ou plus manquantes. Ces positions ne représentent que <4% de toutes les positions, mais ce sont probablement la majorité des cas où vous souhaitez enregistrer une position de départ différente de la position initiale.

Cela conduit à la solution complète

1. Encodez la position et la couleur des pièces selon la méthode ci-dessus. 92 bits .
2. Pour spécifier le type de chaque pièce, utilisez un code Huffman: pion: '0', tour: '100', chevalier: '101', évêque: '110', reine: '1110', roi: '1111'. Cela nécessite (16 * 1 + 12 * 3 + 4 * 4) = 68 bits pour un ensemble complet de pièces. La position de la carte complète peut être codée en 92 + 68 = 160 bits maximum .
3. Un état de jeu supplémentaire doit être ajouté: tour: 1 bit, quel roque est possible: 4 bits, "en passant" possible: jusqu'à 4 bits (1 bit indique que c'est le cas et 3 bits indiquent lequel). La position de départ est codée en = 160 + 9 = 169 bits
4. Pour la liste des coups, énumérez tous les coups possibles pour une position donnée et enregistrez la position du coup dans la liste. La liste des coups comprend tous les cas particuliers (roque, en passant et démission). Utilisez uniquement autant de bits que nécessaire pour stocker la position la plus élevée. En moyenne, il ne doit pas dépasser 7 bits par coup (16 pièces possibles et 8 coups légaux par pièce en moyenne). Dans certains cas, lorsqu'un déplacement est forcé, il ne nécessite qu'un bit (déplacement ou démission).

Il y a 32 pièces sur le plateau. Chaque pièce a une position (une sur 64 carrés). Vous avez donc juste besoin de 32 entiers positifs.

Je sais que 64 positions tiennent en 6 bits mais je ne ferais pas cela. Je garderais les derniers morceaux pour quelques drapeaux (pièce abandonnée, pion reine)

La réponse de cletus est bonne, mais il a oublié de coder également à qui c'est le tour. Il fait partie de l'état actuel et est nécessaire si vous utilisez cet état pour piloter un algorithme de recherche (comme un dérivé alpha-bêta).

Je ne suis pas un joueur d'échecs, mais je crois qu'il y a aussi un autre cas critique: combien de coups ont été répétés. Une fois que chaque joueur fait le même mouvement trois fois, le jeu est un match nul, non? Si tel est le cas, vous devrez enregistrer ces informations dans l'état car après la troisième répétition, l'état est désormais terminal.

Comme plusieurs autres l'ont mentionné, vous pouvez pour chacune des 32 pièces, stocker sur quelle case elles se trouvent et si elles sont sur le plateau ou non, cela donne 32 * (log2 (64) + 1) = 224 bits.

Cependant, les évêques ne peuvent occuper que les carrés noirs ou blancs, donc pour ceux-ci, vous n'avez besoin que de log2 (32) bits pour la position, ce qui donne 28 * 7 + 4 * 6 = 220 bits.

Et comme les pions ne démarrent pas à l'arrière et ne peuvent avancer que sur 56, il devrait être possible d'utiliser cette limitation pour réduire le nombre de bits nécessaires pour les pions.

Un tableau a 64 carrés et peut être représenté par 64 bits indiquant si un carré est vide ou non. Nous n'avons besoin d'informations sur les pièces que si un carré a une pièce. Puisque le joueur + pièce prend 4 bits (comme indiqué précédemment), nous pouvons obtenir l'état actuel en 64 + 4 * 32 = 192 bits. Jetez le tour actuel et vous avez 193 bits.

Cependant, nous devons également encoder les coups légaux pour chaque pièce. Tout d'abord, nous calculons le nombre de coups légaux pour chaque pièce et ajoutons ce nombre de bits après l'identificateur de pièce d'un carré complet. J'ai calculé comme suit:

Pion: En avant, tournez d'abord deux en avant, en passant * 2, promotion = 7 bits. Vous pouvez combiner le premier virage en avant et la promotion en un seul bit car ils ne peuvent pas se produire à partir de la même position, vous avez donc 6. Tour: 7 carrés verticaux, 7 carrés horizontaux = 14 bits Chevalier: 8 carrés = 8 bits Évêque: 2 diagonales * 7 = 14 bits Reine: 7 verticales, 7 horizontales, 7 diagonales, 7 diagonales = 28 bits Roi: 8 carrés environnants

Cela signifie toujours que vous devrez mapper les carrés ciblés en fonction de la position actuelle, mais cela (devrait être) un simple calcul.

Puisque nous avons 16 pions, 4 tours / chevaliers / évêques et 2 reines / rois, c'est 16 * 6 + 4 * 14 + 4 * 8 + 4 * 14 + 2 * 28 + 2 * 8 = 312 bits supplémentaires, ce qui le total à 505 bits au total.

En ce qui concerne le nombre de bits requis par pièce pour les déplacements possibles, quelques optimisations pourraient être ajoutées à cela et le nombre de bits probablement réduit, j'ai juste utilisé des nombres faciles pour travailler. Par exemple, pour les pièces coulissantes, vous pouvez stocker à quelle distance elles pourraient se déplacer, mais cela nécessiterait des calculs supplémentaires.

En bref: ne stockez les données supplémentaires (pièce, etc.) que lorsqu'une case est occupée, et ne stockez que le nombre minimum de bits pour chaque pièce pour représenter ses mouvements légaux.

EDIT1: J'ai oublié la promotion du roque et du pion à n'importe quelle pièce. Cela pourrait porter le total avec des positions explicites à 557 coups (3 bits de plus pour les pions, 2 pour les rois)

Chaque pièce peut être représentée par 4 bits (pion à roi, 6 types), noir / blanc = 12 valeurs

Chaque carré de la carte peut être représenté par 6 bits (x coord, y coord).

Les positions initiales nécessitent un maximum de 320 bits (32 pièces, 4 + 6 bits)

Chaque mouvement suivant peut être représenté par 16 bits (de la position, à la position, pièce).

Le roque nécessiterait 16 bits supplémentaires, car il s'agit d'un double mouvement.

Les pions queened pourraient être représentés par l'une des 4 valeurs de réserve sur 4 bits.

Sans faire les calculs en détail, cela commence à économiser de l'espace après le premier mouvement par rapport au stockage de 32 * 7 bits (tableau prédéfini de pièces) ou 64 * 4 bits (affectation prédéfinie de carrés)

Après 10 coups des deux côtés, l'espace maximum requis est de 640 bits

... mais là encore, si nous identifions chaque pièce de manière unique (5 bits) et ajoutons un sixième bit pour marquer les pions reines, alors nous n'avons besoin que de pièce-id + to-position pour chaque coup. Cela change le calcul en ...

Positions initiales = max 384 bits (32 pièces, 6 + 6 bits) Chaque déplacement = 12 bits (to-position, pièce-id)

Ensuite, après 10 coups de chaque côté, l'espace maximum requis est de 624 bits

Comme Robert G, j'aurais tendance à utiliser PGN car il est standard et peut être utilisé par un large éventail d'outils.

Si, cependant, je joue à une IA d'échecs qui se trouve sur une sonde spatiale lointaine et que chaque bit est donc précieux, c'est ce que je ferais pour les mouvements. Je viendrai bock à encoder l'état initial plus tard.

Les mouvements n'ont pas besoin d'enregistrer l'état; le décodeur peut garder une trace de l'état ainsi que des mouvements légaux à un moment donné. Tout ce qu'il faut savoir, c'est laquelle des différentes alternatives juridiques est choisie. Puisque les joueurs alternent, un mouvement n'a pas besoin d'enregistrer la couleur du joueur. Étant donné qu'un joueur ne peut déplacer que ses propres pièces de couleur, le premier choix est de savoir quelle pièce le joueur déplace (je reviendrai sur une alternative qui utilise un autre choix plus tard). Avec au plus 16 pièces, cela nécessite au plus 4 bits. Au fur et à mesure qu'un joueur perd des pièces, le nombre de choix diminue. De plus, un état de jeu particulier peut limiter le choix des pièces. Si un roi ne peut pas se déplacer sans se mettre en échec, le nombre de choix est réduit de un. Si un roi est en échec, toute pièce qui ne peut pas le mettre hors de contrôle n'est pas un choix viable.

Une fois la pièce spécifiée, elle n'aura qu'un certain nombre de destinations légales. Le nombre exact dépend fortement de la disposition du plateau et de l'historique du jeu, mais nous pouvons déterminer certains maximums et valeurs attendues. Pour tout le monde sauf le chevalier et pendant le roque, une pièce ne peut pas se déplacer à travers une autre pièce. Ce sera une grande source de limites de mouvement, mais c'est difficile à quantifier. Une pièce ne peut pas sortir du plateau, ce qui limitera également largement le nombre de destinations.

Nous encodons la destination de la plupart des pièces en numérotant les carrés le long des lignes dans l'ordre suivant: W, NW, N, NE (le côté noir est N). Une ligne commence dans le carré le plus éloigné dans la direction donnée dans laquelle il est légal de se déplacer et se dirige vers le. Pour un roi libre, la liste des coups est W, E, NW, SE, N, S, NE, SW. Pour le chevalier, nous commençons par 2W1N et procédons dans le sens des aiguilles d'une montre; la destination 0 est la première destination valide dans cet ordre.

• Pions: Un pion immobile a 2 choix de destinations, nécessitant ainsi 1 bit. Si un pion peut en capturer un autre, soit normalement, soit en passant (ce que le décodeur peut déterminer, puisqu'il garde la trace de l'état), il a également 2 ou 3 choix de coups. En dehors de cela, un pion ne peut avoir qu'un seul choix, ne nécessitant aucun bit. Lorsqu'un pion est dans son 7 ^e rang, nous plaçons également le choix de promotion. Puisque les pions sont généralement promus au rang de reines, suivis par les chevaliers, nous encodons les choix comme suit:
  • reine: 0
  • chevalier: 10
  • évêque: 110
  • tour: 111
• Bishop: au plus 13 destinations à {d, e} {4,5} pour 4 bits.
• Tour: au plus 14 destinations, 4 bits.
• Chevaliers: au plus 8 destinations, 3 bits.
• Rois: lorsque le roque est une option, le roi est de retour en S et ne peut pas descendre; cela donne un total de 7 destinations. Le reste du temps, un roi a au plus 8 coups, donnant un maximum de 3 bits.
• Reine: Identique aux choix pour l'évêque ou la tour, pour un total de 27 choix, soit 5 bits

Puisque le nombre de choix n'est pas toujours une puissance de deux, ce qui précède gaspille toujours des bits. Supposons que le nombre de choix soit C et que le choix particulier soit numéroté c , et n = ceil (lg ( C )) (le nombre de bits requis pour coder le choix). Nous utilisons ces valeurs autrement gaspillées en examinant le premier bit du choix suivant. Si c'est 0, ne faites rien. Si c'est 1 et c + C <2 ⁿ , alors ajoutez C à c . Le décodage d'un nombre inverse ceci: si le c reçu > = C , soustrayez C et mettez le premier bit du nombre suivant à 1. Si c<2 ⁿ - C , puis définissez le premier bit du nombre suivant sur 0. Si 2 ⁿ - C <= c < C , ne faites rien. Appelez ce schéma "saturation".

Un autre type de choix potentiel qui pourrait raccourcir l'encodage est de choisir une pièce de l'adversaire à capturer. Cela augmente le nombre de choix pour la première partie d'un mouvement, en choisissant une pièce, pour au plus un bit supplémentaire (le nombre exact dépend du nombre de pièces que le joueur actuel peut déplacer). Ce choix est suivi d'un choix de pièce de capture, qui est probablement beaucoup plus petit que le nombre de coups pour l'une des pièces de joueurs données. Une pièce ne peut être attaquée que par une seule pièce de n'importe quelle direction cardinale plus les chevaliers pour un total d'au plus 10 pièces d'attaque; cela donne un maximum total de 9 bits pour un mouvement de capture, même si je m'attendrais à 7 bits en moyenne. Cela serait particulièrement avantageux pour les captures par la reine, car elle aura souvent plusieurs destinations légales.

Avec la saturation, l'encodage de capture ne présente probablement pas d'avantage. Nous pourrions autoriser les deux options, en spécifiant dans l'état initial lesquelles sont utilisées. Si la saturation n'est pas utilisée, l'encodage du jeu pourrait également utiliser des nombres de choix inutilisés ( C <= c <2 ⁿ ) pour changer les options pendant le jeu. Chaque fois que C est une puissance de deux, nous ne pouvons pas changer les options.

Thomas a la bonne approche pour encoder la carte. Cependant, cela devrait être combiné avec l'approche de ralu pour stocker les mouvements. Faites une liste de tous les mouvements possibles, écrivez le nombre de bits nécessaires pour exprimer ce nombre. Puisque le décodeur effectue le même calcul, il sait combien sont possibles et peut savoir combien de bits lire, aucun code de longueur n'est nécessaire.

Ainsi, nous obtenons 164 bits pour les pièces, 4 bits pour les informations sur le roque (en supposant que nous stockons un fragment d'un jeu, sinon il peut être reconstruit), 3 bits pour les informations d'éligibilité en passant - stockez simplement la colonne où le mouvement s'est produit ( Si en passant n'est pas possible, enregistrez une colonne là où ce n'est pas possible - de telles colonnes doivent exister) et 1 pour qui doit bouger.

Les déplacements prendront généralement 5 ou 6 bits mais peuvent varier de 1 à 8.

Un raccourci supplémentaire - si l'encodage commence par 12 bits 1 (une situation invalide - même un fragment n'aura pas deux rois sur un côté) vous abandonnez le décodage, effacez le tableau et configurez un nouveau jeu. Le bit suivant sera un peu de mouvement.

L'algorithme doit énumérer de manière déterministe toutes les destinations possibles à chaque déplacement. Nombre de destinations:

• 2 évêques, 13 destinations chacun = 26
• 2 tours, 14 destinations chacune = 28
• 2 chevaliers, 8 destinations chacun = 16
• reine, 27 destinations
• roi, 8 destinations

8 pattes pourraient toutes devenir des reines dans le pire des cas (en termes d'énumération), créant ainsi le plus grand nombre de destinations possibles 9 * 27 + 26 + 28 + 16 + 8 = 321. Ainsi, toutes les destinations pour tout déplacement peuvent être énumérées par un nombre de 9 bits.

Le nombre maximum de coups des deux parties est de 100 (si je ne me trompe pas, pas un joueur d'échecs). Ainsi, n'importe quel jeu pourrait être enregistré en 900 bits. Plus la position initiale de chaque morceau peut être enregistrée en utilisant des nombres de 6 bits, qui totalisent à 32 * 6 = 192 bits. Plus un bit pour l'enregistrement "qui se déplace en premier". Ainsi, n'importe quel jeu peut être enregistré en utilisant 900 + 192 + 1 = 1093 bits.

Stockage de l'état de la carte

La façon la plus simple à laquelle j'ai pensé est d'avoir d'abord un tableau de 8 * 8 bits représentant l'emplacement de chaque pièce (donc 1 s'il y a une pièce d'échecs là-bas et 0 s'il n'y en a pas). Comme il s'agit d'une longueur fixe, nous n'avons besoin d'aucun terminateur.

Représentez ensuite chaque pièce d'échecs dans l'ordre de son emplacement. En utilisant 4 bits par pièce, cela prend 32 * 4 bits (128 au total). Ce qui est vraiment un gaspillage.

En utilisant un arbre binaire, nous pouvons représenter un pion dans un octet, un chevalier et une tour et un évêque en 3 et un roi et une reine en 4. Comme nous devons également stocker la couleur de la pièce, ce qui prend un octet supplémentaire, cela finit par comme (pardonnez-moi si c'est faux, je n'ai jamais regardé le codage Huffman en détail auparavant):

• Pion: 2
• Tour: 4
• Chevalier: 4
• Évêque: 4
• Roi: 5
• Reine: 5

Compte tenu des totaux:

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

Qui bat en utilisant un ensemble de bits de taille fixe par 28 bits.

Donc, la meilleure méthode que j'ai trouvée est de le stocker dans un tableau 8 ² + 100 bits

8*8 + 100 = 164

Stockage des mouvements
La première chose que nous devons savoir est de savoir quelle pièce se déplace vers où. Étant donné qu'il y a au maximum 32 pièces sur le plateau et que nous savons ce qu'est chaque pièce, plutôt qu'un entier représentant le carré, nous pouvons avoir un entier représentant le décalage de la pièce, ce qui signifie que nous n'avons qu'à ajuster 32 valeurs possibles pour représenter un pièce.

Malheureusement, il existe diverses règles spéciales, comme le roque ou le renversement du roi et la formation d'une république (référence Terry Pratchett), donc avant de stocker la pièce à déplacer, nous avons besoin d'un seul bit pour indiquer s'il s'agit d'un coup spécial ou non.

Donc, pour chaque mouvement normal, nous avons quelques 1 + 5 = 6bits nécessaires . (Type 1 bit, 5 bits pour la pièce)

Une fois le numéro de pièce décodé, nous connaissons le type de pièce et chaque pièce doit représenter son mouvement de la manière la plus efficace. Par exemple (si mes règles d'échecs sont à la hauteur) un pion a un total de 4 coups possibles (prendre à gauche, prendre à droite, avancer d'un, avancer de deux).
Donc, pour représenter un mouvement de pion, nous avons besoin de bits '6 + 2 = 8'. (6 bits pour l'en-tête de déplacement initial, 2 bits pour quel déplacement)

Se déplacer pour la reine serait plus complexe, en ce sens qu'il serait préférable d'avoir une direction (8 directions possibles, donc 3 bits) et un total de 8 carrés possibles vers lesquels se déplacer pour chaque direction (donc encore 3 bits). Donc, pour représenter le mouvement d'une reine, il faudrait des 6 + 3 + 3 = 12bits.

La dernière chose qui me vient à l'esprit, c'est que nous devons stocker les joueurs qui le tournent. Cela devrait être un seul bit (blanc ou noir pour passer au suivant)

Format résultant
Ainsi, le format de fichier ressemblerait à ceci

[64 bits] Emplacement des pièces initiales
[100 bits max] Pièces initiales [1 bit] Tour du joueur
[n bits] Se déplace

Où un déplacement est
[1 bit] Type de déplacement (spécial ou normal)
[n bits] Détail du déplacement

Si le mouvement est un mouvement normal, le détail du mouvement ressemble à quelque chose comme
[5 bits] pièce
[n bits] mouvement de pièce spécifique (généralement dans la plage de 2 à 6 bits]

S'il s'agit d'un mouvement spécial,
il devrait avoir un type entier et ensuite toute information supplémentaire (comme s'il s'agit d'un roque). Je ne me souviens pas du nombre de coups spéciaux, donc cela peut être juste d'indiquer qu'il s'agit d'un coup spécial (s'il n'y en a qu'un)

Dans le cas de base du plateau initial et des mouvements suivants, considérez ce qui suit.

Utilisez un programme d'échecs pour attribuer des probabilités à tous les coups possibles. Par exemple, 40% pour e2-e4 20% pour d2-d4, et ainsi de suite. Si certains mouvements sont légaux mais non pris en compte par ce programme, donnez-leur une faible probabilité. Utilisez le codage arithmétique pour enregistrer le choix qui a été fait, qui sera un nombre compris entre 0 et 0,4 pour le premier mouvement, 0,4 et 0,6 pour le second, et ainsi de suite.

Faites de même pour l'autre côté. Par exemple, s'il y a 50% de chances que e7-e5 soit la réponse à e2-e4, le nombre encodé sera compris entre 0 et 0,2. Répétez jusqu'à ce que le jeu soit terminé. Le résultat est une gamme potentiellement très petite. Trouvez la fraction binaire avec la plus petite base qui rentre dans cette plage. C'est du codage arithmétique.

C'est mieux que Huffman car il peut être considéré comme un encodage de bits fractionnaires (plus certains à la fin du jeu pour arrondir à un bit entier).

Le résultat devrait être plus compact que celui de Huffman, et il n'y a pas de cas particuliers pour la promotion, en passant, le mouvement des 50 règles et d'autres détails car ils sont gérés par le programme d'évaluation d'échecs.

Pour rejouer, utilisez à nouveau le programme d'échecs pour évaluer le tableau et attribuer toutes les probabilités à chaque coup. Utilisez la valeur arithmétique encodée pour déterminer quel coup a été réellement joué. Répétez jusqu'à ce que vous ayez terminé.

Si votre programme d'échecs est assez bon, vous pouvez obtenir une meilleure compression avec un encodeur à deux états, où les probabilités sont définies en fonction des mouvements pour le noir et le blanc. Dans le cas le plus extrême de plus de 200 états, cela encode l'ensemble complet de toutes les parties d'échecs possibles, et n'est donc pas faisable.

C'est à peu près une manière différente de dire ce que Darius a déjà écrit, seulement avec un petit exemple de la façon dont le codage arithmétique pourrait fonctionner, et un exemple réel d'utilisation d'un programme d'échecs existant pour aider à évaluer la probabilité du (des) prochain (s) coup (s).