Enigma del programmatore:Codifica dello stato della scacchiera durante una partita

https://stackoverflow.com/questions/1831386

11-09-2019
|

Domanda

Non propriamente una domanda, più un enigma...

Nel corso degli anni sono stato coinvolto in alcuni colloqui tecnici con i nuovi dipendenti.Oltre a porre le domande standard "conosci la tecnologia X", ho anche cercato di farmi un'idea di come affrontano i problemi.In genere, invio loro la domanda via e-mail il giorno prima del colloquio e mi aspetto che trovino una soluzione entro il giorno successivo.

Spesso i risultati sarebbero piuttosto interessanti – sbagliati, ma interessanti – e la persona riceverebbe comunque la mia raccomandazione se potesse spiegare perché ha adottato un approccio particolare.

Quindi ho pensato di porre una delle mie domande al pubblico di Stack Overflow.

Domanda: Qual è il modo più efficiente in termini di spazio a cui puoi pensare per codificare lo stato di una partita a scacchi (o un suo sottoinsieme)?Cioè, data una scacchiera con i pezzi disposti legalmente, codifica sia questo stato iniziale che tutte le successive mosse legali intraprese dai giocatori nel gioco.

Nessun codice richiesto per la risposta, solo una descrizione dell'algoritmo che utilizzeresti.

MODIFICARE:Come ha sottolineato uno dei poster, non ho considerato l'intervallo di tempo tra le mosse.Sentiti libero di tenere conto anche di questo come extra opzionale :)

EDIT2:Solo per ulteriori chiarimenti...Ricorda, il codificatore/decodificatore riconosce le regole.Le uniche cose che realmente devono essere memorizzate sono le scelte del giocatore: qualsiasi altra cosa può essere considerata conosciuta dal codificatore/decodificatore.

EDIT3:Sarà difficile scegliere un vincitore qui :) Molte ottime risposte!

Soluzione

Aggiornamento: Questo argomento mi è piaciuto così tanto che ho scritto Puzzle di programmazione, posizioni degli scacchi e codifica Huffman.Se leggi questo ho stabilito che il soltanto Il modo per memorizzare uno stato di gioco completo è memorizzare un elenco completo di mosse.Continua a leggere per sapere perché.Quindi utilizzo una versione leggermente semplificata del problema per il layout del pezzo.

Il problema

Questa immagine illustra la posizione iniziale degli scacchi.Gli scacchi si svolgono su una scacchiera 8x8 con ogni giocatore che inizia con un set identico di 16 pezzi composto da 8 pedoni, 2 torri, 2 cavalieri, 2 alfieri, 1 regina e 1 re come illustrato qui:

Le posizioni sono generalmente registrate come una lettera per la colonna seguita dal numero per la riga, quindi la Donna del Bianco è in d1.Le mosse vengono spesso memorizzate in notazione algebrica, che è inequivocabile e generalmente specifica solo le informazioni minime necessarie.Considera questa apertura:

e4 e5
Cf3 NCc6
…

che si traduce in:

Il bianco muove il pedone del re da e2 a e4 (è l’unico pezzo che può arrivare in e4 quindi “e4”);
Il Nero muove il pedone del Re da e7 a e5;
Il bianco muove il Cavallo (N) in f3;
Il Nero muove il Cavallo in c6.
…

La scheda si presenta così:

Un'abilità importante per qualsiasi programmatore è essere in grado di farlo specificare correttamente e inequivocabilmente il problema.

Quindi cosa manca o è ambiguo?Moltissimo a quanto pare.

Stato del tabellone e stato del gioco

La prima cosa che devi determinare è se stai memorizzando lo stato di una partita o la posizione dei pezzi sulla scacchiera.Codificare semplicemente le posizioni dei pezzi è una cosa, ma il problema riguarda “tutte le successive mosse legali”.Il problema non dice nemmeno nulla sulla conoscenza delle mosse fino a questo punto.Questo è in realtà un problema, come spiegherò.

Arrocco

Il gioco si è svolto come segue:

e4 e5
Cf3 NCc6
Bb5 la6
Ba4 Ac5

La scheda si presenta come segue:

later opening

Il bianco ha l’opzione di arrocco.Parte dei requisiti per questo è che il re e la relativa torre non possano mai essersi mossi, quindi sarà necessario memorizzare se il re o una delle torri di ciascun lato si è mosso.Ovviamente se non sono nella posizione di partenza si sono spostati altrimenti è necessario specificarlo.

Esistono diverse strategie che possono essere utilizzate per affrontare questo problema.

Innanzitutto, potremmo memorizzare altri 6 bit di informazione (1 per ogni torre e re) per indicare se quel pezzo si è mosso.Potremmo semplificare il tutto memorizzando solo un po' per uno di questi sei quadrati se al suo interno si trova il pezzo giusto.In alternativa potremmo trattare ogni pezzo non mosso come un altro tipo di pezzo, quindi invece di 6 tipi di pezzi su ciascun lato (pedone, torre, cavaliere, alfiere, regina e re) ce ne sono 8 (aggiungendo torre non mossa e re non mosso).

En Passant

Un'altra regola peculiare e spesso trascurata negli scacchi è En Passant.

Il gioco è andato avanti.

e4 e5
Cf3 NCc6
Bb5 la6
Ba4 Ac5
O-O b5
Sib3 si4
c4

Il pedone nero in b4 ora ha la possibilità di spostare il suo pedone in b4 in c3 prendendo il pedone bianco in c4.Ciò accade solo alla prima opportunità, il che significa che se il Nero cede l'opzione ora non potrà eseguirla la mossa successiva.Quindi dobbiamo memorizzarlo.

Se conosciamo la mossa precedente possiamo sicuramente rispondere se En Passant è possibile.In alternativa possiamo memorizzare se ogni pedone della 4a traversa si è appena mosso lì con un doppio movimento in avanti.Oppure possiamo guardare ogni possibile posizione En Passant sul tabellone e avere una bandiera per indicare se è possibile o meno.

Promozione

È la mossa del Bianco.Se il Bianco muove il suo pedone da h7 a h8, può essere promosso a qualsiasi altro pezzo (ma non al re).Il 99% delle volte viene promossa a Regina, ma a volte non lo è, in genere perché ciò potrebbe forzare uno stallo quando altrimenti vinceresti.Questo è scritto come:

h8=Q

Questo è importante nel nostro problema perché significa che non possiamo contare sul numero fisso di pezzi su ciascun lato.È del tutto possibile (ma incredibilmente improbabile) che una parte finisca con 9 regine, 10 torri, 10 alfieri o 10 cavalieri se tutti gli 8 pedoni vengono promossi.

Stallo

Quando ti trovi in una posizione dalla quale non puoi vincere, la tua tattica migliore è provare a stallo.La variante più probabile è quella in cui non puoi effettuare una mossa legale (di solito perché qualsiasi mossa mette il tuo re sotto controllo).In questo caso puoi richiedere il pareggio.Questo è facile da soddisfare.

La seconda variante è di triplice ripetizione.Se la stessa posizione sul tabellone si verifica tre volte in una partita (o si verificherà una terza volta alla mossa successiva), si può richiedere un pareggio.Non è necessario che le posizioni siano presenti in un ordine particolare (il che significa che non è necessario ripetere la stessa sequenza di mosse tre volte).Questo complica notevolmente il problema perché devi ricordare ogni posizione precedente sulla scacchiera. Se questo è un requisito del problema, l'unica soluzione possibile al problema è memorizzare ogni mossa precedente.

Infine, c'è il regola delle cinquanta mosse.Un giocatore può richiedere la patta se nessun pedone si è mosso e nessun pezzo è stato preso nelle precedenti cinquanta mosse consecutive, quindi dovremmo memorizzare quante mosse da quando è stato mosso un pedone o preso un pezzo (l'ultima delle due).Ciò richiede 6 bit (0-63).

Di chi è il turno?

Naturalmente dobbiamo anche sapere a chi tocca il turno e questa è solo un'informazione.

Due problemi

A causa del caso di stallo, l'unico modo fattibile o sensato per memorizzare lo stato del gioco è memorizzare tutte le mosse che hanno portato a questa posizione.Affronterò questo problema.Il problema dello stato del consiglio sarà semplificato in questo modo: memorizzare la posizione attuale di tutti i pezzi sulla scacchiera ignorando le condizioni di arrocco, en passant, stallo e di chi è il turno.

Il layout del pezzo può essere gestito in generale in due modi:memorizzando il contenuto di ciascun quadrato o memorizzando la posizione di ciascun pezzo.

Contenuti semplici

Ci sono sei tipi di pezzi (pedone, torre, cavallo, alfiere, regina e re).Ogni pezzo può essere bianco o nero, quindi un quadrato può contenere uno dei 12 pezzi possibili oppure può essere vuoto, quindi ci sono 13 possibilità.13 possono essere memorizzati in 4 bit (0-15). Quindi la soluzione più semplice è memorizzare 4 bit per ogni quadrato moltiplicato per 64 quadrati o 256 bit di informazione.

Il vantaggio di questo metodo è che la manipolazione è incredibilmente facile e veloce.Ciò potrebbe anche essere esteso aggiungendo altre 3 possibilità senza aumentare i requisiti di spazio di archiviazione:un pedone che si è mosso di 2 spazi nell'ultimo turno, un re che non si è mosso e una torre che non si è mossa, il che risolverà molti dei problemi menzionati in precedenza.

Ma possiamo fare di meglio.

Codifica base 13

Spesso è utile pensare alla posizione nel consiglio come a un numero molto grande.Questo viene spesso fatto in informatica.Ad esempio, il problema dell'arresto tratta un programma per computer (giustamente) come un grande numero.

La prima soluzione tratta la posizione come un numero di 64 cifre in base 16 ma, come dimostrato, c'è ridondanza in queste informazioni (essendo le 3 possibilità inutilizzate per “cifra”), quindi possiamo ridurre lo spazio numerico a 64 cifre in base 13.Naturalmente questo non può essere fatto in modo efficiente come la base 16, ma farà risparmiare sui requisiti di archiviazione (e ridurre al minimo lo spazio di archiviazione è il nostro obiettivo).

In base 10 il numero 234 equivale a 2 x 10² + 3×10¹ +4×10⁰.

In base 16 il numero 0xA50 equivale a 10 x 16² +5×16¹ +0×16⁰ = 2640 (decimale).

Quindi possiamo codificare la nostra posizione come p₀ x13⁶³ + pag₁ x13⁶² +...+ pag₆₃ x13⁰ dove pag_io rappresenta il contenuto del quadrato io.

2²⁵⁶ equivale a circa 1,16e77.13⁶⁴ equivale a circa 1,96e71, che richiede 237 bit di spazio di archiviazione.Quel risparmio di appena il 7,5% ha un costo di in modo significativo aumento dei costi di manipolazione.

Codifica base variabile

Nelle plance legali alcuni pezzi non possono apparire in determinate caselle.Ad esempio, i pedoni non possono trovarsi nella prima o nell'ottava traversa, riducendo le possibilità per quelle caselle a 11.Ciò riduce le tavole possibili a 11¹⁶ x13⁴⁸ = 1,35e70 (circa), che richiede 233 bit di spazio di archiviazione.

In realtà codificare e decodificare tali valori da e verso decimale (o binario) è un po' più complicato ma può essere fatto in modo affidabile e viene lasciato come esercizio al lettore.

Alfabeti a larghezza variabile

I due metodi precedenti possono essere entrambi descritti come codifica alfabetica a larghezza fissa.Ciascuno degli 11, 13 o 16 membri dell'alfabeto viene sostituito con un altro valore.Ogni "carattere" ha la stessa larghezza, ma l'efficienza può essere migliorata se si considera che ogni carattere non ha la stessa probabilità.

morse code

Prendere in considerazione codice Morse (nella foto sopra).I caratteri in un messaggio sono codificati come una sequenza di trattini e punti.Quei trattini e punti vengono trasferiti via radio (tipicamente) con una pausa tra loro per delimitarli.

Notare come la lettera E (la lettera più comune in inglese) è un punto singolo, la sequenza più breve possibile, mentre Z (la meno frequente) è composta da due trattini e due bip.

Un tale schema può ridurre significativamente le dimensioni di un previsto messaggio ma ha il costo di aumentare la dimensione di una sequenza di caratteri casuale.

Va notato che il codice Morse ha un'altra caratteristica incorporata:i trattini sono lunghi fino a tre punti, quindi il codice precedente viene creato tenendo presente questo per ridurre al minimo l'uso dei trattini.Poiché gli 1 e gli 0 (i nostri elementi costitutivi) non presentano questo problema, non è una funzionalità che dobbiamo replicare.

Infine, ci sono due tipi di pause nel codice Morse.Una pausa breve (la lunghezza di un punto) viene utilizzata per distinguere tra punti e trattini.Uno spazio più lungo (la lunghezza di un trattino) viene utilizzato per delimitare i caratteri.

Allora come si applica questo al nostro problema?

Codifica Huffman

Esiste un algoritmo per gestire i codici a lunghezza variabile chiamato Codifica di Huffman.La codifica di Huffman crea una sostituzione del codice di lunghezza variabile, in genere utilizza la frequenza prevista dei simboli per assegnare valori più brevi ai simboli più comuni.

Nell'albero sopra, la lettera E è codificata come 000 (o sinistra-sinistra-sinistra) e S è 1011.Dovrebbe essere chiaro che questo schema di codifica lo è inequivocabile.

Questa è una distinzione importante dal codice Morse.Il codice Morse ha il separatore di caratteri quindi può fare sostituzioni altrimenti ambigue (ad esempio 4 punti possono essere H o 2 Is) ma abbiamo solo 1 e 0 quindi scegliamo invece una sostituzione non ambigua.

Di seguito è riportata una semplice implementazione:

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

con dati statici:

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

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

Un possibile output è:

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

Per una posizione iniziale ciò equivale a 32 x 1 + 16 x 3 + 12 x 5 + 4 x 6 = 164 bit.

Differenza di stato

Un altro approccio possibile è combinare il primo approccio con la codifica di Huffman.Ciò si basa sul presupposto che la maggior parte delle scacchiere previste (piuttosto che quelle generate casualmente) hanno maggiori probabilità di assomigliare, almeno in parte, a una posizione di partenza.

Quindi quello che fai è XOR della posizione corrente della scheda a 256 bit con una posizione iniziale a 256 bit e poi codificarla (usando la codifica Huffman o, diciamo, qualche metodo di codifica della lunghezza di esecuzione).Ovviamente questo sarà molto efficiente per iniziare (64 0 probabilmente corrispondono a 64 bit) ma aumenterà lo spazio di archiviazione richiesto man mano che il gioco procede.

Posizione del pezzo

Come accennato in precedenza, un altro modo per affrontare questo problema è memorizzare la posizione di ciascun pezzo posseduto da un giocatore.Funziona particolarmente bene con le posizioni di fine gioco in cui la maggior parte dei quadrati sarà vuota (ma nell'approccio di codifica di Huffman i quadrati vuoti utilizzano comunque solo 1 bit).

Ogni lato avrà un re e 0-15 altri pezzi.A causa della promozione, la composizione esatta di questi pezzi può variare abbastanza da non poter presumere che i numeri basati sulle posizioni di partenza siano massimi.

Il modo logico per dividerlo è memorizzare una Posizione composta da due Lati (Bianco e Nero).Ciascun lato ha:

Un re:6 bit per la posizione;
Ha pedoni:1 (sì), 0 (no);
Se sì, numero di pedoni:3 bit (0-7+1 = 1-8);
Se sì, la posizione di ciascuna pedina è codificata:45 bit (vedi sotto);
Numero di non pedoni:4 bit (0-15);
Per ogni pezzo:tipo (2 bit per regina, torre, cavallo, alfiere) e posizione (6 bit)

Per quanto riguarda la posizione dei pedoni, i pedoni possono trovarsi solo su 48 case possibili (non 64 come le altre).Pertanto, è meglio non sprecare i 16 valori extra che utilizzerebbero utilizzando 6 bit per pedone.Quindi se hai 8 pedoni ce ne sono 48⁸ possibilità, pari a 28.179.280.429.056.Sono necessari 45 bit per codificare così tanti valori.

Sono 105 bit per lato o 210 bit in totale.Tuttavia, la posizione iniziale è il caso peggiore per questo metodo e migliorerà notevolmente man mano che rimuovi i pezzi.

Va precisato che sono meno di 48⁸ possibilità perché i pedoni non possono essere tutti nella stessa casa. La prima ha 48 possibilità, la seconda 47 e così via.48 x 47 x … x 41 = 1,52e13 = memoria a 44 bit.

Puoi migliorare ulteriormente questo aspetto eliminando le caselle occupate da altri pezzi (incluso l'altro lato) in modo da poter posizionare prima i pedoni bianchi, poi i pedoni neri, poi i pedoni bianchi e infine i pedoni neri.In una posizione iniziale ciò riduce i requisiti di archiviazione a 44 bit per il Bianco e 42 bit per il Nero.

Approcci combinati

Un’altra possibile ottimizzazione è che ciascuno di questi approcci ha i suoi punti di forza e di debolezza.Potresti, ad esempio, scegliere i migliori 4 e quindi codificare un selettore di schema nei primi due bit e successivamente l'archiviazione specifica dello schema.

Con un sovraccarico così ridotto, questo sarà di gran lunga l'approccio migliore.

Stato del gioco

Torno al problema della memorizzazione di a gioco piuttosto che a posizione.A causa della tripla ripetizione dobbiamo memorizzare l'elenco delle mosse che si sono verificate fino a questo punto.

Annotazioni

Una cosa che devi determinare è se stai semplicemente memorizzando un elenco di mosse o stai annotando il gioco?Le partite di scacchi sono spesso annotate, ad esempio:

Sib5!!NCc4?

La mossa del Bianco è contrassegnata da due punti esclamativi come brillante mentre quella del Nero è vista come un errore.Vedere Punteggiatura degli scacchi.

Inoltre potrebbe essere necessario memorizzare del testo libero man mano che vengono descritte le mosse.

Presumo che le mosse siano sufficienti, quindi non ci saranno annotazioni.

Notazione algebrica

Potremmo semplicemente memorizzare qui il testo della mossa (“e4”, “Axb5”, ecc.).Includendo un byte finale, stai guardando circa 6 byte (48 bit) per mossa (caso peggiore).Non è particolarmente efficiente.

La seconda cosa da provare è memorizzare la posizione iniziale (6 bit) e la posizione finale (6 bit), quindi 12 bit per mossa.Questo è decisamente meglio.

In alternativa possiamo determinare tutte le mosse legali dalla posizione attuale in modo prevedibile e deterministico e stabilire quale abbiamo scelto.Questo poi risale alla codifica base variabile menzionata sopra.Il Bianco e il Nero hanno 20 mosse possibili ciascuno alla prima mossa, di più alla seconda e così via.

Conclusione

Non esiste una risposta assolutamente giusta a questa domanda.Esistono molti approcci possibili, di cui quelli sopra riportati sono solo alcuni.

Ciò che mi piace di questo e di problemi simili è che richiede abilità importanti per qualsiasi programmatore, come considerare il modello di utilizzo, determinare con precisione i requisiti e pensare a casi limite.

Posizioni degli scacchi prese come screenshot da Allenatore di posizione degli scacchi.

Altri suggerimenti

E 'meglio solo per memorizzare i giochi di scacchi in un formato leggibile, di serie.

Il portatile Notation gioco assume una posizione di partenza standard (anche se non deve ) e appena elenca le mosse, svolta dopo svolta. Un compatto,, formato standard leggibile.

per es.

[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

Se si desidera renderlo più piccolo, quindi solo zip . Lavoro fatto!

grande puzzle!

Vedo che la maggior parte delle persone sono memorizzare la posizione di ogni pezzo. Che ne dite di un approccio più ingenui, e memorizzare il contenuto di ogni quadrato ? Che si occupa automaticamente di promozione e pezzi catturati.

E permette di Codifica Huffman . In realtà, la frequenza iniziale di pezzi sulla scacchiera è quasi perfetta per questo. Metà dei quadrati sono vuoti, la metà dei restanti piazze sono pedine, eccetera

Considerando la frequenza di ogni singolo pezzo, ho costruito un Huffman albero su carta, che non ripeterò qui. Il risultato, in cui c sta per il colore (bianco = 0, nero = 1):

0 per piazze vuote
1C0 per pedone
1c100 per Torre
1C101 per cavaliere
1c110 per il vescovo
1c1110 per la regina
1c1111 per il re

Per tutto il forum nella sua situazione di partenza, abbiamo

quadrati vuoti: 32 * 1 bit = 32 bit
pedine: 16 * 3 bit = 48 bit
Rooks / cavalieri / Vescovi: 12 * 5 bit = 60 bit
regine / re: 4 * 6 bit = 24 bit

totale: 164 bit per il iniziale Stato bordo. Significativamente inferiore 235 bit della risposta massima attualmente ritenute. Ed è solo andando a diminuire nel corso del gioco (tranne dopo una promozione).

Ho guardato solo alla posizione dei pezzi sulla scacchiera; stato aggiuntivo (di turno, che ha arroccato, en passant, ripetendo movimenti, etc.) dovrà essere codificato separatamente. Forse un altro 16 bit al massimo, in modo che 180 bit per l'intero stato del gioco. Possibili ottimizzazioni:

Tralasciando le parti meno frequenti, e memorizzare la loro posizione separatamente. Ma questo non aiuterà ... sostituendo re e la regina da una casella vuota salva 5 bit, che sono esattamente i 5 bit necessari per codificare la loro posizione in un altro modo.
"Non ci sono pedine sulla fila posteriore" potrebbero essere facilmente codificati utilizzando una tabella di Huffman differente per le ultime file, ma dubito che aiuta molto. Si sarebbe probabilmente ancora finire con lo stesso albero di Huffman.
"Uno bianca, un vescovo nero" possono essere codificati con l'introduzione di simboli aggiuntivi che non hanno il bit c, che possono poi essere dedotto dalla piazza che il vescovo è in funzione. (Pedoni promossi ai vescovi interrompere questo schema ...)
ripetizioni di caselle vuote potrebbe essere run-length codificato introducendo simboli aggiuntivi per, ad esempio, "2 quadrati vuoti in una riga" e "4 caselle vuote in una riga". Ma non è così facile da stimare la frequenza di questi, e se si sbaglia, sta andando a male, piuttosto che di aiuto.

L'approccio veramente grande tabella di ricerca

posizione - 18 byte
Stima del numero di posizioni giuridiche è 10 ⁴³
Semplicemente li enumerare e la posizione può essere memorizzata in soli 143 pezzi. è richiesto 1 più bit per indicare quale lato è quello di giocare il prossimo

L'enumerazione non è pratico, naturalmente, ma questo dimostra che almeno 144 bit sono necessari.

Passa - 1 byte
Di solito ci sono circa 30-40 mosse legali per ogni posizione, ma il numero potrebbe essere alto come 218 Consente di enumerare tutte le mosse legali per ogni posizione. Ora ogni mossa può essere codificato in un byte.

Abbiamo ancora un sacco di spazio per mosse speciali come 0xFF per rappresentare le dimissioni.

Sarebbe aggiungere interesse per ottimizzare per caso medio dimensioni per i giochi tipici giocate dagli esseri umani, al posto del caso peggiore. (La dichiarazione del problema non dice quale;. Maggior parte delle risposte assumono caso peggiore)

Per la sequenza di spostamento, hanno un buon motore scacchi generare sposta da ciascuna posizione; esso produrrà un elenco di k possibili mosse, ha ordinato per la sua classifica delle loro qualità. Le persone generalmente prendono buone mosse più spesso di quanto si muove a caso, quindi abbiamo bisogno di imparare una mappatura da ogni posizione nella lista per la probabilità che persone prendere una mossa che 'buono'. Usando queste probabilità (sulla base di un corpus di giochi da parte di alcuni database di internet scacchi), codificare i si muove con codifica aritmetica . (Il decodificatore deve utilizzare lo stesso motore scacchi e mappatura.)

Per la posizione di partenza, l'approccio di Ralu avrebbe funzionato. Potremmo rifinire con codifica aritmetica anche lì, se abbiamo avuto qualche modo per ponderare le scelte di probabilità - per esempio pezzi appaiono spesso nelle configurazioni difendere l'altro, non a caso. E 'difficile vedere un modo semplice per incorporare questa conoscenza. Un'idea: ripiegare su codifica movimento sopra invece, partendo dalla posizione di apertura normale e trovare una sequenza che termina nella scheda desiderata. (Si potrebbe provare una ricerca * con una distanza euristica pari alla somma delle distanze di pezzi dalle loro posizioni finali, o qualcosa del genere). Questo scambia qualche inefficienza dal overspecifying la sequenza di spostamento rispetto al rendimento di approfittare di che gioca a scacchi conoscenza. (È possibile riguadagnare alcune delle inefficienze, eliminando scelte mossa che porterebbe ad una posizione precedentemente esplorato in A * di ricerca:. Questi possono ottenere peso 0 nel codice aritmetica)

E 'anche un po' difficile stimare la quantità di risparmio questo sarebbe comprarti nel caso medio complessità, senza la raccolta di alcune statistiche da un corpus reale. Ma il punto di partenza di tutte le mosse ugualmente probabili penso che sarebbe già battere la maggior parte delle proposte qui: la codifica aritmetica non ha bisogno di un numero intero di bit per spostare

Attaccare un sottoproblema di codificare le operazioni dopo una posizione iniziale è stata codificata. L'approccio è quello di creare una "lista collegata" di passi.

Ogni fase del gioco è codificato come il "vecchio Posizione-> nuova posizione" coppia. Sai la posizione iniziale all'inizio della partita a scacchi; attraversando la lista collegata di passi, è possibile ottenere lo stato dopo X si muove.

Per codificare ogni passo, è necessario 64 valori per codificare la posizione di partenza (6 bit per 64 caselle sulla nave - quadrati 8x8) e 6 bit per la posizione finale. 16 bit per 1 giocata ogni lato.

quantità di spazio che codifica un dato gioco prenderebbe è quindi proporzionale al numero di mosse:

10 x (numero di mosse bianchi + numero di mosse nere) bit.

UPDATE: potenziale complicazione con pedine promosse. Hai bisogno di essere in grado di affermare ciò che il pedone è promosso a - può avere bisogno di bit speciali (userebbe il codice grigio per questo per risparmiare spazio, come promozione del pedone è estremamente raro).

UPDATE 2: Non è necessario codificare le coordinate complete della posizione finale. Nella maggior parte dei casi, il pezzo che viene mosso si può muovere a non più di posti di X. Ad esempio, un pedone può avere un massimo di 3 opzioni di spostamento in ogni punto. Realizzando che il numero massimo di mosse per ogni tipo di pezzo, possiamo risparmiare bit sulla codifica del "destinazione".

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

Quindi la complessità spaziale per mossa di diventa nero o bianco

6 bit per la posizione iniziale + (numero variabile di bit sulla base del tipo di cosa che è spostato).

Ho visto questa domanda ieri sera e mi ha incuriosito così mi sono seduto a letto escogitare soluzioni. La mia risposta finale è molto simile a INT3 di realtà.

soluzione di base

Supponendo una partita a scacchi standard e che non codificare le regole (come bianco va sempre prima), allora si può risparmiare un sacco codificando solo le mosse ogni pezzo fa.

Ci sono 32 pezzi totale, ma in ogni mossa si sa di che colore si muove quindi non c'è solo 16 piazze di cui preoccuparsi, che è 4 bit per il quale pezzo si muove in questo turno.

Ogni pezzo ha solo moveset limitata, che si sarebbe enumerare in qualche modo.

Pegno: 4 opzioni, 2 bit (1 passo avanti, 2 passi avanti, 1 ogni diagonale)
Rook: 14 opzioni, 4 bit (massimo di 7 rispettivamente)
Vescovo: 13 opzioni, 4 bit (se si dispone di 7 in una diagonale, hai solo 6 nell'altro)
Cavaliere: 8 punti, 3 bit
Queen: 27 opzioni, 5 bit (Rook + Bishop)
Re: 9 opzioni, 4 bit (8 si muove un passo, più l'opzione arrocco)

Per la promozione, ci sono 4 pezzi tra cui scegliere (Rook, Vescovo, Cavaliere, Queen) così via che si muovono aggiungiamo noi 2 bit per specificare che. Credo che tutte le altre regole sono coperti automaticamente (ad esempio en passant).

Ulteriori ottimizzazioni

Innanzitutto, dopo 8 parti di uno stesso colore sono stati catturati, si potrebbe ridurre la codifica pezzo da 3 bit, quindi 2 bit per 4 pezzi e così via.

L'ottimizzazione principale è però di elencare solo le possibili mosse in ogni punto del gioco. Assumiamo memorizzare le mosse di un pedone come {00, 01, 10, 11} per 1 passo avanti, 2 passi avanti, diagonale sinistra e destra rispettivamente diagonale. Se alcune mosse non sono possibili possiamo rimuoverle dalla codifica per questo turno.

Sappiamo che lo stato del gioco in ogni fase (dal seguire tutte le mosse), quindi dopo aver letto che pezzo sta per muoversi, si può sempre determinare quanti bit abbiamo bisogno di leggere. Se ci rendiamo conto solo mosse di un pedone a questo punto sono la cattura in diagonale a destra o andare avanti uno, sappiamo leggere solo 1 bit.

In breve, il bit di memoria sopra elencati per ogni parte è un massima solo. Quasi ogni mossa avrà un minor numero di opzioni e spesso meno bit.

In ogni posizione ottenere il numero di tutte le possibili mosse.

prossima mossa viene generato come

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

dimostrabilmente migliore efficienza spazio per la memorizzazione di gioco generato casualmente e serve circa 5 bits / mossa in media dal avete 30-40 possibili mosse. Assemblare stoccaggio è solo generando n in ordine inverso.

memorizzazione della posizione è più difficile da decifrare, perché di grande ridondanza. (Ci possono essere fino a 9 regine a bordo per un sito, ma in quel caso non ci sono pedine, e vescovi se sulla scheda sono in quadrati colorati opposte), ma in generale è come memorizzare combinazione delle stesse pezzi su piazze rimanenti.)

Modifica

Point a risparmio si muove è quello di memorizzare solo l'indice di movimento. Invece di memorizzare KC1-C2 e cercando di ridurre queste informazioni dobbiamo aggiungere solo indice del movimento generato da movegenerator deterministico (posizione)

A ogni mossa aggiungiamo informazioni di formato

num_of_moves = get_number_of_possible_moves(postion) ;

in piscina e questo numero non può essere ridotto

generando piscina informazione è

n=n*num_of_moves+ index_current_move

più

Se c'è solo una mossa disponibile in posizione finale, salvo quanto numero di mosse forzate in precedenza fatto. Esempio:. Se posizione di partenza ha 1 mosse forzate per ogni lato (2 mosse) e vogliamo salvare questo come un gioco mossa, negozio di 1 in pool n

esempio di memorizzazione in informazioni piscina

Consente supponiamo che abbiamo conosciuto posizioni di partenza e noi fare 3 mosse.

In primo movimento ci sono 5 mosse disponibili, e prendiamo indice mossa 4. Nella seconda mossa ci sono 6 mosse disponibili e prendiamo indice di posizione 3 e in movimento 3 ° ci sono 7 si sposta disponibili per quel lato e ha scelto di raccogliere l'indice di movimento 2.

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

Siamo codifica queste informazioni all'indietro, quindi n = 4 + 5 * (3 + 6 * (2)) = 79 (senza moltiplicatore da 7 necessario)

Come unloop questo? In primo luogo abbiamo la posizione e scopriamo che ci sono 5 mosse disponibili. Quindi

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

Prendiamo indice mossa 4 ed esaminare di nuovo la posizione e da questo punto scopriamo che ci sono 6 possibili mosse.

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

E prendiamo indice mossa 3, che ci porta ad una posizione con 7 mosse possibili.

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

Facciamo indice ultima mossa 2 e raggiungiamo posizione finale.

Come si può vedere il tempo di complessità è O (n) ansd spazio complessità è O (n). Edit:. Complessità temporale è in realtà O (n ^ 2) perché il numero multipy da aumenti, ma non ci dovrebbero essere problemi memorizzare i giochi fino a 10.000 movimenti

posizione risparmio

Può essere fatto vicino alla ottimale.

Quando troviamo conoscere informazioni Informazioni stoccaggio Permettetemi di parlare di più. idea generale è quello di ridurre la ridondanza (ne parlerò più avanti). Consente di presumere che non ci sono promozioni e nessuna assunzione per cui ci sono 8 pedine, 2 torri, 2 cavalieri, 2 vescovi 1 letto king e 1 queen per lato.

Che cosa dobbiamo salvare: 1. posizione di ogni pace 2. posibilities di arrocco 3. possibilità di en-passant 4. lato che ha spostare available

Supponiamo che ogni pezzo può stare ovunque, ma non 2 pezzi a stesso luogo. Numero di modi 8 pedine dello stesso colore possono essere disposte a bordo è C (64/8) (binomiale), che è di 32 bit, quindi 2 torri 2R-> C (56/2), 2B -> C (54/2) , 2N-> C (52/2), 1Q-> C (50/1), 1K -> C (49/1), e lo stesso per altri siti, ma a partire da 8P -> C (48/8) e così via .

Moltiplicando questo insieme per entrambi i siti a ottenere il numero 4634726695587809641192045982323285670400000 che è di circa 142 bit, dobbiamo aggiungere 8 per una possibile en-passant (en-passant pedone può essere in una delle 8 posti), 16 (4 bit) per arrocco limitazioni e un po 'per il sito che ha muoversi. Si finisce con 142 + 3 + 4 + 1 = 150bits

Ma ora andiamo a caccia per la ridondanza sul bordo con 32 pezzi e nessuna assunzione.

sia in bianco e neropedine sono sulla stessa colonna e di fronte all'altro. Ogni pedina si trova ad affrontare altre pedina che significa che pedone bianco può essere al massimo al 6 ° rango. Questo ci porta 8 * C (6/2) invece di C (64/8) * C (48/8), che diminuiscono informazioni da 56 bit.
possibilità di arrocco è ridondante. Se corvi non sono in partenza posto v'è alcuna possibilità arrocco di Pentecoste che torre. Così possiamo imaginaly aggiungere 4 caselle a bordo per ottenere le informazioni in più se l'arrocco di Pentecoste questa torre è possibile rimuovere e 4 bit arrocco. Così, invece di C (56/2) * C (40/2) * 16 abbiamo C (58/2) * C (42/2) e abbiamo perso 3.76 bit (quasi tutti di 4 bit)
en-passant: Quando abbiamo memorizzare una delle 8 en possibilites passant, sappiamo posizione del pedone nero e ridurre redindancy informativo (se è mossa bianco e ha pedina 3 ° en-passant che significa che pedone nero è sulla pedina c5 e nero è o c2, c3 o c4) così posto della C (6/2) abbiamo 3 e perso 2.3 bit. Diminuiamo una certa ridondanza, se memorizziamo numero di Pentecoste en-passant anche lato dal quale si può fare (3 possibilities-> sinistra, a destra, entrambi) e sappiamo che il possiton di pegno che può assumere en passant. (Ad esempio da prevous en esempio passant nero di Pentecoste in c5 ciò che può essere a sinistra, a destra o entrambi. Se è su un sito che abbiamo 2 * 3 (3 per psissibilites archiviazione e 2 possibili mosse per pedone nero su 7 ° o 6 rango ) invece di C (6/2) e riduciamo di 1,3 bit e se il boths lati riduciamo da 4.2 bit. in questo modo si può ridurre di 2.3 + 1.3 = 3.6 bit per en passant.
vescovi:. Bisops possono essere su piazze opostite solo, questo ridurre la ridondanza di 1 bit per ogni sito

Se sommiamo abbiamo bisogno 150-56-4-3.6-2 = 85bits per memorizzare la posizione degli scacchi se non ci fossero gli incassi

E probabilmente non molto di più se ci sono incassi e promozioni prese in considerazione (ma io scriverò su che più tardi se qualcuno troverà questo lungo post utile)

La maggior parte delle persone sono state codifica il Consiglio di Stato, ma per quanto riguarda i movimenti stessi .. Ecco una descrizione po-codifica.

Bit per pezzo:

Parte-ID: Max 4 bit per identificare le 16 parti per lato. Bianco / nero può dedurre. Avere un ordinamento definito sui pezzi. Poiché il numero di pezzi scende sotto le rispettive potenze di due, usare meno bit per descrivere i pezzi rimanenti.
Pegno: 3 possibilità sul primo movimento, così +2 bit (. Avanti di una o due piazze, en passant) si muove successivi non permette lo spostamento in avanti da due, così +1 bit è sufficiente. Promozione può dedurre nel processo di decodifica notando quando il pedone ha colpito l'ultimo rango. Se il pedone è noto per essere promosso, il decoder durante altri 2 bit che indicano quale delle 4 parti principali è stato promosso.
Bishop: 1 bit per diagonale utilizzato, fino a +4 bit per la distanza lungo le diagonali (16 possibilità). Il decodificatore può dedurre la massima distanza possibile che il pezzo può muoversi lungo tale diagonale, quindi se è una diagonale corta, usare meno bit.
cavaliere: 8 mosse possibili, +3 bit
Rook: 1 bit per orizzontale / verticale, +4 bit per distanza lungo la linea
Re: 8 mosse possibili, +3 bit. Indicare l'arrocco con una mossa 'impossibile' - dal momento che l'arrocco è possibile solo mentre il re è al primo rango, codificare questa mossa con un'istruzione di spostare il re 'a ritroso' -. Vale a dire fuori del consiglio di amministrazione
Queen: 8 direzioni possibili, + 3bits. Fino a +4 più bit per la distanza lungo la linea / diagonale (meno se la diagonale è più breve, come nel caso del vescovo)

Supponendo tutti i pezzi sono sul bordo, questi sono i bit per mossa: pedone - 6 bit sulla prima mossa, 5 successivamente. 7 se promosso. Vescovo: 9 bit (max), Cavaliere: 7, Rook: 9, Re: 7, Regina:. 11 (max)

Il problema è di dare una codifica che è più efficiente per i giochi tipici di scacchi, o uno che ha la codifica più breve caso peggiore?

Per questi ultimi, il modo più efficiente è anche il più opaco: creare un'enumerazione di tutte le possibili coppie (bordo iniziale, sequenza di mosse legali), che, con il sorteggio contro tre volte ripetuta posizione e no- più-che-cinquanta mosse dal regole ultimo pedone-move-o-capture, è ricorsiva. Allora l'indice di una posizione in questa sequenza finita dà la codifica caso peggiore più breve, ma anche e altrettanto lunga codifica per casi tipici, ed è, mi aspetto, molto costoso da calcolare. La più lunga partita a scacchi possibile dovrebbe essere più di 5000 movimenti, con là tipicamente essendo 20-30 mosse disponibili in ogni posizione ad ogni giocatore (anche se meno quando ci sono pochi pezzi a sinistra) - questo dà qualcosa come 40000 bit necessari per questa codifica.

L'idea di censimento può essere applicata per dare una soluzione più trattabile, come descritto nel suggerimento di Henk Holterman per la codifica muove sopra. Il mio suggerimento: non minimale, ma più breve rispetto agli esempi sopra che ho guardato, e ragionevole trattabili:

64 bit per rappresentare quali piazze occupate (matrice occupazione), più elenco di cui pezzi sono in ciascuna casella occupata (possono avere 3 bit per pedoni, e 4 bit di altri pezzi): questo dà 190 bit per posizione di partenza. Poiché non vi può essere più di 32 pezzi a bordo, la codifica della matrice occupazione è ridondante e così qualcosa come posizioni di bordo comuni possono essere codificati, come dire 33 bit impostati inclusa indice di bordo dalla lista tavole comune.
1 bit di dire chi fa la prima mossa
si sposta di codice per il suggerimento di Henk: tipicamente 10 bit per coppia di bianco / nero mossa, anche se alcune mosse prenderanno 0 bit, quando un giocatore non ha mosse alternative

Questo suggerisce 490 bit per codificare un tipico gioco di 30-move, e sarebbe una rappresentazione ragionevolmente efficiente per i giochi tipici.

abouth codifica la posizione draw-on-tre volte ripetute e no-more-cinquanta-moves che-dal regole ultimo pedone-move-o-Capture: se si codifica thepast arretra per l'ultima mossa di pedone o la cattura , allora si dispone di informazioni sufficienti per decidere se applicare queste regole:. non c'è bisogno di tutta la storia del gioco

La posizione su una scheda può essere definita in 7 bit (0-63, e 1 valore che specifica che non è sul bordo più). Quindi per ogni pezzo sulla scacchiera specificare dove si trova.

32 parti * 7 bit = 224 bit

EDIT: come Cadrian sottolineato ... abbiamo anche la 'pedina promosso Regina' caso. Suggerisco aggiungiamo bit extra al termine per indicare quale pedina sono stati promossi.

Quindi, per ogni pegno, che è stato promosso seguiamo i 224 bit con 5 bit che indicano l'indice del pedone che è stato promosso, e 11111 se è la fine della lista.

caso talmente minima (senza promozioni) è 224 bit + 5 (senza promozioni). Per ogni pegno promosso aggiungere 5 bit.

EDIT: Come sottolinea irsuto rana, abbiamo bisogno di un altro po 'alla fine per indicare chi è il turno; ^)

mi piacerebbe utilizzare una codifica tiratura. Alcuni pezzi sono unici (o esistono solo due volte), quindi posso omettere la lunghezza dopo di loro. Come Cletus, ho bisogno di 13 stati unici, in modo da poter utilizzare un bocconcino (4 bit) per codificare il pezzo. La scheda iniziale sarebbe quindi simile a questa:

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

che mi lascia con 8 + 2 + 4 + 2 + 8 nibble = 24 nibbles = 96 bit. Non riesco a codificare 16 con un bocconcino, ma dal momento che "Vuoto, 0" non ha senso, posso trattare "0" come "16".

Se la scheda è vuota ma per un singolo pedina nell'angolo superiore sinistro, ottengo "pegno, 1, Vuoto, 16, Vuoto, 16, Vuoto 16, Vuoto, 15" = 10 nibbles = 40 bit.

Il caso peggiore è quando ho una casella vuota tra ogni pezzo. Ma per la codifica del pezzo, ho solo bisogno di 13 dei 16 valori, quindi forse posso usare un altro per dire "Empty1". Poi, ho bisogno di 64 bocconcini == 128bits.

Per i movimenti, ho bisogno di 3 bit per il pezzo (il colore è dato dal fatto che il bianco muove sempre prima) più 5 bit (0..63) per la nuova posizione = un byte per movimento. La maggior parte del tempo, non hanno bisogno della vecchia posizione dal momento che solo un singolo pezzo sarà nel raggio d'azione. Per il caso strano, devo utilizzare il codice non utilizzato singolo (ho solo bisogno di 7 codici per codificare il pezzo) e poi 5 bit per il vecchio e 5 bit per la nuova posizione.

Questo mi permette di codificare arrocco in 13 morsi (posso spostare il Re verso la Torre, che è abbastanza per dire quello che intendo).

[EDIT] Se si consente un encoder intelligente, quindi ho bisogno di 0 bit per l'impostazione iniziale (perché non ha bisogno di essere codificati in alcun modo: E 'statica) più un byte per mossa.

[EDIT2] che lascia la trasformazione pedone. Se un pedone raggiunge l'ultima fila, posso spostarlo in atto per dire "trasforma" e quindi aggiungere i 3 bit per il pezzo viene sostituito con (non c'è bisogno di utilizzare una regina, è possibile sostituire il pedone con qualsiasi cosa ma il re).

Proprio come hanno codificano giochi su libri e carte: ogni pezzo ha un simbolo; dal momento che è un gioco "legale", si muove bianchi prima - non c'è bisogno di codificare bianco o nero separetely, basta contare il numero di mosse per determinare che si è trasferito. Inoltre, ogni movimento è codificato come (piece, terminando posizione) dove 'posizione finale' è ridotta alla quantità minima di simboli che permette di discernere ambiguità (può essere zero). Lunghezza del gioco determina il numero di mosse. Si può anche codificare il tempo in minuti (dal ultima mossa) ad ogni passo.

Codifica del pezzo potrebbe essere fatto sia con l'assegnazione di un simbolo per ciascuna (32 in totale) oppure assegnando un simbolo per la classe, e utilizzare la posizione finale per capire che del pezzo è stato spostato. Ad esempio, un pedone ha 6 possibili posizioni fine; ma in media solo un paio sono disponibili per esso ad ogni turno. Quindi, statisticamente, la codifica da posizione finale potrebbe essere meglio per questo scenario.

codifiche simili sono utilizzati per treni di impulsi in neuroscienza computazionale (ARE).

Inconvenienti: è necessario ripetere l'intero gioco per arrivare allo stato attuale e generare un sottoinsieme, molto simile attraversando una lista collegata.

Ci sono 64 possibili posizioni di bordo, quindi è necessario 6 bit per la posizione. Ci sono 32 pezzi iniziali, in modo da avere 192 bit in totale finora, dove ogni 6 bit indica la posizione del pezzo dato. Siamo in grado di predeterminare l'ordine i pezzi appaiono in, in modo da non dover dire quale è quale.

Che cosa succede se un pezzo è fuori dalla tavola? Beh, siamo in grado di mettere un pezzo sullo stesso punto come un altro pezzo per indicare che si è fuori dalla tavola, dal momento che sarebbe illegale altrimenti. Ma anche noi non sappiamo se il primo pezzo sarà sulla scheda oppure no. Quindi si aggiungono 5 bit che indicano quale pezzo è il primo (32 possibilitá = 5 bit per rappresentare il primo pezzo). Poi possiamo usare quel punto per i pezzi successivi che sono fuori dalla tavola. Questo ci porta a 197 bit totale. Ci deve essere almeno un pezzo sulla scacchiera, in modo che funzionerà.

Poi abbiamo bisogno di un bit per cui è il turno - ci porta a 198 bit .

Che dire di promozione del pedone? Possiamo farlo maniera negativa con l'aggiunta di 3 bit per pedone, aggiungendo 42 bit. Ma poi si può notare che la maggior parte del tempo, pedine non sono promossi.

Quindi, per ogni pegno che si trova sul bordo, il bit '0' indica che non è promossa. Se un pedone non è sul tavolo, allora non abbiamo bisogno di un po 'a tutti. Poi possiamo usare stringhe di bit di lunghezza variabile per i quali la promozione che ha. Il più delle volte sarà una regina, in modo da "10" può significare QUEEN. Poi "110" significa corvo, "1110" significa vescovo e "1111" significa cavaliere.

Lo stato iniziale avrà 198 + 16 = 214 bit , in quanto tutte le 16 pedine sono sulla tavola e unpromoted. Un end-game con due promosse pedone-queens potrebbe prendere qualcosa come 198 + 4 + 4, il che significa 4 pedine viventi e non promossi e 2 queen pedine, per 206 bit totale. Sembra piuttosto robusto!

===

codifica Huffman, come altri hanno sottolineato, sarebbe il passo successivo. Se si osserva un paio di milioni di giochi, si noterà ogni pezzo è molto più probabile che sia su alcune piazze. Ad esempio, la maggior parte del tempo, le pedine rimanere in linea retta, o uno a sinistra / uno a destra. Il re di solito bastone intorno alla casa base.

Pertanto, escogitare uno schema di codifica Huffman per ogni posizione separata. Pedine probabilmente solo prendere in media 3-4 bit invece di 6. Il re dovrebbe prendere pochi bit pure.

Anche in questo schema, includere "preso" come una possibile posizione. Questo può molto robusto gestire l'arrocco, come pure - ogni torre e re avranno un extra di "posizione originale, mosso" stato. È anche possibile codificare en passant nei pedine questo modo - "posizione originaria, può en passant".

Con i dati a sufficienza questo approccio dovrebbe produrre risultati veramente buoni.

mi piacerebbe provare a utilizzare Huffman codifica . La teoria alla base di questo è - in ogni partita a scacchi ci saranno alcuni pezzi che si sposta in giro un sacco, e alcuni che non si muovono molto o essere eliminati in anticipo. Se la posizione di partenza ha alcuni pezzi già rimosso - tanto meglio. Lo stesso vale per le piazze -. Alcune piazze arriva a vedere tutte le azioni, mentre alcuni non si ottiene molto toccato

Così mi piacerebbe avere due tabelle di Huffman - uno per pezzi, altri per piazze. Essi saranno generati, cercando in gioco vero e proprio. Ho potuto avere una grande tavola per ogni coppia pezzo quadrato, ma penso che sarebbe piuttosto inefficiente perché non ci sono molte istanze dello stesso pezzo si muove sulla stessa piazza di nuovo.

Ogni pezzo avrebbe un ID assegnato. Poiché ci sono 32 diversi pezzi, avrei bisogno solo 5 bit per l'ID pezzo. Gli ID pezzo non cambiano da partita a partita. Lo stesso vale per gli ID quadrati, per cui avrei bisogno 6 bit.

Gli alberi di Huffman verrebbero codificati scrivendo ciascun nodo giù appena vengono raggiunti in ordine simmetrico (cioè, prima il nodo è uscita, allora i suoi figli da sinistra a destra). Per ogni nodo ci sarà un po 'specifiying se si tratta di un nodo foglia o un nodo ramo. Se si tratta di un nodo foglia, sarà seguita dai bit dando l'ID.

La posizione di partenza sarà semplicemente dato da una serie di coppie piece-spilli. Dopo di che ci saranno un paio pezzo posizione per ogni mossa. È possibile trovare la fine del descrittore posizione di partenza (e l'inizio del descrittore mosse) semplicemente trovando il primo pezzo che viene menzionato due volte. Nel caso in cui un pedone viene promosso ci saranno 2 bit extra che specificano cosa diventa, ma il pezzo ID non cambierà.

Per conto della possibilità che un pedone è promosso all'inizio del gioco ci sarà anche un "tavolo di promozione" tra gli alberi di Huffman e dei dati. In un primo momento ci saranno 4 bit che specificano il numero di pedine vengono aggiornati. Allora per ogni pedone ci sarà il suo ID Huffman codifica e 2 bit specificano ciò che è diventato.

Gli alberi di Huffman saranno generati tenendo conto di tutti i dati (sia la posizione di partenza e le mosse) e la tabella di promozione. Anche se normalmente la tabella di promozione sarà vuoto o avere solo un paio di voci.

Per riassumere in termini grafici:

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

Aggiunto: Questo potrebbe ancora essere ottimizzato. Ogni pezzo ha solo poche mosse legali. Invece di semplicemente codificante il bersaglio di una casella può dare 0-basati ID delle possibili mosse di ogni pezzo. Lo stesso ID otterrebbero riutilizzati per ogni pezzo, quindi in totale ci sarebbero più di 21 diversi ID (la regina può avere al massimo 21 diffferent opzioni di spostamento possibili). Mettere questo in una tabella Huffman invece dei campi.

Questo sarebbe comunque presente una difficoltà nel rappresentare lo stato originale. Si potrebbe generare una serie di mosse per mettere ogni pezzo al suo posto. In questo caso sarebbe necessario in qualche modo segnare la fine dello stato iniziale e l'avvio delle mosse.

In alternativa, potrebbe essere collocato utilizzando compressi 6 bit ID quadrati.

Se questo presenterebbe una diminuzione complessiva in termini di dimensioni - non lo so. Probabilmente, ma dovrebbe sperimentare un po '.

Aggiunto 2: Un altro caso speciale. Se lo stato di gioco non ha mosse diventa importante distinguere che si muove dopo. Aggiungere un altro po 'alla fine per questo. :)

[a cura dopo aver letto la domanda correttamente] Se si assume ogni posizione giuridica può essere raggiunta dalla posizione iniziale (che è una possibile definizione di "legale"), quindi qualsiasi posizione può essere espresso come la sequenza di mosse fin dall'inizio . Un frammento di gioco a partire da una posizione non standard può essere espresso come la sequenza di mosse necessarie per raggiungere la partenza, un interruttore per accendere la fotocamera, seguita da successive mosse.

Quindi cerchiamo di chiamare lo stato bordo iniziale singolo bit "0".

Passa da qualsiasi posizione possono essere elencate numerando piazze e ordinare le mosse (inizio, fine), con il convenzionale 2 salto quadrato indica arrocco. Non c'è bisogno di codificare mosse illegali, in quanto la posizione di bordo e le regole sono sempre già noti. Il flag per accendere la fotocamera potrebbe o essere espressa come una speciale mossa in banda, o più sensibilmente come numero mossa fuori banda.

Ci sono 24 mosse di apertura per entrambi i lati, che possono adattarsi a 5 bit ciascuno. mosse successive potrebbero richiedere più o meno bit, ma le mosse legali sono sempre enumerable, così la larghezza di ogni movimento possono tranquillamente crescere o espandersi. Non ho calcolato, ma immagino posizioni 7 bit sarebbe raro.

Utilizzando questo sistema, un gioco 100 mezza mossa potrebbe essere codificato in circa 500 bit. Tuttavia, potrebbe essere saggio per usare un libro di apertura. Supponiamo che contiene un milione di sequenze. Lasciare poi, un primo 0 indica un inizio dal bordo standard e un 1 seguito da un numero a 20 bit indicano un inizio da tale sequenza di apertura. Giochi con aperture alquanto convenzionali potrebbero essere accorciati diciamo 20 mezze muove, o 100 bit.

Questo non è il massimo di compressione possibile, ma (senza il libro di apertura) che sarebbe stato molto facile da implementare se si dispone già di un modello di scacchi, che la questione assume.

Per comprimere ulteriormente, che ci si vuole ordinare le mosse in base alle probabilità piuttosto che in un ordine arbitrario, e codificare le sequenze probabili in meno bit (usando per esempio Huffman pedine come altri hanno già detto).

Se il tempo di calcolo non è un problema allora si potrebbe utilizzare un generatore di posizione deterministico possibile assegnare gli ID unici per una data posizione.

Da una data posizione prima generare il numero di posizioni possibili in un podere deterministico, ad esempio Partendo in basso a sinistra in movimento verso l'alto a destra. Questo determina quanti bit è necessario per la prossima mossa, alcune situazioni potrebbe essere non più di uno. Poi, quando la mossa è fatta negozio appena l'ID univoco per quella mossa.

Promozione e altre regole semplicemente contano mosse validi fintanto che vengono gestiti in modo deterministico, ad esempio alla regina, a torre, ad ogni conteggio Vescovo come una mossa a parte.

La posizione iniziale è più difficile e potrebbe generare circa 250 milioni di possibili posizioni (credo) che richiederebbero circa 28 bit più un po 'in più per determinare il cui movimento è.

Supponendo che sappiamo che il turno è (ogni turno lancia dal bianco al nero) il generatore deterministico sarebbe simile:

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

'ottenere l'elenco delle possibili mosse' sarebbe fare qualcosa di simile:

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.

Se il re è sotto scacco poi ognuno 'elenco delle possibili mosse xxx' restituisce solo mosse valide che cambiano la situazione di controllo.

La maggior parte delle risposte trascurato 3 ripetizione volte. purtroppo per 3 volte la ripetizione è necessario memorizzare tutte le posizioni giocate finora ...

La domanda ci ha richiesto di memorizzare in modo efficiente lo spazio in modo che davvero non hanno bisogno di memorizzare la posizione il più a lungo possiamo costruire dalla lista di mosse (a patto di avere posizione di partenza standard). Siamo in grado di ottimizzare la PGN e questo è tutto abbiamo finito. Bellow è uno schema semplice.

Ci sono 64 piazze sul bordo, 64 = 2 ^ 6. Se abbiamo memorizzare solo il quadrato iniziale e finale di ogni mossa che porterebbe 12 bit (Promozione verrà affrontato più avanti). Si noti che questo regime riguarda già il giocatore a muoversi, emphassant, pezzo catturato, arrocco ecc; come di questi può essere costruito da solo la riproduzione della lista delle mosse.

per la promozione possiamo mantenere un array separato di vettori che dire "in movimento N promuovere per Pezzo XYZ". siamo in grado di mantenere un vettore di (int, byte).

Si è tentati di ottimizzare (A, Da) vettore Inoltre, dato che molti di questi (A, Da) vettori non sono posible a scacchi. per esempio. non ci sarà un passaggio da e1 a D8 ecc Ma non potevo venire con qualsiasi schema. Eventuali ulteriori idee sono più accolti.

Ci ho pensato che uno per un lungo periodo di tempo (+ - 2 ore). E non ci sono risposte ovvie.

Supponendo che:

Ignorando stato tempo (Un giocatore non ha usato per avere un limite di tempo, pertanto potrebbe costringere un pareggio non giocando)
Quando è stato il gioco giocato?!? E 'importante perché le regole sono cambiate nel corso del tempo (in modo assumeranno un gioco moderno nel punto successivo un gioco moderno ...) Si prega di fare riferimento alla regola pedone morto per esempio (Wikipedia ha un famoso problema che mostra), e se si desidera per tornare indietro nel tempo vescovo buona fortuna utilizzato per spostare solo lentamente e dadi utilizzati per essere utilizzato. lol.

... così fino a data regole moderne esso è. Prima indipendentemente ripetizione e spostare limite repitition.

-C 25 byte arrotondati (64b + 32 * 4b + 5b = 325b)

= 64 bit (qualcosa / nulla) + 32 * 4 bit [1 bit = {color bianco / nero} + 3bit = tipo di pezzo {Re, Regina, Bishop, cavaliere, Rook, Pegno, MovedPawn} NB: pedone Moved ... per esempio se è stata l'ultima pedina spostato nel turno precedente indica che un 'en passant' è fattibile. ] + 5bit per lo stato attuale (che è girare, en passant, possibilità di rooking o meno su entrambi i lati)

Fin qui tutto bene. Probabilmente può essere migliorata, ma poi non ci sarebbe lunghezza variabile e la promozione di prendere in considerazione!?

Ora, le seguenti regole sono applicabili solo quando un giocatore apllies per un pareggio, non è automatico! Così considerare questo 90 si sposta senza una cattura o una mossa un pedone è fattibile se nessun giocatore chiede un pareggio! Il che significa che tutte le mosse devono essere registrati ... e disponibili.

-D repetion della posizione ... per esempio stato di bordo, di cui sopra (vedi C) o meno ... (vedi seguente riguardante le regole FIDE) -E Che lascia il complesso problema della indennità di 50 mossa senza cattura o pedina mossa c'è un contatore è necessario ... Comunque.

Quindi, come si fa a trattare con quello? ... Beh, in realtà non c'è modo. Poiché nessuno dei due giocatori può essere utile per disegnare, o rendersi conto che si è verificato. Ora nel caso E un contatore potrebbe bastare ... ma qui è il trucco e anche leggendo le regole FIDE (http://www.fide.com/component/handbook/?id=124&view=article) non riesco a trovare un rispondere ... che dire di perdita della capacità di rooking. che è una ripetizione? Credo di no, ma poi questo è un argomento offuscata non affrontato, non è chiarito.

Così qui è due regole che sono due complessi o non definito anche per cercare di codificare ... Cin cin.

Quindi l'unico modo per codificare veramente un gioco è quello di registrare tutte dall'inizio ... che poi il conflitto (o no?) Con la domanda "stato di bordo".

Spero che questo aiuto ... non troppo matematica :-) solo per dimostrare che qualche domanda non sono così facili, troppo aperto per l'interpretazione o pre-conoscenza per essere un corretto ed efficiente. Non uno Vorrei prendere in considerazione per intervistare come aprire troppo di una lattina di vite senza fine.

Possibile miglioramento della posizione iniziale nella soluzione di Yacoby

Nessuna posizione legale ha più di 16 pezzi per ciascun colore.Il numero di modi per posizionare fino a 16 pezzi neri e 16 bianchi su 64 caselle è di circa 3,63e27.Log2(3,63e27)=91,55.Ciò significa che puoi codificare la posizione e il colore di tutti i pezzi in 92 bit.Questo è inferiore ai 64 bit per la posizione + fino a 32 bit per il colore richiesti dalla soluzione di Yacoby.Nel peggiore dei casi è possibile risparmiare 4 bit a scapito di una notevole complessità nella codifica.

D'altra parte, aumenta la dimensione per le posizioni con 5 o più pezzi mancanti.Queste posizioni rappresentano solo <4% di tutte le posizioni, ma sono probabilmente la maggior parte dei casi in cui si desidera registrare una posizione iniziale diversa dalla posizione iniziale.

Questo porta alla soluzione completa

Codifica la posizione e il colore dei pezzi secondo il metodo sopra. 92 bit.
Per specificare il tipo di ciascun pezzo, utilizzare un codice Huffman:impegnare:'0', torre:'100', cavaliere:'101', vescovo:'110', regina:'1110', re:'1111'.Ciò richiede (16*1 + 12*3 + 4*4) = 68 bit per un set completo di pezzi.La posizione della pensione completa può essere codificata in 92 + 68 = massimo 160 bit.
Dovrebbe essere aggiunto uno stato di gioco aggiuntivo:giro:1 bit, quale arrocco è possibile:4 bit, possibile “en passant”:fino a 4 bit (1 bit indica il caso e 3 bit indicano quale).La posizione iniziale è codificata in = 160 + 9 = 169 bit
Per l'elenco delle mosse, enumerare tutte le mosse possibili per una determinata posizione e memorizzare la posizione della mossa nell'elenco.L'elenco delle mosse comprende tutti i casi speciali (arrocco, en passant e abbandono).Utilizzare solo il numero di bit necessario per memorizzare la posizione più alta.In media non dovrebbe superare i 7 bit per mossa (16 pezzi possibili e 8 mosse legali per pezzo in media).In alcuni casi, quando una mossa è forzata, richiede solo 1 bit (muovi o dimettiti).

Ci sono 32 pezzi sulla scacchiera. Ogni pezzo ha una posizione (una in 64 quadrati). Quindi, basta 32 numeri interi positivi.

Lo so 64 posizioni tengono in 6 bit, ma io non lo farei. Mi terrei gli ultimi pezzi per un paio di bandiere (pezzo caduto, pedina queen'ed)

Cletus ' risposta è buona, ma ha dimenticato di codificare anche chi è il turno. Fa parte dello stato attuale, ed è necessario se si sta utilizzando quello stato di guidare un algoritmo di ricerca (come un derivato alfa-beta).

Non sono un giocatore di scacchi, ma credo che ci sia anche un altro caso d'angolo: il numero di mosse sono state ripetute. Una volta che ogni giocatore fa la stessa mossa per tre volte, il gioco è un pareggio, no? Se è così, allora si sarebbe necessario salvare le informazioni dello stato perché dopo la terza ripetizione, lo Stato è ormai terminale.

Come molti altri hanno detto si potrebbe per ciascuno dei 32 pezzi è possibile memorizzare gli quadrato sono su e se sono sul tabellone o no, questo dà 32 * (log2 (64) + 1) = 224 bit.

Tuttavia vescovi possono occupare solo sia i quadrati neri o bianchi così per questi è sufficiente log2 (32) bit per la posizione, che danno 28 * 7 + 4 * 6 = 220 bit.

E poiché le pedine non iniziano sul retro e possono muovere solo avanti, possono essere solo su 56, dovrebbe essere possibile utilizzare questa limitazione per ridurre il numero di bit necessari per i pedoni.

Una tavola ha 64 caselle, e può essere rappresentato da 64 bit che mostrano se un quadrato è vuoto o meno. Abbiamo solo bisogno di informazioni pezzo, se un quadrato ha un pezzo. Poiché il giocatore + piece prende 4 bit (come indicato in precedenza) si può ottenere lo stato corrente a 64 + 4 * 32 = 192 bit. Gettare la turno in corso e si dispone di 193 bit.

Tuttavia, abbiamo anche bisogno di codificare le mosse legali per ogni pezzo. In primo luogo, si calcola il numero di mosse legali per ogni pezzo, e aggiungiamo che molti bit dopo il pezzo identificatore di una piazza piena. Ho calcolato nel seguente modo:

Pegno: Attaccante, prima girare due in avanti, en passant * 2, di promozione = 7 bit. È possibile combinare il primo turno in avanti e la promozione in un singolo bit dal momento che non possono accadere dalla stessa posizione, in modo da avere 6. Rook: 7 quadrati verticali, orizzontali 7 quadrati = 14 bit Cavaliere: 8 quadrati = 8 bit Bishop: 2 diagonali * 7 = 14 bit Regina: 7 verticale, orizzontale 7, 7 diagonale, 7 diagonali = 28 bit Re: 8 piazze circostanti

Questo significa che ancora si avrebbe bisogno di mappare le piazze mirati in base alla posizione corrente, ma (dovrebbe essere) un semplice calcolo.

Poiché abbiamo 16 pedine, 4 Rooks / cavalieri / vescovi e 2 regine / re, questo è 16 * 6 + 4 * 14 + 4 * 8 + 4 * 14 + 2 * 28 + 2 * 8 = più 312 bit, per un totale di 505 bit globale.

Per quanto riguarda il numero di bit necessari per pezzo per possibili mosse, alcune ottimizzazioni potrebbe essere aggiunto a questo e il numero di bit probabilmente ridotta, ho solo usato i numeri facile da lavorare. Ad esempio, per scivolare pezzi è possibile memorizzare quanto lontano potevano muoversi, ma questo richiederebbe calcoli aggiuntivi.

Per farla breve:. Conservare i dati aggiuntivi (pezzo, ecc) quando una casella è occupata, e solo memorizzare il numero minimo di bit per ogni pezzo di rappresentare le sue mosse legali

Edit1: dimenticato di arrocco e promozione del pedone a qualsiasi pezzo. Questo potrebbe portare il totale con le posizioni esplicite di 557 mosse (altre 3 bit per pedine, 2 per i re)

Ogni pezzo può essere rappresentato da 4 bit (pedone di re, 6 tipi), nero / bianco = 12 valori

Ogni casella della scheda può essere rappresentato da 6 bit (x coord, y) coord.

posizioni iniziali richiedono massima di 320 bit (32 pezzi, 4 + 6 bit)

Ogni mossa successiva può essere rappresentato da 16 bit (da posizioni, per posizione, pezzo).

L'arrocco richiederebbe un extra di 16 bit, in quanto è una doppia mossa.

pedine Queened possono essere rappresentati da una delle 4 valori pezzi su 4 bit.

Senza fare la matematica in dettaglio, questo comincia a risparmiare spazio dopo la prima mossa rispetto alla memorizzazione 32 * 7 bit (array predefinito di pezzi) o 64 * 4 bit (assegnazione predefinita dei quadrati)

Dopo 10 si muove su entrambi i lati, lo spazio massimo richiesto è 640 bit

... ma poi di nuovo, se ci identifichiamo ogni pezzo unico (5 bit) e aggiungere un sesto bit della segnalazione del pedine queened, quindi abbiamo solo bisogno pezzo-id + a-position per ogni mossa. Questo cambia il calcolo per ...

posizioni iniziali max = 384 bit (32 pezzi, 6 + 6 bit) Ogni mossa = 12 bit (per posizione, piece-id)

Poi dopo 10 si sposta su ogni lato dello spazio massimo richiesto è 624 bit

Come Robert G, mi piacerebbe tendono ad usare PGN dal momento che è standard e può essere utilizzato da una vasta gamma di strumenti.

Se, invece, sto giocando uno scacchi AI che si trova su una sonda spaziale lontana, e quindi ogni bit è prezioso, questo è quello che farei per gli spostamenti. Verrò bock alla codifica allo stato iniziale in seguito.

Le mosse non hanno bisogno di registrare lo stato; il decodificatore può prendere tenere traccia di stato, nonché quali mosse sono legali in qualsiasi dato punto. Tutte le mosse devono registrare è che le varie alternative legali viene scelto. Dal momento che i giocatori si alternano, una mossa non ha bisogno di registrare colore del giocatore. Dal momento che un giocatore può muovere solo i propri pezzi a colori, la prima scelta è quale pezzo il giocatore si muove (I torneranno a un'alternativa che utilizza un'altra scelta in seguito). Con almeno 16 pezzi, ciò richiede al massimo 4 bit. Come un giocatore perde pezzi, il numero di scelte diminuisce. Inoltre, un particolare stato di gioco può limitare la scelta dei pezzi. Se un re non può muoversi senza ponendosi sotto controllo, il numero di scelte si riduce di uno. Se un re è sotto controllo, ogni pezzo che non può ottenere il re di controllo non è una scelta praticabile. Numero dei pezzi in fila fine grande da a1 (h1 viene prima a2).

Una volta che il pezzo è specificato, avrà solo un certo numero di destinazioni di legge. Il numero esatto è fortemente dipendente dalle layout della scheda e la storia del gioco, ma possiamo capire alcuni massimi e valori attesi. Per tutti ma il cavaliere e durante arrocco, un pezzo non può muoversi attraverso un altro pezzo. Questa sarà una grande fonte di spostare termini, ma è difficile da quantificare. Un pezzo non può muoversi fuori del consiglio di amministrazione, che sarà anche in gran parte limitare il numero di destinazioni.

Codifichiamo la destinazione della maggior parte dei pezzi numerando piazze lungo linee nel seguente ordine: W, NW, N, NE (lato nero è N). Una linea inizia nel lontano quadrato nella direzione, dato che è legale per spostarsi e procede verso il. Per un re sgombro, l'elenco di mosse è W, E, NW, SE, N, S, NE, SO. Per il cavaliere, si parte con 2W1N e procediamo in senso orario; 0 tappa è la prima destinazione valida in questo ordine.

I pedoni: una pedina impassibile ha 2 scelte delle destinazioni, il che richiede 1 bit. Se un pedone può catturare un altro, sia normalmente o en passant (che il decodificatore può determinare, dal momento che è tenere traccia di stato), ha anche 2 o 3 scelte di mosse. A parte questo, un pedone può avere solo 1 scelta, richiede nessun bit. Quando un pedone è nel suo rango 7 ^th, abbiamo bordeggiamo anche sulla scelta di promozione. Dal momento che pedine di solito sono promossi a regine, seguiti da cavalieri, abbiamo codificare le scelte come:
- regina: 0
- cavaliere: 10
- Vescovo: 110
- Torre: 111
Vescovo:. Al massimo 13 destinazioni quando al {d, e} {4,5} per 4 bit
Rook:. Al massimo 14 destinazioni, 4 bit
Cavalieri:. Al massimo 8 destinazioni, 3 bit
Re: Quando l'arrocco è un'opzione, il re ha si torna a S e non può muoversi verso il basso; questo dà un totale di 7 destinazioni. Il resto del tempo, un re ha al massimo 8 si sposta, con un massimo di 3 bit.
Queen: come scelte per il vescovo o torre, per un totale di 27 scelte, che è 5 bit

Poiché il numero di scelte non sempre è una potenza di due, sopra spreca ancora bit. Supponiamo che il numero di scelte è C e la particolare scelta è numerata c e n = ceil (lg ( C )) (il numero di bit necessari per codificare la scelta). Noi facciamo uso di questi valori che altrimenti andrebbe perduta esaminando il primo bit della scelta successiva. Se è 0, non fare nulla. Se si tratta di 1 e c + C <2 ⁿ, quindi aggiungere C per c . Decodifica di un numero di inverte questo: se la ricevuta c > = C , sottrarre C e impostare il primo bit per il prossimo numero 1. Se c <2 ⁿ - C , quindi impostare il primo bit per il numero accanto a 0.Se 2 ⁿ - C <= c < C , poi non fare nulla. Chiamare questo schema di "saturazione".

Un altro tipo di scelta potenziale che potrebbe accorciare la codifica è quello di scegliere un pezzo avversario da catturare. Questo aumenta il numero di scelte per la prima parte di un movimento, raccogliendo un pezzo, per un massimo di un ulteriore bit (il numero esatto dipende da quanti pezzi il giocatore di turno può muovere). Questa scelta è seguita da una scelta di brano cattura, che è probabilmente molto più piccolo rispetto al numero di mosse per una delle date pezzi giocatori. Un pezzo può essere attaccata da un pezzo da ogni direzione cardinale più i cavalieri per un totale di al massimo 10 pezzi in attacco; questo dà un totale massimo di 9 bit per una mossa di cattura, anche se mi aspetto 7 bit in media. Questo sarebbe particolarmente vantaggioso per la cattura da parte della regina, dal momento che spesso hanno un bel paio di destinazioni di legge.

Con la saturazione, la cattura-codifica probabilmente non offre un vantaggio. Potremmo consentire entrambe le opzioni, specificando nello stato iniziale che vengono utilizzati. Se la saturazione non viene utilizzato, la codifica gioco potrebbe anche usare i numeri di scelta non utilizzati ( C <= c <2 ⁿ) per modificare le opzioni durante il gioco. Ogni volta che C è una potenza di due, non siamo riusciti a modificare le opzioni.

Thomas ha il giusto approccio per la codifica della scheda. Tuttavia, questo dovrebbe essere combinato con l'approccio di ralu per la memorizzazione di mosse. Fate una lista di tutte le possibili mosse, scrivere il numero di bit necessari per esprimere questo numero. Dal momento che il decoder sta facendo lo stesso calcolo si sa quanti sono possibili e possono sapere quanti bit a leggere, non sono necessari codici di lunghezza.

Così otteniamo 164 bit per i pezzi, 4 bit per informazioni arrocco (supponendo abbiamo memorizzato un frammento di un gioco, altrimenti può essere ricostruito), 3 bit per en passant informazioni ammissibilità - semplicemente memorizzare la colonna in cui la mossa si è verificato (se en passant non è possibile memorizzare una colonna in cui non è possibile - devono esistere tali colonne). e 1 per chi è di spostare

mosse tipicamente prendere 5 o 6 bit, ma può variare da 1 a 8.

Un collegamento aggiuntivo - se la codifica inizia con 12 1 bit (una situazione non valida - nemmeno un frammento avrà due re su un lato) si interrompe la decodifica, pulire il bordo e impostare un nuovo gioco. Il bit successivo sarà un po 'mossa.

algoritmo dovrebbe deterministico enumerare tutte le destinazioni possibili ad ogni mossa. Numero di destinazioni:

2 vescovi, 13 destinazioni ogni = 26
2 cornacchie, 14 destinazioni ogni = 28
2 cavalieri, 8 destinazioni ciascuna = 16
regina, 27 destinazioni
re, 8 destinazioni

8 zampe potrebbero diventare tutti regine nel peggiore dei casi (enumerazione-saggio), rendendo così più grande numero di possibili destinazioni * 27 + 9 + 26 + 28 + 16 = 321 8. Così, tutte le destinazioni per qualsiasi mossa possono essere elencate da un numero 9 bit.

Numero massimo di mosse di entrambe le parti è di 100 (se non sbaglio, non un giocatore di scacchi). Pertanto, qualsiasi gioco potrebbe essere registrato in 900 bit. Più posizione iniziale ogni pezzo può essere registrato utilizzando numeri 6 bit, che ammonta a 32 * 6 = 192 bit. Più uno bit per "chi si muove prima" record. Pertanto, qualsiasi gioco può essere registrato utilizzando 900 + 192 + 1 = 1093 bit.

Memorizzazione del Consiglio di Stato

Il modo più semplice ho pensato è troppo prima avere una gamma di 8 * 8 bit che rappresenta la posizione di ogni pezzo (1 Quindi se c'è un pezzo degli scacchi lì e 0 se non c'è). Poiché si tratta di una lunghezza fissa non abbiamo bisogno di alcun terminatore.

Avanti rappresentano ogni pezzo degli scacchi in ordine alla sua posizione. Utilizzando 4 bit per pezzo, questo richiede 32 * 4 bit (128 in totale). Che è davvero uno spreco.

Utilizzando un albero binario, possiamo rappresentare una pedina in un byte, un cavaliere e la torre e vescovo in 3 e un re e la regina in 4. Come abbiamo anche bisogno di memorizzare il colore del pezzo, che prende un byte extra finisce per come (mi perdoni se questo è sbagliato, non ho mai guardato codifica di Huffman ogni dettaglio prima):

Pegno: 2
Rook: 4
Cavaliere: 4
Vescovo: 4
Re: 5
Queen: 5

Dati i totali:

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

che batte con una dimensione fissa insieme di bit da 28 bit.

Quindi il metodo migliore che ho trovato è quello di conservarlo in un 8 ² + 100 bit array

8*8 + 100 = 164

Passa Memorizzazione
La prima cosa che abbiamo bisogno di sapere con quale pezzo è si muove a dove. Dato che ci sono massimo 32 pezzi sulla scacchiera e sappiamo ciò che ogni pezzo è, piuttosto che un intero che rappresenta il quadrato, possiamo avere un numero intero che rappresenta l'offset pezzo, il che significa che abbiamo solo per misura 32 possibili valori per rappresentare un pezzo.

Purtroppo ci sono varie regole speciali, come arrocco o rovesciare il re e formando una Repubblica (Terry Pratchett riferimento), quindi prima di memorizzare il pezzo da muovere abbiamo bisogno di un singolo bit che indica se è una mossa speciale oppure no.

Quindi, per ogni mossa normale abbiamo una necessaria bit 1 + 5 = 6. (1 tipo di bit, 5 bit per il pezzo)

Dopo che il numero di pezzi è stato decodificato, abbiamo poi conosciamo il tipo di pezzo, e ogni pezzo dovrebbe rappresentare il suo movimento in modo più efficiente. Per esempio (Se le mie regole degli scacchi sono fino a zero) una pedina ha un totale di 4 mosse possibili (prendere a sinistra, prendere a destra, spostare uno in avanti, andare avanti di due).
Quindi, per rappresentare una mossa pedina abbiamo bisogno '6 + 2 = 8' bit. (6 bit per intestazione mossa iniziale, 2 bit per quale mossa)

Moving per la regina sarebbe più complessa, che sarebbe meglio avere una direzione (8 direzioni possibili, quindi 3 bit) e un totale di 8 possibili quadrati per spostarsi per ciascuna direzione (tanto altro 3 bit) . Quindi, per rappresentare lo spostamento una regina sarebbe necessario bit 6 + 3 + 3 = 12.

L'ultima cosa che gli eventi per me è che abbiamo bisogno di memorizzare cui i giocatori turno. Questo dovrebbe essere un singolo bit (bianco o nero per spostarsi successivo)

Formato risultante
Così il formato di file sarebbe simile a questo

[64 bit] posizioni iniziali pezzo
[Max 100 bit] pezzi iniziali [1 bit] turno di giocatore
[N bit] Passa

Se una mossa è
[1 bit] tipo di Move (speciale o normale)
[N bit] Sposta Particolare

Se la mossa è una mossa normale, la mossa Particolare sembra qualcosa di simile
[5 bit] pezzo
[n bit] specifica piece mossa (di solito nell'intervallo da 2 a 6 bit]

Se si tratta di una mossa speciale
Si dovrebbe avere un tipo intero e quindi eventuali informazioni aggiuntive (come se arrocco). Non riesco a ricordare il numero di mosse speciali, quindi potrebbe essere OK solo per indicare che si tratta di una mossa speciale (se v'è una sola)

Nel caso base del bordo iniziale più movimenti successivi, considerare quanto segue.

Usa un programma di scacchi per assegnare probabilità di tutte le possibili mosse. Ad esempio, il 40% per e2-e4 20% per d2-d4, e così via. Se alcune mosse sono legali, ma non considerato da quel programma, dare loro un po 'bassa probabilità. Utilizzare codifica aritmetica per salvare quale scelta è stata presa, che sarà un numero compreso tra 0 e 0,4 per la prima mossa, 0,4 e 0,6 per il secondo, e così via.

Fare lo stesso per l'altro lato. Ad esempio, se v'è una probabilità del 50% di e7-e5 come la risposta di e2-e4 allora il numero codificato sarà compreso tra 0 e 0,2. Ripetere fino a quando il gioco è fatto. Il risultato è un potenzialmente molto piccola gamma. Trovare la frazione binaria con la base più piccola che si inserisce in tale intervallo. Ecco codifica aritmetica.

Questo è meglio di Huffman, perché può essere pensato codifica bit frazionario (più alcuni alla fine del gioco per arrotondare fino a un intero bit).

Il risultato dovrebbe essere più compatto di Huffman, e non ci sono casi speciali per la promozione, en passant, la regola delle 50 mosse, e altri dettagli, perché sono gestiti dal programma di valutazione degli scacchi.

Per ripetere, ancora una volta utilizzare il programma di scacchi per valutare la scheda e assegnare tutte le probabilità per ogni mossa. Utilizzare il valore aritmetico codificato per determinare quale mossa è stata effettivamente svolto. Ripetere l'operazione fino a cottura.

Se il programma di scacchi è abbastanza buono, è possibile ottenere una migliore compressione con un encoder a due stati, dove le probabilità sono definite sulla base di movimenti sia in bianco e nero. Nel caso più estremo di alcuni 200+ stati, questa codifica l'intero insieme di tutti i possibili giochi di scacchi, e pertanto non è fattibile.

Questo è più o meno un modo diverso di dire ciò che Dario già scritto, solo con un po 'di esempio di come codifica aritmetica potrebbe funzionare, e un vero e proprio esempio di utilizzo di un programma di scacchi esistente per aiutare a valutare la probabilità che la prossima mossa ( s).

Autorizzato sotto: CC-BY-SA insieme a attribuzione

Non affiliato a StackOverflow