Main iChomp Dalam Talian

Permainan Gabungan: permainan dua orang dengan maklumat yang sempurna dan menang atau kalah dan tiada peluang bergerak.

Permainan yang tidak berat sebelah: permainan gabungan di mana pergerakan yang dibenarkan hanya bergantung pada kedudukan dan bukan di mana salah satu daripada dua pemain sedang bergerak. Juga, hasilnya simetri. Dalam erti kata lain, satu-satunya perbezaan antara pemain 1 dan pemain 2 ialah pemain 1 mula dahulu. Contoh: Chomp.

Permainan Partisan: permainan yang tidak memihak. Contoh: Catur.

Permainan Yang Biasa: Pemain yang membuat langkah terakhir MENANG, iaitu pemain yang tidak dapat bergerak, iaitu yang tidak mempunyai apa-apa untuk diambil, kalah.

Permainan secara Misère: Pemain untuk membuat langkah terakhir KALAH.

Chomp: permainan yang diperkenalkan di laman permainan kami yang menggunakan satu kuadran dan Permainan secara Misère.

Adakah permainan Nim kerana ia dimainkan di laman permainan kami menggunakan permainan biasa atau secara misère?
- Permainan Nim kami menggunakan permainan secara misère, kerana pemain yang mengambil perlawanan terakhir kehilangan permainan.
Adakah permainan Chomp kerana ia dimainkan di halaman permainan Chomp kami menggunakan permainan biasa atau secara misère?
- Permainan Chomp kerana ia dimainkan di halaman permainan kami menggunakan permainan secara misère, kerana pemain yang mengambil gula-gula terakhir kalah.
Mengapa tidak masuk akal untuk menggunakan permainan biasa untuk Chomp?
- Menggunakan permainan biasa bermakna sesiapa yang mengambil jubin terakhir menang. Oleh itu, pemain yang bergerak terlebih dahulu boleh menang dengan serta-merta dengan mengambil jubin di sudut kiri atas.
Adakah permainan iChomp kerana ia dimainkan di laman web ini menggunakan Biasa atau Permainan secara Misère?
- Di iChomp, pemain yang mengambil jubin terakhir menang, jadi permainan ini menggunakan Permainan Biasa.
Adakah anda mempunyai cadangan bagaimana seseorang boleh menukar papan Chomp untuk menggunakan Permainan Biasa dan masih bermain permainan yang sama?
- Seseorang boleh bermula dengan kedudukan di mana gula-gula (beracun) di sudut kiri atas sudah hilang dari permulaan. Mengambil gula-gula terakhir dari papan sedemikian bermakna seseorang akan menang dalam Permainan Biasa. Dalam Permainan secara Misère dan dengan jubin ini maka pemain lain perlu mengambilnya dan kalah yang merupakan hasil yang sama.
  
  Oleh itu, mempunyai jubin sudut atas kiri dan menggunakan Permainan secara Misère atau tidak mempunyai jubin ini sejak awal permainan dan menggunakan Permainan Biasa kedua-duanya adalah permainan yang sama.

Permainan iChomp direka untuk menjadi pakatan empat orang Chomp permainan dimainkan pada masa yang sama, semuanya di bawah peraturan Permainan Biasa. Ini menjadikan permainan lebih cantik dalam dua aspek, yang akan dijelaskan di bawah. Juga, iChomp tidak begitu sukar untuk dimainkan daripada Chomp jika seseorang menggunakan teori Sprague-Grundy, yang juga diterangkan di bawah.

Kelas permainan yang digunakan adalah Permainan gabungan yang tidak memihak. Teori ini melakukan dua perkara untuk kita:
1. Ia memberi kita algoritma yang menentukan untuk setiap permainan (iaitu setiap kedudukan) nombor (kita akan memanggilnya nilai SG) supaya nombor itu adalah 0 jika dan hanya jika ia adalah kedudukan yang kalah (dipanggil 'kedudukan P' dalam kesusasteraan mengenai teori permainan gabungan dengan 'P' menunjukkan bahawa 'pemain p' yang sebelumnya (p'revious) memainkan langkah kemenangan). Ini bermakna jika nilai SG ini ialah 1, 2, 3, ... maka ini adalah kedudukan yang menang (dipanggil kedudukan 'N' dalam kesusasteraan). Dalam kes itu, sesiapa yang bergerak seterusnya ('n'ext) boleh menguatkuasakan kemenangan jika bermain secara optimum.
2. Tujuan kedua teori SG adalah untuk menerangkan bagaimana untuk memenangi permainan yang terdiri daripada beberapa kedudukan yang dimainkan pada masa yang sama. Langkah dalam permainan gabungan sedemikian dibuat dengan membuat satu langkah dalam mana-mana kedudukan yang digabungkan.
  
  Apa yang perlu diketahui ialah nilai SG bagi setiap kedudukan gabungan. Untuk mendapatkan mereka, seseorang perlu mengetahui nilai SG selepas setiap langkah dalam mana-mana kedudukan gabungan ini. Ini diperlukan juga untuk bermain secara optimum.
  
  Sebagai contoh: Dalam permainan Nim, seseorang mempunyai satu atau dua atau lebih timbunan perlawanan. Jika kita tahu nilai SG untuk bermain setiap longgokan individu sahaja, maka teori SG memberitahu kita bagaimana untuk bermain secara optimum dengan semua buasir ini dengan mengambil bilangan perlawanan yang sesuai dari mana-mana satu daripada timbunan ini.
Apa yang menakjubkan tentang teori SG ialah kedudukan yang boleh digabungkan kepada satu permainan bukan sahaja timbunan permainan Nim tetapi mana-mana kedudukan mana-mana Permainan gabungan yang tidak memihak. Sebagai contoh, seseorang boleh menggabungkan beberapa kedudukan chomp ke dalam satu permainan "super-chomp", atau seseorang boleh bermain permainan secara optimum yang bermula dengan 5 kedudukan chomp yang berbeza dan 3 timbunan perlawanan dan mana-mana satu daripada 8 tempat boleh dimainkan pada bila-bila masa.

iChomp adalah versi baru Chomp yang diperkenalkan oleh Peraduan Caribou yang dimainkan di laman web ini. 'i' dalam iChomp bermaksud 'isotropik' iaitu semua arah dilayan sama rata.

Dalam Chomp biasa penyingkiran satu jubin juga menghilangkan semua jubin ke Timur dan Selatannya. Jadi, arah Timur dan Selatan memainkan peranan khas.

Dalam iChomp semua jubin ke arah lain boleh dikeluarkan juga bergantung kepada di mana jubin yang dikeluarkan adalah yang paling dekat dengan pusat. Jika jubin ini, sebagai contoh, dalam arah Utara-Barat pusat maka semua jubin di Utara atau Barat juga dikeluarkan.

Mengeluarkan peraturan tiruan, sebagai contoh, peraturan bahawa Timur dan Selatan adalah istimewa biasanya dianggap menjadikan permainan secara matematik lebih cantik.

Terdapat satu lagi pengindahan yang iChomp ada berbanding dengan Chomp.

Di Chomp jubin di sudut atas kiri memainkan peranan khas berbanding jubin lain. Jika itu adalah satu-satunya jubin di papan permainan sudah berakhir. Jika jubin lain dikeluarkan permainan berterusan. Seseorang boleh memulakan Chomp tanpa jubin sudut itu supaya semua jubin diperlakukan sama, tetapi ini sendiri akan menjadi peraturan tiruan mengapa untuk memulakan permainan tanpa jubin itu dan bukan tanpa jubin lain juga.

Dalam iChomp semua jubin hadir pada permulaan dan semua diperlakukan sama. Mana-mana jubin boleh dikeluarkan tanpa menamatkan permainan secara automatik.

Beberapa soalan timbul:

Adakah iChomp permainan remeh kerana ia adalah gabungan atau 4 permainan Chomp remeh dalam 'Permainan Biasa'?
- Jawapannya tidak. Sebagai contoh, permainan Nim dengan satu timbunan perlawanan adalah remeh. Di bawah 'Permainan Biasa', seseorang boleh mengalih keluar keseluruhan longgokan dalam satu gerakan dan menang. Di Nim di bawah Permainan Secara 'Misère', seseorang boleh mengeluarkan semua kecuali satu perlawanan dan menang. Walau bagaimanapun, gabungan permainan Nim 1-pile sedemikian kepada permainan Nim berbilang cerucuk seperti di halaman permainan Nim kami tidak remeh.
  
  Begitu juga di sini: Permainan chomp tunggal menggunakan jubin sudut dan 'Permainan Biasa' adalah remeh kerana seseorang boleh mengeluarkan semua jubin dalam satu gerakan dan menang. Tetapi gabungan 4 permainan sedemikian tidak remeh.
Ringkasan Perbandingan
- IChomp secara matematik lebih cantik daripada Chomp kerana ia tidak membezakan arah Tenggara secara buatan dan tidak memberikan satu jubin peranan khas. Harga nampaknya iChomp jauh lebih sukar untuk dimainkan daripada Chomp tetapi teori SG membantu. Ia cukup untuk mengetahui nilai SG kedudukan Chomp sehingga beberapa saiz untuk dengan mudah mengira nilai SG kedudukan iChomp sehingga 4 kali saiz itu dan dengan itu untuk mengetahui cara bermain iChomp secara optimum sehingga saiz 4 kali lebih besar.

Eksklusif Atau, atau pendek kata XOR, adalah operasi logik yang dilakukan pada data binari. Menggunakan data binari, kita boleh mempunyai salah satu daripada dua nilai, benar (=1) atau palsu (=0). Operasi XOR pada dua nilai perduaan ditakrifkan melalui jadual berikut.

a b a XOR b
1 1 0
1 0 1
0 1 1
0 0 0

Walaupun mudah untuk menggunakan operasi ini pada nilai 1 (benar) atau 0 (palsu), untuk pengiraan kita, kita perlu dapat melakukan XOR pada dua nombor. Ini juga boleh dilakukan, namun langkah baru diperlukan sebelum kita dapat melakukan XOR.

Apa yang pertama kali berlaku ialah nombor perlu ditukar menjadi binari, iaitu untuk menukarnya dari asas 10 ke asas 2.

Bagaimanakah seseorang boleh menukar nombor dari asas 10 menjadi asas 2?
- Algoritma berikut boleh digunakan untuk menukar nombor n dalam asas 10 menjadi asas 2 format. (Diingatkan bahawa 2⁰ = 1):
  1. Cari p eksponen tertinggi 2, supaya 2^p ≤ n.
  2. Rakam 1 dan tolak 2^p daripada n.
  3. Jika p = 0 maka berhenti lagi tolak 1 daripada p dan teruskan.
  4. Jika 2 p > n maka rekod 0 lagi tolak 2^p daripada n dan rekod 1.
  5. Kembali ke langkah 3.
  Urutan 1's dan 0's yang anda rakam mengikut algoritma ini akan menjadi perwakilan binari nombor n. Sebagai contoh:
  
  Marilah kita menukar nombor 13 menjadi format asas 2. Kita mulakan dengan mencari kuasa tertinggi 2 kurang daripada atau sama dengan 13, iaitu 2³, atau 8. Kami kemudian merekodkan 1 dan tolak 8 daripada 13, yang memberi kita 5. Seterusnya kita semak 2⁽³⁻¹⁾ = 2² = 4. Sejak 4 ≤ 5, kami merekodkan 1, dan tolak 4 dari 5, yang memberi kita 1. Kuasa bawah seterusnya 2 ialah 2¹ = 2. 2 > 1, jadi kami merekodkan 0. Kuasa seterusnya 2 ialah 2 0 = 1, yang sama dengan n kami 1, jadi kami merekodkan 1 dan tolak 1 daripada 1, memberikan kami⁰. Sejak p = 0 kita menghentikan algoritma. Oleh itu 13 (asas 10) = 1101 (asas 2).
  
  Selepas kita menukar dua nombor ke dalam perwakilan binari, kita kini boleh melakukan operasi XOR pada digit yang sepadan dengan dua nombor binari. Hasilnya ialah nombor perduaan yang kemudiannya boleh ditukar kembali kepada asas 10 jika itu lebih mudah untuk penggunaan nilai XOR itu pada masa hadapan. Sebagai contoh:
  
  Marilah kita mengira XOR nombor 6 dan 13. Perwakilan binari untuk kedua-dua nombor ini ialah 6 = 110, dan 13 = 1101. Pada mulanya kami menambah 0 di sebelah kiri nombor yang lebih kecil supaya kedua-duanya mempunyai bilangan digit yang sama, jadi 6 = 0110. Kita kemudian boleh melakukan XOR dengan melapisi mereka dan melaksanakan operasi pada setiap digit individu:
  
  0110
  XOR 1101
  ------
  1011
  
  Oleh itu 6 XOR 13 = 1011 (asas 2) = 1×2³+0×2²+1×2 1+1×2⁰ = 8+2+1 = 11 (asas¹⁰).
Marilah kita menyemak pemahaman kita tentang XOR dengan beberapa soalan.

Apakah m XOR m untuk sebarang nombor m?
- Untuk sebarang nombor m kita mempunyai m XOR m = 0 kerana 0 XOR 0 = 0 dan juga 1 XOR 1 = 0.
Adakah n XOR m = m XOR n untuk sebarang nombor n, m?
- Ya, kerana 1 XOR 0 = 0 XOR 1 (=1).
Berapakah 0 XOR m untuk sebarang nombor m?
- 0 XOR m = m kerana 0 XOR 0 = 0 dan 0 XOR 1 = 1.
Jika nombor m ialah XOR'ed dengan nombor n hingga m XOR n maka digit m mana yang akan dibalikkan?
- Jika digit dalam m ialah XOR'ed dengan 0 maka digit tidak berubah (kerana 0 XOR 0 = 0 dan 1 XOR 0 = 1). Jika digit dalam m ialah XOR'ed dengan 1 maka digit dibalikkan (kerana 0 XOR 1 = 1 dan 1 XOR 1 = 0). Oleh itu, XOR n membalikkan semua digit yang mana digit sepadan dalam n ialah 1.

a	b	a XOR b
1	1	0
1	0	1
0	1	1
0	0	0

Algoritma berikut mengira nilai SG mana-mana kedudukan P dalam mana-mana permainan gabungan yang tidak memihak. Kami menerangkannya menggunakan permainan Chomp.
- Setiap kedudukan permainan yang merupakan kedudukan kalah mendapat nilai SG 0. Di Chomp, jubin tunggal (di sudut Utara-Barat) adalah satu-satunya kedudukan tanpa langkah susulan dan oleh itu adalah kedudukan kalah dengan SG-value 0.
- Kita memerlukan nilai-nilai SG bagi semua jawatan yang boleh dicapai dari kedudukan P dalam satu langkah. Oleh itu, jika kedudukan P mempunyai n jubin maka terdapat n-1 pergerakan yang mungkin: kecuali jubin di sudut Utara-Barat, semua jubin lain boleh dikeluarkan bersama-sama dengan semua jubin ke Selatan / Timur jubin itu.
- Nilai SG bagi kedudukan P ialah nombor bukan negatif terkecil yang tiada dalam senarai nilai SG n-1 yang boleh dicapai ini.
Algoritma ini berulang kerana untuk mengira nilai SG kedudukan P kita memerlukan nilai SG semua kedudukan yang dapat dicapai dari P dalam satu langkah. Ia masih berfungsi kerana nilai-nilai SG yang diperlukan melibatkan kedudukan yang lebih kecil daripada jubin yang lebih sedikit dan nilai SG kedudukan terkecil yang mungkin (satu jubin di sudut Utara-Barat) diketahui.

Cuba sahkan sifat ke-3 dalam permainan di atas dengan memilih lebar dan ketinggian papan yang lebih besar dan klik 'Papan rawak'.
- Apabila anda menggerakkan tetikus ke atas jubin, maka jubin ini dan jubin lain yang akan dikeluarkan diserlahkan. Nombor dalam jubin itu ialah nilai SG kuadran di bawah 'Main Normal' (bukan 'Misère Play') yang akan terhasil jika jubin ini diklik. Anda boleh menyemak bahawa nombor yang ditunjukkan dalam teks 'SG value Base Ten:' di sebelah kuadran ialah nombor terkecil yang tidak ditunjukkan dalam kuadran. Anda juga boleh menyemak bahawa jika anda mengklik jubin maka nombor yang berada di dalamnya kini ditunjukkan sebagai 'SG value Base Ten:' kedudukan baru.
Bagaimana untuk mempercepatkan penentuan nilai-nilai SG:

Kerana kedudukan yang sama dapat dicapai dari kedudukan yang berbeza dalam satu langkah, dan boleh muncul berulang kali apabila mengira nilai SG kedudukan yang lebih besar, ia akan menjadi satu pembaziran usaha untuk mengiranya lagi dan lagi. Oleh itu, sebaik sahaja nilai SG kedudukan P dikira, ia harus disimpan untuk kegunaan kemudian.

Jika seseorang ingin mengira nilai SG semua kedudukan sehingga beberapa saiz, maka pendekatan berikut berguna. Kami mulakan dengan menetapkan satu-satunya kedudukan dengan satu jubin (di sudut Utara-Barat) sifar nilai SG. Kemudian, kami menggunakan algoritma di atas untuk mengira nilai SG semua kedudukan dengan 2 jubin, kemudian dengan 3 jubin dan sebagainya.

Kedudukan iChomp terdiri daripada 4 jawatan Chomp, satu dalam setiap kuadran lembaga.
- Pada mulanya kita menentukan nilai SG setiap satu daripada 4 kedudukan Chomp menggunakan peraturan Chomp 'Misère Play'. Kuadran kosong bukan kedudukan Chomp, jadi kami memberikannya nilai −1.
- Kami kemudian menambah 1 kepada setiap nilai.
- Untuk setiap satu daripada 4 nombor yang terhasil kita mengira perwakilan binari.
- Kami mengira nilai XOR daripada 4 nilai binari dan mendapatkan nilai SG kedudukan itu (dalam bentuk binari). Sekiranya nilai ini sifar, ia adalah kedudukan yang kalah, jika tidak, ia adalah kedudukan yang menang.

Mengapa kita menambah '1'?

Kami menambah 1 untuk mendapatkan nilai SG kedudukan Chomp di bawah 'Main Normal' daripada nilai SG di bawah 'Misère Play'. Teorem berikut menerangkannya.

Teorem:
--------
Untuk mendapatkan nilai SG kedudukan Chomp di bawah 'Normal Play' (iaitu mengambil jubin terakhir memenangi permainan yang bukan cara biasa untuk bermain Chomp) seseorang perlu menambah 1 kepada nilai SG kedudukan yang sama di bawah 'Misère Play' (iaitu mengambil jubin terakhir kalah yang merupakan cara biasa untuk bermain Chomp).

Bolehkah anda cuba membuktikan teorem dengan induksi?
- Bukti (dengan induksi (dan secara terperinci)):
  
  Kes Asas (1 jubin):
  -------------------
  Di bawah 'Main Biasa' papan kosong tanpa jubin adalah kedudukan yang kalah dan oleh itu mempunyai sifar nilai SG. Tambahan pula, di bawah 'Main Normal' untuk papan dengan satu jubin (di sudut kiri atas) satu-satunya langkah yang mungkin adalah untuk mengeluarkan jubin ini menghasilkan kedudukan dengan SG-value 0. Jadi, di bawah 'Main Normal' nilai SG bukan negatif terkecil yang tidak dapat dicapai dengan langkah adalah 1, jadi itulah nilai SG kedudukan dengan satu jubin di bawah 'Main Normal'.
  
  Di bawah 'Misère Play' yang mempunyai satu jubin adalah kehilangan kedudukan dengan SG-value 0.
  
  Oleh itu, untuk 1 jubin, nilai SG 'Normal Play' adalah 1 lebih besar daripada nilai 'Misère Play'.
  
  Langkah induktif
  ---------------
  
  Hipotesis Induksi (n jubin):
  ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
  Kami menganggap bahawa terdapat nombor n supaya untuk semua kedudukan dengan ≥1 dan ≤n jubin nilai SG di bawah 'Normal Play' adalah satu yang lebih besar daripada di bawah 'Misère Play'. Tuntutan Induksi (n + 1 jubin):
  ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
  Kami akan menunjukkan bahawa ini juga berlaku untuk semua kedudukan dengan jubin n + 1.
  
  Langkah induksi ( n jubin → n + 1 jubin):
  ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
  Untuk sebarang kedudukan 'Misère Play' dan 'Normal Play' membenarkan pergerakan yang sama kecuali 'Main Biasa' juga membolehkan untuk mengambil semua jubin melalui jubin sudut kiri atas.
  
  Jika kedudukan mempunyai n + 1 jubin, maka membuat langkah menghasilkan kedudukan dengan kebanyakan n jubin yang mana kita boleh menggunakan hipotesis induksi:
  
  Oleh itu, senarai nilai SG yang boleh diperolehi di bawah 'Main Normal' diperoleh daripada senarai nilai SG yang boleh diperolehi di bawah 'Misère Play' masing-masing meningkat sebanyak 1 dan dengan menambah nilai 0 melalui mengambil semua jubin.
  
  Oleh itu, nombor bukan negatif terkecil YANG TIDAK boleh diperolehi di bawah 'Main Normal' adalah 1 lebih tinggi daripada nombor bukan negatif terkecil YANG TIDAK boleh diperolehi di bawah 'Misère Play'. Dalam erti kata lain, untuk kedudukan asal dengan n+1 jubin nilai SG di bawah 'Main Normal' adalah satu lebih tinggi daripada nilai SG di bawah 'Misère Play'. ∎ (Ini melengkapkan bukti.)

Matlamatnya adalah untuk bergerak supaya nilai SG kedudukan yang terhasil adalah sifar. Apa sahaja langkah yang dibuat, ia mesti berada di salah satu daripada 4 kuadran. Ini bermakna bahawa nilai SG kedudukan di mana langkah itu telah dibuat dan nilai SG dari 3 kuadran lain yang tidak berubah semua XOR'ed mesti memberikan sifar. Ini berlaku jika dan hanya jika 3 nilai SG yang lain XOR'ed memberikan nilai SG kuadran baru selepas membuat langkah (lihat lebih lanjut di bawah untuk bukti pernyataan ini). Oleh itu, prosedur ini adalah seperti berikut:
- (mudah) Kes: Dua daripada 4 kuadran mempunyai nilai SG yang sama. Kemudian XOR kedua-dua nilai yang sama ini akan memberikan sifar sehingga kedua-dua kuadran akan diabaikan.
- (am) Kes:
Mengapa itu langkah menang?
- Sila ingatkan diri anda tentang sifat XOR seperti yang ditunjukkan sebelum ini untuk menjawab soalan-soalan berikut.
  
  jika anda = w XOR x XOR y XOR z, maka apakah y XOR u ?
  - Dengan menggunakan peraturan XOR yang dipelajari sebelum ini kita dapat
       y XOR u
    = y XOR w XOR x XOR y XOR z
    = y XOR y XOR w XOR x XOR z
    =        0     XOR w XOR x XOR z
    =            w XOR x XOR z.
  Jika y digantikan oleh y XOR u maka apakah XOR baru semua 4 nilai SG?
  - XOR baru akan menjadi
    (y XOR u) XOR w XOR x XOR z
    = (w XOR x XOR z) XOR (w XOR x XOR z)
    = 0
    kerana m XOR m = 0 untuk sebarang nombor m.
    
    Ini bermakna nilai SG baru keseluruhan lembaga akan menjadi sifar, jadi itu akan menjadi kedudukan yang kalah seperti yang dimaksudkan.
  Mengapa perlu wujud langkah yang mengubah nilai SG y menjadi nilai yang lebih rendah?
  - Menurut definisi: Kedudukan mempunyai nilai SG y jika dan hanya jika wujud pergerakan yang menjana kedudukan dengan nilai SG 0,1,..,(y-1). Jadi, jika y > (y XOR u), maka mesti ada langkah yang menjana nilai SG (y XOR u) < y.
  Apa yang masih perlu dijawab ialah:
  
  Mengapa perlu ada kuadran dengan nilai SG y yang memuaskan y > (y XOR u)?
  - Peringatan:
    Terdahulu, apabila kita mengetahui tentang sifat XOR, kita melihat: XOR u membalikkan semua digit yang mana digit yang sepadan dalam u ialah 1.
    
    Jika anda ≠ 0, maka U mengandungi kuasa tertinggi 2, katakan 2^p. Kuasa 2 ini mesti berlaku dalam bilangan ganjil 4 nilai SG, jadi dalam sekurang-kurangnya satu, katakan y.
    
    Ini bermakna, apabila mengira y XOR u, 1 dalam y ini akan dibalikkan kepada 0 oleh 1 yang sepadan dalam u. Mungkin terdapat digit binari lain yang dibalikkan dalam y yang terletak di sebelah kanan 1 ini. Nilai terbesar mungkin y − (y XOR u) berlaku jika digit dalam y di sebelah kanan 1 ini adalah sifar dan digit dalam diri anda di sebelah kanan 1 itu adalah satu. Dalam kes itu u = 111..111 perubahan y = *100..00 (di mana * bermaksud sebarang bilangan digit) kepada y XOR u = *011..11. Perbezaan mereka ialah:
    
    y − (y XOR u)
    = 2^p − (2^p−1 + 2^p−2+ ... +2⁰)
    = 2^p − (2^p−1 + 2^p−2+ ... +2⁰)× (2-1)/(2-1)
    = 2^p − (2^p−1)/(2-1)
    = 1.
    Ini bermakna y sekurang-kurangnya satu lebih besar daripada (y XOR u). ∎
Cuba algoritma ini dengan bermain dan menang menentang 'Kesukaran: Keras'.
- Untuk memulakan, pilih 'Kesukaran: Keras' yang menjamin permainan komputer yang optimum. Jika anda masih menang maka anda bermain setiap langkah secara optimum.
  
  Nilai SG bagi setiap kuadran ditunjukkan dalam asas 10 dan asas 2. Semak bahawa nombor ini adalah nilai terkecil yang tidak ditunjukkan dalam kuadran.
  
  Di bawahnya, XOR semua 4 nilai SG yang dipanggil u ditunjukkan. Sahkan nilai anda dengan hanya menukar mana-mana pasangan dua 1 dalam 4 nilai SG kepada 0 jika kedua-dua 1 berada dalam kedudukan yang sama. Kemudian letakkan baki 1 ke dalam satu nombor binari dan tukarkannya kepada asas 10.
  
  Untuk membuat langkah diteruskan seperti yang diterangkan di atas:
  - Cari salah satu daripada 4 nilai SG, katakan y, yang mempunyai 1 dalam kedudukan yang sama dengan yang paling kiri 1 dalam u.
  - Kira y XOR u dalam bentuk binari dan kemudian tukar kepada asas 10.
  - Dalam y-kuadran klik jubin dengan dikira y XOR u.
  - Mainkan pergerakan anda dengan cara ini sehingga anda menang.
  - Main semula tetapi kali ini bermula dengan langkah rawak. Kecuali anda bernasib baik dan bermain secara tidak sengaja langkah kemenangan, anda tidak akan dapat memenangi permainan ini walaupun anda kemudian cuba bermain secara optimum.

Untuk mengira nilai SG kedudukan, seseorang perlu mengetahui nilai-nilai SG semua kedudukan yang boleh dicapai daripadanya dalam satu langkah. Ini adalah proses rekursif. Oleh itu, kita perlu bermula dengan kedudukan dengan bilangan jubin yang paling sedikit dan bekerja dengan cara kita.

Bolehkah anda mencari nilai SG 1,2,3,... jubin dalam satu baris?
- Mempunyai hanya 1 jubin (di sudut kiri atas) adalah kedudukan yang kalah dengan oleh itu SG-value 0.
  
  Mempunyai 2 jubin (di baris atas atau lajur kiri), satu-satunya langkah yang mungkin ialah mengambil satu jubin mendapatkan kedudukan yang disebutkan dengan SG-value 0. Jadi nilai SG bukan negatif terkecil yang tidak dapat dicapai dengan langkah adalah 1, jadi nilai SG kedudukan dengan 2 jubin adalah 1.
  
  Mempunyai 3 jubin semua di baris atas, seseorang boleh mengambil sama ada 1 atau 2 jubin dan mendapatkan nilai SG 1 dan 0, jadi nilai SG adalah 2.
  
  Begitu juga, nilai SG n jubin di baris atas ialah n-1.
  
  Marilah kita mempertimbangkan 3 jubin, 2 di baris atas dan 2 di lajur kiri. Kita boleh mengeluarkan hanya 1 jubin dan mencapai nilai SG 1 tetapi tidak 0, jadi nilai SG terkecil yang tidak dapat diperoleh ialah 0 yang oleh itu adalah nilai SG kedudukan ini. Ini adalah kedudukan yang kalah.
Bolehkah anda mencari nilai SG kedudukan dengan jubin m+n−1 yang mana n berada di baris atas dan jubin m berada di lajur kiri?
- Seseorang hanya boleh mengalih keluar jubin dari baris atas atau dari lajur kiri. Oleh itu, nilai SG adalah sama seperti mempunyai dua kuadran, satu dengan n jubin di baris atas dan satu dengan jubin m di lajur kiri. Oleh itu, nilai SG ialah (m-1) XOR (n-1). Ini adalah sama seperti bermain NIM dengan dua timbunan dan peraturan 'Normal Play' di mana perlawanan boleh dikeluarkan daripada hanya satu longgokan dalam satu gerakan.
Bolehkah anda mencari nilai SG kedudukan dengan jubin hanya dalam dua baris teratas?
- Formula untuk kedudukan ini lebih rumit. Setakat yang kita tahu, mereka tidak pernah diterbitkan sebelum ini. Anda boleh cuba mengesahkannya untuk sebilangan kecil jubin.
  
  Biarkan n dan m menjadi bilangan jubin di bahagian atas dan baris kedua.
  
  Sekiranya n adalah ketika itu
    k = (n-2)/2
    jika m walaupun begitu
      a = m/2
      Nilai SG = 2*k+a+1
    lain (m adalah ganjil)
      a = (m-1)/2
      jika ≤ (k/2) maka nilai SG = 2*k-a
      lain nilai SG = 3*(k-a)
  lain (n adalah ganjil)
    k = (n-1)/2
    jika m walaupun begitu
      a = m/2
      jika ≤ (k/2) maka nilai SG = 2*k-a
      lain nilai SG = 3*(k-a)
    lain (m adalah ganjil)
      a = (m-1)/2
      Nilai SG = 2*k+a+1
  
  Semak sama ada formula betul menggunakan papan permainan di atas.
  - Pilih ketinggian papan minimum supaya terdapat kuadran dengan hanya dua baris jubin. Selepas menggunakan formula di atas, anda harus mendapatkan nilai SG yang lebih rendah daripada nilai yang ditunjukkan di bawah 'SG Value Base Ten:' kerana formula adalah untuk 'Misère Play' manakala iChomp menggunakan 'Main Normal'.

Kami mulakan dengan pemerhatian: Peraturan Chomp tidak membezakan antara arah Timur dan Selatan.

Apakah kesan kepada nilai SG dua kedudukan yang simetri cermin antara satu sama lain di bawah mencerminkan pepenjuru yang bermula dari sudut kiri atas?
- Kerana arah Timur dan Selatan dicerminkan antara satu sama lain, ini bermakna kedua-duanya mesti mempunyai nilai SG yang sama.
Apakah maksudnya untuk iChomp apabila 2 kuadran mempunyai kedudukan yang simetri di bawah putaran kuadran dan / atau pencerminan pepenjuru?
- Kedua-dua kuadran boleh diabaikan. Mengapa? Kedua-dua kuadran mempunyai nilai SG yang sama di bawah permainan misère dan selepas menambah 1 juga nilai SG yang sama di bawah permainan biasa. XOR kedua-dua nilai yang sama ini memberikan sifar. Oleh itu, kedua-dua kuadran tidak mempunyai sumbangan kepada nilai SG bagi keseluruhan kedudukan lembaga.
Oleh itu, strategi bermain mana yang harus berfungsi?
- Seseorang harus membuat langkah yang mencipta dua pasang kuadran supaya kuadran dalam setiap pasangan mempunyai kedudukan simetri dengan nilai SG yang sama, katakan A dan A, dan B dan B. Kemudian, nilai SG gabungan semua 4 kuadran ialah A XOR A XOR B XOR B = 0 XOR 0 = 0 atau (A XOR B) XOR (A XOR B) = 0 sentiasa 0. Satu mencipta kedudukan yang kalah.
  
  Sama-sama satu tidak boleh membuat langkah yang meninggalkan dua kuadran simetri dan dua yang lain di mana satu boleh diubah menjadi satu lagi dalam satu gerakan oleh pihak lawan. Ini akan membolehkan pihak lawan mencipta kedudukan yang kalah.

Berikut datang beberapa soalan di mana anda boleh menguji pemahaman anda tentang Chomp, iChomp dan teori SG.

Adakah pengetahuan tentang nilai SG cukup untuk bermain Chomp dengan sempurna?
- Ya. Jika nilai SG kedudukan adalah sifar, maka ia adalah kedudukan yang kalah (kerana tiada langkah wujud untuk menjadikannya sifar, jadi tiada langkah kemenangan wujud, jadi ia adalah kedudukan yang kalah). Jika nilai SG lebih besar daripada sifar, maka ini bermakna terdapat langkah untuk menjadikan nilai SG bagi kedudukan sifar yang terhasil, jadi terdapat langkah menang.
Adakah seseorang perlu tahu nilai-nilai SG kedudukan Chomp untuk bermain Chomp dengan sempurna?
- Tidak. Untuk bermain Chomp kita perlu mencari langkah yang menjana kedudukan kalah. Jika tiada langkah sedemikian wujud maka ia adalah kedudukan yang kalah dan sebarang langkah boleh dimainkan. Tetapi, jika langkah sedemikian ditemui, seseorang boleh berhenti mencari. Nilai SG tidak diperlukan.
Apakah nilai SG yang baik untuk itu?
- Mereka hanya perlu bermain beberapa permainan Chomp selari dengan permainan baru, seperti dalam iChomp.
Berapa banyak lagi yang sukar di Chomp untuk mengira nilai SG kedudukan daripada langkah menang?
- Untuk bermain Chomp kita perlu mencari langkah yang menjana kedudukan kalah. Jika tiada langkah sedemikian wujud maka ia adalah kedudukan yang kalah dan sebarang langkah boleh dimainkan. Tetapi, jika langkah sedemikian ditemui, seseorang boleh berhenti mencari.
  
  Usaha untuk mencari nilai SG kedudukan biasanya lebih tinggi. Untuk mencari nilai SG, seseorang sentiasa perlu mencari SEMUA pergerakan untuk mencari semua nilai SG kedudukan yang terhasil dan mencari nilai bukan negatif terkecil yang tidak dapat dicapai dalam perjalanan. Nilai ini ialah nilai SG bagi kedudukan tersebut.
  
  Sebagai contoh, dalam pengiraan kami (Caribou), kami dapat menentukan semua kedudukan yang kalah (dan dengan itu memenangi kedudukan) dengan sehingga 93 jubin. Dengan usaha pengiraan yang setanding, kami dapat mengira nilai SG semua kedudukan Chomp dengan sehingga 82 jubin.
  
  Dalam pengertian ini menentukan nilai SG secara pengiraan lebih mahal daripada menentukan langkah menang.
Jika Nim dengan 4 buasir lebih sukar untuk dimainkan daripada NIM dengan 1 longgokan, adakah iChomp dengan 4 kuadran jauh lebih sukar untuk dimainkan daripada Chomp dengan 1 kuadran?
- Di Nim, nilai SG satu longgokan hanyalah bilangan perlawanan dalam longgokan itu. (Sila sahkan ini dengan menggunakan komen di atas bagaimana mengira nilai SG pada satu timbunan di Nim.) Satu-satunya komplikasi bermain beberapa buasir di Nim adalah untuk XOR nilai SG yang berbeza dari buasir ini untuk mendapatkan nilai SG semua buasir digabungkan.
  
  Dalam Chomp ia adalah pengiraan mahal untuk mendapatkan nilai SG kedudukan (yang berada dalam satu kuadran). Dalam iChomp, sebaik sahaja nilai SG dari 4 kuadran diketahui, nilai-nilai ini perlu XOR'ed juga, tetapi itu lebih mudah daripada mencari nilai SG satu kuadran.
  
  Untuk bermain Chomp secara optimum seseorang tidak perlu mengetahui nilai SG kedudukan, mengetahui langkah kemenangan cukup baik, tetapi seperti yang ditunjukkan di atas perbezaannya tidak begitu besar.
  
  Jadi jawapannya adalah TIDAK, tidak lebih sukar untuk bermain iChomp secara optimum daripada Chomp.
Di Chomp, bolehkah langkah mencipta kedudukan yang mempunyai nilai SG yang lebih tinggi?
- Ya. Nilai SG bagi sesebuah kedudukan adalah nilai terkecil yang tidak boleh dijana dengan bergerak.
Di Chomp, bolehkah terdapat langkah yang berbeza yang mewujudkan kedudukan dengan nilai SG yang sama?
- Ya. Anda boleh melihat contoh dengan meningkatkan saiz papan dan klik butang 'Tunjukkan nilai SG Bergerak'. Sebagai contoh, kedudukan
  
  ###
  ##
  #
  
  mempunyai 3 gerakan menang, semuanya mewujudkan kedudukan dengan nilai SG 0. Kami juga mendapati kedudukan dengan 7 gerakan kemenangan:
```
 + 10  6 15  2 20 21 14 22 11  0 23  7 26
13  7 11  9 14  0 19  5
17 11 14 18  0 24 23  8
 3 19  2  0 20
11  4  0  5  1
 8  0
 0
 4
23
25
24
```

iChomp^©

Cara Bermain:

Cara Menang:

Giliran Pemain 1

	0110
XOR	1101
	------
	1011

iChomp©

Cara Bermain:

Cara Menang:

Giliran Pemain 1

iChomp^©