300000
Total number of wins: 33356
Точок
Якщо вас просто цікавить, які ходи грати, а не чому, перейдіть до «Дерева рішень» внизу. "Індекс" нижче перелічує всі терміни, які вводяться в тексті і можуть бути використані як короткий вступ.
основи
Термінологія: Давайте введемо деякі нові терміни, які ми будемо використовувати, щоб поговорити про гру.
box — невеликий квадрат з 4 сусідніми точками у вигляді кутів. Коробка може мати намальованих 0, 1, 2, 3, 4 її сторін і тоді називається 0-box, 1-box, 2-box, 3-box, 4-box.
A line — відрізок лінії, що зв'язує дві сусідні точки.
Малювання лінії також називається making a move.
Якщо не намальована лінія розділяє 2-коробку та 3-коробку, то малювання цієї лінії робить 3 речі: вона завершує 3-коробку і, таким чином, набирає очко, вона змінює 2-коробку на 3-коробку, що дає гравцеві ще один хід, який можна використовувати для завершення нової 3-коробки. Такий вид «ланцюгової реакції» трапляється дуже часто.
Всі з'єднані 2-коробки складають chain. Ланцюг може мати 2 кінці, а потім називається linear chain, незалежно від того, пряма це лінія чи ні, як
+ + +---+---+ + +---+
| | , або | |
+ + +---+---+ +---+ +
|
+---+---+, що показує ланцюги з 1, 2 і 4 коробками.
Ланцюг також не може мати кінців, і тоді ми називаємо його loopy chain або просто loop, незалежно від того, схожий він на коло чи ні, як цей
+---+---+---+
| |
+ +---+ +
| | |
+---+ + +
| |
+---+---+
Здійснення ходу всередині ланцюга або на одному з його кінців називається розривання ланцюга в математичній літературі про цю гру.
Що станеться, якщо ланцюг буде розірваним?
Якщо гравець малює одну з не намальованих ліній у ланцюгу, наприклад, переміщує A1 в
+---+---+---+
| |
+ +A1-+ +
| |
+---+---+, тоді принаймні одна 2-коробка стає 3-коробкою (тут коробка вище і коробка нижче A1 рухається), а інший гравець може завершити цю(ці) коробку(и) після цього в 4-коробку, заробити одне або два очки і одночасно перетворити сусідню 2-коробку в 3-коробку (тут коробка зліва від B1 і праворуч від B2) в
+---+---+---+
| B1 |
+ +A1-+ + .
| B2 |
+---+---+Щоразу, коли коробка заповнюється, гравець повинен зробити ще один хід, який можна використовувати для завершення наступноі коробки та всіх інших коробок ланцюга. Після завершення останньоі коробки гравець повинен зробити ще один хід в іншому місці, якщо всі коробки на дошці не будуть завершені.
Початкова гра
Правило 1: Найочевидніша гра полягає в тому, щоб уникнути створення 3-і коробки, яку суперник міг би взяти, завершивши її . Це просте і корисне правило, хоча воно не ідеальне, як ми побачимо в кінці цього сайту. На якомусь етапі, як тільки проводиться близько половини всіх ліній, створення 3-коробки стає неминучим. Що тоді відбувається? Оскільки ланцюги з 1, 2 або ≥ 3 коробками розглядаються по-різному, ми повинні дивитися на них окремо.
Почнемо з того, що розглянемо ланцюги, що мають тільки одну коробку.
Чи потрібно завжди завершувати одну 3-коробку, тобто ланцюг з однією коробкою.
+---+
| ?
+---+
Так, треба робити завжди. Незалежно від того, чи бере хтось коробку, а потім робить хід А, чи не бере коробку і грає на А, це не впливає на те, що робить суперник, за винятком того, що або ви, або суперник отримуєте коробку, тому краще, щоб ви отримали коробку.
Як можуть виглядати ланцюги з двома коробками і як в них потрібно грати?
Ланцюги з двома коробками виглядають як
+---+---+ +---+---+ +---+---+
або | або | |
+---+---+ +---+ + + + +або їх обернені і дзеркальні варіанти. Креслення там середньої лінії веде до
+---+---+ +---+---+ +---+---+
| або | | або | | |
+---+---+ +---+ + + + +і називається в літературі Hard-Hearted Handout .
Чи завжди потрібно брати обидві коробки в такому положенні?
Так, слід брати обидві коробки так само як завжди слід брати 1-коробкові ланцюги. Будь ласка, переконайте себе.
Проведення лінії на кордоні ланцюга з 2 коробок (одного з трьох ланцюгів з 2 коробок, показаних вище) веде до
+---+---+ +---+---+ | або | | +---+---+ +---+ +
і називається Half-Hearted Handout.
Хід на кордоні вищевказаних позицій призводить до
+---+---+ | | . +---+---+
Такий хід в літературі називається Double Dealing (DD). Щоб уточнити, існує чітка різниця між наступними двома ходами:
+---+---+ +---+---+ 1) to | +---+---+ +---+---+
і
+---+---+---+ +---+---+---+ 2) | to | | +---+---+---+ +---+---+---+
, хоча обидва отримані ланцюжки з 2 коробок виглядають однаково. Велика різниця полягає в тому, що хід на 2) завершує коробку і, таким чином, дозволяє гравцеві знову переміститися і зіграти в DD, тоді як під 1) жодна коробка не завершена, і тому гравець не може грати в DD відразу після цього. У той час як хід 2) є звичайним ходом, хід 1) називається Half-Hearted Handout.
Малювання лінії посередині, яка завершує обидві клітинки, називається подвійним перехрещенням. Таким ходом завжди завершується петля, але в лінійному ланцюжку це може статися лише тоді, коли суперник виконує хід DD, щоб взяти контроль, як описано нижче. Після ходу ДД гравцем А, наступний гравець Б не має іншого вибору, як зіграти в середині Подвійний перехресний хід. Хоча цей хід дасть B 2 коробки, вартість буде вищою, якщо B буде грати в довшому ланцюжку, який повністю перейде до A. У такій ситуації гравець Б, який робить хід з подвійним хрестом, обманюється, тобто «подвійний хрест», тому і назва цього ходу.
Чи повинен наступний гравець після DD завжди брати обидві коробки?
Хід DD - це жертва двох коробок, тому що гравець може альтернативно спочатку зіграти всередині Hard-Hearted Handout, а потім на кордоні і заробити таким чином дві коробки.Чому комусь хотілося б пожертвувати 2 коробками? Продовжуйте читати, щоб дізнатися!
Хід на кшталт ходу Half-Hearted Handout перед DD, який давав опоненту можливість зробити жертву, в літературі називається безглуздим ходом. Цього безглуздого ходу можна і потрібно уникати. Інші безглузді рухи, такі як відкриття ланцюжка з 3 або більше коробками, можуть бути неминучими.
Повертаючись до «Половинчастих роздаткових матеріалів», чи завжди потрібно брати обидві коробки в такому положенні? Якщо ні, то коли варто грати в ДД на кордоні ланцюжка 2-х боксів? Спробуйте обидва варіанти в іграх і подивіться, яка різниця.
Розглянемо всі відмінності. Якщо взяти одну коробку з 2-х коробкового ланцюжка, то слід взяти другу коробку, як ми знайшли раніше. Якщо взяти обидва бокси, то отримує 2 очки, але потім доводиться робити хід в іншому місці. Це може коштувати дорого, тому що може знадобитися відкрити ланцюжок з безліччю коробок, що дозволить супернику взяти більше клітинок. Якщо хтось грає на межі, він не завершує клітинку і, отже, не потрібно грати десь ще. Але гра на кордоні дає наступному гравцеві обидва бокси, про які щойно йшлося. Тому можливі обидві п'єси. До цього питання ми повернемося пізніше, щоб визначити, який хід кращий в тій чи іншій ситуації.
Якщо гравцеві потрібно відкрити ланцюг з 2-ма коробками, тому що всі інші ходи будуть більш дорожчими, чи варто йому грати в Hard-Hearted , а чи в Half-Hearted Handout?
Якщо гравець грає посередині ланцюга (Hard-Hearted Handout), то інша сторона буде змушена взяти обидві коробки, а потім зробити потенційно дорогий хід де-небудь ще:
+---+---+ +---+---+ +---+---+
→ | → | | | плюс де-небудь ще.
+---+---+ +---+---+ +---+---+
Якщо хтось грає на кордоні ланцюга (Half-Hearted Handout), то він дає супернику можливість або взяти дві коробки, як було вище, або зіграти на кордоні (хід Double Dealing (DD):
+---+---+ +---+---+ +---+---+
→ | → | |
+---+---+ +---+---+ +---+---+
Цей варіант гри в ДД може виявитися дуже цінним, як ми дізнаємося пізніше. Надання супернику додаткових можливостей ніколи не може бути кращим ходом, тому, прагнучи до оптимальної гри, ніколи не слід грати в Half-Hearted Handout при активації ланцюжка з 2 коробок. У неоптимальній веселій грі можна спробувати рухи половинчасто, щоб з'ясувати майстерність суперника, або заплутати суперника, якщо один знаходиться позаду (але не якщо хтось намагається грати оптимально).
Що необхідно робити з розкритими лінійними ланцюгами з трьох і більше коробок?
Якщо ланцюг розкритий, то він має принаймні одну 3-коробку. Можна було б завершити цю коробку, і інші коробки, але чи варто це робити?
Чи є коробки, які обов'язково слід брати з лінійного розірваного ланцюга?
З одного боку, ми хочемо взяти якомога більше коробок. З іншого боку, ми, можливо, не захочемо платити ціну за гру в іншому місці після цього і тим самим відкрити ще більший ланцюжок для суперника. Що ми обов'язково повинні зробити, так це взяти всі коробки, крім двох, як це було виправдано раніше, вони безкоштовні, немає негативного побічного ефекту. Після цього ми можемо подумати про те, щоб взяти 2 бокси, що залишилися, або зіграти в DD (Double Dealing). Про це ми поговоримо нижче.
Ланцюги з ≥ 3 коробками називаються long chains.. До них відносяться як лінійні, так і петлеподібні ланцюги.
Чому існує особлива назва для таких ланцюгів?
Якщо залишилися тільки довгі ланцюги, що мають хоча б 3 коробки , то відкриття однієі з них, незважаючи як ви це зробите, означало б, що хоча б з одного боку ходу є не менше 2 сусідніх коробок .Таким чином, інший гравець може грати в Double Dealing, що має вирішальне значення для визначення решти гри.
Скільки коробок потрібно для виготовлення петлі?
Найменша петля має 4 коробки.
+---+---+ | | + + + | | +---+---+
Якщо петля є розірваною, чи можна не задумуючись безпечно взяти всі коробки, крім 2-ох ?
Давайте спробуємо це зробити. Найменший можливий відкритий цикл - це
+---+---+ | | +---+ + | | +---+---+
Звичайно, ми могли б взяти всі 4 коробки, а потім грати в іншому місці, але що, якщо ми хочемо уникнути гри в іншому місці за будь-яку ціну? Якщо ми візьмемо дві коробки, ми досягнемо
+---+---+ | | | +---+---+ | | +---+---+
, але нам потрібно буде зробити ще один хід. Отже, ми не могли зупинитися на цьому, тому що всі лінії на кордоні вже намальовані, тому ми повинні продовжувати добиратися до
+---+---+ | | | +---+---+ | | | +---+---+
, а потім ми зобов'язані зробити хід в іншому місці, що, можливо, могло б передати супернику ще більший ланцюг.
Що ще ми могли б зробити замість цього?
Ми хочемо зіграти хід, який не завершує коробку, щоб уникнути необхідності грати в іншому місці. Єдиний можливий хід - грати в середині розірваноі петлі, щоб створити
+---+---+ | | +---+---+ . | | +---+---+
Цей хід не завершує коробку, aле надає іншому гравцеві можливість зробити наступний хід . Ми назвемо цей хід Double Double Dealing (DDD). Ціна полягає в тому, що небхідна буде пожертвувати 4 -ма коробками, замість 2 -ох. Для суперника найкраще взяти 4 коробки і зіграти в іншому місці після цього.
Що робити, якщо розірвана петля має більше , ніж 4 коробки?
Ми можемо взяти скільки завгодно коробок, поки ми все ще можемо грати хід після цього, який не завершує квадрат. Це означає, що ми можемо взяти всі, крім 4 коробок, наприклад, відкривши
+---+---+---+---+ +---+---+---+---+ | | | | | + +---+---+ + дає, наприклад, + +---+---+ + | | | | +---+---+---+---+ +---+---+---+---+
і взявши 8 − 4 = 4 коробки, наприклад,
+---+---+---+---+ | | | | | + +---+---+---+ . | | | +---+---+---+---+
Тепер нам доведеться вирішити, чи брати решту 4 коробок, чи пожертвувати ними супернику, граючи
+---+---+---+---+ | | | | | + +---+---+---+ . | | | | +---+---+---+---+
. Детальніше про це пізніше.
У випадку одного розірваного ланцюга або малоймовірного випадку розривання декількох ланцюгів, скільки коробок можна безпечно взяти, не замислюючись про те, чи грати в DD , чи не грати в DD?Якщо є відкриті лінійні та/або відкриті петльові ланцюги, то завершіть усі коробки всіх цих ланцюгів, крім 2 сусідніх коробок одного відкритого лінійного ланцюга, або, якщо відкритого лінійного ланцюга немає, то за винятком 4 коробок одного з відкритих петлеподібних ланцюгів. Після того, як ці коробки будуть завершені, можна починати думати про те, грати в DD/DDD чи ні.
Ми дізналися, що гра починається з більш-менш випадкових ходів, за винятком того, що обидва гравці уникають створення 3-боксів якомога довше, тобто вони уникають відкриття ланцюжків. Коли це стає неминучим, ми сприймаємо це як початок endgame.. Ми починаємо пояснювати ендшпіль, тому що це найлегша частина всіх ігор.
Ендшпіль
Як і у всіх інших іграх, чим ближче до кінця, тим легше стає передбачити, хто і на скільки переможе при оптимальній грі. Тому ми починаємо наш аналіз з кінця гри. В ендшпілі всі ходи або розірваними ланцюгами, або повними коробками, або є ходами DD/DDD. Коли гравцеві доводиться розривати ланцюг, то першою стратегією може бути розривання найменшого з доступних ланцюгів, щоб дати супернику найменшу кількість коробок. Давайте спробуємо це на кількох прикладах.
Приклад 1.
Припустимо, що всі коробки є завершеними, крім двох ланцюгів з 3 і 4 коробками:
+ +---+---+ | | | | + +---+---+ | +---+---+---+ +---+---+---+
Гравець А, який ходить наступним, відкриє коротший ланцюжок (з будь-яким ходом, наприклад А1) для іншого гравця Б, щоб отримати цей ланцюг і отримав 3 очки, а А щоб отримати більший ланцюжок з коробками, а потім з рахунком з цих двох ланцюжків А:В=(0+4):(3+0)=4:3.
+A9-+---+---+ | | | | +A8-+---+---+ | B5 A6 A7 +---+---+---+ B2 A1 B3 B4 +---+---+---+
До речі, хід А1 - це те, що ми раніше визначили як безглуздий хід, хід, який дає супернику можливість зробити жертву. Тут цього не уникнути.
І ось що відбувається на наступній схемі. Гравець Б бере тільки одну коробку з ходом В2 (на наступній діаграмі), потім грає в подвійну роздачу з В3. Потім А потрібно взяти 2 коробки з А4, змушує відкрити великий ланцюжок деяким ходом, наприклад А5, а Б отримує решту 4 коробки з кінцевим рахунком А:В = (2+0):(1+4)=2:5.
+B9-+---+---+ | | | | +B8-+---+---+ | A5 B6 B7 +---+---+---+ B2 A1 A4 B3 +---+---+---+Ми бачимо, що в цій ситуації В вигідно пожертвувати двома коробками.
Приклад 2.
Припустимо, що всі коробки є завершеними, крім одного ланцюга з 3 коробками і однієї петлі з 4 коробками.
+---+---+---+ | | | + + +---+ | | | +---+---+---+ +---+---+---+Гравець А рухається далі.
Випадок 1: А відкриває ланцюг з 3 коробками.
Якщо після A1 гравець бере весь ланцюг, гравець A отримує петлю і рахунок з цих двох ланцюгів дорівнює A:В= (0+4):(3+0) = 4:3.
+---+---+---+ | A7 | | +A6-+A8-+---+ | B5 | | +---+---+---+ B2 A1 B3 B4 +---+---+---+
Якщо після A1 гравець В грає в DD, то після
+---+---+---+ | B7 | | +B6-+B8-+---+ | A5 | | +---+---+---+ B2 A1 A4 B3 +---+---+---+рахунок з цих двох ланцюгів A:В = (2+0):(1+4) = 2:5, тому також тут вигідно для В грати в DD і досягати A:Б = 2:5.
Випадок 2: А розриває петлю з 4 коробками.
Якщо після А1 гравець Б бере весь цикл, гравець А отримує коротший ланцюжок, і рахунок цих двох ланцюжків такий: А:В = (0+3):(4+0) = 3:4.
+---+---+---+ | B3 | | +B2-+B4-+---+ | A1 | | +---+---+---+ B5 A6 A7 A8 +---+---+---+
Якщо після A1 гравець B грає в DDD з B2, ми отримуємо
+---+---+---+ | B2 | | +A3-+A4-+---+ | A1 | | +---+---+---+ B6 A5 B7 B8 +---+---+---+і рахунок з цих двох ланцюжків A:B = (4+0):(0+3) = 4:3. У цьому випадку краще, щоб B НЕ грав у DDD і таким чином отримав A:B = 3:4. Якщо А спочатку грає в коротшому лінійному ланцюжку, то А може виконати лише A:B = 2:5. Тоді як коли A відкриває більший цикл першим, A може досягти кращого результату A:B = 3:4.
Чим це пояснюється?
Якщо A потрібно відкрити довгий ланцюг (з >2 коробками), то гравець B матиме можливість зіграти в DD/DDD в кінці отримання коробок цього ланцюга і, таким чином, отримати наступний ланцюжок, і знову грати DD/DDD в цьому ланцюжку і так до кінця гри. Ми називаємо це «контролем», оскільки гравець А ніколи не матиме можливості грати в DD/DDD, якщо гравець B цього не хоче. Що може зробити гравець А, так це зробити ціну DD/DDD високою. Якщо А відкриває лінійний ланцюг, то ціна за те, що Б візьме ДД, становить жертву 2 ящиків. Якщо А відкриває петльовий ланцюжок, то ціна для Б для гри в DDD становить 4 камені. Звідси видно, що при сортуванні ланцюгів за значенням значення слід виправляти, віднімаючи 2 квадрати для лінійних ланцюгів і віднімаючи 4 коробки для петлястих ланцюгів.
Приклад 3.
У цьому прикладі ми хочемо дізнатися більше про те, в якому порядку повинні розриватися ланцюги. Припустимо, що всі коробки завершені, за винятком двох лінійних ланцюгів з 3 і 4 коробками і однієї петлі з 4 коробками, як тут:
+---+---+ +---+
| | |
+ + +---+ +
| | | |
+---+---+---+ +
|
+---+---+ +---+Гравець А рухається далі. Зрозуміло, що А не розірве більший лінійний ланцюг з 4 коробками, якщо є лінійний ланцюг з 3 коробками.
Випадок 1: А розриває ланцюг з 3 коробками.
Перш ніж прийняти рішення про оптимальну гру для гравця В, давайте перевіримо, який з інших 2 ланцюгів слід розірвати першим:
+---+---+ +---+ | | | + + +---+ + | | | | +---+---+---+ + | | | | +---+---+---+---+
Нехай гравці будуть С і D, а С рухаються далі.
Випадок 1.1: В розриває петлю
+---+---+ +---+
| | |
+ + +---+ +
| C1 | | |
+---+---+---+ +
| | | |
+---+---+---+---+ Якщо після C1 гравець D грає в DDD з D2, то після
+---+---+C5-+---+ | D2 | D6 | +C3-+C4-+---+D7-+ | C1 | | | +---+---+---+D8-+ | | | | D9 +---+---+---+---+
рахунок з цих двох ланцюгів дорівнює C:D = (4+0):(0+4) = 4:4. Якщо D не грає в DDD, але бере петлю, то після
+---+---+D5-+---+ | D3 | C6 | +D2-+D4-+---+C7-+ | C1 | | | +---+---+---+C8-+ | | | | C9 +---+---+---+---+
рахунок з цих двох ланцюгів є C:D = (0+4):(4+0) = 4:4.
Випадок 1.2: C розриває ланцюг 4 коробок
+---+---+C1-+---+
| | |
+ + +---+ +
| | | |
+---+---+---+ +
| | | |
+---+---+---+---+ Якщо після C1 гравець D бере весь ланцюг, то після
+---+---+C1-+---+ | C8 | D2 | +C7-+C9-+---+D3-+ | D6 | | | +---+---+---+D4-+ | | | | D5 +---+---+---+---+
рахунок дорівнює C:D = (0+4):(4+0) = 4:4. Якщо після C1 гравець D грає DD з D4, то після
+---+---+C1-+---+ | D8 | D2 | +D7-+D9-+---+D3-+ | C6 | | | +---+---+---+C5-+ | | | | D4 +---+---+---+---+рахунок є C:D = (2+0):(2+4) = 2:6. Найкраще, що D може застосувати після C1, - це C:D = 2:6.
Що ми дізнаємося з двох випадків?
Гравцеві, який грає далі (C), найкраще розірвати петлю, досягнувши C:D = 4:4, а не лінійний ланцюг, що дасть лише C:D = 2:6. Якби ми сортували ланцюги за розміром − 2, щоб вирішити, які розривати першими, тоді (4−2) = 2 < 4 дали б правильний результат. Тепер ми можемо визначитися з оптимальною грою для B в:
+---+---+- +---+
| | |
+ + +---+ +
| | | |
+---+---+---+ +
A1 |
+---+---+ +---+
Чи варто B брати ланцюг, а чи краще грати в DD?
Якщо B бере ланцюг, то після
+---+---+A9-+---+ | A7 | B10 | +A6-+A8-+---+B11+ | B5 | | | +---+---+---+B12+ B2 A1 B3 | B13 +---+---+B4-+---+
рахунок на цих 3 ланцюгах дорівнює A:B = (0+4+0):(3+0+4) = 4:7. Якщо B грає замість DD з B3, то після
+---+---+B9-+---+ | B7 | B10 | +B6-+B8-+---+B11+ | A5 | | | +---+---+---+B12+ B2 A1 A4 | B13 +---+---+B3-+---+
рахунок на цих 3 ланцюгах дорівнює A:B = (2+0+4):(1+4+0) = 6:5. Отже, найкраще, чого B може досягти після A1 - це A:B = 4:7, якщо B не буде грати DDD. В обох випадках ми використовували раніш зроблений висновок, що петлю треба розірвати наступним кроком.
Випадок 2: A розриває петлю з 4 коробками:
+---+---+ +---+
| | |
+ + +---+ +
| A1 | | |
+---+---+---+ +
|
+---+---+ +---+
Випадок 2.1: B бере всю петлю.
Зрозуміло, що малий ланцюг слід грати з DD, що веде до
+---+---+B9-+---+ | B3 | A10 | +B2-+B4-+---+A11+ | A1 | | | +---+---+---+A12+ B5 A6 B8 | A13 +---+---+A7-+---+, даючи paхунок на цих 3 ланцюгах A:B = (0+1+4):(4+2+0) = 5:6.
Випадок 2.2: В жертвує петлею.
Знову ж таки, маленький ланцюг слід грати з DD, що веде до
+---+---+A9-+---+ | B2 | B10 | +A3-+A4-+---+B11+ | A1 | | | +---+---+---+B12+ A5 B6 A8 | B13 +---+---+B7-+---+, даючи рахунок на цих 3 ланцюгах A:B = (4+2+0):(0+1+4) = 6:5.
Що ми дізнаємося з випадків 2.1 і 2.2?
Через високу ціну гри DDD в петлі , найкращим в цьому випадку для B буде взяти всю петлю, досягнувши цим рахунку A:B = 5:6.
Що ми дізнаємося з випадків 1 і 2?
У нас є два лінійних ланцюга з 3 і 4 коробками і петля з 4 коробками. Найкраще, щоб А розімкнув петлю і досяг результату A:B = 5:6. Якщо А відкриває ланцюжок з 3 коробками, то він досягає тільки А:В = 4:7. Зрозуміло, що не може бути краще, щоб Б відкривав ланцюг з 4 коробками перед ланцюжком з 3 коробками. Тому сортувати ланцюжки просто за розміром, щоб визначити, які відкривати наступними, не виходить. Але сортування їх за розміром − 2 для лінійних ланцюгів і розмір -4 для петлястих ланцюгів, здається, працює, тому що (4−4) = 0 < 1 = 3 − 2 indicating that the loop should be opened first.
Порядок, в якому розриваються ланцюги
З досвідом, отриманим з наведених вище прикладів, ми зараз вирішуємо проблему визначення порядку, в якому ланцюги будуть розірвані і завершені. Цей порядок ланцюгів буде використовуватися нижче, щоб визначити, коли один з гравців буде грати в DD / DDD, хто виграє гру і на скільки. Добра новина полягає в тому, що в ендшпілі ця послідовність розривання ланцюгів залежить не від того, чия це черга або хто грав у DD/DDD раніше.Причинoю є те, що в будь-який момент гри значення мають тільки лінії, які були накреслені, а не ким вони були накреслені і не в якому порядку. Навіть рахунок в цей момент не впливає на майбутню оптимальну гру. Розбиття складної проблеми на більш легкі проблеми - це вже успіх. У цьому випадку складним завданням було визначення того, хто робить який крок в ендшпілі, і яке було розділено на дві проблеми: проблема порядку, в якому потрібно розривати ланцюги , і проблема того, хто і коли грає в DD/DDD. Перш ніж ми почнемо, потрібно подумати про загальну тенденцію в ендшпілі.
Чи «вартість» розірваних ланцюгів зменшується до кінця гри , чи вона збільшується?
Відкритий ланцюжок віддається супернику. Тому ланцюжок повинен мати найменше можливе «значення», де value — це, на перший погляд, кількість коробок. Таким чином, протягом ендшпілю «вартість» відкритих ланцюгів може тільки зростати або залишатися незмінною, але не знижуватися. У нашому прикладі вище ми побачили, що відкрити ланцюжок з найменшою кількістю коробок, які може взяти суперник, не виходить. Але ми хочемо відсортувати ланцюжки за певною «вартістю», тому що кожен гравець хоче відкрити найменш цінний ланцюжок для суперника. Для опонента цінність ланцюжка складається не тільки з кількості ящиків; також має значення, чи підходить відкритий ланцюжок для відтворення в ньому DD/DDD. Хорошим кандидатом для такого коригування придатності для ДД є віднімання 2 з числа коробок, якщо ланцюжок є петлею. Це еквівалентно віднімання 2 з лінійних ланцюгів і 4 з петлястих ланцюгів. Отже, щоб відсортувати ланцюжки за 'value', де ми беремо 'value' = # коробок, якщо ланцюг НЕ є циклом, і беремо 'value' = # коробок − 2, якщо ланцюг IS циклом.
Починаємо з положень дошки, де в кожній коробці накреслено не менше 2 сторін. Для цього ми можемо сформулювати два правила, які впорядковують усі ланцюги.
Правило 2: Щоб замовити ланцюги, візьміть для останнього ланцюга найбільший лінійний ланцюг, а якщо лінійного ланцюга немає, то візьміть найбільшу петлю.
Обґрунтування правила 2
Гравець, який контролює гру, не розриває ланцюги і тому не сортує ланцюги. Таким чином, будь-який гравець, який сортує ланцюги, хоче зробити взяття або утримання контролю (тобто відтворення ходів DD/DDD) для суперника максимально дорогим. Переміщення DD коштує 2 коробки, а переміщення DDD коштує 4 коробки. Цю ціну потрібно заплатити за всі ланцюги, окрім останнього. Тому, щоб максимально збільшити загальні витрати для суперника, при сортуванні ланцюгів останній ланцюг по можливості повинен бути лінійним, а не петлею. ∎
Правило 3: Якщо в ендшпілі у всіх коробках накреслено не менше 2 сторін, то, щоб упорядкувати всі інші ланцюги, відсортуйте їх за (кількістю коробок − 2, якщо це є петля).
Обґрунтування правила 3
Спочатку слід відкривати ланцюжки в 1 коробку, потім ланцюги в 2 коробки, а потім довгі ланцюги. Віднімаючи 2 коробки з усіх лінійних ланцюгів, ланцюг з 1 коробки матиме значення 1−2 = −1, а ланцюг з 2 коробок — значення 2−2 = 0. Ці значення менші, ніж значення довгих ланцюгів, тому правило віднімання 2 коробок дає правильний результат сортування і для коротких ланцюгів.
Для того, щоб наступний гравець взяв або зберіг контроль, значенням ланцюга є кількість його коробок − 2, якщо це лінійний ланцюг, і − 4, якщо це петля. Для сортування ланцюжків можна отримати той самий результат, якщо відняти лише 2 у випадку циклу.
Що робити, якщо суперник не контролює ситуацію і не візьме контроль у наступний хід? Хіба опонент не виграє, коли, виходячи з цього порядку, опонент повинен рухатися далі у відкритому циклі з двома більшими коробками, ніж отримуючи лінійний ланцюг з тією ж «вартістю», але меншою кількістю коробок? Ні! Якщо суперник завершує весь цикл, то згодом, коли настане черга цього гравця, буде на одну петлю менше, і взяти контроль буде на 2 бокси дешевше. ∎
Ми бачили цей ефект у прикладі 3, випадку 2.1, де після того, як гравець А відкриває петлю з А1, гравець Б бере всю петлю, але, як наслідок, для А потім стало доступно взяти під контроль А7 і отримати найкращий можливий результат.
Вищенаведені правила зрозумілі, якщо всі коробки належать ланцюгу, тобто якщо у всіх коробок накреслено не менше 2 сторін. Але що робити, якщо є 0- і 1-коробка?
До яких ланцюгів належать ці коробки?
Правило 4: Щоб встановити послідовність ланцюгів, відсортованих за вартістю, виконайте наступний цикл ходів, поки вся дошка не буде завершена.
- Розірвіть один із ланцюгів, для якого вартість (кількість коробок, або якщо це петля, кількість коробок −2) є мінімальною, але за одним винятком: Якщо є хоча б одна петля, з'єднана або роз'єднана, і якщо є тільки один роз'єднаний лінійний ланцюг, і якщо немає з'єднаного дерева одних лінійних ланцюгів, то не розривайте останній роз'єднаний лінійний ланцюг.
- Завершіть розірваний ланцюг не рахуючи коробок. Креслення ліній на кінці лінійного ланцюга може змінити 1-коробку на 2-коробку і, таким чином, або об'єднати два лінійних ланцюга, або відрізати петлю.
Якщо в ендшпілі ще є 0-коробки і 1-коробки, то можна думати про таку коробку як про точку і думати про ланцюги як про лінії, які закінчуються в таких точках або закінчуються на краю дошки, а потім отримують штучну додаткову точку.
Точки разом з їхніми сполучними лініями в математиці називаються graph.
Виняток у правилі 4, сформульованому мовою ‘graph’, був би таким: Не розривайте лінійний ланцюг, що відповідає лінії, від'єднаній від решти графа, якщо graph, що залишився, має роз'єднану частину, яка містить петлю і не має роз'єднаної частини, яка не містить петлі (і тому називається "деревом" на мові graph).
Приклад 4: Graph, подібний до 'T'
На 1-коробці написано "T":
+---+---+---+ + | T | | + + + + + | | | | + + +---+---+ | | | + +---+---+ +
Graph, що відповідає цій дошці, буде схожий на T з 4 точками, той, де − і | в Т зустрічають і 3 tочки на 3-х кінцях Т.
Зліва від 1-коробки знаходиться одна з двох найкоротших ланцюжків. Відкривши його і завершивши
+---+---+---+ + +---+---+---+ + | | | | | | | + + + + + +---+ + + + | | | | | | | | +---+ +---+---+ +---+ +---+---+ | | | | | | + +---+---+ + +---+---+---+ +
, можна побачити, що дошка буде завершена, завершивши 2 ланцюжки, один з 3 і один з 9 коробками.
Приклад 5: Graph, подібний до "P"
На 1-коробці написано "P":
+---+---+---+---+ | | + +---+---+ + | P | + +---+---+---+ | | +---+---+---+ +
Креслення сторони над 1-коробкою або праворуч від цієї коробки створило б і відкрило б один великий лінійний ланцюг з 12 коробками
+---+---+---+---+ | | +---+---+---+ + | | + +---+---+---+ | | +---+---+---+ +
, які не хотілося б віддавати супернику. Креслення лінії під 1-коробкою, розділить дошку на розірваний лінійний ланцюг з 4 коробками і на петлю з 8 коробками.
+--+--+--+--+ | | + +--+--+ + | | +--+--+--+--+ | | +--+--+--+ +
У правилі 4 вище був сформульований виняток. Приклад 6 ілюструє цей виняток.
Приклад 6: Graph "P" плюс роз'єднаний лінійний ланцюг
Два лінійних ланцюги можуть бути розірваними , один справа і один внизу.
+---+---+---+---+ + | P | | + + +---+ + + | | | | + +---+---+---+ + | | | +---+---+---+ + +
Ситуація 1. Відкриття найкоротшого ланцюга напочатку
Було зроблено 21 хід, тому, якщо гравець А стартував, гравець В рухається далі.
Якщо після відкриття найменшого ланцюга з B1 гравець A відразу візьме під контроль, ми отримаємо
+---+---+---+---+B1-+ | B5 B12 | | +A6-+ +---+ +A2-+ | | | | +A7-+---+---+---+B4-+ | A8 A9 B11 | | +---+---+---+A10+A3-+
і рахунок A:B = (1+4+6):(2+2+0) = 11:4, де (2+2+0) означає, що гравець B отримає з 3 відкритих ланцюгів у цьому порядку 2, 2 та 0 коробок. Оскільки B може розірвати лише 2-й лінійний ланцюг з B5, гравець A може залишатися під контролем з A10 з вартістю всього 2 і отримати петлю безкоштовно.
Ситуація 2. Розривання довшого лінійного ланцюга першим
Після того, як B розірве довший ланцюг з B1 внизу і цей ланцюг буде завершений, той, хто отримає останній квадрат(и), повинен розірвати ланцюг. Згідно з нашим Правилом 2 , гравець B розриває петлю поруч із B8, щоб зробити взяття/утримання контролю дорогим. Ця стратегія працює, тому що взяття/утримання контролю в петлі не має сенсу для гравця А, оскільки це коштує 4 коробки, але виграє лише 3 коробки в останньому ланцюгу.
+---+---+---+---+A14+ | B1 A13 B8 | | +A2-+A12+---+A9-+B15+ | | A11 A10 | | +A3-+---+---+---+B16+ | A4 A5 B7 | | +---+---+---+A6-+B17+
Рахунок є A:B = (4+6+0):(2+0+3) = 10:5
Якби A не грав DD у першому ланцюгу:
+---+---+---+---+B14+ | B1 B13 A8 | | +A2-+B12+---+B9-+A15+ | | B11 B10 | | +A3-+---+---+---+A16+ | A4 A5 A6 | | +---+---+---+A7-+A17+
тоді рахунок A:B = (6+0+3):(0+6+0) = 9:6 був би гіршим для A. Причина в тому, що гра в петлю після її розірвання (В9 вище) коштує 6-3=3 очки, а взяття контролю в першому довгому ланцюгу коштує всього 2 очки, тому варто взяти під контроль в першому ланцюгу. 10:5 краще, ніж 9:6 для гравця А.
При порівнянні випадків 1 і 2 і двох рахунків 11:4 і 10:5 видно, що гравець В повинен спочатку відкрити довший ланцюжок. Причина в тому, що якби B спочатку відкрив відключений лінійний ланцюг, то цикл був би завершений останнім, що означає, що гравцеві A не доведеться платити 4 очки при грі DDD в циклі, щоб залишатися під контролем. Ми порушили б наше попереднє Правило 2. Загалом можна показати, що якщо роз'єднаний ланцюг має m коробок, то з'єднаний лінійний ланцюг має n коробок, а петля має p коробки, і тоді гравець B, який розриває роз'єднаний ланцюг першим , спочатку дає B 4 очка від 2 разів DD, але тоді як B розриває приєднаний лінійний ланцюг, тоді B отримує
min(p + max(0,m-4),min(6,m+2))
багато очків. Найнижчу вартість це може прийняти, коли p має найнижчу вартість, що дорівнює 4 (петля має принаймні 4 коробки), аm має найнижчу вартість, що дорівнює 3 (найкоротший довгий лінійний ланцюг, якщо найкоротший ланцюг мав би лише 2 коробки, які були б миттєво зіграні в Half-Hearted Handout, і формула була б різною). Для p = 4 і m = 3 гравець B отримав би
min(4 + max(0,-1),min(6,5)) = min(4+0,5) = 4
а за p > 4 або m > 4 гравець B отримав би більше 4 очок.
Що робити, якщо існують різні ланцюги з однаковою найнижчою вартістю ?
Якщо різні ланцюги мають однакову найнижчу вартість, то наша програма використовує правило розривання з’єднаного ланцюга. Ідея полягає в тому, що існує ймовірність того, що через цей розірваний ланцюг петля стає доступною, що може зробити взяття/утримання контролю ще більш дорожчим.
В іграх зазвичай беруть гравець бере контроль, коли грає в DD/DDD на початку ендшпілю. Але якщо є багато ланцюгів з 3 коробками та петлями з менш ніж 8 коробками, тоді , можливо, краще не грати в DD/DDD і не брати контроль. Тому нам потрібен загальний алгоритм, а не тільки практичне правило.
Коли гравець повинен грати в DD/DDD, а коли ні?
У літературі про гру Dots перша гра DD/DDD також називається брати контроль. Це означає, що гравець бере контроль в тому, хто отримує останній довгий ланцюг, що може означати не те саме, що взяти контроль у грі і виграти її, НЕ граючи в DD/DDD, як ми побачимо нижче.
Коли гравець має можливість грати в DD/DDD, то цей гравець має можливість помінятися ролями з суперником ціною 2 очок (DD) або 4 очок (DDD). Якщо гравець знає рахунок, отриманий від оптимальної гри в інших ланцюгах, то може вирішити, чи варто мінятися ролями зараз ціною 2 (якщо розіграний в даний момент ланцюг є лінійним) або вартістю 4 (якщо розіграний в даний момент ланцюг це петля). Разом із визначенням виграшу з цього ланцюга гравець може визначити і рахунок, перш ніж розірвати цей ланцюг. Цей розрахунок можна виконати у зворотному порядку, починаючи з кінця гри, якщо знати послідовність розірваних ланцюгів. Таку послідовність можна визначити за вищевказаним Правилом 4.
Правило 5: Вирішіть, чи грати DD/DDD чи ні, використовуючи наведений нижче псевдокод.
У наступному псевдокомп'ютерному коді змінна A - це кількість очок, отриманих в решті гри гравцем, який відкриває наступний ланцюг, а змінна B - це кількість очок, отриманих іншим гравцем. Кількість залишившихся коробок: A+B. Oбчислимо у зворотному порядку і для зручності позначимо ланцюги у зворотному порядку: останній ланцюг у грі є ланцюг 1, ланцюг перед цим є ланцюг 2 і так далі. Поточний ланцюг є ланцюг k. Будь-який ланцюг j має n_j коробок. Змінна гра DD реєструє, чи було зіграно DD/DDD в ланцюгу j.
У наступному псевдокоді ряд(и)
- (1)-(3) ініціалізує 3 змінних в результаті гри останнього ланцюга.
- (4)-(22) оновлення A, B, гри DD для ланцюга j, де j біжить у зворотньому порядку від останнього, але одного ланцюга (j=2) до теперішнього ланцюга k.
- (5)-(13) якщо ланцюг j лінійний, вартість становить 2
- (14)-(22), якщо ланцюжок j є петлеподібним, вартість становить 4
- (6)-(9), (15)-(18), якщо виграш B&minus ; A більший за вартість (2 або 4), то грайте DD і зменшуйте B на вартість і додайте його до А. У будь-якому випадку B отримає n_j.
(1) A = 0
(2) B = n_1
(3) playDD = Помилково
(4) Для кожного ланцюга j від 2 до k:
(5) Якщо ланцюг j є лінійним:
(6) Якщо B > (A + 2):
(7) playDD = Правильно:
(8) B = B + n_j - 2
(9) A = A + 2
(10) Інакше:
(11) playDD = Помилково:
(12) B = A + n_j
(13) A = B
(14) Інакше → Якщо ланцюг j є петлеподібний:
(15) Якщо B > (A + 4):
(16) playDD = Правильно
(17) B = B + n_j - 4
(18) A = A + 4
(19) Інакше
(20) playDD = Помилково
(21) B = A + n_j
(22) A = B
Після цього розрахунку A - рахунок для гравця, який відкрив поточний ланцюг В - рахунок для суперника і Гра DD каже, чи повинен суперник зараз грати в DD/DDD. ∎ (Кінець Правила 5)
Цей псевдокод може здатися складним для непрограміста, але його легко виконати в голові, оскільки це означає лише перевірити, чи вигода зберігати контроль переважає його вартість, тобто вартість гри DD/DDD.
Тестове питання
Ми знаємо, що першими відкриваються ланцюги найнижчої вартості. Чи це означає, що гра в DD/DDD стає більш вигідною ближче до кінця гри?
Іншими словами, чи грати в DD/DDD зараз буде означати , що потрібно грати в неї до кінця, оскільки в іншому випадку суперник візьме на себе контроль і переможе?
Так, майже у всіх випадках. Але ми побачили в Прикладі 6, випадку 2, що деяка петля низької вартості може бути доступною лише після того,як лінійні ланцюги з більш вищою вартістю будуть завершені. Як наслідок, хоча не було достатньо стимулу грати в DDD, коли петля була розірвана (останній ланцюг мав лише 3 коробки, тоді як DDD коштує 4 коробки), стимулу було достатньо, щоб грати раніше DD, вартість якого становить лише 2.
Тестове питання
Припустимо, що хтось правильно оцінює, чи варто грати в DD/DDD. Вони вирішують зіграти в неї і отримати останній ланцюг.
Чи завжди цей гравець виграє?
Ні. Наприклад, припустимо, що у нас є 5 лінійних ланцюгів по 3 коробки в кожному. Отримання останнього дає стимул у 3 коробки, яких достатньо, щоб заплатити за 3 DD кожна вартістю 2 і отримати 1 коробку. Це означає, що перший ланцюг є завершений в цілому і ще 3 гри DD дають рахунок (3+2+2+2+0) : (0+1+1+1+3) = 9:6 для гравця, який не отримав останній ланцюг.
Чи ідеальні наші правила гри в ендшпілі?
Ні. Коли на великій дошці є багато ланцюжків, з'єднаних через 0-бокси та 1-бокси, то кілька з них можуть мати однакову кількість коробок, і тоді може знадобитися більш уточнена теорія або пошук, щоб вибрати оптимальну, виходячи з чого інші ланцюжки стають доступними пізніше через завершення перших ланцюжків.
Правило довгого ланцюга
Правило 6: Перший гравець повинен спробувати зробити кількість точок + кількість довгих лінійних ланцюгів парними, а другий гравець повинен спробувати зробити це значення непарним.
Oбгрунтування правила
Для початку введемо деякі змінні, де '#' означає 'число':
nt = # пeреходів (# разів, коли гравець грав послідовні ходи)
nd = # точок
r = # рядів точок
c = # стовпців точок
nl = # ліній
nb = # коробок
nc = # довгих ланцюгів
nz = # переходу, який розірвав перший довгий ланцюг в ендшпілі
Ми починаємо з виведення відношення, відомого як Ідентичність Ейлера.
nb = (r&мінус;1)(c&мінус;1) = rc &мінус; r &мінус; c + 1
nd = rc
nl = # горизонтальних ліній + # вертикальних ліній
= r(c&мінус;1) + c(r &мінус;1)
= 2rc &мінус; r &мінус; c
і тому
nl = nb + nd &мінус; 1.
. Це відношення еквівалентно ідентичності Ейлера, яка справедлива для довільних графів, тобто будь-якого числа nd точок, пов'язаних будь-яким числом nl ліній, не тільки по вертикалі і горизонталі, що оточують nf грані, де в нашому випадку nf = nb + 1, тому що наша прямокутна сітка точок має додаткову навколишню грань, яка також враховується в ідентичності Ейлера:
nl &мінус; nd + 2 = nf (= nb + 1).
Далі підраховуємо кількість переходів всієї гри.
nt = nl − ((# разів, коли креслення лінії завершилося принаймні 1 коробкою)
− 1 {Завершення останнього коробки не дає іншого ходу.})
= nl − (nb − (# ходів, які завершують 2 коробки) &мінус; 1)
= nl &мінус; nb + 1 + (# ходів, які завершують 2 коробки)
= nd {використовуючи наше більш попереднє відношення nl = nb + nd &мінус; 1}
+ (# DD в лінійних ланцюгах) + (# петель) + (# DDD в петлях)
Остання лінія є результатом того, що при завершенні петлі останній хід завжди завершує дві коробки, а якщо DDD грається в петлі, то інший хід також завершує 2 коробки. Назвемо похідне відношення
Формула кількості переходів:
nt = nd + (# DD в лінійних ланцюгах) + (# петель) + (# DDD в петлях)
Це є точна формула, яка не ґрунтується на будь-яких припущеннях.
Обчислення нз, що є поворотом, який відкриває перший довгий ланцюг
Після того, як перший довгий ланцюг буде розірваний в ендшпілі, в разі, якщо не грається DD і DDD, то кількість залишившихся переходів дорівнює кількості довгих ланцюгів, оскільки кожен гравець завершує один ланцюг. Тому, якщо (# DD) = (# DDD) = 0 тоді
nz {# переходів, які розривають перший довгий ланцюг в ендшпілі}
= nd + (# петель) &мінус; (# довгих ланцюгів)
= nd &мінус; (# довгих лінійних ланцюгів)
Формула для nz також справедлива, якщо грається в DD/DDD.
Обґрунтування :
Будь-яка гра в DD/DDD не може змінити того, що вже відбулося раніше, а саме nz переходів , які призводять до розриву першого довгого ланцюга в ендшпілі. Для кожного зіграного DD і DDD кількість переходів в ендшпілі збільшується на 1 (будь ласка, перевірте), тому коли віднімемо кількість переходів в ендшпілі від загальної кількості переходів, тоді кожен (# DD) і (# DDD) буде скасований, і ми отримаємо те саме значення для nz, якщо б не гралося в DD/DDD.
Тому жоден гравець не хоче робити цей хід, тобто перший гравець не хоче, щоб nz був непарним, але хоче, щоб nz був парним. 2&помножене; (# довгих лінійних ланцюгів) є парним числом, тому додавання його до nz не змінює, чи є nz непарним або навіть що, нарешті, призводить до
Правило довгого ланцюга: Перший гравець намагається зробити (# точок) + (# довгих лінійних ланцюгів) навіть тоді, коли другий гравець намагається зробити це непарним. ∎
Неправильне виведення Правила довгого ланцюга
У деяких публікаціях про гру DOTS робляться два непотрібних припущення для виведення Правила довгого ланцюга.
1. Припущення: Якщо обидва гравці грають в ендшпіль оптимально, тоді той, хто зіграє останній хід, виграє через високу вартість останнього і найбільшого ланцюга і через те, що йому не доведеться знову робити хід і відкривати ще один ланцюг для суперника.
Таким чином, перший гравець хоче, щоб nt = (# переходів) був непарним, щоб мати можливість зробити перший і останній хід і виграти.
2. Припущення: Всі довгі ланцюги, крім останнього ланцюга, граються з DD/DDD. Таким чином (# петель) + (# DDD в петлях) є парним і може бути проігнорований і nt = nd + (# DD в лінійних ланцюгах) стає nt = nd + (# довгих лінійних ланцюгів) &мінус;1. Тому перший гравець хоче, щоб цей nt був непарним, щоб мати можливість зробити останній хід, який є тоді, коли (# точок) + (# довгих лінійних ланцюгів) є парним - Правило довгого ланцюга. ∎
Але ми знаємо, що ці 2 припущення не є необхідними для того, щоб Правило довгого ланцюга було вірним. Наступний приклад продемонструє це.
Який успіх гарантується цим правилом для одного гравця?
Правило довгого ланцюга дає необхідну і достатню умову, щоб вирішити, хто з гравців першим зіграє в першому розірваному довгому ланцюгу в ендшпілі. Цей гравець P може вибрати, чи грати в DD/DDD чи не грати в DD/DDD. У нас 2 випадки.
Якщо перший довгий ланцюг лінійний, то він має принаймні 3 коробки, а гра в DD має вартість 2 коробок.
&куля; Якщо стимул для гри в DD становить <2, то гравець P не буде грати в DD і візьме весь перший ланцюг, а суперник отримає на 1 коробку більше від решти ланцюгів, тому P отримує в ендшпілі як мінімум на 3&мінус;1 = 2 коробки більше, ніж суперник.
&куля; Якщо стимул дорівнює 2, то не має значення, чи Р грає в DD чи не грає в DD у першому довгому ланцюгу і, отже, отримує на &ge ;3 коробки більше в ендшпілі.
&куля; Якщо стимул становить >2, то P грає в DD і отримує на >3 коробки більше в ендшпілі.
Які можливі відмінності в рахунку на старті ендшпілю?
&куля; Якщо кількість 1-ланцюгів парна, а кількість лінійних 2-ланцюгів парна, тоді різниця в рахунку на початку ендшпілю дорівнює нулю.
&куля; Якщо кількість 1-ланцюгів парна, а кількість лінійних 2-ланцюгів непарна, то рахунок на початку ендшпілю дорівнює 2.
&куля; Якщо кількість 1-ланцюгів непарна, то після завершення всіх 1-ланцюгів різниця в рахунку дорівнює 1. Тоді кожен завершений 2-ланцюг буде лише перекидатися між обома гравцями в залежності від того, хто веде на 1 коробку більше.
Отже, наскільки важливими Правило довгого ланцюга?
Коли Правило довгого ланцюга не визначає результат?
Якого правила тоді слід дотримуватися?
Приклад 7: Перевірка правила в нестандартній ситуації
Далі гру починає гравець А. На цій дошці зроблено непарне число 5×3 = 15 ходів. Хід 16 відкриє перший довгий ланцюг, який задовольняє виведеній нами формулі: 16 = (# точок) − (# лінійного довгого ланцюга) = 20 − 4. Той, хто зробить цей хід, в даному випадку гравець Б, програє, якщо гравець А зіграє ДД належним чином.
+-B-+ + + + | | | | | + + + + + | | | | | + + + + + | | | | | + + + + +
Гравець А стартував, а гравець Б повинен був відкрити ланцюжок.
Який рахунок, якщо зіграно три ДД?
Якщо A грає DD 3 рази, то остаточний рахунок дорівнює A:B = 6:6.
+---+---+---+---+ | A | A | A | A | +---+---+---+---+ | B | B | B | A | +---+---+---+---+ | B | B | B | A | +---+---+---+---+
Рахунок з останніх 3-х ланцюгів є 5:4, тому грати в DD в першому ланцюгу і платити 2 очка за отримання одного очка не оптимально.
Яким є рахунок, якщо зіграно два ДД?
Для А краще взяти весь перший ланцюг і отримати підсумковий рахунок А:В = 7:5.
+---+---+---+---+ | A | B | B | B | +---+---+---+---+ | A | A | A | B | +---+---+---+---+ | A | A | A | B | +---+---+---+---+
Яке припущення про неправильне виведення Правила довгого ланцюга порушується?
Обидва припущення були порушені. A перемогає, але не отримуєтостаннього ланцюга. DD грається не в кожному довгому лінійному ланцюгу.
Чи Правило довгого ланцюга все ще зберігається для цієї оптимальної гри?
Отримуємо (# точок) + (# довгих лінійних ланцюгів) = 20 + 4 = 24, що є парним, і перший гравець виграє, як правило, передбачає. Отже, це правило краще, ніж альтернативне доведення з непотрібними припущеннями та неправильними тлумаченнями.
Питання тесту
Чи оптимальна гра вимагає грати DD/DDD, чи не грати DD/DDD?
Ні, обидва можуть бути однаково хорошими. Маючи лише два довгих ланцюжка з 3 коробками, А повинен грати DD, ставлячи оцінку A:B = 4:2.
+-B-+ + +---+---+ | | | | A | A | + + + +---+---+ | | | → | B | A | + + + +---+---+ | | | | B | A | + + + +---+---+
Таким чином, стимул грати в DD перед цими двома ланцюжками становить 4 − 2 = 2, що дорівнює вартості гри в DD. Тому обидві п'єси дають однакові оцінки: А:В = (0+1+3):(3+2+0) = 4:5 = (2+2+0):(1+1+3)
+---+---+---+ +---+---+---+ | B | A | A | | B | B | B | +---+---+---+ +---+---+---+ | B | B | A | = | A | A | B | +---+---+---+ +---+---+---+ | B | B | A | | A | A | B | +---+---+---+ +---+---+---+
Питання тесту
Чи може таке статися при оптимальній грі, коли гравці неодноразово починають і перестають грати в DD/DDD?
Так. Вище ми побачили, як додавання ланцюга з 3 коробками змінило рахунок з 4:2 на 4:(2+3) = 4:5. Стимулoм грати в DD до того, як ці 3 ланцюги будуть 5& мінус; 4 = 1 < 2, тому менше, ніж вартість гри DD, яка дорівнює 2. Отже, з чотирма ланцюгами по 3 коробки, перший не буде грати з DD. Якби був ще один ланцюг з 3 коробками, рахунок став би (4+3):5 = 7:5 = (4+1):(5+2), тому стимул грати другим у 5 ланцюгах 3-коробок становив би 7&мінус; 5 = 2, тому грати в DD було б нормально, даючи в обох випадках рахунок (2+5):(1+7) = 7:8 = 7:(3+5).
+-B-+---+---+---+ | A | B | B | B | +---+---+---+---+ | A | A | A | B | +---+---+---+---+ | A | A | A | B | +---+---+---+---+
Додавши більше ланцюгів з 3 коробками, можна було б мати більше змін між грою та не грою DD.
Чи є задовільним Правило Довгого Ланцюга?
Читачеві рекомендується перевірити Правило Довгого Ланцюга з більшою кількістю прикладів, які включають петлі.
Приклад 8: Застосування Правила Довгого Ланцюга
На цьому веб-сайті Девіда Вілсона показана наступна позиція, яка має лише один хід, щоб наступний гравець виграв.
+ + + +
|
+ + +---+
+---+---+---+
|
+ +---+ +
Хто б виграв, якби обидва гравці дотримувалися наших правил ендшпілю?
Ця плата має парну кількість точок і парну кількість довгих ланцюгів. В останньому довгому ланцюгу не буде зіграно хід ДД, тому зазвичай буде відтворюватися непарна кількість ходів DD, і, таким чином, # очок + # DD є непарною, тому кількість переходів є непарною, тому перший гравець отримає останній ланцюг і виграє. Це відповідає «Правилу Довгого Ланцюга»: «Перший гравець повинен спробувати зробити # точок + # довгих (лінійних) ланцюгів парними, а другий гравець повинен спробувати зробити їх непарними».
Що може зробити 2-й гравець?
2-й гравець не може змінити кількість точок, а радше кількість ходів DD, пожертвувавши 2 коробками та відтворивши хід, позначений як B, що є єдиним виграшним ходом, який має 2-й гравець у цій ситуації:
+ + + +
|
+ + +---+
+---+---+---+
| B
+ +---+ +Цей хід зменшує кількість довгих ланцюгів з 2 до 1 і, таким чином, робить # точок + # довгих (лінійних) ланцюгів непарними і, таким чином, дозволяє 2-му гравцеві виграти на одне очко замість програшу на одне очко.
Як могла продовжуватись гра?
Всі наступні варіанти призводять до A:B = 4:5 і таким чином до 1-очкової перемоги B.
+A8-+B4-+A5-+ B9 | B13 B14 +A3-+A12+---+ A11 B10 B15 B16 +---+---+---+ | B A2 A7 +A1-+---+B6-+ +A5-+A10+B6-+ B13 | B9 A11 +A12+A3-+---+ B4 B14 B15 B16 +---+---+---+ | B A2 B8 +A1-+---+A7-+ +A5-+B4-+B6-+ A10 | B13 B14 +B9-+A13+---+ A11 A3 B15 B16 +---+---+---+ | B A2 B8 +A1-+---+A7-+
Здійснення цього кроку порушує найперше Правило 1 не створювати 3-коробки, якщо це не є необхідним. Наскільки поганий це порушення Правила 1?
Це порушення Правила 1 є не менш дивним, ніж гра в DD. Як ми з'ясували раніше, нормальним є грати в DD і платити ціну в 2 бали, щоб помінятися ролями. Так що ця жертва є мінімальною і хорошою, якщо вона має такий же ефект, як і хід ДД.
У вищенаведеній частині цієї сторінки були представлені технічні терміни і правила були сформульовані. Детально описаний ендшпіль і для першої частини гри Правило Довгого Ланцюга дає вказівки. Якщо ви хочете дізнатися більше про першу частину гри, будь ласка, перевірте [2] та [3] у списку літератури. Наведене нижче дерево рішень підсумовує цю веб-сторінку.
Дерево рішень
Щоб посилання нижче працювали, потрібно розгорнути вищенаведений текст , натиснувши
- Якщо є хоча б одна 3-коробка (коробка, яку можна добудувати), то визначте всі ланцюги, які кріпляться до всіх цих 3-коробок.
- Якщо один з цих ланцюгів лінійний і має принаймні 2 сусідні коробки, то завершіть всі коробки з усіх лінійних і всіх петлеподібних відкритих ланцюгів, крім цих двох сусідніх коробок цього одного лінійного ланцюга. Потім проаналізуйте, чи потрібно грати в DD і або відтворити DD, або заповнити останні 2 поля.
- Якщо всі відкриті ланцюги мають довжину 1 або є петлеподібними, то спочатку завершіть всі відкриті ланцюги довжиною 1, а якщо є хоча б один відкритий петлеподібний ланцюг, то завершіть всі відкриті петлеві ланцюги, за винятком останніх 4 коробок одного з відкритих петлевих ланцюгів. Потім проаналізуйте, чи грати в DDD, чи завершити останні 4 бокси.
- Якщо немає коробки, яку можна завершити, то
- Якщо кожен хід буде створювати 3-коробки, то
- Якщо найкоротшим ланцюгом є 2-ланцюговий
+---+---+ +---+---+
, де 2 ненакреслені лінії можуть бути де завгодно, але не в одному полі, то грайте посередині, щоб досягти (в цьому випадку):+---+---+ | +---+---+ - В іншому випадку визначте , який наступний ланцюг буде розірваним і грайте в будь-якому місці цього ланцюга
- Якщо найкоротшим ланцюгом є 2-ланцюговий
- Якщо є хід, який не створює 3 поля, то
- якщо в грі буде не більше 1 довгого ланцюга (лінійного або петльового), наприклад, через те, що прямокутник точок маленький або тонкий, то ходи DD/DDD не будуть відтворюватися, і тоді гравець, який робить останній хід, виграє, і через формулу Number of Turns, перший гравець повинен спробувати зробити суму # точок + # петель непарною, а другий гравець парним. Оскільки # точок є фіксованим, можна тільки намагатися отримати парне відповідно непарне число петель. Якщо це неможливо, то змініть, хто грає першим.
- якщо зрозуміло, що в грі буде принаймні два довгих ланцюга, але незрозуміло, скільки, то дотримуйтесь правила Long Chain Rule і як перший гравець намагається зробити # з точок + # довгих лінійних ланцюгів парними, і як другий гравець намагається зробити суму непарною, інакше
- якщо зрозуміло, скільки довгих лінійних ланцюгів з'явиться в грі і якщо Правило довгого ланцюга передбачає програш гри, то подумайте про те, як зробити жертовний хід, щоб зменшити кількість довгих лінійних ланцюгів.
- Якщо кожен хід буде створювати 3-коробки, то
Посилання
[1] Вікідемія: Точки та Коробки, дивіться там інші посилання.
[2] Берлікемп, Елвин Р..; Конвей, Джон Х.; Гай, Річард К. (1982), «Глава 16: Точки і коробки», Виграшні шляхи для ваших математичних ігор, том 2: Ігри, зокрема, академічна преса, с. 507–550.
[3] Berlekamp, Elwyn (2000), The Dots-and-Boxs Game: Витончена дитяча гра, AK Peters, Ltd, ISBN 1-56881-129-2.
[4] Wilson, David, Dots-and-Boxs Analysis Results, Університет у Вісконсоні
Індекс
Щоб посилання нижче працювали, потрібно розгорнути текст вище, натиснувши
- #…
- кількість…
- Box
- маленький квадрат з 4 сусідніми точками, які є кутами цих квадратів
- ?-Box
- 0-box, 1-box, 2-box, 3-box, 4-box - це коробки, в яких накреслені 0, 1, 2, 3, 4 їхні сторони.
- Ланцюг
- послідовність, яка складається із з‘єднаних 2-boxes. Існують ланцюги лінійні і ланцюги петлясті .
- Подвійний Перехрещений Хід
- хід, який завершує відразу дві сусідніх коробки. Він грається відразу після ходу Double Dealing в лінійному ланцюгу, або коли петля завершена.
- DD
- aбревіатура дляDouble Dealing
- DDD
- абревіатура дляDouble Double Dealing
- Подвійна угода
- хід, що веде до
- Double Double Dealing
- хід посередині розірваної петлі з 4-Ма коробками, що залишилися, створюючи, наприклад,
+---+---+ +---+---+---+---+ | | | | | +---+---+ або +---+---+---+---+ або | | +---+---+ +---+---+ +---+---+---+ | | | | | +---+---+---+ або +---+---+ + | | | | +---+---+ +---+- Eндшпіль
- завершальний етап гри, який починається, коли стає неминучим створення 3-box в наступному ході
- Ідентичність Ейлера
- загальне відношення для будь-якого graph на площині, а не тільки для гри Dots, де лінії не перетинаються: (# рядків) − (# точок) + 2 = (# облич), де обличчя включають "зовнішнє обличчя" , тому для нас (# облич) = (# коробок) + 1.
- Graph
- - поняття в математиці, де ряд точок з'єднано кількома лініями
- Hard-Hearted Handout
- - креслення середньої лінії в
+---+---+ +---+---+ +---+---+ або | або | | +---+---+ +---+ + + + +або обернених і дзеркальних їх версій, дають+---+---+ +---+---+ +---+---+ | або | | або | | | +---+---+ +---+ + + + +або повернуті і дзеркальні їх версії- Half-Hearted Handout
- малювання лінії на кордоні ланцюжка з двома квадратиками, що ведуть до
+---+---+ +---+---+ | або | | +---+---+ +---+ +
- Line
- відрізок лінії, що зв'язує дві сусідні точки по горизонталі +---+ або по вертикалі
- Лінійний ланцюг
- це ланцюг, який має 2 кінці, не обов'язково прямий
- Правило довгого ланцюга
- Перший гравець повинен спробувати зробити # з точок + # з довгих ланцюгів парними, а другий гравець повинен спробувати це зробити дивним значенням.
- Довгий ланцюг
- це ланцюг з ≥ 3 коробками
- Безглуздий хід{ }це хід, що дає супернику можливість піти на жертву
- Петля
- абревіатура для Петлеподібного ланцюга
- Петлеподібний ланцюг
- ланцюг без кінців
- Хід
- креслення лінії
- Формула кількості черг
- точна формула дає кількість черг у грі, яка є основою для правила довгого ланцюга і яка корисна для низької кількості точок, щоб вирішити, бути першим гравцем чи ні
- Відкриття ланцюга
- робить хід усередині ланцюга або на одному з його кінців (якщо це лінійний ланцюг) і таким чином створює 3-box.
- Правило 1
- Найочевидніша гра полягає в тому, щоб уникнути створення 3-коробки, яку суперник міг би взяти, виконавши її .
- Правило 2
- Для впорядкування ланцюжків візьміть за останній ланцюг найбільший довгий лінійний ланцюг, а якщо довгого лінійного ланцюга немає, то візьміть найбільшу петлю.
- Правило 3
- Якщо в ендшпілі всі коробки мають принаймні 2 накреслені сторони, то, щоб упорядкувати всі інші ланцюги, відсортуйте їх за (# коробок) &мінус; 2 (якщо це петля).
- Правило 4
- Щоб встановити послідовність ланцюгів, відсортованих за значенням для наступного гравця, спочатку найменше значення, виконайте послідовність ходів (див. text), поки вся дошка не буде завершена.
- Правило 5
- Використовуйте наданий псевдокод (див. text), щоб вирішити, відтворювати DD/DDD чи ні.
- Правило 6
- Посилається на правило Правилo Довгого Ланцюга
- Взяття під контроль
- те саме, що відтворення DD/DDD, що як важливий побічний ефект дає можливість повторити відтворення DD/DDD в наступних ланцюгах
- Turn
- ряд послідовних ходів одного гравця
Слідкуйте за оновленнями або підписуйтесь на них: