Bukan hanya pertanyaan, lebih dari teka-teki ...

Selama bertahun-tahun, saya telah terlibat dalam beberapa wawancara teknis dengan karyawan baru. Selain menanyakan pertanyaan standar "apakah Anda tahu teknologi X", saya juga mencoba merasakan bagaimana mereka mendekati masalah. Biasanya, saya akan mengirimi mereka pertanyaan melalui email sehari sebelum wawancara, dan mengharapkan mereka menemukan solusi pada hari berikutnya.

Seringkali hasilnya cukup menarik - salah, tapi menarik - dan orang tersebut masih akan mendapatkan rekomendasi saya jika mereka dapat menjelaskan mengapa mereka mengambil pendekatan tertentu.

Jadi saya pikir saya akan melemparkan salah satu pertanyaan saya ke luar sana untuk audiens Stack Overflow.

Pertanyaan: Apa cara paling hemat ruang yang dapat Anda pikirkan untuk menyandikan keadaan permainan catur (atau bagiannya)? Artinya, diberi papan catur dengan bidak-bidak yang disusun secara sah, yang menyandikan keadaan awal ini dan semua langkah hukum selanjutnya yang diambil oleh para pemain dalam permainan.

Tidak ada kode yang diperlukan untuk jawabannya, cukup deskripsi algoritma yang akan Anda gunakan.

EDIT: Seperti yang ditunjukkan salah satu poster, saya tidak mempertimbangkan interval waktu antara gerakan. Jangan ragu untuk memperhitungkannya juga sebagai tambahan opsional :)

EDIT2: Hanya untuk klarifikasi tambahan ... Ingat, encoder / decoder peka terhadap aturan. Satu-satunya hal yang benar-benar perlu disimpan adalah pilihan pemain - hal lain dapat dianggap diketahui oleh encoder / decoder.

EDIT3: Akan sulit untuk memilih pemenang di sini :) Banyak sekali jawaban yang bagus!

Pembaruan: Saya sangat menyukai topik ini sehingga saya menulis Teka-teki Pemrograman, Posisi Catur, dan Pengkodean Huffman . Jika Anda membaca ini, saya telah menentukan bahwa satu - satunya cara untuk menyimpan status permainan lengkap adalah dengan menyimpan daftar lengkap gerakan. Baca terus untuk alasannya. Jadi saya menggunakan versi masalah yang sedikit disederhanakan untuk tata letak bagian.

Masalah

Gambar ini mengilustrasikan posisi awal Catur. Catur terjadi pada papan 8x8 dengan setiap pemain dimulai dengan set identik 16 buah yang terdiri dari 8 pion, 2 benteng, 2 ksatria, 2 uskup, 1 ratu dan 1 raja seperti yang diilustrasikan di sini:

Posisi umumnya dicatat sebagai huruf untuk kolom diikuti dengan nomor baris sehingga ratu Putih berada di d1. Gerakan paling sering disimpan dalam notasi aljabar , yang tidak ambigu dan umumnya hanya menentukan informasi minimal yang diperlukan. Pertimbangkan pembukaan ini:

1. e4 e5
2. Nf3 Nc6
3. …

yang diterjemahkan menjadi:

1. Putih memindahkan pion raja dari e2 ke e4 (itu adalah satu-satunya bidak yang bisa sampai ke e4 maka “e4”);
2. Hitam memindahkan pion raja dari e7 ke e5;
3. Putih memindahkan ksatria (N) ke f3;
4. Hitam memindahkan ksatria ke c6.
5. …

Papannya terlihat seperti ini:

Kemampuan penting bagi setiap programmer adalah dapat menentukan masalah dengan benar dan jelas .

Jadi, apa yang kurang atau ambigu? Ternyata banyak.

Status Papan vs Status Game

Hal pertama yang perlu Anda tentukan adalah apakah Anda menyimpan status permainan atau posisi bidak di papan. Mengkodekan posisi potongan adalah satu hal tetapi masalahnya mengatakan "semua langkah hukum berikutnya". Masalahnya juga tidak mengatakan apa-apa tentang mengetahui pergerakan ke titik ini. Itu sebenarnya masalah seperti yang akan saya jelaskan.

Castling

Permainan telah berjalan sebagai berikut:

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

Papan tersebut terlihat sebagai berikut:

Putih memiliki opsi rokade . Sebagian dari persyaratan untuk ini adalah bahwa raja dan benteng yang bersangkutan tidak akan pernah bisa pindah, jadi apakah raja atau benteng dari masing-masing sisi telah berpindah perlu disimpan. Jelas jika mereka tidak berada di posisi awal, mereka telah pindah jika tidak maka perlu ditentukan.

Ada beberapa strategi yang bisa digunakan untuk mengatasi masalah ini.

Pertama, kami dapat menyimpan 6 bit informasi tambahan (1 untuk setiap benteng dan raja) untuk menunjukkan apakah bidak itu telah pindah. Kita dapat merampingkan ini dengan hanya menyimpan sedikit untuk salah satu dari enam kotak ini jika bagian yang tepat kebetulan ada di dalamnya. Sebagai alternatif, kita dapat memperlakukan setiap bidak yang tidak digerakkan sebagai jenis bidak lain sehingga alih-alih 6 jenis bidak di setiap sisi (bidak, benteng, ksatria, uskup, ratu dan raja) ada 8 (menambahkan benteng yang tidak digerakkan dan raja yang tidak digerakkan).

Sambil lalu

Aturan lain yang aneh dan sering diabaikan dalam Catur adalah En Passant .

Permainan telah berkembang.

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

Bidak Hitam di b4 sekarang memiliki opsi untuk memindahkan pionnya di b4 ke c3 mengambil bidak Putih di c4. Ini hanya terjadi pada kesempatan pertama yang berarti jika Black meneruskan opsi tersebut sekarang dia tidak dapat mengambil langkah selanjutnya. Jadi kita perlu menyimpan ini.

Jika kita tahu langkah sebelumnya, kita pasti bisa menjawab jika En Passant memungkinkan. Alternatifnya kita bisa menyimpan apakah setiap bidak di peringkat ke-4 baru saja pindah ke sana dengan gerakan maju ganda. Atau kita dapat melihat setiap kemungkinan posisi En Passant di papan tulis dan memiliki bendera untuk menunjukkan apakah itu memungkinkan atau tidak.

Promosi

Ini adalah langkah Putih. Jika Putih memindahkan pionnya di h7 ke h8, itu bisa dipromosikan ke bidak lain (tapi bukan raja). 99% dari waktu itu dipromosikan menjadi Ratu tetapi terkadang tidak, biasanya karena itu dapat memaksa jalan buntu ketika jika tidak Anda akan menang. Ini ditulis sebagai:

56. h8 = Q

Ini penting dalam masalah kita karena itu berarti kita tidak dapat mengandalkan jumlah keping yang tetap di setiap sisi. Sangat mungkin (tetapi sangat tidak mungkin) untuk satu pihak berakhir dengan 9 ratu, 10 benteng, 10 uskup atau 10 ksatria jika semua 8 pion dipromosikan.

Jalan buntu

Ketika dalam posisi di mana Anda tidak bisa menang, taktik terbaik Anda adalah mencoba jalan buntu . Varian yang paling mungkin adalah di mana Anda tidak dapat melakukan langkah hukum (biasanya karena tindakan apa pun ketika membuat raja Anda di cek). Dalam hal ini Anda dapat mengklaim hasil imbang. Yang ini mudah dipenuhi.

Varian kedua adalah dengan pengulangan tiga kali lipat . Jika posisi papan yang sama terjadi tiga kali dalam permainan (atau akan terjadi untuk ketiga kalinya pada langkah berikutnya), hasil imbang dapat diklaim. Posisi tidak perlu terjadi dalam urutan tertentu (artinya tidak harus urutan gerakan yang sama yang diulang tiga kali). Yang ini sangat memperumit masalah karena Anda harus mengingat setiap posisi papan sebelumnya. Jika ini merupakan persyaratan masalah, satu-satunya solusi yang mungkin untuk masalah tersebut adalah menyimpan setiap langkah sebelumnya.

Terakhir, ada aturan lima puluh langkah . Seorang pemain dapat mengklaim hasil imbang jika tidak ada bidak yang bergerak dan tidak ada bidak yang diambil dalam lima puluh langkah berturut-turut sebelumnya, jadi kami perlu menyimpan berapa banyak gerakan sejak bidak dipindahkan atau bidak diambil (yang terbaru dari dua bidak. Ini membutuhkan 6 bit (0-63).

Giliran siapa sekarang?

Tentu saja kita juga perlu tahu giliran siapa dan ini sedikit informasi.

Dua Masalah

Karena kasus buntu, satu-satunya cara yang layak atau masuk akal untuk menyimpan status game adalah menyimpan semua gerakan yang mengarah ke posisi ini. Saya akan mengatasi satu masalah itu. Masalah status papan akan disederhanakan menjadi ini: simpan posisi saat ini dari semua bagian di papan dengan mengabaikan kondisi rokade, en passant, jalan buntu dan giliran siapa .

Tata letak satuan dapat ditangani secara luas dengan salah satu dari dua cara berikut: dengan menyimpan isi setiap kotak atau dengan menyimpan posisi setiap bagian.

Isi Sederhana

Ada enam jenis bidak (pion, benteng, ksatria, uskup, ratu dan raja). Tiap bidak bisa Putih atau Hitam jadi bujur sangkar bisa berisi salah satu dari 12 kemungkinan keping atau mungkin kosong jadi ada 13 kemungkinan. 13 dapat disimpan dalam 4 bit (0-15) Jadi solusi paling sederhana adalah dengan menyimpan 4 bit untuk setiap kuadrat dikalikan 64 kotak atau 256 bit informasi.

Keuntungan dari metode ini adalah manipulasi sangat mudah dan cepat. Ini bahkan dapat diperpanjang dengan menambahkan 3 kemungkinan lagi tanpa menambah persyaratan penyimpanan: bidak yang telah berpindah 2 ruang pada belokan terakhir, raja yang belum bergerak dan benteng yang belum bergerak, yang akan melayani banyak orang. masalah yang disebutkan sebelumnya.

Tapi kita bisa lebih baik.

Pengkodean Basis 13

Seringkali membantu untuk memikirkan posisi papan sebagai angka yang sangat besar. Ini sering dilakukan dalam ilmu komputer. Misalnya, masalah penghentian memperlakukan program komputer (dengan benar) sebagai angka yang besar.

Solusi pertama memperlakukan posisi sebagai 64 digit bilangan basis 16 tetapi seperti yang ditunjukkan ada redundansi dalam informasi ini (menjadi 3 kemungkinan yang tidak digunakan per "digit") sehingga kita dapat mengurangi ruang bilangan menjadi 64 basis 13 digit. Tentu saja ini tidak dapat dilakukan seefisien basis 16 tetapi akan menghemat kebutuhan penyimpanan (dan meminimalkan ruang penyimpanan adalah tujuan kami).

Dalam basis 10 angka 234 sama dengan 2 x 10 ² + 3 x 10 ¹ + 4 x 10 ⁰ .

Dalam basis 16 angka 0xA50 setara dengan 10 x 16 ² + 5 x 16 ¹ + 0 x 16 ⁰ = 2640 (desimal).

Jadi kita dapat menyandikan posisi kita sebagai p ₀ x 13 ⁶³ + p ₁ x 13 ⁶² + ... + p ₆₃ x 13 ⁰ dimana p _i mewakili isi dari kuadrat i .

2 ²⁵⁶ sama dengan sekitar 1,16e77. 13 ⁶⁴ sama dengan kira-kira 1.96e71, yang membutuhkan ruang penyimpanan 237 bit. Penghematan hanya 7,5% itu menimbulkan biaya manipulasi yang meningkat secara signifikan .

Pengkodean Basis Variabel

Di papan hukum, bagian tertentu tidak dapat muncul di kotak tertentu. Misalnya, bidak tidak dapat muncul di peringkat pertama atau kedelapan, mengurangi kemungkinan untuk kotak tersebut menjadi 11. Hal itu mengurangi kemungkinan papan menjadi 11 ¹⁶ x 13 ⁴⁸ = 1.35e70 (kurang-lebih), membutuhkan ruang penyimpanan 233 bit.

Sebenarnya encoding dan decoding nilai-nilai seperti itu ke dan dari desimal (atau biner) sedikit lebih berbelit-belit tetapi dapat dilakukan dengan andal dan dibiarkan sebagai latihan bagi pembaca.

Huruf Lebar Variabel

Kedua metode sebelumnya dapat dideskripsikan sebagai pengkodean alfabet dengan lebar tetap . Masing-masing dari 11, 13 atau 16 anggota alfabet diganti dengan nilai lain. Setiap "karakter" memiliki lebar yang sama tetapi efisiensinya dapat ditingkatkan jika Anda mempertimbangkan bahwa setiap karakter tidak mungkin sama.

Pertimbangkan kode Morse (digambarkan di atas). Karakter dalam pesan dikodekan sebagai urutan tanda hubung dan titik. Tanda hubung dan titik tersebut ditransfer melalui radio (biasanya) dengan jeda di antara keduanya untuk membatasinya.

Perhatikan bagaimana huruf E (huruf yang paling umum dalam bahasa Inggris ) adalah titik tunggal, urutan yang paling pendek, sedangkan Z (paling jarang) adalah dua tanda hubung dan dua bip.

Skema seperti itu dapat secara signifikan mengurangi ukuran pesan yang diharapkan, tetapi mengakibatkan peningkatan ukuran urutan karakter acak.

Perlu dicatat bahwa kode Morse memiliki fitur bawaan lainnya: tanda hubung sepanjang tiga titik sehingga kode di atas dibuat dengan pemikiran ini untuk meminimalkan penggunaan tanda hubung. Karena 1s dan 0s (blok penyusun kami) tidak memiliki masalah ini, ini bukan fitur yang perlu kami tiru.

Terakhir, ada dua jenis sandaran dalam kode Morse. Istirahat singkat (panjang sebuah titik) digunakan untuk membedakan antara titik dan garis. Celah yang lebih panjang (panjang tanda hubung) digunakan untuk membatasi karakter.

Jadi, bagaimana ini berlaku untuk masalah kita?

Huffman Coding

Ada algoritma untuk menangani kode panjang variabel yang disebut pengkodean Huffman . Pengkodean Huffman membuat substitusi kode panjang variabel, biasanya menggunakan frekuensi simbol yang diharapkan untuk menetapkan nilai yang lebih pendek ke simbol yang lebih umum.

Pada pohon di atas, huruf E dikodekan sebagai 000 (atau kiri-kiri-kiri) dan S adalah 1011. Seharusnya jelas bahwa skema pengkodean ini tidak ambigu .

Ini adalah perbedaan penting dari kode Morse. Kode Morse memiliki pemisah karakter sehingga dapat melakukan substitusi yang ambigu (misalnya 4 titik bisa H atau 2 Is) tetapi kita hanya memiliki 1 dan 0 jadi kita memilih substitusi yang tidak ambigu.

Di bawah ini adalah implementasi sederhana:

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

dengan data statis:

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

dan:

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

Salah satu kemungkinan keluarannya adalah:

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

Untuk posisi awal, ini setara dengan 32 x 1 + 16 x 3 + 12 x 5 + 4 x 6 = 164 bit.

Perbedaan Negara

Pendekatan lain yang mungkin adalah menggabungkan pendekatan pertama dengan pengkodean Huffman. Ini didasarkan pada asumsi bahwa papan Catur yang paling diharapkan (daripada yang dihasilkan secara acak) lebih mungkin daripada tidak, setidaknya sebagian, menyerupai posisi awal.

Jadi yang Anda lakukan adalah XOR posisi papan arus 256 bit dengan posisi awal 256 bit dan kemudian menyandikannya (menggunakan pengkodean Huffman atau, katakanlah, beberapa metode pengkodean panjang jalan ). Jelas ini akan sangat efisien untuk memulai (64 0 mungkin sesuai dengan 64 bit) tetapi peningkatan penyimpanan diperlukan saat permainan berlangsung.

Posisi Bidak

Seperti disebutkan, cara lain untuk mengatasi masalah ini adalah dengan menyimpan posisi setiap bidak yang dimiliki pemain. Ini bekerja sangat baik dengan posisi permainan akhir di mana sebagian besar kotak akan kosong (tetapi dalam pendekatan pengkodean Huffman kotak kosong hanya menggunakan 1 bit).

Setiap sisi akan memiliki raja dan 0-15 bidak lainnya. Karena promosi, susunan yang tepat dari potongan-potongan itu dapat cukup bervariasi sehingga Anda tidak dapat menganggap angka berdasarkan posisi awal adalah maksimal.

Cara logis untuk membagi ini adalah menyimpan Posisi yang terdiri dari dua Sisi (Putih dan Hitam). Setiap Sisi memiliki:

• Seorang raja: 6 bit untuk lokasi;
• Memiliki bidak: 1 (ya), 0 (tidak);
• Jika ya, jumlah bidak: 3 bidak (0-7 + 1 = 1-8);
• Jika ya, lokasi setiap bidak dikodekan: 45 bit (lihat di bawah);
• Jumlah bukan bidak: 4 bidak (0-15);
• Untuk setiap bidak: jenis (2 bit untuk ratu, benteng, ksatria, bishop) dan lokasi (6 bit)

Sedangkan untuk lokasi bidak, bidak hanya dapat berada di 48 petak yang memungkinkan (bukan 64 petak lainnya). Karena itu, lebih baik tidak menyia-nyiakan 16 nilai ekstra yang akan digunakan menggunakan 6 bit per bidak. Jadi jika Anda memiliki 8 pion ada 48 ⁸ kemungkinan, sama dengan 28.179.280.429.056. Anda membutuhkan 45 bit untuk menyandikan banyak nilai itu.

Itu 105 bit per sisi atau total 210 bit. Posisi awal adalah kasus terburuk untuk metode ini dan itu akan menjadi jauh lebih baik saat Anda menghapus potongan.

Harus dijelaskan bahwa ada kurang dari 48 ⁸ kemungkinan karena bidak tidak bisa semuanya berada di kotak yang sama. Yang pertama memiliki 48 kemungkinan, yang kedua 47 dan seterusnya. 48 x 47 x… x 41 = 1,52e13 = penyimpanan 44 bit.

Anda dapat meningkatkan ini lebih jauh dengan menghilangkan petak yang ditempati oleh bidak lain (termasuk sisi lain) sehingga Anda dapat menempatkan bidak putih terlebih dahulu, kemudian bidak hitam, lalu bidak putih, dan terakhir bidak hitam. Pada posisi awal, ini mengurangi persyaratan penyimpanan menjadi 44 bit untuk Putih dan 42 bit untuk Hitam.

Pendekatan Gabungan

Pengoptimalan lain yang mungkin adalah bahwa masing-masing pendekatan ini memiliki kekuatan dan kelemahan. Anda dapat, katakanlah, memilih 4 terbaik dan kemudian menyandikan pemilih skema dalam dua bit pertama dan kemudian penyimpanan khusus skema setelah itu.

Dengan overhead sekecil itu, sejauh ini ini akan menjadi pendekatan terbaik.

Status Game

Saya kembali ke masalah menyimpan permainan daripada posisi . Karena pengulangan tiga kali lipat kami harus menyimpan daftar gerakan yang telah terjadi hingga saat ini.

Anotasi

Satu hal yang harus Anda tentukan adalah apakah Anda hanya menyimpan daftar gerakan atau Anda membuat anotasi permainan? Permainan catur sering kali diberi anotasi, misalnya:

17. Bb5 !! Nc4?

Langkah Putih ditandai dengan dua tanda seru sebagai brilian sedangkan Hitam dipandang sebagai kesalahan. Lihat tanda baca catur .

Selain itu, Anda juga perlu menyimpan teks bebas saat gerakan dijelaskan.

Saya berasumsi bahwa pergerakannya cukup sehingga tidak akan ada anotasi.

Notasi Aljabar

Kita cukup menyimpan teks perpindahan di sini ("e4", "Bxb5", dll). Termasuk byte pengakhiran yang Anda lihat sekitar 6 byte (48 bit) per gerakan (kasus terburuk). Itu tidak terlalu efisien.

Hal kedua yang harus dicoba adalah menyimpan lokasi awal (6 bit) dan lokasi akhir (6 bit) jadi 12 bit per gerakan. Itu jauh lebih baik.

Atau kita dapat menentukan semua langkah hukum dari posisi saat ini dengan cara dan keadaan yang dapat diprediksi dan deterministik yang telah kita pilih. Ini kemudian kembali ke pengkodean basis variabel yang disebutkan di atas. Putih dan Hitam memiliki 20 kemungkinan gerakan masing-masing pada langkah pertama mereka, lebih banyak pada langkah kedua dan seterusnya.

Kesimpulan

Tidak ada jawaban yang benar-benar tepat untuk pertanyaan ini. Ada banyak kemungkinan pendekatan yang di atas hanyalah beberapa di antaranya.

Apa yang saya suka tentang ini dan masalah serupa adalah bahwa ia menuntut kemampuan yang penting bagi programmer mana pun seperti mempertimbangkan pola penggunaan, menentukan persyaratan secara akurat, dan memikirkan kasus sudut.

Posisi catur diambil sebagai tangkapan layar dari Chess Position Trainer .

Yang terbaik adalah menyimpan permainan catur dalam format standar yang dapat dibaca manusia.

The Portabel Permainan Notasi mengasumsikan posisi awal standar (meskipun tidak harus ) dan hanya berisi daftar bergerak, secara bergiliran. Format standar yang ringkas, dapat dibaca manusia.

Misalnya

[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

Jika Anda ingin membuatnya lebih kecil, maka ritsleting saja . Pekerjaan selesai!

Teka-teki yang bagus!

Saya melihat bahwa kebanyakan orang menyimpan posisi masing-masing bagian. Bagaimana dengan mengambil pendekatan yang lebih berpikiran sederhana, dan menyimpan konten setiap kotak ? Itu menangani promosi dan potongan yang diambil secara otomatis.

Dan itu memungkinkan pengkodean Huffman . Sebenarnya, frekuensi awal bidak di papan hampir sempurna untuk ini: setengah dari kotak kosong, setengah dari kotak yang tersisa adalah bidak, dan sebagainya.

Mempertimbangkan frekuensi setiap bagian, saya membuat pohon Huffman di atas kertas, yang tidak akan saya ulangi di sini. Hasilnya, di mana csingkatan warna (putih = 0, hitam = 1):

• 0 untuk kotak kosong
• 1c0 untuk pion
• 1c100 untuk benteng
• 1c101 untuk ksatria
• 1c110 untuk uskup
• 1c1110 untuk ratu
• 1c1111 untuk raja

Untuk seluruh dewan dalam situasi awalnya, kami punya

• kotak kosong: 32 * 1 bit = 32 bit
• bidak: 16 * 3 bit = 48 bit
• benteng / ksatria / uskup: 12 * 5 bit = 60 bit
• ratu / raja: 4 * 6 bit = 24 bit

Total: 164 bit untuk status papan awal . Secara signifikan kurang dari 235 bit jawaban yang dipilih tertinggi saat ini. Dan itu hanya akan menjadi lebih kecil saat permainan berlangsung (kecuali setelah promosi).

Saya hanya melihat pada posisi kepingan di papan; status tambahan (yang gilirannya, yang telah mengebiri, en passant, gerakan berulang, dll.) harus dikodekan secara terpisah. Mungkin paling banyak 16 bit lagi, jadi 180 bit untuk seluruh status game. Pengoptimalan yang mungkin:

• Meninggalkan potongan yang lebih jarang, dan menyimpan posisinya secara terpisah. Tapi itu tidak akan membantu ... mengganti raja dan ratu dengan kotak kosong menghemat 5 bit, yang persis 5 bit yang Anda butuhkan untuk menyandikan posisi mereka dengan cara lain.
• "Tidak ada bidak di baris belakang" dapat dengan mudah dikodekan dengan menggunakan tabel Huffman yang berbeda untuk baris belakang, tapi saya ragu itu banyak membantu. Anda mungkin masih akan mendapatkan pohon Huffman yang sama.
• "Satu putih, satu uskup hitam" dapat dikodekan dengan memasukkan simbol tambahan yang tidak memiliki cbit, yang kemudian dapat disimpulkan dari kotak tempat uskup berada. (Bidak yang dipromosikan menjadi uskup mengganggu skema ini ...)
• Pengulangan kotak kosong dapat dikodekan sepanjang jalan dengan memasukkan simbol tambahan untuk, katakanlah, "2 kotak kosong dalam satu baris" dan "4 kotak kosong dalam satu baris". Tetapi tidak mudah untuk memperkirakan frekuensinya, dan jika Anda salah, itu akan lebih menyakitkan daripada membantu.

Pendekatan tabel pencarian yang sangat besar

Posisi - 18 byte
Perkiraan jumlah posisi legal adalah 10 ⁴³
Cukup sebutkan semuanya dan posisi dapat disimpan hanya dalam 143 bit. 1 bit lagi diperlukan untuk menunjukkan sisi mana yang akan dimainkan selanjutnya

Penghitungan tentu saja tidak praktis, tetapi ini menunjukkan bahwa diperlukan setidaknya 144 bit.

Moves - 1 byte
Biasanya ada sekitar 30-40 legal move untuk setiap posisi tetapi jumlahnya mungkin setinggi 218 Mari kita hitung semua langkah legal untuk setiap posisi. Sekarang setiap gerakan dapat dikodekan menjadi satu byte.

Kami masih memiliki banyak ruang untuk gerakan khusus seperti 0xFF untuk mewakili pengunduran diri.

Ini akan menambah minat untuk mengoptimalkan ukuran kasing rata-rata untuk gim biasa yang dimainkan oleh manusia, alih-alih kasus terburuk. (Pernyataan masalah tidak mengatakan yang mana; sebagian besar tanggapan menganggap kasus terburuk.)

Untuk urutan langkah, miliki mesin catur yang baik menghasilkan gerakan dari setiap posisi; itu akan menghasilkan daftar k gerakan yang mungkin, diurutkan berdasarkan peringkat kualitasnya. Orang pada umumnya memilih gerakan yang baik lebih sering daripada gerakan acak, jadi kita perlu mempelajari pemetaan dari setiap posisi dalam daftar ke kemungkinan orang memilih gerakan yang 'bagus'. Menggunakan probabilitas ini (berdasarkan kumpulan game dari beberapa database catur internet), menyandikan gerakan dengan pengkodean aritmatika . (Dekoder harus menggunakan mesin catur dan pemetaan yang sama.)

Untuk posisi awal, pendekatan ralu akan berhasil. Kita bisa menyempurnakannya dengan pengkodean aritmatika di sana juga, jika kita memiliki beberapa cara untuk menimbang pilihan dengan probabilitas - misalnya potongan-potongan sering muncul dalam konfigurasi yang saling membela, bukan secara acak. Lebih sulit untuk melihat cara mudah untuk memasukkan pengetahuan itu. Satu ide: kembali pada penyandian langkah di atas, mulai dari posisi pembukaan standar dan temukan urutan yang berakhir di papan yang diinginkan. (Anda dapat mencoba pencarian A * dengan jarak heuristik yang sama dengan jumlah jarak bidak dari posisi akhir mereka, atau sesuatu di sepanjang garis tersebut.) Ini memperdagangkan beberapa inefisiensi dari menentukan terlalu banyak urutan langkah vs. efisiensi dari memanfaatkan permainan catur pengetahuan.

Ini juga agak sulit untuk memperkirakan berapa banyak penghematan yang akan membeli Anda dalam kompleksitas kasus rata-rata, tanpa mengumpulkan beberapa statistik dari korpus yang sebenarnya. Tetapi titik awal dengan semua gerakan sama-sama mungkin saya pikir sudah akan mengalahkan sebagian besar proposal di sini: pengkodean aritmatika tidak memerlukan bilangan bulat bit per langkah.

Menyerang subproblem pengkodean langkah-langkah setelah posisi awal telah dikodekan. Pendekatannya adalah membuat "daftar terkait" langkah-langkah.

Setiap langkah dalam permainan dikodekan sebagai pasangan "posisi lama-> posisi baru". Anda tahu posisi awal di awal permainan catur; dengan melintasi daftar langkah yang ditautkan, Anda bisa mencapai status setelah X bergerak.

Untuk menyandikan setiap langkah, Anda memerlukan 64 nilai untuk menyandikan posisi awal (6 bit untuk 64 kotak di papan - kotak 8x8), dan 6 bit untuk posisi akhir. 16 bit untuk 1 gerakan di setiap sisi.

Jumlah ruang yang akan digunakan untuk menyandikan game tertentu kemudian sebanding dengan jumlah gerakan:

10 x (jumlah gerakan putih + jumlah langkah hitam) bit.

UPDATE: potensi komplikasi dengan bidak yang dipromosikan. Harus dapat menyatakan ke mana pion tersebut dipromosikan - mungkin perlu bit khusus (akan menggunakan kode abu-abu untuk ini untuk menghemat tempat, karena promosi pion sangat jarang).

UPDATE 2: Anda tidak perlu menyandikan koordinat lengkap posisi akhir. Dalam kebanyakan kasus, bagian yang sedang dipindahkan tidak dapat dipindahkan lebih dari X tempat. Misalnya, bidak dapat memiliki maksimal 3 opsi gerakan pada titik tertentu. Dengan menyadari bahwa jumlah gerakan maksimum untuk setiap jenis bagian, kita dapat menyimpan bit pada pengkodean "tujuan".

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

Jadi kompleksitas spasial per gerakan hitam atau putih menjadi

6 bit untuk posisi awal + (jumlah variabel bit berdasarkan jenis benda yang dipindahkan).

Saya melihat pertanyaan ini tadi malam dan itu membuat saya penasaran, jadi saya duduk di tempat tidur memikirkan solusi. Jawaban terakhir saya sangat mirip dengan int3 sebenarnya.

Solusi dasar

Dengan asumsi permainan catur standar dan Anda tidak menyandikan aturan (seperti Putih selalu duluan), maka Anda dapat menghemat banyak dengan hanya menyandikan gerakan yang dilakukan setiap bidak.

Ada total 32 buah tetapi pada setiap gerakan Anda tahu warna apa yang bergerak sehingga hanya ada 16 kotak yang perlu dikhawatirkan, yaitu 4 bit untuk bagian mana yang bergerak pada giliran ini.

Setiap bidak hanya memiliki gerakan terbatas, yang akan Anda sebutkan dengan cara tertentu.

• Pion: 4 opsi, 2 bit (1 langkah maju, 2 langkah maju, 1 setiap diagonal)
• Benteng: 14 opsi, 4 bit (maks 7 di setiap arah)
• Uskup: 13 pilihan, 4 bit (jika Anda memiliki 7 dalam satu diagonal, Anda hanya memiliki 6 di yang lain)
• Knight: 8 pilihan, 3 bit
• Ratu: 27 pilihan, 5 bit (Benteng + Peluncur)
• Raja: 9 opsi, 4 bit (8 langkah satu langkah, ditambah opsi kastling)

Untuk promosi, ada 4 buah untuk dipilih (Benteng, Peluncur, Ksatria, Ratu) jadi pada langkah itu kita akan menambahkan 2 bit untuk menentukannya. Saya pikir semua aturan lainnya tercakup secara otomatis (misalnya en passant).

Pengoptimalan lebih lanjut

Pertama, setelah 8 bagian dari satu warna ditangkap, Anda dapat mengurangi bagian pengkodean menjadi 3 bit, kemudian 2 bit untuk 4 bagian dan seterusnya.

Pengoptimalan utama adalah dengan menyebutkan hanya kemungkinan gerakan di setiap titik dalam game. Asumsikan kita menyimpan gerakan Pion sebagai{00, 01, 10, 11} untuk 1 langkah maju, 2 langkah maju, kiri diagonal, dan kanan diagonal. Jika beberapa gerakan tidak memungkinkan, kami dapat menghapusnya dari pengkodean untuk giliran ini.

Kami mengetahui status permainan di setiap tahap (dari mengikuti semua gerakan), jadi setelah membaca bagian mana yang akan bergerak, kami selalu dapat menentukan berapa banyak bit yang perlu kami baca. Jika kita menyadari pion hanya bergerak pada titik ini ditangkap secara diagonal ke kanan atau maju satu, kita tahu hanya membaca 1 bit.

Singkatnya, penyimpanan bit yang tercantum di atas untuk setiap bagian adalah maksimum saja. Hampir setiap gerakan akan memiliki lebih sedikit opsi dan seringkali lebih sedikit bit.

Di setiap posisi, dapatkan jumlah semua kemungkinan gerakan.

langkah selanjutnya dihasilkan sebagai

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

terbukti efisiensi ruang terbaik untuk menyimpan game yang dibuat secara acak dan membutuhkan kira-kira 5 bit / bergerak rata-rata karena Anda memiliki 30-40 kemungkinan gerakan. Penyimpanan perakitan hanya menghasilkan n dalam urutan terbalik.

Posisi penyimpanan lebih sulit dipecahkan, karena redundansi yang besar. (Bisa ada hingga 9 ratu di papan untuk satu situs tetapi dalam kasus itu tidak ada bidak, dan uskup jika di papan berada di kotak berwarna berlawanan) tetapi umumnya seperti menyimpan kombinasi bidak yang sama di atas petak yang tersisa.)

EDIT:

Poin dalam menyimpan gerakan adalah menyimpan hanya indeks gerakan. Alih-alih menyimpan Kc1-c2 dan mencoba mengurangi info ini, kita harus menambahkan hanya indeks pergerakan yang dihasilkan dari deterministic movegenerator (posisi)

Di setiap gerakan kami menambahkan informasi ukuran

num_of_moves = get_number_of_possible_moves(postion) ;

di pool dan jumlah ini tidak dapat dikurangi

menghasilkan kolam informasi

n=n*num_of_moves+ index_current_move

tambahan

Jika hanya ada satu gerakan yang tersedia di posisi akhir, simpan sebagai jumlah gerakan paksa yang dilakukan sebelumnya. Contoh: jika posisi awal memiliki 1 gerakan paksa untuk setiap sisi (2 gerakan) dan kami ingin menyimpannya sebagai permainan satu langkah, simpan 1 di pool n.

contoh penyimpanan ke dalam kumpulan info

Misalkan kita telah mengetahui posisi awal dan kita melakukan 3 gerakan.

Pada langkah pertama ada 5 langkah yang tersedia, dan kami mengambil indeks bergerak 4. Pada langkah kedua ada 6 langkah yang tersedia dan kami mengambil indeks posisi 3 dan pada langkah ke-3 ada 7 langkah tersedia untuk sisi itu dan dia memilih untuk memilih pindah indeks 2.

Bentuk vektor; indeks = [4,3,2] n_moves = [5,6,7]

Kami menyandikan info ini ke belakang, jadi n = 4 + 5 * (3 + 6 * (2)) = 79 (tidak perlu mengalikan dengan 7)

Bagaimana cara membuka pengait ini? Pertama kami memiliki posisi dan kami menemukan bahwa ada 5 gerakan yang tersedia. Begitu

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

Kami mengambil indeks bergerak 4 dan memeriksa posisi lagi dan dari titik ini kami menemukan bahwa ada 6 kemungkinan gerakan.

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

Dan kami mengambil indeks bergerak 3 yang membawa kami ke posisi dengan 7 kemungkinan gerakan.

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

Kami melakukan langkah terakhir indeks 2 dan kami mencapai posisi akhir.

Seperti yang Anda lihat, kompleksitas waktu adalah O (n) dan kompleksitas ruang adalah O (n). Sunting: kompleksitas waktu sebenarnya adalah O (n ^ 2) karena jumlah yang Anda perkalian dengan meningkat, tetapi seharusnya tidak ada masalah menyimpan game hingga 10.000 gerakan.

posisi tabungan

Dapat dilakukan mendekati optimal.

Ketika kita mencari tahu tentang informasi dan menyimpan informasi izinkan saya berbicara lebih banyak tentangnya. Ide umumnya adalah mengurangi redundansi (saya akan membicarakannya nanti). Mari kita asumsikan bahwa tidak ada promosi dan tidak ada pengambilan jadi ada 8 pion, 2 benteng, 2 ksatria, 2 uskup 1 raja dan 1 ratu per sisi.

Apa yang harus kita selamatkan: 1. posisi masing-masing perdamaian 2. kemungkinan castling 3. kemungkinan en-passant 4. pihak yang telah bergerak tersedia

Misalkan setiap bagian dapat berdiri di mana saja tetapi tidak 2 buah pada tempat yang sama. Jumlah cara menyusun 8 bidak berwarna sama di papan adalah C (64/8) (binomial) yaitu 32 bit, lalu 2 bidak 2R-> C (56/2), 2B -> C (54/2) , 2N-> C (52/2), 1Q-> C (50/1), 1K -> C (49/1) dan sama untuk situs lain tetapi dimulai dengan 8P -> C (48/8) dan seterusnya .

Mengalikan ini bersama-sama untuk kedua situs memberi kita nomor 4634726695587809641192045982323285670400000 yang kira-kira 142 bit, kita harus menambahkan 8 untuk satu kemungkinan en-passant (pion en-passant dapat berada di salah satu dari 8 tempat), 16 (4 bit) untuk batasan kastling dan satu bit untuk situs yang sudah pindah. Kami berakhir dengan 142 + 3 + 4 + 1 = 150bits

Tapi sekarang mari kita pergi berburu redundansi di papan tulis dengan 32 buah dan tanpa pengambilan.

1. kedua bidak hitam dan putih berada pada satu kolom yang sama dan saling berhadapan. Tiap pion berhadapan dengan pion lain artinya pion putih bisa paling banyak berada di peringkat 6. Ini membawa kita 8 * C (6/2) bukan C (64/8) * C (48/8) yang mengurangi informasi sebanyak 56 bit.

2. kemungkinan rokade juga berlebihan. Jika benteng tidak berada di tempat awal, tidak ada kemungkinan kastil sedikit pun dari benteng itu. Jadi kita bisa membayangkan menambahkan 4 kotak di papan untuk mendapatkan info tambahan jika mengebiri sedikit pun benteng ini mungkin dan menghapus 4 bit kastil. Jadi alih-alih C (56/2) * C (40/2) * 16 kami memiliki C (58/2) * C (42/2) dan kami kehilangan 3,76 bit (hampir semua 4 bit)

3. en-passant: Ketika kita menyimpan salah satu dari 8 kemungkinan passant, kita mengetahui posisi bidak hitam dan mengurangi redindancy informasi (jika pion putih dan en-passant pion ke-3 itu berarti pion hitam ada di c5 dan pion putih ada c2, c3 atau c4) jadi dengan C (6/2) kita punya 3 dan kita kehilangan 2.3 bits. Kita mengurangi beberapa redundansi jika kita menyimpan sedikit pun nomor en-passant serta sisi dari mana yang bisa dikerjakan (3 kemungkinan-> kiri, kanan, keduanya) dan kita tahu kepemilikan bidak yang bisa lewat. (Misalnya dari prevous en passant contoh hitam putih di c5 apa bisa di kiri, kanan atau keduanya. jika di satu situs kami memiliki 2 * 3 (3 untuk menyimpan psissibilites dan 2 kemungkinan jurus untuk pion hitam di peringkat 7 atau 6 ) dengan C (6/2) dan kita kurangi sebesar 1,3 bit dan jika pada kedua sisi kita kurangi sebesar 4,2 bit, dengan begitu kita dapat mengurangi sebesar 2,3 + 1,3 = 3.

4. uskup: uskup hanya boleh berada di kotak yang berlawanan, ini mengurangi redundansi 1 bit untuk setiap situs.

Jika kita menjumlahkan kita membutuhkan 150-56-4-3.6-2 = 85bits untuk menyimpan posisi catur jika tidak ada pengambilan.

Dan mungkin tidak lebih jika ada pengambilan dan promosi yang diperhitungkan (tetapi saya akan menulis tentang itu nanti jika seseorang akan menemukan posting panjang ini berguna)

Kebanyakan orang telah mengkodekan status papan, tetapi mengenai gerakan itu sendiri .. Berikut adalah deskripsi pengkodean bit.

Bit per potong:

• ID Bagian: Maks 4 bit untuk mengidentifikasi 16 buah per sisi. Putih / hitam bisa disimpulkan. Tetapkan urutan pada potongan. Saat jumlah bidak turun di bawah pangkat dua masing-masing, gunakan lebih sedikit bidak untuk mendeskripsikan bidak yang tersisa.
• Menggadaikan: 3 kemungkinan pada langkah pertama, jadi +2 bit (maju satu atau dua kotak, en passant.) Gerakan selanjutnya tidak memungkinkan untuk bergerak maju dua, jadi +1 bit sudah cukup. Promosi dapat disimpulkan dalam proses decoding dengan mencatat ketika bidak telah mencapai peringkat terakhir. Jika bidak diketahui dipromosikan, decoder akan mengharapkan 2 bit lagi yang menunjukkan mana dari 4 bidak utama yang telah dipromosikan.
• Bishop: +1 bit untuk penggunaan diagonal, Hingga +4 bit untuk jarak sepanjang diagonal (16 kemungkinan). Dekoder dapat menyimpulkan jarak maksimum yang mungkin bahwa potongan dapat bergerak di sepanjang diagonal itu, jadi jika diagonalnya lebih pendek, gunakan lebih sedikit bit.
• Knight: 8 kemungkinan gerakan, +3 bit
• Benteng: +1 bit untuk horizontal / vertikal, +4 bit untuk jarak sepanjang garis.
• Raja: 8 kemungkinan gerakan, +3 bit. Tunjukkan rokade dengan gerakan 'tidak mungkin' - karena rokade hanya mungkin dilakukan saat raja berada di peringkat pertama, lakukan sandi langkah ini dengan instruksi untuk memindahkan raja 'mundur' - yaitu keluar dari papan.
• Ratu: 8 kemungkinan arah, + 3bits. Hingga +4 bit lagi untuk jarak sepanjang garis / diagonal (kurangi jika diagonal lebih pendek, seperti pada kasus uskup)

Dengan asumsi semua bidak ada di papan, ini adalah bit per gerakan: Pion - 6 bit pada langkah pertama, 5 selanjutnya. 7 jika dipromosikan. Bishop: 9 bit (maks), Knight: 7, Benteng: 9, Raja: 7, Ratu: 11 (maks).

Apakah masalah untuk memberikan pengkodean yang paling efisien untuk permainan catur biasa, atau yang memiliki pengkodean kasus terburuk terpendek?

Untuk yang terakhir, cara yang paling efisien juga yang paling buram: buat penghitungan semua pasangan yang mungkin (papan awal, urutan gerakan yang sah), yang, dengan draw-on-three-repeat-position dan no-more-than -lima puluh-gerakan sejak aturan-pion-pindah-atau-tangkap terakhir, bersifat rekursif. Kemudian indeks posisi dalam urutan terbatas ini memberikan pengkodean kasus terburuk terpendek, tetapi juga pengkodean yang sama panjangnya untuk kasus-kasus biasa, dan, saya perkirakan, sangat mahal untuk dihitung. Permainan catur terpanjang seharusnya lebih dari 5000 gerakan, dengan biasanya ada 20-30 gerakan yang tersedia di setiap posisi untuk setiap pemain (meskipun lebih sedikit ketika ada beberapa bidak tersisa) - ini memberikan sekitar 40000 bit yang dibutuhkan untuk pengkodean ini.

Ide enumerasi dapat diterapkan untuk memberikan solusi yang lebih mudah diatur, seperti yang dijelaskan dalam saran Henk Holterman untuk pengkodean langkah di atas. Saran saya: tidak minimal, tapi lebih pendek dari contoh di atas yang pernah saya lihat, dan masuk akal bisa ditelusuri:

1. 64 bit untuk mewakili kotak mana yang ditempati (matriks hunian), ditambah daftar bidak mana yang berada di setiap kotak yang ditempati (dapat memiliki 3 bit untuk bidak, dan 4 bit untuk bidak lainnya): ini memberikan 190 bit untuk posisi awal. Karena tidak boleh lebih dari 32 buah di papan, pengkodean matriks hunian berlebihan & sesuatu seperti posisi papan umum dapat dikodekan, katakanlah sebagai 33 bit set ditambah indeks papan dari daftar papan umum.

2. 1 bit untuk mengatakan siapa yang membuat langkah pertama

3. Pergerakan kode sesuai saran Henk: biasanya 10 bit per pasang gerakan putih / hitam, meskipun beberapa gerakan akan mengambil 0 bit, ketika pemain tidak memiliki gerakan alternatif.

Ini menyarankan 490 bit untuk mengkodekan permainan 30 langkah yang khas, dan akan menjadi representasi yang cukup efisien untuk permainan biasa.

Di awal penyandian draw-on-three-repeat-position dan tidak-lebih-dari-lima puluh-gerakan sejak aturan pion-pindahkan-atau-tangkap terakhir: jika Anda mengenkode gerakan terakhir kembali ke langkah pion terakhir atau tangkap, maka Anda memiliki informasi yang cukup untuk memutuskan apakah aturan ini berlaku: tidak perlu untuk seluruh riwayat permainan.

Posisi di papan dapat ditentukan dalam 7 bit (0-63, dan 1 nilai yang menentukan itu tidak ada di papan lagi). Jadi untuk setiap bagian di papan tulis tentukan di mana lokasinya.

32 buah * 7 bit = 224 bit

EDIT: seperti yang ditunjukkan Cadrian ... kami juga memiliki kasus 'pion yang dipromosikan menjadi ratu'. Saya sarankan kita menambahkan bit ekstra di akhir untuk menunjukkan bidak mana yang telah dipromosikan.

Jadi untuk setiap bidak yang dipromosikan, kita mengikuti 224 bita dengan 5 bita yang menunjukkan indeks bidak yang dipromosikan, dan 11111 jika itu adalah akhir dari daftar.

Jadi kasus minimal (tidak ada promosi) adalah 224 bit + 5 (tidak ada promosi). Untuk setiap pion yang dipromosikan tambahkan 5 bit.

EDIT: Seperti yang ditunjukkan katak berbulu, kita membutuhkan sedikit lagi di akhir untuk menunjukkan giliran siapa; ^)

Saya akan menggunakan pengkodean run length. Beberapa bagian unik (atau hanya ada dua kali), jadi saya bisa menghilangkan panjang setelahnya. Seperti cletus, saya memerlukan 13 status unik, jadi saya dapat menggunakan nibble (4 bit) untuk menyandikannya. Papan awal akan terlihat seperti ini:

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

yang menyisakan saya dengan 8 + 2 + 4 + 2 + 8 camilan = 24 camilan = 96 bit. Saya tidak bisa mengenkode 16 dengan gigitan tapi karena "Empty, 0" tidak masuk akal, saya bisa memperlakukan "0" sebagai "16".

Jika papan kosong tetapi untuk bidak tunggal di sudut kiri atas, saya mendapatkan "Pion, 1, Kosong, 16, Kosong, 16, Kosong 16, Kosong, 15" = 10 camilan = 40 bit.

Kasus terburuk adalah ketika saya memiliki kotak kosong di antara setiap bagian. Tapi untuk pengkodean bagian, saya hanya perlu 13 dari 16 nilai, jadi mungkin saya bisa menggunakan nilai lain untuk mengatakan "Kosong1". Kalau begitu, saya butuh 64 camilan == 128bits.

Untuk pergerakan, saya membutuhkan 3 bit untuk bagian (warna diberikan oleh fakta bahwa putih selalu bergerak pertama) ditambah 5 bit (0..63) untuk posisi baru = satu byte per gerakan. Sebagian besar waktu, saya tidak membutuhkan posisi lama karena hanya satu bagian yang berada dalam jangkauan. Untuk kasus ganjil, saya harus menggunakan kode tunggal yang tidak digunakan (saya hanya perlu 7 kode untuk menyandikannya) dan kemudian 5 bit untuk yang lama dan 5 bit untuk posisi baru.

Ini memungkinkan saya untuk menyandikan kastel dalam 13 gigitan (saya bisa menggerakkan Raja ke Benteng yang cukup untuk mengatakan apa yang saya inginkan).

[EDIT] Jika Anda mengizinkan pembuat enkode cerdas, maka saya perlu 0 bit untuk penyiapan awal (karena tidak harus dikodekan dengan cara apa pun: Ini statis) ditambah satu byte per gerakan.

[EDIT2] Yang meninggalkan transformasi bidak. Jika bidak mencapai baris terakhir, saya dapat memindahkannya di tempat untuk mengatakan "mengubah" dan kemudian menambahkan 3 bit untuk bidak yang menggantikannya (Anda tidak harus menggunakan ratu; Anda dapat mengganti bidak dengan apa pun tapi Raja).

Sama seperti mereka menyandikan permainan di atas buku dan kertas: setiap bagian memiliki simbol; karena ini adalah permainan "legal", putih bergerak lebih dulu - tidak perlu menyandikan putih atau hitam secara terpisah, cukup hitung jumlah gerakan untuk menentukan siapa yang pindah. Selain itu, setiap gerakan dikodekan sebagai (bagian, posisi akhir) di mana 'posisi akhir' dikurangi menjadi simbol paling sedikit yang memungkinkan untuk membedakan ambiguitas (bisa nol). Panjang permainan menentukan jumlah gerakan. Seseorang juga dapat menyandikan waktu dalam menit (sejak langkah terakhir) di setiap langkah.

Pengkodean bidak dapat dilakukan baik dengan menetapkan simbol ke masing-masing (total 32) atau dengan menetapkan simbol ke kelas, dan menggunakan posisi akhir untuk memahami bagian mana yang dipindahkan. Misalnya, bidak memiliki 6 kemungkinan posisi akhir; tetapi rata-rata hanya pasangan yang tersedia untuk itu di setiap kesempatan. Jadi, secara statistik, pengkodean dengan posisi akhir mungkin yang terbaik untuk skenario ini.

Pengodean serupa digunakan untuk kereta lonjakan dalam ilmu saraf komputasi (AER).

Kekurangan: Anda perlu memutar ulang seluruh game untuk mendapatkan status saat ini dan menghasilkan subset, seperti menelusuri daftar tertaut.

Ada 64 kemungkinan posisi papan, jadi Anda membutuhkan 6 bit per posisi. Ada 32 buah awal, jadi sejauh ini kami memiliki total 192 bit, di mana setiap 6 bit menunjukkan posisi potongan yang diberikan. Kita dapat menentukan sebelumnya urutan bidak-bidak itu muncul, jadi kita tidak perlu mengatakan yang mana.

Bagaimana jika ada bagian dari papan? Nah, kita dapat menempatkan keping di tempat yang sama dengan bidak lainnya untuk menunjukkan bahwa itu tidak berlaku, karena itu akan ilegal jika tidak. Tapi kami juga tidak tahu apakah potongan pertama akan ada di papan atau tidak. Jadi kami menambahkan 5 bit yang menunjukkan bagian mana yang pertama (32 kemungkinan = 5 bit untuk mewakili bagian pertama). Kemudian kita dapat menggunakan tempat itu untuk potongan-potongan berikutnya yang ada di luar papan. Itu membawa kita ke total 197 bit. Harus ada setidaknya satu bagian di papan, sehingga itu akan berhasil.

Kemudian kita membutuhkan satu bit untuk siapa gilirannya - menghasilkan 198 bit .

Bagaimana dengan promosi gadai? Kita bisa melakukannya dengan cara yang buruk dengan menambahkan 3 bit per bidak, menambahkan 42 bit. Tetapi kemudian kita dapat melihat bahwa sebagian besar waktu, bidak tidak dipromosikan.

Jadi, untuk setiap bidak yang ada di papan, bit '0' menandakan tidak dipromosikan. Jika bidak tidak ada di papan maka kita tidak membutuhkannya sama sekali. Kemudian kita dapat menggunakan string bit panjang variabel yang promosinya dia miliki. Yang paling sering adalah ratu, jadi "10" bisa berarti RATU. Kemudian "110" berarti benteng, "1110" berarti uskup, dan "1111" berarti kesatria.

Keadaan awal akan mengambil 198 + 16 = 214 bit , karena semua 16 bidak ada di papan dan tidak dipromosikan. Permainan akhir dengan dua pion-ratu yang dipromosikan mungkin membutuhkan sesuatu seperti 198 + 4 + 4, yang berarti 4 bidak hidup dan tidak dipromosikan dan 2 pion ratu, dengan total 206 bit . Sepertinya cukup kuat!

===

Pengodean Huffman, seperti yang ditunjukkan orang lain, akan menjadi langkah selanjutnya. Jika Anda mengamati beberapa juta permainan, Anda akan melihat bahwa setiap bagian kemungkinan besar berada di kotak tertentu. Misalnya, sebagian besar waktu, bidak tetap dalam garis lurus, atau satu ke kiri / satu ke kanan. Raja biasanya akan bertahan di sekitar pangkalan.

Oleh karena itu, buat skema pengkodean Huffman untuk setiap posisi terpisah. Bidak kemungkinan hanya akan mengambil rata-rata 3-4 bit, bukan 6. Raja juga harus mengambil beberapa bit.

Juga dalam skema ini, sertakan "diambil" sebagai posisi yang memungkinkan. Ini juga dapat menangani rokade dengan sangat kuat - setiap benteng dan raja akan memiliki status ekstra "posisi awal, dipindahkan". Anda juga dapat mengkodekan en passant di bidak dengan cara ini - "posisi awal, bisa en passant".

Dengan data yang cukup, pendekatan ini akan memberikan hasil yang sangat bagus.

Saya akan mencoba menggunakan pengkodean Huffman . Teori di balik ini adalah - dalam setiap permainan catur akan ada beberapa buah catur yang akan banyak bergerak, dan beberapa tidak banyak bergerak atau tersingkir lebih awal. Jika posisi awal memiliki beberapa bagian yang sudah dilepas - semuanya lebih baik. Hal yang sama berlaku untuk kotak - beberapa kotak dapat melihat semua aksi, sementara beberapa tidak banyak tersentuh.

Jadi saya akan memiliki dua tabel Huffman - satu untuk potongan, lainnya untuk kotak. Mereka akan dihasilkan dengan melihat game yang sebenarnya. Saya dapat memiliki satu meja besar untuk setiap pasangan bujur sangkar, tetapi saya pikir itu akan sangat tidak efisien karena tidak banyak contoh bidak yang sama bergerak di kotak yang sama lagi.

Setiap bagian akan memiliki ID yang ditetapkan. Karena ada 32 bagian yang berbeda, saya hanya membutuhkan 5 bit untuk ID bagian. ID bidak tidak berubah dari game ke game. Hal yang sama berlaku untuk ID persegi, yang saya perlukan 6 bit.

Pohon Huffman akan dikodekan dengan menuliskan setiap node ke bawah saat mereka dilintasi secara inorder (yaitu, pertama node adalah output, kemudian turunannya dari kiri ke kanan). Untuk setiap node akan ada satu bit yang menentukan apakah itu node daun atau node cabang. Jika itu simpul daun, itu akan diikuti oleh bit yang memberikan ID.

Posisi awal hanya akan diberikan oleh serangkaian pasangan lokasi potongan. Setelah itu akan ada satu pasangan lokasi potong untuk setiap gerakan. Anda dapat menemukan akhir deskriptor posisi awal (dan deskriptor awal gerakan) cukup dengan mencari bagian pertama yang disebutkan dua kali. Jika pion dipromosikan, akan ada 2 bit ekstra yang menentukan menjadi apa, tetapi ID bidak tidak akan berubah.

Untuk memperhitungkan kemungkinan pion dipromosikan di awal permainan, juga akan ada "tabel promosi" antara pohon huffman dan data. Pada awalnya akan ada 4 bit yang menentukan berapa banyak bidak yang ditingkatkan. Kemudian untuk setiap pion akan ada ID yang dikodekan huffman dan 2 bit yang menentukan jadinya seperti apa.

Pohon huffman akan dibuat dengan memperhitungkan semua data (baik posisi awal dan gerakan) dan tabel promosi. Meskipun biasanya tabel promosi akan kosong atau hanya memiliki beberapa entri.

Untuk meringkasnya dalam istilah grafis:

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

Ditambahkan: Ini masih bisa dioptimalkan. Setiap bagian hanya memiliki beberapa langkah hukum. Alih-alih hanya mengenkode kotak target, seseorang dapat memberikan ID berbasis 0 untuk kemungkinan pergerakan setiap bagian. ID yang sama akan digunakan kembali untuk setiap bidak, jadi totalnya tidak akan ada lebih dari 21 ID yang berbeda (ratu dapat memiliki paling banyak 21 opsi pemindahan yang berbeda). Letakkan ini di tabel huffman, bukan di kolom.

Namun hal ini akan menimbulkan kesulitan dalam merepresentasikan keadaan aslinya. Seseorang mungkin menghasilkan serangkaian gerakan untuk menempatkan setiap bagian pada tempatnya. Dalam hal ini akan perlu untuk entah bagaimana menandai akhir dari keadaan awal dan dimulainya gerakan.

Atau mereka dapat ditempatkan dengan menggunakan ID persegi 6-bit yang tidak terkompresi.

Apakah ini akan menyebabkan penurunan ukuran secara keseluruhan - saya tidak tahu. Mungkin, tapi harus sedikit bereksperimen.

Menambahkan 2: Satu kasus khusus lagi. Jika status permainan tidak memiliki gerakan NO, penting untuk membedakan siapa yang bergerak selanjutnya. Tambahkan satu bit lagi di akhir untuk itu. :)

[diedit setelah membaca pertanyaan dengan benar] Jika Anda menganggap setiap posisi hukum dapat dicapai dari posisi awal (yang merupakan definisi yang mungkin dari "legal"), maka posisi apa pun dapat dinyatakan sebagai urutan langkah dari awal. Cuplikan permainan yang dimulai dari posisi non-standar dapat dinyatakan sebagai urutan gerakan yang diperlukan untuk mencapai awal, sakelar untuk menyalakan kamera, diikuti dengan gerakan berikutnya.

Jadi mari kita sebut papan awal menyatakan bit tunggal "0".

Gerakan dari posisi mana pun dapat dihitung dengan menomori kotak dan mengurutkan gerakan dengan (mulai, akhir), dengan lompatan 2 kotak konvensional yang menunjukkan rokade. Tidak perlu menyandikan gerakan ilegal, karena posisi papan dan aturan selalu sudah diketahui. Bendera untuk menyalakan kamera dapat diekspresikan sebagai gerakan in-band khusus, atau lebih bijaksana sebagai nomor langkah out-of-band.

Ada 24 gerakan pembukaan untuk kedua sisi, yang masing-masing dapat memuat 5 bit. Gerakan selanjutnya mungkin membutuhkan lebih banyak atau lebih sedikit bit, tetapi langkah legal selalu dapat dihitung, sehingga lebar setiap gerakan dapat dengan senang hati tumbuh atau berkembang. Saya belum menghitung, tapi saya membayangkan posisi 7 bit akan langka.

Dengan menggunakan sistem ini, permainan 100 setengah gerak dapat dikodekan dalam sekitar 500 bit. Namun, mungkin bijaksana untuk menggunakan buku pembuka. Misalkan berisi sejuta urutan. Biarkan, awal 0 menunjukkan awal dari papan standar, dan 1 diikuti dengan nomor 20 bit menunjukkan awal dari urutan pembukaan itu. Game dengan bukaan yang agak konvensional dapat dipersingkat dengan katakanlah 20 setengah gerakan, atau 100 bit.

Ini bukan kompresi terbesar yang mungkin, tetapi (tanpa buku pembuka) akan sangat mudah diterapkan jika Anda sudah memiliki model catur, yang diasumsikan oleh pertanyaan tersebut.

Untuk mengompres lebih lanjut, Anda ingin mengurutkan gerakan sesuai dengan kemungkinan daripada dalam urutan sewenang-wenang, dan menyandikan urutan kemungkinan dalam bit yang lebih sedikit (misalnya menggunakan token Huffman seperti yang disebutkan orang).

Jika waktu komputasi tidak menjadi masalah, maka Anda dapat menggunakan generator posisi deterministik yang memungkinkan untuk menetapkan id unik ke posisi tertentu.

Dari posisi tertentu, pertama-tama buatlah sejumlah kemungkinan posisi dalam manor deterministik, misalnya mulai dari kiri bawah ke kanan atas. Itu menentukan berapa banyak bit yang Anda perlukan untuk langkah selanjutnya, beberapa situasi bisa jadi sesedikit itu. Kemudian ketika pindah dilakukan simpan hanya id unik untuk pindah itu.

Promosi dan aturan lainnya hanya dihitung sebagai gerakan yang sah selama mereka ditangani dengan cara deterministik, misalnya ke ratu, ke benteng, ke uskup, masing-masing dihitung sebagai gerakan terpisah.

Posisi awal paling sulit dan dapat menghasilkan sekitar 250 juta kemungkinan posisi (menurut saya) yang akan membutuhkan sekitar 28 bit ditambah sedikit tambahan untuk menentukan gerakan siapa itu.

Dengan asumsi kita tahu siapa yang memutarnya (setiap belokan berubah dari putih menjadi hitam) generator deterministik akan terlihat seperti:

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

'dapatkan daftar gerakan yang mungkin' akan menghasilkan sesuatu seperti:

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.

Jika raja di cek maka setiap 'daftar kemungkinan xxx bergerak' hanya mengembalikan gerakan yang valid yang mengubah situasi pemeriksaan.

Sebagian besar jawaban mengabaikan pengulangan 3 kali lipat. sayangnya untuk pengulangan 3 kali lipat Anda harus menyimpan semua posisi yang dimainkan sejauh ini ...

Pertanyaan tersebut mengharuskan kami untuk menyimpan dalam cara yang efisien ruang sehingga kami benar-benar tidak perlu menyimpan posisi selama kami dapat membangunnya dari daftar gerakan (asalkan kami memiliki posisi awal standar). PGN bisa kita optimalkan dan selesai. Di bawah ini adalah skema sederhana.

Ada 64 kotak di papan, 64 = 2 ^ 6. Jika kita hanya menyimpan kotak awal dan akhir dari setiap gerakan yang akan membutuhkan 12 bit (Promosi akan ditangani nanti). Perhatikan bahwa skema ini sudah mencakup pemain untuk bergerak, tegas, bidak ditangkap, rokade, dll; karena ini dapat dibuat hanya dari memutar ulang daftar langkah.

untuk promosi kita dapat menyimpan array vektor terpisah yang akan mengatakan "pada langkah N promosikan ke Bagian XYZ". kita dapat menyimpan vektor (int, byte).

Sangat menggoda untuk mengoptimalkan vektor (To, From) juga, Karena banyak dari vektor (To, From) ini tidak dimungkinkan dalam catur. misalnya. tidak akan ada perpindahan dari e1 ke d8 dll. Tapi saya tidak bisa menemukan skema apapun. Ide lebih lanjut akan sangat disambut.

Saya sudah memikirkan itu untuk waktu yang lama (+ - 2 jam). Dan tidak ada jawaban yang jelas.

Asumsi:

1. Mengabaikan status waktu (Seorang pemain tidak menggunakan untuk memiliki batas waktu sehingga dapat memaksa hasil imbang dengan tidak bermain)
2. Kapan game itu dimainkan?!? Ini penting karena aturannya telah berubah dari waktu ke waktu (jadi akan mengasumsikan permainan modern pada poin berikutnya sebagai permainan modern ...) Silakan merujuk ke aturan bidak mati misalnya (wikipedia memiliki masalah yang sangat terkenal yang menunjukkannya), dan jika Anda mau untuk kembali ke masa semoga sukses uskup dulu hanya bergerak perlahan dan dadu biasa digunakan. lol.

... jadi aturan modern terkini. Pertama terlepas dari pengulangan dan pindahkan batas pengulangan.

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

= 64 bits (sesuatu / tidak sama sekali) + 32 * 4 bits [1bit = color {black / withe} + 3bit = type bidak {Raja, Ratu, Uskup, kNight, Benteng, Pion, MovedPawn} NB: Bidak Pindah ... misalnya jika itu adalah bidak yang terakhir dipindahkan pada giliran sebelumnya yang menunjukkan bahwa 'en passant' layak. ] + 5bit untuk keadaan sebenarnya (siapa yang berbalik, sambil lalu, kemungkinan rooking atau tidak di setiap sisi)

Sejauh ini baik. Mungkin bisa ditingkatkan tapi kemudian akan ada variabel panjang dan promosi yang harus dipertimbangkan !?

Sekarang, aturan berikut hanya berlaku KETIKA seorang pemain mendaftar untuk seri, ITU TIDAK otomatis! Jadi anggaplah 90 langkah ini tanpa penangkapan atau gerakan bidak adalah layak jika tidak ada pemain yang meminta hasil imbang! Artinya semua gerakan perlu direkam ... dan tersedia.

-D pengulangan posisi ... misalnya keadaan papan seperti yang disebutkan di atas (lihat C) atau tidak ... (lihat berikut mengenai aturan FIDE) -E Itu menyisakan masalah kompleks 50 penyisihan bergerak tanpa penangkapan atau pion bergerak di sana a counter diperlukan ... Namun.

Jadi bagaimana Anda mengatasinya? ... Sebenarnya tidak mungkin. Karena tidak ada pemain yang ingin menggambar, atau menyadari bahwa itu telah terjadi. Sekarang dalam kasus E penghitung mungkin cukup ... tetapi berikut adalah trik dan bahkan membaca aturan FIDE (http://www.fide.com/component/handbook/?id=124&view=article) Saya tidak dapat menemukan menjawab ... bagaimana dengan hilangnya kemampuan rooking. Apakah itu pengulangan? Saya kira tidak, tetapi kemudian ini adalah subjek kabur yang tidak dialamatkan, tidak diklarifikasi.

Jadi di sini ada dua aturan yang dua kompleks atau tidak terdefinisi bahkan untuk mencoba menyandikan ... Cheers.

Jadi, satu-satunya cara untuk benar-benar menyandikan game adalah merekam semua dari awal ... yang kemudian bertentangan (atau tidak?) Dengan pertanyaan "status papan".

Semoga bantuan ini ... tidak terlalu banyak matematika :-) Hanya untuk menunjukkan bahwa beberapa pertanyaan tidak semudah, terlalu terbuka untuk interpretasi atau pra-pengetahuan untuk menjadi benar dan efisien. Tidak satu pun yang akan saya pertimbangkan untuk wawancara karena membuka terlalu banyak kaleng cacing.

Kemungkinan perbaikan pada posisi awal dalam solusi Yacoby

Tidak ada posisi hukum yang memiliki lebih dari 16 buah setiap warna. Jumlah cara untuk menempatkan hingga 16 buah hitam dan 16 buah putih pada 64 kotak adalah sekitar 3.63e27. Log2 (3.63e27) = 91.55. Ini berarti Anda dapat menyandikan posisi dan warna semua bagian dalam 92 bit. Ini kurang dari 64 bit untuk posisi + hingga 32 bit untuk warna yang dibutuhkan oleh solusi Yacoby. Anda dapat menyimpan 4 bit dalam kasus terburuk dengan mengorbankan kerumitan yang cukup besar dalam pengkodean.

Di sisi lain, ini meningkatkan ukuran untuk posisi dengan 5 atau lebih bagian yang hilang. Posisi ini hanya mewakili <4% dari semua posisi, tetapi mungkin sebagian besar kasus di mana Anda ingin merekam posisi awal yang berbeda dari posisi awal.

Ini mengarah pada solusi lengkap

1. Encode posisi dan warna potongan sesuai dengan metode di atas. 92 bit .
2. Untuk menentukan tipe tiap bidak, gunakan Kode Huffman: pion: '0', benteng: '100', ksatria: '101', uskup: '110', ratu: '1110', raja: '1111'. Ini membutuhkan (16 * 1 + 12 * 3 + 4 * 4) = 68 bit untuk satu set lengkap potongan. Posisi papan penuh dapat dikodekan dalam 92 + 68 = maksimum 160 bit .
3. Status permainan tambahan harus ditambahkan: putar: 1 bit, yang memungkinkan untuk melakukan castling: 4 bit, "en passant" mungkin: hingga 4 bit (1 bit menyatakan masalahnya dan 3 bit memberi tahu yang mana). Posisi awal dikodekan dalam = 160 + 9 = 169 bit
4. Untuk daftar gerakan, hitung semua gerakan yang mungkin untuk posisi tertentu dan simpan posisi gerakan tersebut dalam daftar. Daftar gerakan mencakup semua kasus khusus (castling, en passant, dan mengundurkan diri). Gunakan bit sebanyak yang diperlukan untuk menyimpan posisi tertinggi. Rata-rata itu tidak boleh melebihi 7 bit per gerakan (16 kemungkinan potongan dan rata-rata 8 gerakan hukum per buah). Dalam beberapa kasus, ketika suatu gerakan dipaksa, itu hanya membutuhkan 1 bit (pindah atau mundur).

Ada 32 buah di papan tulis. Setiap bidak memiliki posisi (satu dalam 64 kotak). Jadi, Anda hanya perlu 32 bilangan bulat positif.

Saya tahu 64 posisi bertahan dalam 6 bit tetapi saya tidak akan melakukannya. Saya akan menyimpan potongan terakhir untuk beberapa bendera (potongan jatuh, pion ratu)

jawaban cletus bagus, tapi dia lupa juga menyandikan giliran siapa. Ini adalah bagian dari status saat ini, dan diperlukan jika Anda menggunakan status tersebut untuk menjalankan algoritme penelusuran (seperti turunan alfa-beta).

Saya bukan pemain catur, tapi saya yakin ada satu kasus lagi di sudut: berapa banyak gerakan yang telah diulang. Setelah setiap pemain melakukan gerakan yang sama tiga kali, permainannya seri, bukan? Jika demikian, maka Anda perlu menyimpan informasi itu di negara bagian karena setelah pengulangan ketiga, status sekarang terminal.

Seperti yang telah disebutkan beberapa orang lain, Anda bisa untuk masing-masing dari 32 buah yang dapat Anda simpan di kotak mana mereka berada dan jika mereka ada di papan atau tidak, ini memberikan 32 * (log2 (64) + 1) = 224 bit.

Namun para uskup hanya dapat menempati kotak hitam atau putih jadi untuk ini Anda hanya perlu log2 (32) bit untuk posisi tersebut, yang memberikan 28 * 7 + 4 * 6 = 220 bit.

Dan karena bidak tidak mulai dari belakang dan hanya bisa bergerak maju, bidak hanya bisa berada di 56, seharusnya mungkin menggunakan batasan ini untuk mengurangi jumlah bidak yang dibutuhkan untuk bidak.

Sebuah papan memiliki 64 kotak, dan dapat diwakili oleh 64 bit yang menunjukkan apakah sebuah kotak kosong atau tidak. Kami hanya membutuhkan informasi bidak jika bujur sangkar memiliki bidak. Karena pemain + bidak membutuhkan 4 bit (seperti yang ditunjukkan sebelumnya), kita bisa mendapatkan status saat ini dalam 64 + 4 * 32 = 192 bit. Lempar di belokan saat ini dan Anda memiliki 193 bit.

Namun, kami juga perlu menyandikan langkah hukum untuk setiap bagian. Pertama, kami menghitung jumlah langkah hukum untuk setiap bagian, dan menambahkan banyak bit setelah pengidentifikasi bagian dari kotak penuh. Saya menghitung sebagai berikut:

Pion: Maju, giliran pertama dua ke depan, en passant * 2, promotion = 7 bits. Anda dapat menggabungkan belokan pertama ke depan dan promosi menjadi satu bit karena tidak dapat terjadi dari posisi yang sama, jadi Anda memiliki 6. Benteng: 7 kotak vertikal, 7 kotak horizontal = 14 bit Knight: 8 kotak = 8 bit Bishop: 2 diagonal * 7 = 14 bit Queen: 7 vertikal, 7 horizontal, 7 diagonal, 7 diagonal = 28 bit King: 8 kotak sekeliling

Ini tetap berarti Anda perlu memetakan kotak yang ditargetkan berdasarkan posisi saat ini, tetapi ini (seharusnya) merupakan perhitungan sederhana.

Karena kita memiliki 16 pion, 4 benteng / ksatria / uskup, dan 2 ratu / raja, ini adalah 16 * 6 + 4 * 14 + 4 * 8 + 4 * 14 + 2 * 28 + 2 * 8 = 312 bidak lagi, membawa total menjadi 505 bit secara keseluruhan.

Adapun jumlah bit yang diperlukan per bagian untuk kemungkinan gerakan, beberapa optimisasi dapat ditambahkan ke sana dan jumlah bit mungkin berkurang, saya hanya menggunakan angka yang mudah untuk dikerjakan. Misalnya, untuk potongan geser Anda dapat menyimpan seberapa jauh mereka bisa bergerak, tetapi ini akan membutuhkan perhitungan ekstra.

Singkat cerita: Hanya menyimpan data tambahan (potongan, dll) ketika sebuah persegi ditempati, dan hanya menyimpan jumlah bit minimum untuk setiap bagian untuk mewakili langkah hukumnya.

EDIT1: Lupa tentang rokade dan promosi gadai ke bagian mana pun. Ini bisa membuat total dengan posisi eksplisit menjadi 557 gerakan (3 bit lagi untuk bidak, 2 untuk raja)

Setiap bidak dapat diwakili oleh 4 bit (pion to king, 6 jenis), hitam / putih = 12 nilai

Setiap kotak di papan dapat diwakili oleh 6 bit (x coord, y coord).

Posisi awal membutuhkan maksimum 320 bit (32 buah, 4 + 6 bit)

Setiap gerakan selanjutnya dapat diwakili oleh 16 bit (dari posisi, ke posisi, bidak).

Castling akan membutuhkan 16 bit ekstra, karena ini merupakan gerakan ganda.

Bidak yang antri dapat diwakili oleh salah satu dari 4 nilai cadangan dari 4 bit.

Tanpa melakukan matematika secara rinci, ini mulai menghemat ruang setelah langkah pertama dibandingkan dengan menyimpan 32 * 7 bit (larik potongan yang telah ditentukan) atau 64 * 4 bit (penetapan kotak yang telah ditentukan sebelumnya)

Setelah 10 langkah di kedua sisi, ruang maksimum yang dibutuhkan adalah 640 bit

... tetapi sekali lagi, jika kita mengidentifikasi setiap bidak secara unik (5 bit) dan menambahkan bit keenam untuk menandai bidak ratu, maka kita hanya perlu bidak-bidak + ke posisi untuk setiap gerakan. Ini mengubah kalkulasi menjadi ...

Posisi awal = maks 384 bit (32 buah, 6 + 6 bit) Setiap gerakan = 12 bit (ke posisi, bagian-id)

Kemudian setelah 10 langkah di setiap sisi ruang maksimum yang dibutuhkan adalah 624 bit

Seperti Robert G, saya cenderung menggunakan PGN karena ini standar dan dapat digunakan oleh berbagai alat.

Namun, jika saya memainkan AI catur yang berada di wahana antariksa yang jauh, dan karenanya setiap bit berharga, inilah yang akan saya lakukan untuk pergerakannya. Saya akan datang untuk menyandikan keadaan awal nanti.

Gerakan tidak perlu merekam status; decoder dapat melacak keadaan serta gerakan apa yang legal pada titik tertentu. Semua langkah yang perlu dicatat adalah yang mana dari berbagai alternatif hukum yang dipilih. Karena pemain bergantian, gerakan tidak perlu merekam warna pemain. Karena pemain hanya dapat memindahkan bidak warnanya sendiri, pilihan pertama adalah bidak mana yang dipindahkan pemain (saya akan kembali ke alternatif yang menggunakan pilihan lain nanti). Dengan paling banyak 16 buah, ini membutuhkan paling banyak 4 bit. Saat pemain kehilangan bidak, jumlah pilihan berkurang. Juga, keadaan permainan tertentu mungkin membatasi pilihan bidak. Jika seorang raja tidak bisa bergerak tanpa menempatkan dirinya di cek, jumlah pilihan dikurangi satu. Jika seorang raja di cek, bidak apa pun yang tidak bisa mengeluarkan raja dari cek bukanlah pilihan yang tepat.

Setelah barang ditentukan, barang tersebut hanya akan memiliki sejumlah tujuan resmi. Jumlah pastinya sangat bergantung pada tata letak papan dan riwayat permainan, tetapi kami dapat mengetahui nilai maksimum dan yang diharapkan tertentu. Untuk semua kecuali ksatria dan selama rokade, bidak tidak bisa bergerak melalui bidak lain. Ini akan menjadi sumber batas pergerakan yang besar, tetapi sulit untuk diukur. Sepotong tidak bisa lepas dari papan, yang juga akan membatasi jumlah tujuan.

Kami menyandikan tujuan sebagian besar potongan dengan menomori kotak di sepanjang garis dalam urutan berikut: W, NW, N, NE (sisi hitam adalah N). Sebuah garis dimulai di kotak terjauh ke arah yang ditentukan yang sah untuk dipindahkan dan dilanjutkan menuju. Untuk raja yang tidak terbebani, daftar langkahnya adalah W, E, NW, SE, N, S, NE, SW. Untuk ksatria, kita mulai dengan 2W1N dan searah jarum jam; tujuan 0 adalah tujuan valid pertama dalam urutan ini.

• Pion: Pion yang tidak bergerak memiliki 2 pilihan tujuan, sehingga membutuhkan 1 bit. Jika bidak dapat menangkap pion lain, baik secara normal atau sambil lalu (yang dapat ditentukan oleh decoder, karena ia melacak keadaan), ia juga memiliki 2 atau 3 pilihan gerakan. Selain itu, bidak hanya dapat memiliki 1 pilihan, tidak membutuhkan bidak. Ketika bidak berada di peringkat ^ke -7 , kami juga memilih pilihan promosi. Karena bidak biasanya dipromosikan menjadi ratu, diikuti oleh ksatria, kami menyandikan pilihan sebagai:
  • ratu: 0
  • kesatria: 10
  • uskup: 110
  • benteng: 111
• Uskup: maksimal 13 tujuan saat di {d, e} {4,5} untuk 4 bit.
• Benteng: paling banyak 14 tujuan, 4 bit.
• Ksatria: paling banyak 8 tujuan, 3 bit.
• Raja: Ketika rokade adalah sebuah pilihan, raja mengembalikannya ke S dan tidak bisa bergerak ke bawah; ini memberikan total 7 tujuan. Sisa waktu, seorang raja memiliki paling banyak 8 gerakan, memberikan maksimum 3 bit.
• Ratu: Sama seperti pilihan untuk uskup atau benteng, dengan total 27 pilihan, yaitu 5 bit

Karena jumlah pilihan tidak selalu merupakan pangkat dua, di atas masih membuang bit. Misalkan jumlah pilihan adalah C dan pilihan tertentu diberi nomor c , dan n = ceil (lg ( C )) (jumlah bit yang diperlukan untuk menyandikan pilihan). Kami memanfaatkan nilai-nilai yang terbuang percuma ini dengan memeriksa bit pertama dari pilihan berikutnya. Jika 0, jangan lakukan apa pun. Jika 1 dan c + C <2 ⁿ , maka tambahkan C ke c . Mengurai kode angka membalikkan ini: jika menerima c > = C , kurangi C dan atur bit pertama untuk angka berikutnya menjadi 1. Jika c<2ⁿ - C , kemudian set bit pertama untuk angka berikutnya ke 0. Jika 2 ⁿ - C <= c < C , maka jangan lakukan apa-apa. Sebut skema ini "saturasi".

Jenis pilihan potensial lain yang mungkin mempersingkat pengkodean adalah memilih bagian lawan untuk ditangkap. Ini meningkatkan jumlah pilihan untuk bagian pertama dari sebuah gerakan, mengambil satu buah, paling banyak untuk bit tambahan (jumlah pastinya tergantung pada berapa banyak buah yang dapat dipindahkan oleh pemain saat ini). Pilihan ini diikuti oleh pilihan bidak penangkap, yang mungkin jauh lebih kecil daripada jumlah gerakan untuk bidak pemain mana pun yang diberikan. Sebuah bidak hanya dapat diserang oleh satu bidak dari arah mata angin mana pun ditambah ksatria dengan total paling banyak 10 bidak serang; ini memberikan total maksimum 9 bit untuk gerakan penangkapan, meskipun saya mengharapkan rata-rata 7 bit. Ini akan sangat menguntungkan untuk ditangkap oleh ratu, karena sering kali memiliki beberapa tujuan resmi.

Dengan saturasi, encoding-capture mungkin tidak memberikan keuntungan. Kami dapat mengizinkan kedua opsi tersebut, dengan menentukan status awal yang digunakan. Jika saturasi tidak digunakan, encoding game juga dapat menggunakan nomor pilihan yang tidak digunakan ( C <= c <2 ⁿ ) untuk mengubah opsi selama game. Kapan pun C adalah pangkat dua, kami tidak dapat mengubah opsi.

Thomas memiliki pendekatan yang tepat untuk mengkodekan papan. Namun ini harus dikombinasikan dengan pendekatan ralu untuk menyimpan gerakan. Buatlah daftar semua kemungkinan gerakan, tuliskan jumlah bit yang diperlukan untuk mengekspresikan angka ini. Karena decoder melakukan kalkulasi yang sama, ia mengetahui berapa banyak yang mungkin dan dapat mengetahui berapa banyak bit yang akan dibaca, tidak diperlukan kode panjang.

Jadi kami mendapatkan 164 bit untuk potongan-potongan, 4 bit untuk info kastil (dengan asumsi kami menyimpan fragmen permainan, jika tidak dapat direkonstruksi), 3 bit untuk info kelayakan sambil lalu - cukup simpan kolom tempat perpindahan terjadi ( Jika en passant tidak memungkinkan, simpan kolom yang tidak memungkinkan - kolom seperti itu harus ada) dan 1 untuk siapa yang akan pindah.

Perpindahan biasanya membutuhkan 5 atau 6 bit tetapi dapat bervariasi dari 1 hingga 8.

Satu pintasan tambahan - jika penyandian dimulai dengan 12 1 bit (situasi yang tidak valid - bahkan sebuah fragmen tidak akan memiliki dua raja di satu sisi) Anda membatalkan decode, menghapus papan dan mengatur permainan baru. Bit berikutnya akan menjadi sedikit bergerak.

Algoritme harus menghitung secara deterministik semua kemungkinan tujuan di setiap gerakan. Jumlah tujuan:

• 2 uskup, masing-masing 13 tujuan = 26
• 2 benteng, masing-masing 14 tujuan = 28
• 2 ksatria, masing-masing 8 tujuan = 16
• queen, 27 tujuan
• raja, 8 tujuan

8 kaki semuanya bisa menjadi ratu dalam kasus terburuk (enumerasi-bijaksana), sehingga membuat jumlah kemungkinan tujuan terbesar 9 * 27 + 26 + 28 + 16 + 8 = 321. Dengan demikian, semua tujuan untuk setiap gerakan dapat dihitung dengan angka 9 bit.

Jumlah langkah maksimal kedua belah pihak adalah 100 (kalau saya tidak salah, bukan pecatur). Dengan demikian permainan apa pun dapat direkam dalam 900 bit. Ditambah posisi awal setiap potongan dapat direkam menggunakan 6 bit angka, yang totalnya menjadi 32 * 6 = 192 bit. Ditambah satu bit untuk rekor "siapa yang bergerak lebih dulu". Jadi, permainan apa pun dapat direkam menggunakan 900 + 192 + 1 = 1093 bit.

Menyimpan status papan

Cara paling sederhana yang saya pikirkan adalah terlalu pertama memiliki array 8 * 8 bit yang mewakili lokasi setiap bidak (Jadi 1 jika ada bidak catur di sana dan 0 jika tidak ada). Karena ini adalah panjang tetap, kami tidak memerlukan terminator apa pun.

Selanjutnya mewakili setiap bidak catur dalam urutan lokasinya. Menggunakan 4 bit per potong, ini membutuhkan 32 * 4 bit (total 128). Benar-benar boros banget.

Dengan menggunakan pohon biner, kita dapat merepresentasikan bidak dalam satu byte, ksatria dan benteng dan uskup dalam 3 dan raja dan ratu dalam 4. Karena kita juga perlu menyimpan warna bidak, yang membutuhkan byte ekstra, itu berakhir sebagai (maafkan saya jika ini salah, saya belum pernah melihat pengkodean Huffman secara detail sebelumnya):

• Pion: 2
• Benteng: 4
• Ksatria: 4
• Uskup: 4
• Raja: 5
• Ratu: 5

Mengingat totalnya:

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

Yang mengalahkan menggunakan set ukuran tetap bit sebesar 28 bit.

Jadi metode terbaik yang saya temukan adalah menyimpannya dalam array 8 ² + 100 bit

8*8 + 100 = 164

Menyimpan Pindah
Hal pertama yang perlu kita ketahui adalah bidak mana yang bergerak ke mana. Mengingat bahwa ada maksimum 32 buah di papan dan kita tahu apa itu setiap bagian, daripada bilangan bulat yang mewakili persegi, kita dapat memiliki bilangan bulat yang mewakili potongan offset, yang berarti kita hanya harus memasukkan 32 nilai yang mungkin untuk mewakili a bagian.

Sayangnya ada berbagai aturan khusus, seperti mengebiri atau menggulingkan raja dan membentuk republik (referensi Terry Pratchett), jadi sebelum kita menyimpan bidak untuk bergerak kita perlu sedikit yang menunjukkan apakah itu langkah khusus atau tidak.

Jadi untuk setiap gerakan normal kami memiliki 1 + 5 = 6bit yang diperlukan . (Tipe 1 bit, 5 bit untuk potongan)

Setelah nomor bidak didekodekan, kita kemudian mengetahui jenis bidak, dan setiap bidak harus mewakili pergerakannya dengan cara yang paling efisien. Misalnya (Jika aturan catur saya sesuai dengan keinginan) bidak memiliki total 4 kemungkinan langkah (ambil kiri, ambil kanan, maju satu, maju dua).
Jadi untuk merepresentasikan pion kita membutuhkan '6 + 2 = 8' bit. (6 bit untuk header langkah awal, 2 bit untuk langkah apa)

Bergerak untuk ratu akan lebih kompleks, karena akan lebih baik untuk memiliki arah (8 kemungkinan arah, jadi 3 bit) dan total 8 kotak yang mungkin untuk dipindahkan untuk setiap arah (jadi 3 bit lagi). Jadi untuk mewakili memindahkan ratu, itu membutuhkan 6 + 3 + 3 = 12bit.

Hal terakhir yang terjadi pada saya adalah kita perlu menyimpan pemain mana yang mengubahnya. Ini harus menjadi satu bit (Putih atau hitam untuk pindah selanjutnya)

Format Hasil
Jadi format file akan terlihat seperti ini

[64 bits] Lokasi bidak awal
[100 bits max] Potongan awal [1 bit] Giliran pemain
[n bits] Bergerak

Dimana Pindah adalah
[1 bit] Jenis Pindah (khusus atau normal)
[n bit] Pindah Detil

Jika Pindah adalah gerakan normal, Detail Pindah terlihat seperti
[5 bit] bagian
[n bit] gerakan tertentu (biasanya dalam kisaran 2 hingga 6 bit]

Jika itu adalah gerakan khusus,
itu harus memiliki tipe integer dan kemudian informasi tambahan apa pun (seperti jika itu adalah rokade). Saya tidak dapat mengingat jumlah gerakan khusus, jadi mungkin boleh saja untuk menunjukkan bahwa ini adalah gerakan khusus (jika hanya ada satu)

Dalam kasus dasar papan awal ditambah gerakan selanjutnya, pertimbangkan hal berikut.

Gunakan program catur untuk menetapkan probabilitas ke semua kemungkinan gerakan. Misalnya, 40% untuk e2-e4 20% untuk d2-d4, dan seterusnya. Jika beberapa gerakan legal tetapi tidak dipertimbangkan oleh program itu, beri mereka probabilitas rendah. Gunakan pengkodean aritmatika untuk menyimpan pilihan mana yang diambil, yaitu beberapa angka antara 0 dan 0,4 untuk langkah pertama, 0,4 dan 0,6 untuk langkah kedua, dan seterusnya.

Lakukan hal yang sama untuk sisi lainnya. Misalnya, jika ada peluang 50% dari e7-e5 sebagai respons terhadap e2-e4 maka nomor yang disandikan akan berada di antara 0 dan 0,2. Ulangi sampai permainan selesai. Hasilnya adalah rentang yang berpotensi sangat kecil. Temukan pecahan biner dengan basis terkecil yang sesuai dalam kisaran itu. Itu pengkodean aritmatika.

Ini lebih baik daripada Huffman karena dapat dianggap sebagai pengkodean bit pecahan (ditambah beberapa di akhir permainan untuk dibulatkan menjadi keseluruhan bit).

Hasilnya harus lebih kompak dari Huffman, dan tidak ada kasus khusus untuk promosi, passant, 50 rule move, dan detail lainnya karena ditangani program evaluasi catur.

Untuk memutar ulang, gunakan kembali program catur untuk mengevaluasi papan dan menetapkan semua probabilitas untuk setiap gerakan. Gunakan nilai enkode aritmatika untuk menentukan gerakan mana yang sebenarnya dimainkan. Ulangi sampai selesai.

Jika program catur Anda cukup baik, Anda bisa mendapatkan kompresi yang lebih baik dengan pembuat enkode dua-status, dengan probabilitas ditentukan berdasarkan gerakan untuk hitam dan putih. Dalam kasus yang paling ekstrim dari sekitar 200+ negara bagian, ini mengkodekan seluruh rangkaian dari semua permainan catur yang mungkin, dan oleh karena itu tidak layak.

Ini adalah cara yang sangat berbeda untuk mengatakan apa yang sudah ditulis Darius, hanya dengan sedikit contoh bagaimana pengkodean aritmatika dapat bekerja, dan contoh nyata menggunakan program catur yang ada untuk membantu mengevaluasi kemungkinan langkah selanjutnya.