Puzzle de programmeur : Encodage un état de Conseil d’échecs tout au long d’un jeu

Question

Pas strictement une question de plus en plus un casse-tête...

Au fil des ans, j'ai été impliqué dans quelques entretiens de nouveaux employés. Autres que de demander à la norme "savez-vous X de la technologie" questions, j'ai aussi essayé d'avoir une idée de la façon dont ils abordent les problèmes. Généralement, je préfère les envoyer à la question par e-mail la veille de l'entrevue, et s'attendre à trouver une solution pour le lendemain.

Souvent, le résultat serait tout à fait intéressant - faux, mais intéressant et la personne serait toujours obtenir ma recommandation s'ils pouvaient expliquer pourquoi ils ont pris une approche particulière.

J'ai donc pensé que je jetterais une de mes questions pour le Débordement de la Pile de l'auditoire.

Question: qu'est-Ce que la plupart de l'espace-efficace que vous pouvez penser à coder l'état du jeu d'échecs (ou sous-ensemble de celui-ci)? C'est, étant donné un échiquier avec des pièces disposées légalement, de coder cet état initial et de tous les déplacements pris par les joueurs dans le jeu.

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

EDIT: Comme l'une des affiches de l'a souligné, je n'ai pas en compte l'intervalle de temps entre les coups. Se sentir libre de tenir compte de cela aussi comme une option supplémentaire :)

EDIT2: Juste pour des précisions supplémentaires... Rappelez-vous, le codeur/décodeur est la règle. Les seules choses qui ont vraiment besoin d'être stocké sont les choix du joueur - rien d'autre ne peut être supposé connu par le codeur/décodeur.

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

Answer 1

Il est préférable de stocker les jeux d'échecs en lisible par l'utilisateur, le format standard.

Le Portable Game Notation suppose une norme de la position de départ (bien qu'il n'a pas d') et des listes de la se déplace, au tour par tour. Un compact, lisible par l'homme, le format standard.

E. g.

[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 rendre plus petit, puis il suffit de le zipper. Travail de fait!

Answer 2

Grand puzzle!

Je vois que la plupart des gens sont mémorisation de la position de chaque pièce. Comment prendre un plus simple d'esprit, et de stocker le contenu de chaque carré? Qui prend soin de promotion et de pièces capturées automatiquement.

Et il permet le codage Huffman. En fait, la fréquence initiale des pièces sur l'échiquier est presque parfait pour cela: la moitié des places sont vides, la moitié des places sont des pions, et cætera.

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

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

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

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

Total: 164 bits pour l' initiale du conseil d'etat. Beaucoup moins que les 235 bits du plus haut voté réponse. Et il va seulement pour obtenir plus petits comme le jeu progresse (sauf après une promotion).

J'ai regardé seulement à la position des pièces sur l'échiquier; état supplémentaire (à qui le tour, qui a fortifié, en passant, la répétition de mouvements, etc.) devront être codées séparément. Peut-être un autre de 16 bits au maximum, afin 180 bits pour l'ensemble de l'état de jeu. Optimisations possibles:

• En laissant de côté les moins fréquentes morceaux, et le stockage de leur position séparément. Mais ça n'aide pas... en remplaçant le roi et la reine par un carré vide permet d'économiser de 5 bits, qui sont exactement les 5 éléments dont vous avez besoin pour coder leur position d'une autre manière.
• "Pas de pions sur la rangée arrière" peut facilement être codé à l'aide d'une autre table de Huffman pour les lignes arrière, mais je doute que cela aide beaucoup. Vous seriez probablement se retrouver avec le même arbre de Huffman.
• "Un blanc, un noir évêque" peut être codé par l'introduction d'extra-symboles qui n'ont pas l' c bits, ce qui peut en être déduit à partir de la place que l'évêque est sur. (Pions promu évêques perturber ce schéma...)
• Les répétitions de cases vides pourraient être codées run-length par l'introduction d'extra-symboles pour, disons, "2 cases vides dans une rangée" et "4 cases vides dans une rangée". Mais il n'est pas si facile à estimer la fréquence de ceux-ci, et si vous vous trompez, il va faire mal plutôt que de l'aide.

Answer 3

Vraiment grande table de recherche approche

Position - 18 octets
Estimation du nombre de postes est de 10⁴³
Simplement les énumérer tous, et la position peuvent être stockés dans seulement 143 bits. 1 bit est nécessaire d'indiquer de quel côté est de jouer à côté

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

Déplace - 1 octet
Il y a généralement autour de 30 à 40 coups autorisés pour chaque position, mais le nombre peut être aussi élevé que 218 Permet d'énumérer tous les déplacements pour chaque position. Maintenant, chaque mouvement peut être codé sur un octet.

Nous avons encore beaucoup de place pour les coups spéciaux tels que 0xFF pour représenter sa démission.

Answer 4

L'attaque d'un subproblem de l'encodage de la procédure après une première position a été codé. L'approche est de créer une "liste" des étapes.

Chaque étape dans le jeu est codé comme une "vieille poste->nouvelle position" paire. Vous connaissez la position initiale dans le début du jeu d'échecs; en parcourant la liste des étapes, vous pouvez obtenir de l'etat après X coups.

Pour le codage de chaque étape, vous avez besoin de 64 valeurs à coder la position de départ (6 bits pour 64 places sur la carte - 8x8 cases), et 6 bits pour la position de fin. 16 bits pour 1 déplacer de chaque côté.

Quantité d'espace que le codage d'un jeu donné est alors proportionnelle au nombre de coups:

10 x (nombre de blanc se déplace + nombre de noirs se déplace) bits.

Mise à JOUR: le potentiel de complications avec le promu pions. Besoin pour être en mesure à ce que le pion est promu à des besoins spéciaux bits (utiliserait gris code pour économiser de l'espace, comme la promotion d'un pion est extrêmement rare).

Mise à JOUR 2: Vous n'avez pas à coder la position de fin de coordonnées complètes. Dans la plupart des cas, la pièce qui est déplacé peut se déplacer à plus de X places. Par exemple, un pion peut avoir un maximum de 3 options de déplacement à un moment donné. En se rendant compte que le nombre maximum de coups pour chaque pièce de type, nous pouvons sauver 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

Donc, la complexité spatiale par coup de noir ou de blanc devient

6 bits pour la position initiale + (nombre variable de bits, basé sur le type de la chose qui est déplacé).