300000
Jumlah kemenangan: 30022
Titik
Jika anda hanya berminat dengan gerakan mana yang perlu dimainkan dan bukan kenapa kemudian pergi ke 'Pepohon Keputusan' di bahagian bawah. 'Indeks' di bawah menyenaraikan semua istilah yang diperkenalkan dalam teks dan boleh digunakan sebagai pengenalan ringkas.
Asas-asas
Terminologi: Mari kita perkenalkan beberapa istilah baharu yang akan kita gunakan untuk bercakap tentang permainan.
Sebuah kotak ialah segi sama kecil dengan 4 titik berjiran sebagai penjuru. Sebuah kotak boleh dilukis 0, 1, 2, 3, 4 pada sisinya dan kemudian dipanggil kotak-0, kotak-1, kotak-2, kotak-3, kotak-4.
Garisan ialah segmen garisan yang memautkan dua titik berjiran.
Melukis garisan juga dipanggil membuat pergerakan.
Jika garisan yang tidak dilukis memisahkan sebuah kotak-2 dan sebuah kotak-3 kemudian melukis garisan ini melakukan 3 perkara: ia melengkapkan kotak-3 dan dengan itu mendapat satu mata, ia menukar kotak-2 kepada kotak-3, dan ia memberikan pemain satu lagi langkah yang boleh digunakan untuk melengkapkan kotak-3 baharu. Jenis "tindak balas berantai" ini berlaku sangat kerap.
Semua kotak-2 yang disambungkan membentuk rantai. Rantaian boleh mempunyai 2 hujung dan kemudian dipanggil rantai linear, sama ada garis lurus atau tidak, seperti
+ + +---+---+ + +---+
| | , atau | |
+ + +---+---+ +---+ +
|
+---+---+menunjukkan rantai dengan kotak-1, -2 dan -4.
Rantaian juga boleh tidak mempunyai hujung dan kemudian kami memanggilnya rantai gelung atau hanya gelung, sama ada ia kelihatan seperti bulatan atau tidak, seperti ini
+---+---+---+
| |
+ +---+ +
| | |
+---+ + +
| |
+---+---+
Bergerak di dalam rantai atau pada salah satu hujungnya dipanggil membuka rantai dalam kesusasteraan matematik tentang permainan ini.
Apakah yang berlaku jika rantai dibuka?
Jika pemain melukis salah satu garisan yang belum dilukis dalam rantai seperti gerakan A1 dalam
+---+---+---+
| |
+ +A1-+ +
| |
+---+---+kemudian sekurang-kurangnya satu kotak-2 menjadi kotak-3 (di sini kotak di atas dan kotak di bawah A1 bergerak) dan selepas itu pemain lain boleh melengkapkan kotak (ini) kepada kotak-4, memperoleh satu atau dua mata dan pada masa yang sama tukarkan kotak-2 jiran kepada kotak-3 (di sini kotak kiri B1 dan kanan B2) dalam
+---+---+---+
| B1 |
+ +A1-+ + .
| B2 |
+---+---+Setiap kali kotak dilengkapkan pemain mesti membuat satu lagi gerakan yang boleh digunakan untuk melengkapkan kotak seterusnya dan semua kotak lain dalam rantaian tersebut. Selepas melengkapkan kotak terakhir pemain mesti membuat satu lagi pergerakan ke tempat lain melainkan semua kotak di papan telah diselesaikan.
Permainan Awal
Peraturan 1: Pernainan yang paling jelas ialah mengelak daripada mencipta kotak-3 yang boleh diambil oleh pihak lawan dengan melengkapkannya. Ini adalah peraturan yang mudah dan berguna walaupun ia tidak sempurna seperti yang mana kita lihat di penghujung laman web ini. Pada peringkat tertentu, apabila kira-kira separuh daripada semua garisan dilukis, mencipta kotak-3 menjadi tidak dapat dielakkan. Apa yang berlaku kemudian? Kerana rantaian dengan kotak-2, -2 atau ≥ 3 dilayan secara berbeza, kita perlu melihatnya secara individu.
Mari kita mulakan dengan melihat rantai yang mempunyai hanya satu kotak.
Patutkah pemain sentiasa melengkapkan satu kotak-3, contohnya rantaian dengan dengan kotak-1?
+---+
| ?
+---+
Ya, pemain harus selalu berbuat demikian. Sama ada pemain mengambil kotak dan selepas itu membuat gerakan A atau tidak mengambil kotak dan bermain di A tidak mempunyai kesan ke atas apa yang dilakukan pihak lawan kecuali sama ada anda atau pihak lawan mendapat kotak itu, jadi adalah lebih baik anda mendapatkan kotak itu.
Bagaimanakah rantaian dengan dua kotak kelihatan dan bagaimanakah pemain harus bermain di dalamnya?
Rantaian dengan dua kotak kelihatan seperti
+---+---+ +---+---+ +---+---+
atau | atau | |
+---+---+ +---+ + + + +atau versi diputar dan dicerminkan. Melukis garis tengah di sana menuju ke
+---+---+ +---+---+ +---+---+
| atau | | atau | | |
+---+---+ +---+ + + + +dan dipanggil dalam kesusasteraan Hard-Hearted Handout .
Patutkah pemain sentiasa mengambil kedua-dua kotak dalam kedudukan sedemikian?
Ya, pemain harus mengambil kedua-dua kotak atas sebab yang sama kerana pemain harus sentiasa mengambil rantaian kotak-1. Sila yakinkan diri anda.
Melukis garisan pada sempadan rantaian dengan dua kotak menuju ke
+---+---+ +---+---+ | atau | | +---+---+ +---+ +
dan dipanggil Half-Hearted Handout..
Pergerakan di sempadan Half-Hearted Handout membawa kepada
+---+---+ | | . +---+---+
Pergerakan sedemikian dipanggil dalam kesusasteraan Double Dealing (DD).
Melukis garisan di tengah yang melengkapkan kedua-dua kotak dipanggil Pergerakan Silang Berganda. Gelung sentiasa dilengkapkan dengan gerakan sedemikian tetapi dalam rantaian linear, ia hanya boleh berlaku apabila pihak lewan memainkan gerakan DD untuk mengawal seperti yang dijelaskan di bawah. Dalam keadaan sedemikian, pemain yang membuat pergerakan silang berganda ditipu, oleh itu nama ini untuk pergerakan itu.
Patutkah pemain seterusnya sentiasa mengambil kedua-dua kotak selepas DD?
Pergerakan DD adalah pengorbanan dua kotak kerana pemain secara alternatif boleh bermain di tengah-tengah di Hard-Hearted Handout dan kemudian di sempadan dan memperoleh dua kotak dengan cara ini. Kenapa nak korbankan 2 kotak? Teruskan membaca untuk mengetahui!
Pergerakan seperti Half-Hearted Handout sebelum DD, yang memberi pihak lawan pilihan untuk berkorban dipanggil dalam kesusasteraan sebagai langkah gila. Contoh-contoh lain bagi langkah gila ialah gerakan yang membuka rantai dengan 3 atau lebih kotak kerana pemain seterusnya juga mendapat pilihan untuk bermain DD seperti yang akan kita lihat di bawah.
Kembali ke Half-Hearted Handout, patutkah pemain sentiasa mengambil kedua-dua kotak dalam kedudukan sedemikian? Jika tidak, bilakah pemain harus bermain DD di sempadan? Cuba kdua-duanya dalam permainan dan lihat perbezaannya.
Mari kita pertimbangkan semua perbezaan. Jika pemain mengambil satu kotak maka pemain harus mengambil kotak kedua seperti yang kita dapati sebelum ini. Jika pemain mengambil kedua-dua kotak, pemain mandapat 2 mata, tetapi selepas itu pemain itu perlu bergerak ke tempat lain. Ini mungkin membahayakan kerana pemain mungkin perlu membuka rantai dengan banyak kotak yang membolehkan pihak lawan mengambil lebih banyak kotak. Jika pemain bermain di sempadan, dia tidak melengkapkan kotak dan oleh itu dia tidak perlu bermain di tempat lain. Tetapi bermain di sempadan memberikan pemain seterusnya kedua-dua kotak seperti yang baru dibincangkan. Oleh itu, kedua-dua permainan adalah mungkin. Kami akan kembali kepada soalan ini kemudian untuk menentukan langkah mana yang lebih baik dalam situasi tertentu.
Jika pemain perlu membuka rantai dengan dua kotak kerana semua pergerakan lain akan menjadi lebih membahayakan, adakah pemain itu harus memainkan Hard-Hearted atau Half-Hearted Handout?
Jika pemain bermain di tengah-tengah rantaian (Hard-Hearted Handout) maka pihak yang satu lagi terpaksa mengambil kedua-dua kotak dan selepas itu membuat perpindahan yang berpotensi membahayakan di tempat lain:
+---+---+ +---+---+ +---+---+
→ | → | | | tambahan di tempat lain +---+---+ +---+---+ +---+---+
Jika pemain bermain di sempadan rantai (Half-Hearted Handout) maka pemain itu memberi pihak lawan pilihan sama ada mengambil dua kotak seperti di atas atau bermain di sempadan (Pergerakan Double Dealing (DD)):
+---+---+ +---+---+ +---+---+
→ | → | |
+---+---+ +---+---+ +---+---+
Pilihan ini mungkin sangat berharga kerana kita akan ketahui kemudian. Memberi pilihan tambahan kepada pihak lawan tidak boleh menjadi satu langkah yang lebih baik, jadi menyasarkan permainan optimum pemain itu tidak seharusnya memainkan Half-Hearted Handout. Dalam permainan yang tidak optimum, pemain boleh mencuba pergerakan Half-Hearted untuk mengetahui kemahiran pihak lawan, atau untuk mengelirukan pihak lawan jika pemain berada di belakang (tetapi tidak jika pemain cuba bermain secara optimum).
Apakah yang perlu dilakukan dengan membuka rantai linear tiga atau lebih kotak?
Jika rantai dibuka maka ia mempunyai sekurang-kurangnya satu kotak-3. Pemain boleh melengkapkan kotak ini dan kotak lain juga, tetapi patutkah pemain berbuat demikian?
Adakah terdapat kotak yang mesti diambil dari rantai terbuka linear?
Kita mahu mengambil sebanyak mungkin kotak. Sebaliknya, kita mungkin tidak mahu membayar harga bermain di tempat lain selepas itu dan dengan itu membuka rantaian yang lebih besar untuk diambil oleh pihak lawan. Apa yang perlu kita lakukan ialah mengambil semua kecuali dua kotak seperti yang dibenarkan sebelum ini, ia adalah bebas, tiada kesam sampingan negatif. Selapas itu, kita boleh berfikir untuk mengambil baki 2 kotak juga atau bermain DD (Double Dealing). Kami akan bincang lebih lanjut mengenainya kemudian.
Rantai dengan ≥3 kotak dipanggil rantai panjang.. Ini termasuk kedua-duanya, rantai linear dan gelung.
Mengapakah terdapat nama khas untuk rantai tersebut?
Jika hanya rantai panjang dengan sekurang-kurangnya 3 kotak yang tinggal, maka membuka salah satu daripadanya, tidak kira dalam apa cara sekalipun, bermakna sekurang-kurangnya pada satu sisi pergerakan terdapat sekurang-kurangnya 2 kotak bersebelahan. Jadi, pemain lain boleh bermain Double Dealing yang penting dalam menentukan baki permainan.
Berapakah bilangan kotak yang diperlukan untuk membuat gelung?
Gelung terkecil yang mungkin mempunyai 4 kotak:
+---+---+ | | + + + | | +---+---+
Jika gelung dibuka, bolehkah pemain mengambil semua kecuali 2 kotak dengan selamat tanpa berfikir?
Marilah kita mencubanya. Gelung terbuka terkecil yang mungkin ialah
+---+---+ | | +---+ + | | +---+---+
Sudah tentu kita boleh mengambil kesemua 4 kotak dan kemudian bermain di tempat lain, tetapi bagaimana jika kita mahu mengelak daripada bermain di tempat lain pada semua kos? Jika kita akan mengambil dua kotak, kita mencapai
+---+---+ | | | +---+---+ | | +---+---+
tetapi kita perlu membuat satu lagi langkah. Jadi kita tidak boleh berhenti di sini kerana semua garisan di sempadan sudah dilukis jadi kita perlu terus ke
+---+---+ | | | +---+---+ | | | +---+---+
dan kemudian kita diwajibkan untuk bergerak ke tempat lain, yang mungkin boleh menyerahkan rantai yang lebih besar kepada pihak lawan.
Apa lagi yang boleh kita lakukan?
Kami mahu bermain gerakan yang tidak melengkapkan kotak untuk mengelak daripada bermain di tempat lai. Satu-satunya langkah yang mungkin adalah bermain di tengah-tengah gelung yang dibuka untuk mencipta
+---+---+ | | +---+---+ . | | +---+---+
Langkah ini tidak melengkapkan kotak dan dengan itu pamain lain bermain seterusnya. Kita akan memanggil langkah ini Double Double Dealing (DDD). Harga yang akan dikorbankan adalah 4 dan bukan 2 kotak. Bagi pihak lawan, sebaiknya ambil 4 kotak dan bermain di tempat lain selepas itu.
Bagaimana jika gelung yang dibuka mempunyai lebih daripada 4 kotak?
Kita boleh mengambil seberapa banyak kotak yang kita suka selagi kita masih boleh bermain gerakan selepas itu yang tidak melengkapkan kotak. Ini bermakna kita boleh mengambil semua kecuali 4 kotak, contohnya, membuka
+---+---+---+---+ +---+---+---+---+ | | | | | + +---+---+ + memberikan, sebagai contoh, + +---+---+ + | | | | +---+---+---+---+ +---+---+---+---+
dan mengambil 8 - 4 = 4 kotak hasil, contohnya,
+---+---+---+---+ | | | | | + +---+---+---+ . | | | +---+---+---+---+
Sekarang kita perlu memutuskan sama ada untuk mengambil baki 4 kotak atau mengorbankannya kepada pihak lawan dengan bermain
+---+---+---+---+ | | | | | + +---+---+---+ . | | | | +---+---+---+---+
Lebih lanjut mengenai itu kemudian.
Dalam kes satu rantai terbuka atau kemungkinan beberapa rantai terbuka, beberapa banyak kotak yang boleh diambil dengan selamat tanpa memikirkan tentang bermain DD atau tidak bermain DD?Jika terdapat sekurang-kurangnya satu rantai linear terbuka yang mempunyai dua kotak bersebelahan, kemudian lengkapkan semua kotak lain dalam rantai ini dan lengkapkan semua kotak semua rantai linear terbuka dan gelung yang lain. Jika tidak, jika terdapat hanya satu atau lebih rantai gelung terbuka, maka lengkapkan semua kecuali empat kotak dari satu rantai gelung terbuka dan semua kotak semua rantai gelung terbuka yang lain. Selepas kotak-kotak ini siap, pemain boleh mula berfikir sama ada mahu bermain DD/DDD atau tidak.
Kita mengetahui bahawa permainan bermula dengan lebih atau kurang pergerakan rawak kecuali kedua-dua pemain mengelak daripada mencipta kotak-3 selagi mungkin, iaitu mereka mengelak membuka rantai. Apabila ini menjadi tidak dapat dielakkan, kami menganggapnya sebagai permulaan permainan akhir.. Kita bermula dengannya kerana ia adalah bahagian paling mudah dari semua permainan.
Permainan Terakhir
Seperti semua permainan lain, semakin hampir ke penghujungnya, semakin mudah untuk meramalkan siapa yang akan menang di bawah permainan optimum dan berapa banyak. Oleh itu, kami memulakan analisis kami dari akhir permainan. Dalam permainan akhir, semua pergerakan sama ada rantai terbuka atau kotak lengkap atau gerakan DD/DDD. Apabila permain perlu membuka rantai maka idea pertama untuk strategi mungkin membuka rantai terkecil yang tersedia untuk memberikan pihak lawan bilangan kotak yang paling sedikit. Marilah kita mencubanya dalam beberapa contoh.
Contoh 1
Mari kita andaikan bahawa semua kotak telah lengkap kecuali dua rantai dengan 3 kotak dan 4 kotak:
+ +---+---+ | | | | + +---+---+ | +---+---+---+ +---+---+---+
Pemain A yang bergerak seterusnya akan membuka rantai yang lebih pendek (dengan langkah A1) untuk pemain B yang lain untuk menuntut rantai itu dan mendapat 3 mata dan A untuk mendapatkan rantai yang lebih besar dengan kotak selepas itu dengan mata daripada dua rantai A:B ini = (0+4) : (3+0) = 4:3
+A9-+---+---+ | | | | +A8-+---+---+ | B5 A6 A7 +---+---+---+ B2 A1 B3 B4 +---+---+---+
Di samping itu, langkah A1 adalah apa yang kami takrifkan sebelum ini sebagai langkah gila, satu langkah yang memberi pilihan kepada pihak lawan untuk berkorban.
Tetapi pemain B bijak dan mengambil hanya satu kotak dengan langkah B2 (dalam rajah seterusnya), kemudian mengambil langkah Urusan Ganda dengan B3. A kemudiannya perlu mengambil 2 kotak dengan A4, terpaksa membuka rantai besar dengan beberapa pergerakan, seperti A5 dan B mendapat baki 4 kotak dengan mata akhir A:B = (2+0) : (1+4) = 2.5.
+B9-+---+---+ | | | | +B8-+---+---+ | A5 B6 B7 +---+---+---+ B2 A1 A4 B3 +---+---+---+Kami melihat bahawa dalam keadaan ini adalah berfaedah bagi B untuk mengorbankan dua kotak.
Contoh 2
Mari kita andaikan bahawa semua kotak telah siap kecuali satu rantai dengan 3 kotak dan satu gelung dengan 4 kotak.
+---+---+---+ | | | + + +---+ | | | +---+---+---+ +---+---+---+Pemain A bergerak seterusnya.
Kes 1: A membuka rantai dengan 3 kotak.
Jika selepas A1, pemain B mengambil keseluruhan rantai, pemain A mendapat gelung dan mata daripada 2 rantai ini ialah A:B = (0+4):(3+0) = 4:3.
+---+---+---+ | A7 | | +A6-+A8-+---+ | B5 | | +---+---+---+ B2 A1 B3 B4 +---+---+---+
Jika selepas A1, pemain B bermain DD maka selepas
+---+---+---+ | B7 | | +B6-+B8-+---+ | A5 | | +---+---+---+ B2 A1 A4 B3 +---+---+---+mata daripada kedua-dua rantai ini ialah A:B = (2+0):(1+4) = 2:5 jadi juga di sini adalah berfaedah untuk B bermain DD dan capai A:B = 2:5.
kES 2: A membuka gelung dengan 4 kotak.
Jika selepas A1, pemain B mengambil keseluruhan gelung, pemain A mendapat rantai yang lebih pendek dan mata daripada 2 rantai ini ialah A:B = (0+3):(4+) = 3:4.
+---+---+---+ | B3 | | +B2-+B4-+---+ | A1 | | +---+---+---+ B5 A6 A7 A8 +---+---+---+
Jika selepas A1, pemain B bermain DDD dengan B2, kita mendapat
+---+---+---+ | B2 | | +A3-+A4-+---+ | A1 | | +---+---+---+ B6 A5 B7 B8 +---+---+---+dan mata daripada dua rantai A:B = (4+0):(0+3) = 4:3 INI. Dalam kes ini adalah lebih baij untuk B TIDAK bermain DDD kemudian untuk mendapatkan A:B = 3:4.
Apakah yang kita pelajari daripada dua kes tersebut?
Kami melihat dalam kes kedua bahawa kos bermain DDD dalam gelung adalah tinggi (4 kotak) yang boleh menjadikannya lebih baik untuk tidak memainkannya tetapi mengambil keseluruhan gelung. Jadi rantaian manakah yang harus dibuka oleh pemain dalam contoh ini? Adalah lebih baik untuk A membuka gelung yang mencapai A:B = 3:4 daripada membuka tiga rantai kotak yang mencapai A:B = 2:5. Kami telah mengetahui bahawa jika gelung terlibat, rantai tidak seharusnya hanya diisih mengikut saiz (bilangan kotak) untuk memutuskan rantaian yang hendak dibuka dahulu. Tetapi menyusunnya mengikut saiz -2 jika ia adalah gelung akan berfungsi di sini: 4 - 2 = 2 < 4.
Contoh 3
Dalam contoh ini, kami ingin mengetahui lebih lanjut tentang susunan rantai harus dibuka. Mari kita andaikan bahawa semua kotak telah dilengkapkan kecuali dua rantai linear dengan 3 dan 4 kotak dan satu gelung dengan 4 kotak seperti di sisi:
+---+---+ +---+
| | |
+ + +---+ +
| | | |
+---+---+---+ +
|
+---+---+ +---+Pemain A bergerak seterusnya. Jelas bahawa A tidak akan membuka rantai linear yang lebih besar dengan 4 kotak jika terdapat rantai linear dengan 3 kotak.
Kes 1: A membuka rantai dengan 3 kotak.
Sebelum menutuskan permainan optimum untuk pemain B, mari kita semak yang mana antara 2 rantai lain yang harus dibuka dahulu:
+---+---+ +---+ | | | + + +---+ + | | | | +---+---+---+ + | | | | +---+---+---+---+
Biarkan pemain menjadi C dan D dengan C bergerak seterusnya.
Kes 1.1: C membuka gelung
+---+---+ +---+
| | |
+ + +---+ +
| C1 | | |
+---+---+---+ +
| | | |
+---+---+---+---+ Jika selepas pemain C1, D bermain DDD dengan D2 maka selepas
+---+---+C5-+---+ | D2 | D6 | +C3-+C4-+---+D7-+ | C1 | | | +---+---+---+D8-+ | | | | D9 +---+---+---+---+
mata daripada dua rantai ini ialah C:D (4+0):(0+4) = 4:4. Jika D tidak memainkan DDD tetapi mengambil gelung maka selepas
+---+---+D5-+---+ | D3 | C6 | +D2-+D4-+---+C7-+ | C1 | | | +---+---+---+C8-+ | | | | C9 +---+---+---+---+
mata daripada dua rantai ini juga C:D = (0+4):(4+0) = 4:4.
Kes 1.2: C membuka rantai 4 kotak
+---+---+C1-+---+
| | |
+ + +---+ +
| | | |
+---+---+---+ +
| | | |
+---+---+---+---+ Jika selepas pemain C1, D megambil keseluruhan rantai meka selepas
+---+---+C1-+---+ | C8 | D2 | +C7-+C9-+---+D3-+ | D6 | | | +---+---+---+D4-+ | | | | D5 +---+---+---+---+
mata ialah C:D (0+4):(4+0) = 4:4. Jika selepas pemain C1, D bermain DD dengan D4 maka selepas
+---+---+C1-+---+ | D8 | D2 | +D7-+D9-+---+D3-+ | C6 | | | +---+---+---+C5-+ | | | | D4 +---+---+---+---+mata ialah C:D = (2+0):(2+4) = 2:6. Yang terbaik yang boleh D kuatkuasakan selepas C1 ialah C:D = 2:6.
Apakah yang kita pelajari daripada dua kes tersebut?
Adalah lebih baij untuk pemain yang bermain seterusnya (C) untuk membuka gelung mencapai C:D =4:4 daripada rantai linear mencapai hanya C:D 2:6. Jika kita akan menyusun rantai mengikut saiz -2 untuk memutuskan mana yang hendak dibuka dahulu maka (4-2) = 2<4 akan memberikan hasil yang betul. Kini kita boleh memutuskan permainan optimum untuk B dalam:
+---+---+- +---+
| | |
+ + +---+ +
| | | |
+---+---+---+ +
A1 |
+---+---+ +---+
Patutkah B mengambil rantai atau bermain DD?
Jika B mengambil rantai maka selepas
+---+---+A9-+---+ | A7 | A10 | +A6-+A8-+---+A11+ | B5 | | | +---+---+---+A12+ B2 A1 B3 | A13 +---+---+B4-+---+
mata pada 3 rantai ini ialah A:B = (0+4+0) : (3+0+4) = 4:7. Jika B sebaliknya bermain DD dengan B3 maka selepas
+---+---+B9-+---+ | B7 | A10 | +B6-+B8-+---+A11+ | A5 | | | +---+---+---+A12+ B2 A1 A4 | A13 +---+---+B3-+---+
mata pada 3 rantai ini ialah A:B = (2+0+4) : (1+4+0) = 6:5. Jadi yang terbaik yang B boleh capai selepas A1 ialah A:B = 4:7 yang diperolehi oleg B melalui tidak bermain DDD. Dalam kedua-dua kes, kami menggunakan penemuan awal bahawa gelung harus dibuka seterusnya.
Kes 2: A membuka gelung dengan 4 kotak:
+---+---+ +---+
| | |
+ + +---+ +
| A1 | | |
+---+---+---+ +
|
+---+---+ +---+
Kes 2.1 : B mengambil keseluruhan gelung.
Jelas sekali bahawa rantai kevil harus dimainkan dengan DD yang membawa kepada
+---+---+B9-+---+ | B3 | A10 | +B2-+B4-+---+A11+ | A1 | | | +---+---+---+A12+ B5 A6 B8 | A13 +---+---+A7-+---+memberikan mata pada 3 rantai A:B = (0+1+4) : (4+2+0) = 5:6 ini.
Kes 2.2 : B mengorbankan gelung.
Sekali lagi rantai kecil harus dimainkan dengan DD yang membawa kepada
+---+---+A9-+---+ | B2 | B10 | +A3-+A4-+---+B11+ | A1 | | | +---+---+---+B12+ A5 B6 A8 | B13 +---+---+B7-+---+memberikan mata pada 3 rantai A:B = (4+2+0) : (0+1+4) = 6:5 ini.
Apakah yang kita pelajari daripada kes 2.1 dan 2.2?
Oleh kerana harga yang tinggi untuk bermain DDD dalam gelung, yang terbaik untuk B di sini ialah mengambil keseluruhan gelung mencapai mata A:B = 5:6.
Apakah yang kita pelajari daripada kes 1 dan 2?
Kami mempunyai dua rantai linear dengan 3 dan 4 kotak dan gelung dengan 4 kotak. Adalah lebih baik untuk A membuka gelung dan mencapai mata A:B = 5:6. Jika A membuka rantai dengan 3 kotak maka ia hanya mencapau A:B = 4:7. Adalah jelas bahawa tidak lebih baik untuk B membuka rantai dengan 4 kotak sebelum rantai dengan 3 kotak. Oleh itu, menyusun rantai hanya mengikut saiz untuk menentukan yang akan dibuka seterusnya tidak berfungsi. Tetapi menyusunnya mengikut saiz -2 jika ia adalah gelung nampaknya berfungsi kerana (4-2) = 2<3 menunjukkan bahawa gelung harus dibuka dahulu.
Susunan di mana rantai dibuka
Dengan pengalaman yang diperoleh daripada contoh di atas, kami kini menangani masalah menentukan susunan rantaian akan dibuka dan disiapkan. Susunan rantai ini akan digunakan di bawah untuk menentukan bila salah seorang pemain akan bermain DD/DDD, siapa yang akan memenangi permainan dan berapa banyak. Berita baiknya ialah pada perlawanan akhir susunan rantaian pembukaan ini tidak bergantung pada giliran siapa atau siapa yang bermain DD/DDD sebelum ini. Sebabnya ialah pada bila-bila masa dalam permainan hanya garisan yang telah dilukis menjadi perkara, bukan oleh siapa dan bukan mengikut susunan yang mana. Malah mata semasa tidak mempunyai kesan ke atas permainan optimum masa hadapan. Membahagikan masalah yang sukar kepada masalah yang lebih mudah sudah berjaya. Dalam kes ini, tugas sukar untuk menentukan siapa yang bergerak dalam permainan akhir telah dibahagikan kepada dua masalah: masalah susunan untuk membuka rantai, dan masalah siapa yang bermain DD/DDD dan bila. Sebelum kita bermula, kita perlu memikirkan tentang trend umum dalam permainan akhir.
Adakah 'nilai' rantaian terbuka berkurangan atau meningkat menjelang akhir?
Rantai yang dibuka diberikan kapada pihak lawan. Oleh itu, rantaian harus mempunyai "nilai" yang paling sedikit mungkin di mana nilai, sepintas lalu, dengan bilangan kotak. Oleh itu sepanjang permainan akhir 'nilai' rantaian yang dibuka hanya boleh naij atau kekal tetapi tidak berkurangan. Dalam contoh kami di atas, kami melihat bahawa membuka rantai dengan kotak paling sedikit untuk diambil oleh pihak lawan tidak berfungsi. Tetapi kami mahu menyusun rantai mengikut beberapa "nilai" kerana setiap pemain mahu membuka rantai yang paling tidak bernilai untuk pihak lawan. Bagi pihak lawan, nilai rantai bukan sahaja terdiri daripada bilangan kotak; ia juga pentng sama ada rantai yang dibuka sesuai untuk memainkan DD/DDD di dalamnya. Calon yang baij uktuk pelarasan kesesuaian untuk DD ialah menolak 2 daripada bilangan kotak jika rantai itu ialah gelung. Jadi untuk mengisih rantai mengikut 'nilai' di mana kita mengambil 'nilai' = # kotak jika rantai BUKAN gelung dan mengambil 'nilai' = # kotak -2 jika rantai ADALAH gelung.
Kita mulakan dengan kedudukan papan di mana setiap kotak mempunyai sekurang-kurangnya 2 sisi yang dilukis. Untuk itu, kita boleh merumuskan dua peraturan yang memerintahkan semua rantai.
Peraturan 2: Untuk menyusun rantai, ambil rantai linear terbesar sebagai rantai terakhir dan jika tiada rantai linear maka ambil gelung terbesar.
Justifikasi Peraturan 2
Pemain yang mengawal tidak membuka rantai dan oleh itu tidak menyusun rantai. Oleh itu, mana-mana pemain yang mentusun rantai ingin membuat pengambilan atau mengekalkan kawalan (iaitu bermain gerakan DD/DDD) untuk puhak lawan semahal mungkin. Satu pergerakan DD berharga 2 kotak dan satu pergerakan DDD berharga 4 kotak. Harga ini perlu dibayar untuk semua rantai kecuali yang terakhir. Oleh itu, untuk memaksimumkan jumlah kos untuk pihak lawan, dalam penyusunan rantai, jika boleh rantai terakhir harus linear dan bukan gelung.
Peraturan 3: Jika dalam permainan akhir, semua kotak memounyai sekurang-kurangnya 2 sisi yang dilukis, maka untuk menyusun semua rantai lain, menyusun mengikut (bilangan kotak -2 jika ia adalah gelung).
Justifikasi Peraturan 3
Untuk pemain seterusnya mengambil atau mengekalkan kawalan, nilai rantai ialah bilangan kotaknya -2 jika ia adalah rantai linear dan -4 jika ia adalah gelung. Untuk menyusun rantai, pemain mendapat hasil yang sama jika pemain hanya menolak 2 dalam kes gelung.
Bagaimana jika pihak lawan mempunyai kawalan pada giliran seterusnya? Adakah pihak lawan tidak akan mendapat manfaat apabila, berdasarkan susunan ini, pihak lawan bergerak seterusnya dalam gelung terbuka dengan dua kotak lagi daripada mendapatkan rantai linear dengan 'nilai' yang sama tetapi kurang kotak? Tidak! Jika pihak lawan melengkapkan keseluruhan gelung maka selepas itu apabila giliran pemain ini. akan ada satu gelung kurung dan ia akan menjadi 2 kotak lebih murah untuk mengawal.
Kami melihat kesan itu dalam Contoh 3 kes 2.1 di mana, selepas pemain A membuka gelung dengan A1, pemain B mengambil keseluruhan gelung tetapi sebagai akibatnya ia menjadi mampu untuk A selepas itu mengawal dengan A7 dan memperoleh hasil yang terbaik.
Peraturan di atas adalah jelas jika semua kotak tergolong dalam rantai, iaitu jika semua kotak mempunyai sekurang-kurangnya 2 sisi yang dilukis. Tetapi bagaimana jika terdapat kotak-0 dan kotak -2?
Kotak-kotak ini tergolong dalam rantai yang manakah?
Peraturan 4: Untuk mewujubkan susunan rantai yang disusun mengikut nilai diwujub oleh kitaran berikut untuk membuat pergerakan sehingga keseluruhan papan diselesaikan.
- Buka salah satu rantai yang nilainya (bilangan kotak, atau jika gelung bilangan kotak -2) adalah minimum dengan satu pengecualian: Jika masih terdapat sekurang-kurangnya satu gelung, sama ada disambungkan atau diputuskan, dan jika terdapat hanya satu rantai linear yang terputus, dan jika tiada pepohon yang bersambung bagi rantai linear sahaja maka jangan buka rantai linear terputus terakhir.
- Lengkapkan rantai yang dibuka tanpa mengira kotak. Melukis garisan pada penghujung rantai linear boleh menukar kotak-1 kepada kotak-2 dan dengan itu sama ada menggabungkan dua rantao linear atau memotong gelung.
Jika dalam permainan akhir masih terdapat kotak-0 dan kotak-1 maka pemain boleh menganggap kotak sedemikian sebagai titik dan memikirkan rantai sebagai garisan yang berakhir pada titik tersebut atau berakhir di tepi papan dan kemudian mendapat titik tambahan tiruan.
Titik bersama-sama bersambung dengan garis dipanggil graf dalam matematik.
Pengecualian dalam Peraturan 4 yang dirumuskan dalam 'bahasa graf' akan menyatakan: Jangan buka rantai linear yang sepadan dengan garis yang terputus daripada graf yang tinggal jika baki graf mempunyai bahagian terputus yang mengandungi gelung dan tidak mempunyai bahagian terputus yang tidak mengandungi gelung (dan oleh itu dipanggil 'pepohon' dalam bahasa graf).
Contoh 4: Graf seperti 'T'
Kotak-1 mempunyai tulisan 'T' :
+---+---+---+ + | T | | + + + + + | | | | + + +---+---+ | | | + +---+---+ +
Graf yang menyelaras dengan papan ini akan menjadi seperti T dengan 4 mata, satu di mana - dan | dalam penemuan T dan 3 mata pada 3 hujung T.
Yang terkecil daripada 3 rantai yang dipasang pada kotak-1 adalah di sebelah kirinya. Dengan membukanya dan melengkapkannya
+---+---+---+ + +---+---+---+ + | | | | | | | + + + + + +---+ + + + | | | | | | | | +---+ +---+---+ +---+ +---+---+ | | | | | | + +---+---+ + +---+---+---+ +
pemain dapat melihat bahawa papan itu mempunyai dua rantai linear, satu dengan 3 dan satu dengan 9 kotak.
Contoh 5: Graf seperti 'P'
Kotak-1 mempunyai tulisan 'P':
+---+---+---+---+ | | + +---+---+ + | P | + +---+---+---+ | | +---+---+---+ +
Melukis sisi di atas kotak-1 atau di sebelah kanan kotak ini akan mencipta dan membuka satu rantai linear besar dengan 12 kotak
+---+---+---+---+ | | +---+---+---+ + | | + +---+---+---+ | | +---+---+---+ +
yang tidak mahu diberikan kapada pihak lawan. Melukis garisan di bawah kotak-1 akan membahagikan papan menjadi rantai linear terbuka dengan 4 kotak dan gelung dengan 8 kotak.
+--+--+--+--+ | | + +--+--+ + | | +--+--+--+--+ | | +--+--+--+ +
Dalam Peraturan 4 di atas pengecualian telah dirumuskan. Contoh 6 menggambarkan pengecualian ini.
Contoh 6: Graf 'P' ditambah rantai linear yang terputus.
Dua rantai linear boleh dibuka, satu di sebelah kanan dan satu di bahagian bawah.
+---+---+---+---+ + | P | | + + +---+ + + | | | | + +---+---+---+ + | | | +---+---+---+ + +
Kes 1. Buka rantai terpendek dahulu
21 gerakan telah dibuat, jadi jika pemain A bermula, pemain B vergerak seterusnya.
Jika selepas membuka rantai terkecil dengan B1, pemain A mengawal serta-merta, kita mendapat
+---+---+---+---+B1-+ | B5 B12 | | +A6-+ +---+ +A2-+ | | | | +A7-+---+---+---+B4-+ | A8 A9 B11 | | +---+---+---+A10+A3-+
dan mata A:B = (1+4+6):(2+2+0) = 11:4 di mana (2+2+0) bermakna pemain B mendapat daripada 3 rantai yang dibuka dalam susunan 2, 2 dan 0 kotak itu. Oleh kerana B hanya boleh membuka rantai linear ke-2 dengan B5, pemain A boleh kekal mengawal dengan A10 dan dengan kos hanya 2 dan mendapatkan gelung secara percuma.
Kes 2. Buka rantai linear yang lebih panjang dahulu.
Selepas B membuka rantai yang lebih panjang dengan B1 di bawah dan rantai ini selesai, sesiapa yang mendapat kotak terakhir perlu membuka rantai. Menurut Peraturan 2 kami, pemain B membuka gelung seterusnya dengan B8 untuk membuat pengambilan / menjaga kawalan yang mahal. Strategi ini berfungsi kerana mengambil / menjaga kawalan dalam gelung tidak masuk akal untuk pemain A kerana ia berharga 4 kotak tetapi hanya memenangi 3 kotak dalam rantaian terakhir.
+---+---+---+---+A14+ | B1 A13 B8 | | +A2-+A12+---+A9-+B15+ | | A11 A10 | | +A3-+---+---+---+B16+ | A4 A5 B7 | | +---+---+---+A6-+B17+
Mata ialah A:B = (4+6+0) : (2+0+3) = 10:5.
Jika A tidak akan memainkan DD dalam rantaian pertama:
+---+---+---+---+B14+ | B1 B13 A8 | | +A2-+B12+---+B9-+A15+ | | B11 B10 | | +A3-+---+---+---+A16+ | A4 A5 A6 | | +---+---+---+A7-+A17+
maka mata A:B = (6+0+3) : (0+6+0) = 9:6 akan menjadi lebih teruk untuk A. Sebabnya ialah bermain dalam gelung selepas ia dibuka (B9 di atas) bernilai 6-3=3 mata dan mengambil kawalan dalam rantai panjang pertama hanya berharga 2 mata, jadi ia patut mengambil kawalan dalam rantai pertama. 10:5 lebih baik daripada 9:6 untuk pemain A.
Apabila membandingkan kes 1 dan 2 dan dua mata 11:4 dan 10:5 adalah jelas bahawa pemain B harus membuka rantai yang lebih panjang terlebih dahulu. Sebabnya ialah jika B akan membuka rantai linear yang terputus dahulu, maka gelung itu akan disiapkan terakhir yang bermakna pemain A tidak perlu memyerah 4 mata apabila bermain DDD dalam gelung untuk kekal dalam kawalan. Kami akan melanggar Peraturan 2 kami yang terdahulu. Pemain boleh menunjukkan secara umum bahawa jika rantai yang terputus mempunyai m kotak, rantai linear yang disambungkan mempunyai n kotak dan gelung mempunyai p kotak maka pemain B membuka rantaiyang terputus terlebih dahulu memberikan B 4 mata daripada 2 kali DD manakala apabila B membuka rantai linear yang dipasang kemudian B dapat
min(p + maks(0,m-4),min(6,m+2))
banyak mata. Nilai terendah yang boleh diambil adalah apabila p mempunyai nilai tererndah initu 4 (gelung mempunyai sekurang-kurangnya 4 kotak) dan m mempunyai nilai terendah iaitu 3 (panjang terpendek rantai linear, jika rantai terpendek hanya mempunyai 2 kotak yang akan dimainkan dengan Hard-Hearted Handout serta-merta dan formulanya akan berbeza). Untuk p = 4 dan m = 3 pemain B akan dapat
min(4 + maks(0,-1),min(6,5)) = min(4+0,5) = 4
dan untuk p > 4 atau m >4 pemain B akan mendapat lebih daripada 4 mata.
Bagaimana jika terdapat rantaian yang berbeza dengan nilai terendah yang sama?
Jika rantai yang berbeza mempunyai nilai terendah yang sama maka program kami menggunakan peraturan untuk membuka rantai yang bersambung. Pemikiran di sebaliknya ialah terdapat kemungkinan bahawa melalui rantaian yang dibuka ini, gelung boleh diakses yang boleh menjadikan pengambilan / penjagaan kawalan hanya lebih mahal.
Dalam permainan, pemain biasanya mengawal dengan bermain DD/DDD pada permulaan permaina tamat. Tetapi jika terdapat banyak rantai dengan 3 kotak dan gelung dengan kurang daripada 8 korak maka mungkin lebih baik untuk tidak bermain DD/DDD dan tidak mengambil kawalan, Oleh itu, kami memerlukan algoritma umum dan bukan sahaja paraturan praktikal.
Bilakah pemain harus bermain DD/DDD dan bila tidak?
Dalam kesusasteraan tentang permainan Titik, permainan pertama DD/DDD juga dipanggil mengambil kawalan. Maksudnya ialah pemain mengawal siapa yang mendapat rantai panjang terakhir, yang mungkin tidak sama dengan mengawal permainan dan memenanginya dengan TIDAK bermain DD/DDD seperti yang akan kita lihat di bawah.
Apabila pemain mempunyai pilihan untuk bermain DD/DDD maka pemain ini mempunyai pilihan untuk bertukar peranan dengan pihak lawan pada harga 2 mata (DD) atau 4 mata (DDD). Jika pemain mengetahui mata yang boleh diperolehi daripada bermain secara optimum dalam rantaian yang selebihnya, maka pemain boleh memutuskan sama ada berbaloi untuk menukar peranan sekarang dengan kos 2 (jika rantaian yang sedang dimainkan adalah linear) atau kos 4 mata (jika pada masa ini -rantai yang dimainkan ialah gelung). Bersama-sama dengan pendapatan daripada rantaian semasa pemain s boleh menentukan mata sebelum membuka rantaian semasa. Pengiraan ini boleh dilakukan ke belakang bermula dari akhir permainan jika pemain mengetahui susunan rantai yang dibuka. Susunan sedemikian boleh ditentukan oleh Peraturan 4 di atas.
Peraturan 5: Tentukan sama ada hendak memainkan DD/DDD atau tidak dengan menggunakan kod psurdo di bawah.
Dalam kod komputer pseudo berikut, pembolehubah A ialah bilangan mata yang diperoleh dalam baki permainan oleh pemain yang membuka rantai seterusnya, dan pembolehubah B ialah bilangan mata yang diperoleh oleh pemain lain. Bilangan kotak yang tinggal ialah A+B. Kami mengira ke belakang dan untuk kemudahan label rantaian ke belakang: rantaian terakhir yang dibuka dalam permainan ialah rantai 1, rantai sebelum itu adalah rantai 2 dan seterusnya. Rantai semasa ialah rantai k. Mana-mana rantai j mempunyai n_j kotak. Pembolehubah gerakan DD merekodkan sama ada DD/DDD dimainkan dalam rantai j.
Dalam baris kod psuedo berikut
- (1)-(3) memulakan 3 pembolehubah sebagai hasil daripada memainkan rantai terakhir.
- (4)-(22) kemas kini A, B, gerakan DD untuk rantai j di mana j berjalan ke belakang dari rantai terakhir tetapi satu (j=2) ke rantai k sekarang.
- (5)-(13) jika rantai j adalah linear kos ialah 2
- (14)-(22) jika rantai j ialah gelung, kos ialah 4
- (4), (8) jika keuntungan B & tolak; A lebih besar daripada kos (2 atau 4) kemudian mainkan DD dan kurangkan B mengikut kos dan tambahkannya pada A. Dalam apa jua keadaan B dapatkan n_j.
(1) A = 0
(2) B = n_1
(3) playDD = false
(4) For each chain j from 2 to k:
(5) If chain j is linear:
(6) If B > (A + 2):
(7) playDD = true:
(8) B = B + n_j - 2
(9) A = A + 2
(10) Otherwise:
(11) playDD = false:
(12) B = A + n_j
(13) A = B
(14) Otherwise → If chain j is a loop:
(15) If B > (A + 4):
(16) playDD = true
(17) B = B + n_j - 4
(18) A = A + 4
(19) Otherwise
(20) playDD = false
(21) B = A + n_j
(22) A = B
Selepas pengiraan ini, A ialah mata untuk pemain yang membuka rantai semasa, B ialah mata untuk pihak lawan dan mainkan DD mengatakan sama ada pihak lawan harus bermain DD/DDD sekarang. (Tamat Peraturan 5)
Kod pseudo ini mungkin kelihatan sukar untuk pemain yang bukan pemprogram， tetapi ia adalah mudah untuk dilaksanakan dalam kepada pemain kerana ia hanya bermaksud untuk menyemak sama ada faedah kekal dalam kawalan melebihi kosnya, iaitu kos bermain DD/DDD.
Soalan Ujian
Kami tahu bahawa rantaian nilai terendah dibuka dahulu. Adakah ini bermakna bahawa bermain DD/DDD menjadi lebih berfaedah menjelang akhir permainan
Dalam erti kata lain, adakah bermain DD/DDD kini sentiasa bermakna pemain itu perlu memainkannya sehingga tamat kerana jika tidak pihak lawan akan mengambil alih kawalan dan menang?
Dalam hampir semua kes, ya. Tetapi kita melihat dalam Contoh 6, kes 2 bahawa beberapa gelung nilai rendah boleh diakses hanya selepas rantai linear bernilai lebih tinggi disiapkan. Akibatnya, walaupun tidak ada insentif yang mencukupi untuk bermain DDD apabila gelung dibuka (rantai terakhir hanya mempunyai 3 kotak menakala DDD berharga 4 kotak), insentif itu cukup untuk bermain DD lebih awal yang mempunyai kos hanya 2.
Soalan Ujian
Mari kita anggap bahawa pemain sedang menilai dengan betul sama ada hendak bermain DD/DDD. Mereka menuruskan untuk memainkannya dan mendapatkan rantai terakhir.
Adakah pemain itu sentiasa menang?
Tidak. Sebagai contoh, katakan kita mempunyai 5 rantai linear dengan 3 kotak setiap satu. Mendapat yang terakhir memberikan insentif 3 kotak yang cukup untuk membayar 3 DD setiap satu berharga 2 kotak dan mendapat 1 kotak. Ini bermakna rantaian pertama selesai secara keseluruhan dan 3 lagi permainan DD memberikan mata (3+2+2+2+0) : (0+1+1+1+3) = 9:6 untuk pemain yang tidak dapatkan rantai terakhir.
Adakah peraturan kami untuk bermain permainan akhir sempurna?
Tidak. Apabila pemain mempunyai banyak rantai yang disambungkan melalui kotak-0 dan kotak-1 maka beberapa daripadanya mungkin mempunyai bilangan kotak yang sama dan kemudian teori atau carian mungkin diperlukan untuk memilih yang optimum berdasarkan rantaian lain yang boleh diakses kemudian melalui penyiapan rantaian pertama.
Adakah ia akan memberi perbezaan kepada teori akhir permainan di atas jika pihak lawan memainkan Half-Hearted Handout secara tidak optimum?
Kedudukan
+---+---+ +---+ + | atau | | +---+---+ +---+---+
atau dicerminkan / diputarkan oleh peraturan kami seperti mana-mana rantai linear lain, hanya mempunyai 2 kotak. Rantaian ini memberi pemain seterusnya pilihan untuk mengambil rantai atau bermain DD supaya ia dianggap seperti rantai panjang yang dibuka yang mempunyai sekurang-kurangnya 3 kotak.
Peraturan Rantaian Panjang
Peraturan 6: Pemain pertama harus cuba menjadikan bilangan titik + bilangan rantai linear penjang genap dan pemain kedua harus cuba menjadikan nilai ini ganjil.
Justifikasi peraturan
Untuk memulakan, kami memperkenalkan beberapa pembolehubah dengan '#' bermaksud 'nombor':
nt = # bilangan pusingan (# kali pemain memainkan gerakan berbangkit) nd = # titik r = # lajur titik c = # baris titik nl = # baris nb = # kotak nc = # rantai panjang nz = # pusingan yang membuka rantai
Kita mulakan dengan memperoleh hubungan yang dikenali sebagai identiti Euler.
Seterusnya kita mengira bilangan pusingan keseluruhan permainan.
Formula Bilangan Pusingan:
nt = nd + (# daripada DD dalam rantai linear) + (# daripada DDD dalam gelung) ialah peraturan yang tepat tanpa anggaran.
Pengiraan nz iaitu giliran yang membuka rantai panjang pertama
Selepas rantai panjang pertama dibuka dalam permainan akhir, jika tiada DD dan tiada DD dimainkan, maka bilangan pusingan yang tinggal adalah sama dengan bilangan rantai panjang apabila setiap pemain melengkapkan satu rantai. Oleh itu, jika (# daripada DD) = (# daripada DDD) = 0 maka
nz {# pusingan yang membuka rantai panjang pertama dalam permainan akhir}
= nd + (# gelung) - (# rantai linear ppanjang)
Formula untuk nz juga sah jika DD/DDD dimainkan.
Justifikasi:
Mana-mana permainan DD/DDD tidak dapat mengubah apa yang telah berlaku sebelum ini, iaitu pusingan nz yang membawa kepada pembukaan rantai panjang pertama dalam permainan akhir. Bagi setiap DD dan DDD yang dimainkan, bilangan pusingan dalam permainan akhir meningkat sebanyak 1 (sila sahkan) jadi apabila menolak bilangan pusingan dalam permainan akhir daripada jumlah pusingan maka (# DD) dan (#DDD) akan setiap satu dibatalkan dan kami akan mendapat nilai yang sama untuk nz seolah-olah tiada DD/DDD dimainkan.
Jadi tiada pemain yang mahu melakukan langkah itu, iaitu pemain pertama tidak mahu nz menjadi ganjil dan oleh itu mahu nz menjadi genap. 2 x (# rantai linear panjang) ialah nombor genap jadi menambahkannya pada nz tidak berubah sama ada nz ganjil atau genap yang akhirnya menghasilkan
Peraturan Rantaian Panjang: Pemain pertama cuba membuat (#titik) + (# rantai linear panjang) walaupun semasa pemain kedua cuba menjadikannya ganjil.
Penyataan yang salah bagi Peraturan Rantaian Panjang
Dalam beberapa penerbitan mengenai permainan Titik, dua andaian yang tidak perlu dibuat untuk mendapatkan Peraturan Rantaian Panjang.
1. Andaian: Jika kedua-dua pemaina bermain permainan akhir secara optimum, maka sesiapa yang bermain gerakan terakhir menang kerana nilai tinggi rantai terakhir dan terbesar dan kerana tidak perlu bergerak lagi dan membuka rantai lain untuk pihak lawan.
Jadi pemain pertama mahu nt = (# pusingan) menjadi ganjil untuk dapat membuat gerakan pertama dan terakhir serta menang.
2. Andaian: Semua rantai panjang kecuali rantai terakhir dimainkan dengan DD/DDD. Oleh itu (# gelung) + (# DDD dalam gelung) adalah genap dan boleh diabaikan dan nt = nd + (#DD dalam rantai linear) menjadi nt = nd + (# rantai linear panjang) - 1. Olehitu pemain pertama mahu nt ini ganjil untuk dapat membuat langkah terakhir iaitu apabila (# titik) + (# rantai linear panjang) genap - Peraturan Rantaian Panjang.
Tetapi kita tahu bahawa 2 andaian ini tidak perlu untuk Peraturan Rantaian Panjang menjadi benar. Contoh seterusnya akan menunjukkan ini.
Kejayaan yang manakah dijamin oleh peraturan untuk seorang pemain?
Peraturan Rantaian Panjang memberikan syarat yang perlu dan mencukupi untuk memutuskan pemain mana yang pertama bermain dalam rantaian panjang yang pertama dibuka dalam permainan akhir. Pemain P ini boleh memilih sama ada untuk bermain DD/DDD atau tidak bermain DD/DDD. Kami ada 2 kes.
Jika rantai penjang pertama adalah linear maka ia mempunyai sekurang-kurangnya 3 kotak, dan bermain DD mempunyai kos 2 kotak.
Jika insentif untuk bermain DD ialah <2 maka pemain P tidak akan bermain DD dan mengambil keseluruhan rantai pertama dan pihak lawan akan mandapat paling banyak 1 kotak lagi daripada rantai yang tinggal, jadi P mendapat dalam permainan akhir sekurang-kurangnya 3 - 1 = 2 kotak lagi daripada pihak lawan.
Jika insentif adalah 2 maka tidak kira sama ada P bermain DD atau tidak bermain DD dalam rantaian panjang pertama dan oleh itu memperoleh >3 kotak lagi dalam permainan akhir.
Jika insentif ialah >2 maka P bermain DD dan mendapat >3 kotak lagi dalam permainan akhir.
Jika rantai panjang pertama ialah gelung maka dalam kes paling teruk, rantai pertama mempunyai 4 kotak dan insentif ialah 4 dan kemudian sama ada pemain bermain DDD atau tidak, kedua-dua pemain akan mendapat jumlah mata yang sama dalam permainan akhir. Tetapi jiak insentif adalah >4, maka bermain DDD akan memberikan lebih banyak mata dan jika insentif adalah <4 maka tidak bermain DDD akan memberikan lebih banyak mata kerana gelung mempunyai sekurang-kurangnya 3 kotak. Dan jika rantai panjang pertama ialah gelung dengan lebih daripada 4 kotak, maka P akan mendapat mata tambahan ini sebagai kelebihan dalam permainan akhir, walaupun insentifnya ialah 4.
Apakah perbezaan mata yang mungkin berlaku pada permulaan permainan akhir?
Jika bilangan rantai-1 genap dan bilangan linear rantai-2 genap maka perbezaan mata pada permulaan permainan akhir ialah sifar.
Jika bilangan rantai-1 genap dan bilangan linear rantai-2 ganjil maka mata pada permulaan permainan akhir ialah 2.
Jika bilangan rantai-1 adalah ganjil maka selepas melengkapkan semua rantai-1, perbezaan mata adalah 1. Kemudian setiap rantai-2 yang lengkap hanya akan membalik antara kedua-dua pemain yang mendahului dengan 1 kotak.
Jadi betapa pentingnya Peraturan Rantaian Panjang?
Bilakah Peraturan Rantaian Panjang tidak menentukan keputusannya?
Peraturan manakah yang harus dipatuhi seterusnya?
Contoh 7: Menguji peraturan dalam situasi luar biasa
Di papan ini, bilangan ganjil 5 x 3 = 15 pergerakan telah dibuat. Pindah 16 akan membuka rantai panjang pertama yang memenuhi formula yang kami peroleh: 16 = (# titik) - (# rantai panjang lenear) = 20 - 4. Sesiapa yang membuat langkah ini, dalam kes ini, pemain B akan kalah jika pemain A bermain DD dengan sewajarnya.
+ + + + + | | | | | + + + + + | | | | | + + + + + | | | | | + + + + +
Pemain A bermula dan pemain B perlu membuka rantai sekarang.
berapa mata jika tiga DD dimainkan?
Jika A bermain DD 3 kali maka mata akhir ialah A:B = 6:6.
+---+---+---+---+ | A | A | A | A | +---+---+---+---+ | B | B | B | A | +---+---+---+---+ | B | B | B | A | +---+---+---+---+
Mata daripada 3 rantaian terakhir ialah 5:4, jadi bermain DD dalam rantaian pertama dan membayar dengan 2 mata untuk mendapatkan satu mata adalah tidak optimum.
Berapakah mata jika dua DD dimainkan?
Adalah lebih baik untuk A mengambil keseluruhan rantaian pertama dan mendapat mata akhir A:B = 7:5.
+---+---+---+---+ | A | B | B | B | +---+---+---+---+ | A | A | A | B | +---+---+---+---+ | A | A | A | B | +---+---+---+---+
Andaian manakah tentang pernyataan yang salah bagi Peraturan Rantaian Panjang yang dilanggar?
Kedua-dua andaian telah dilangar. A menang tetapi tidak mendapat rantai terakhir. DD tidak dimainkan dalam setiap rantai linear yang panjang.
Adakah Peraturan Rantaian Panjang masih berlaku untuk permainan optimum ini?
Kami mendapat (# titik) + (# rantai linear panjang) = 20 + 4 = 24 iaitu genap dan pemain pertama menang seperti yang diramalkan oleh peraturan. Jadi peraturan itu lebih baik daripada pembuktian alternatif dengan andaian dan salah tafsir yang tidak perlu.
Soalan Ujian
Adakah permainan optimum memerlukan SAMA ADA bermain DD/DDD ATAU tidak bermain DD/DDD?
Tidak, kedua-duanya boleh menjadi sama baik. Dengan hanya dua rantai panjang dengan 3 kotak, A perlu bermain DD memberikan mata A:B = 4:2.
+ + + +---+---+ | | | | A | A | + + + +---+---+ | | | → | B | A | + + + +---+---+ | | | | B | A | + + + +---+---+
Jadi insentif untuk memainkan DD sebelum dua rantai ini ialah 4 - 2 = 2 yang sama dengan kos bermain DD. Oleh itu, kedua-dua permainan memberikan mata yang sama: 4:(2+0) = 4:5 = (2+2) : (4+1)
+---+---+---+ +---+---+---+ | B | A | A | | B | B | B | +---+---+---+ +---+---+---+ | B | B | A | = | A | A | B | +---+---+---+ +---+---+---+ | B | B | A | | A | A | B | +---+---+---+ +---+---+---+
Soalan Ujian
Bolehkah ia berlaku di bawah permainan optimum yang pemain berulang kali bermula dan berhenti bermain DD/DDD?
Ya. Kami melihat di atas bagaimana menambah rantai dengan 3 kotak mengubah mata daripada 4:2 kepada 4:(2+3) = 4:5. Insentif untuk memainkan DD sebelum 3 rantai ini ialah 5 - 4 = 1 < 2 jadi kurang daripada kos bermain DD iaitu 2. Olehitu, dengan empat rantai 3 kotak, yang pertama tidak akan bermain dengan DD. Jika terdapat satu lagi rantaian dengan 3 kotak mata akan menjadi (4+3):5 = 7:5 = (4+1):(5+2) jadi insentif untuk bermain kedua dalam 5 rantaian 3 kotak ialah 7-5=2 jadi bermain DD adalah ok memberikan dalam kedua-dua kes, mata (2+5):(1+7) = 7:8 = 7:(3+5).
+---+---+---+---+---+ +---+---+---+---+---+ | B | B | A | A | A | | B | B | A | B | B | +---+---+---+---+---+ +---+---+---+---+---+ | A | B | B | B | A | = | A | B | A | A | B | = +---+---+---+---+---+ +---+---+---+---+---+ | A | B | B | B | A | | A | B | A | A | B | +---+---+---+---+---+ +---+---+---+---+---+ +---+---+---+---+---+ +---+---+---+---+---+ | B | A | B | B | B | | B | A | B | A | A | +---+---+---+---+---+ +---+---+---+---+---+ | B | A | A | A | B | = | B | A | B | B | A | +---+---+---+---+---+ +---+---+---+---+---+ | B | A | A | A | B | | B | A | B | B | A | +---+---+---+---+---+ +---+---+---+---+---+
Dengan menambahkan lebih banyak rantai dengan 3 kotak, pemain boleh mempunyai lebih banyak perubahan antara gerakan dan tanpa-gerakan DD.
Adakah Peraturan Rantaian Panjang berpuas hati?
Pembaca digalakkan menyemak Peraturan Rantaian Panjang dengan lebih banyak contoh yang melibatkan gelung.
Contoh 8: Mengaplikasikan Peraturan Rantai Panjang
Pada halaman web ini oleh David Wilson, kedudukan berikut ditunjukkan yang hanya mempunyai satu pergerakan untuk pemain seterusnya menang.
+ + + +
|
+ + +---+
+---+---+---+
|
+ +---+ +
Siapa yang akan menang jika kedua-dua pemain mematuhi peraturan akhir permainan kami?
Papan ini mempunyai biangan titik genap dan bilangan rantai panjang genap. Rantaian panjang terakhir tidak akan mempunyai gerakan DD yang dimainkan jadi bilangan pergerakan DD ganjil biasanya akan dimainkan dandengan itu # mata + # DD adalah ganjil jadi bilangan lilitan adalah ganjil jadi pemain pertama akan mendapat rantai terakhir dan menang. Ini selaras dengan 'Peraturan Rantaian Panjang': 'Pemain pertama harus cuba membuat # titik + # rantaian panjang (linear) genap dan pemain kedua harus cuba menjadikannya ganjil.'
Apa yang pemain ke-2 boleh buat?
pemain ke-2 tidak boleh menukar bilangan titik sebaliknya bilangan pergerakan DD dengan mengorbankan 2 kotak dan memainkan gerakan yang ditandakan sebagai B yang merupakan satu-satunya gerakan yang menang yang dimiliki pemain ke-2 dalam situasi ini:
+ + + +
|
+ + +---+
+---+---+---+
| B
+ +---+ +Pergerakan ini mengurangkan bilangan rantai panjang dari 2 hingga 1 dan dengan itu menjadikan # titk + # rantai panjang (linear) ganjil dan dengan itu membolehkan pemain ke-2 menang dengan satu mata dan bukannya kalah satu mata.
Bagaimanakah permainan itu boleh diteruskan?
Vairasi berikut semuanya membawa kepada A:B = 4:5 jadi kepada kemenangan 1 mata untuk B.
+ +A10+B6-+
A3 | B9 A11
+ +A5-+---+
B4 A12
+---+---+---+
| | A2 B8
+A1-+---+A7-+
+A3-+A5-+B6-+
A11 | A12
+B9-+ +---+
A10 B4
+---+---+---+
| | A2 B8
+A1-+---+A7-+
+A3-+A10+B6-+
| B9 A11
+ +B4-+---+
A5 A12
+---+---+---+
| | A2 B8
+A1-+---+A7-+
Menbuat pergerakan ini melanggar Peraturan 1 yang pertama iaitu tidak mencipta 3 kotak jika tidak benar-benar perlu. Sejauh manakah pelanggaran Peraturan 1 itu?
Pelanggaran Peraturan 1 ini tidak kurang aneh daripada bermain DD. Seperti yang kita ketahui sebelum ini, adalah perkara biasa untuk bermain DD dan membayar harga 2 mata untuk menukar peranan. Jadfi pengorbabnan ini adalah minimum dan baik jika ia mempunyai kesan yang sama seperti gerakan DD.
Di bahagian atas halaman ini, istilah teknikal telah diperkenalkan dan peraturan telah dirumuskan. Permainan akhir diterangkan secara terperinci dan untuk bahagian pertama permainan Peraturan Rantaian Panjang memberi panduan. Jika anda ingin mengetahui lebih lanjut mengenai bahagian pertama permain, sila semak [2] dan [3] dalam Rujukan. Pepohon keputusan berikut meringkaskan halaman web ini.
Pepohon Keputusan
Untuk pautan di bawah berfungsi, pemain perlu membuka pilatan teks di atas dengan klik
- Sebelum memullakan permainan, fikirkan sama ada bermain pertama atau kedua. Lihat perkara 3.A.a di bawah.
- Jika terdapat sekurang-kurangnya satu kotak-3 (kotak yang boleh dilengkapkan), kemudian kenal pasti semua rantai yang dilekatkan pada semua kotak-3 ini.
- Jika salah satu daripada rantai ini adalah linear dan mempunyai sekurang-kurangnya 2 kotak berjiran, maka lengkapkan semua kotak dari semua rantai linear dan semua rantai gelung selain daripada dua kotak jiran rantai linear yang satu ini. Kemudian analisis sama ada hendak memainkan DD dan sama ada memainkan DD atau lengkapkan 2 kotak terakhir.
- Jika semua rantai mempunyai sama ada panjang 1 atau bergelung, maka lengkapkan semua rantai penjang 1 dan jika terdapat sekurang-kurangnya satu rantai gelung maka lengkapkan semua rantai gelung kecuali 4 kotak terakhir salah satu rantai gelung. Kemudian analisis sama ada hendak bermain DDD atau lengkapkan 4 kotak terakhir.
- Jika tiada kotak yang boleh disiapkan, maka
- Jika setiap gerakan akan mencipta kotak-3, maka
- jika rantai terpendek ialah 2 rantai
+---+---+ +---+---+
di mana 2 garisan yang tidak dilukis boleh berada di mana-mana tetapi tidak dalam kotak yang sama, kemudian bermain di tengah untuk mencapai:+---+---+ | +---+---+ - Jika tidak, tentukan rantai seterusnya untuk dibuka dan bermain di mana-mana sahaja dalam rantaian ini.
- jika rantai terpendek ialah 2 rantai
- jika ada gerakan yang tidak mencipta koatk-3 maka
- jika dalam permainan akan ada paling banyak 1 rantai panjang (linear atau gelung), contohnya, kerana segi empat tepat titik kecil atau nipis, maka tiada pergerakan DD / DDD akan dimainkan dan kemudian pamain yang mengambil giliran terakhir menang dan kerana Formula Bilangan Pusingan,pemain pertama harus cuba menjadikan jumlah # titik + # gelung ganjil dan pemain kedua genap. Kerana # titik adalah tetap, pemain hanya boleh mencuba untuk mendapatkan 0 masung-masing 1 gelung. Jika itu mustahil, tukar siapa yang bermain dahulu.
- jika jelas berapa banyak rantai linear yang akan wujub pada penghujung permainan dan jiak Peraturan Rantaian Panjang meramalkan kehilangan maka pertimbangkan untuk melakukan pengorbanan untuk mengurangkan bilangan rantai panjang, jika tidak
- jika tidak jelas berapa banyak rantai panjang yang akan ada pada penghujung permainan, maka sebagai pemain pertama cuba membuat # titik + # rantai panjang (linear) ganjil dan sebagai pemain kedua cuba membuat jumlah genap.
- Jika setiap gerakan akan mencipta kotak-3, maka
Rujukan
[1] Wikipedia: Dots and Boxes, lihat rujukan lain di sama.
[2] Berlekamp, Elwyn R.; Conway, John H.; Guy, Richard K. (1982), 'Chapter 16: Dots-and-Boxes', Winning Ways for your Mathematical Plays, Volume 2: Games in Particular, Academic Press, pp. 507–550.
[3] Berlekamp, Elwyn (2000), The Dots-and-Boxes Game: Sophisticated Child's Play, AK Peters, Ltd, ISBN 1-56881-129-2.
[4] Wilson, David, Dots-and-Boxes Analysis Results, University of Wisconsin
Indeks
Untuk pautan di bawah berfungsi, pemain perlu membuka lipatan teks di atas dengan klik
- # ...
- bilangan untuk ...
- Kotak
- segi empat kecil dengan 4 titik berjiran sebagai penjuru
- Kotak-?
- kotak-0, kotak-1, kotak-2, kotak-3, kotak-4 ialah kotak yang mempunyai 0, 1, 2, 3, 4 bahagiannya dilukis.
- Rantai
- susunan yang terdiri daripada kotak-2 yang disambungkan. Terdapat rantai linear dan rantai gelung.
- Pergerakan Silang Berganda
- gerakan yang melengkapkan dua kotak bersebelahan sekali gus. Ia dimainkan serta-merta selepas pergerakan Urusan Ganda dalam rantaian linear atau apabila gelung selesai.
- DD
- singkatan daripada Urusan Ganda (Double Dealing)
- DDD
- singkatan daripada Urusan berganda-ganda (Double Double Dealing)
- Urusan ganda
- gerakan di sempadan Half-Hearted Handout yang mambawa kepada
+---+---+ | | . +---+---+
- Urusan Berganda-ganda
- gerakan di tengah-tengah gelung yang dibuka dengan 4 kotak yang tinggal, mencipta, contohnya,
+---+---+ +---+---+---+---+ | | | | | +---+---+ atau +---+---+---+---+ atau | | +---+---+ +---+---+ +---+---+---+ | | | | | +---+---+---+ atau +---+---+ + | | | | +---+---+ +---+ - Permainan Akhir
- peringkat akhir permainan yang bermula apabila ia menjadi tidak dapat dielakkan untuk mencipta kotkak-3 dalam gerakan seterusnya
- Identiti Euler
- hubungan umum untuk mana-mana graf dalam satah, bukan sahaja permainan Titik, di mana garisan tidak bersilang: (# baris) - (# titik) + 2 = (# muka) di mana muka termasuk 'muka luaran' jadi bagi kita (# muka) = (# kotak) + 1.
- Graf
- konsep dalam matematik di mana beberapa titik disambungkan dengan beberapa baris
- Hard-Hearted Handout
- melukis garis tengah dalan
+---+---+ +---+---+ +---+---+ atau | atau | | +---+---+ +---+ + + + +atau diputar dan dicerminkan menghasilkan+---+---+ +---+---+ +---+---+ | atau | | atau | | | +---+---+ +---+ + + + +atau diputar dan dicerminkan - Half-Hearted Handout
- melukis garisan pada sempadan rantai dengan dua kotak menuju ke
+---+---+ +---+---+ | atau | | +---+---+ +---+ +
- Gariskan
- segmen garis yang memautkan dua titikl berjiran secara mendatar +---+ atau menegak
- Rantai linear
- rantai yang mempinyai 2 hujung, tidak semestinya lurus
- Peraturan Rantaian Panjang
- Pemain pertama harus cuba menjadikan # titik + # rantai panjang genap dan pemain kedua harus cuba menjadikan nilai ini ganjil.
- Rantai panjang
- rantai dengan ≥ 3 kotak
- Gerakan Gila
- gerakan yang memberi pihak lawan pilihan untuk berkorban
- Gelung
- singkatan untuk rantai gelung
- Rantai gelung
- rantai tanpa hujung
- Bergerak
- melukis garisan
- Formula Bilangan Pusingan
- suatu formula tepat memberikan bilangan pusingan dalam permainan yang merupakan asa bagi Peraturan Rantaian Panjang dan yang berguna untuk bilangan titk yang rendah untuk memutuskan sama ada menjadi pemain pertama atau tidak
- Membuka rantai
- membuat pergerakan di dalam rantai atau pada salah satu hujungnya (jika ia adalah rantai linear)
- Peraturan 1
- Permainan yang paling jelas ialah mengelak daripada mencipta kotak-3 yang boleh diambil oleh pihak lawan dengan melengkapkannya.
- Peraturan 2
- Untuk memesan rantai, ambil rantai linear terbesar untuk rantai terakhir dan jika tiada rantai linear maka ambil gelung terbesar.
- Peraturan 3
- Jika dalam permainan akhir semua kotak mempunyai sekurang-kurangnya 2 sisi yang dilukis kemudian untuk menyusuns emula rantai lain, susun mengikut (# kotak) - 2 (jika ia gelung).
- Peraturan 4
- Untuk mewujubkan susunan rantai yang diisih mengikut nilai untuk pemain seterusnya, nilai terendah dahulu, lakukan susunan pergerakan (lihat teks) ) seingga leseluruhan satah diselesaikan.
- Peraturan 5
- Gunakan kod pseudo yang disediakan (lihat teks ) untuk memutuskan sama ada mahu memainkan DD/DDD atau tudak.
- Peraturan 6
- Merujuk kepada Peraturan Rantaian Panjang
- Mnegambil kawalam
- sama seperti bermain DD/DDD yang, sebagai kesan sampingan yang penting, memberikan pilihan untuk mengulangi memainkan dd/ddd dalam rantaian seterusnya
- Pusingan
- susunan pergerakan berturut-turut seorang pemain
Ikuti atau langgan untuk kemas kini: