300000
English | Français | فارسی | 中文 | Українська | Azerbaijani | ខ្មែរ | Tiếng Việt | Bahasa Melayu | Deutsch | O'zbek | РусскийiChomp©
Total number of plays: 873208
Total number of wins: 500874
Total number of wins: 500874
Як грати:
- Кожен гравець по черзі знімає цукерки з дошки
- Вилучені цукерки залежать від квадранту, з якого було обрано цукерку.
- У верхньому лівому квадранті видаляються всі цукерки зверху та зліва від обраної цукерки, праворуч
Як перемогти:
- Гравець, який видаляє останню клітинку, виграє гру
Твоя черга
Ширина дошки:
Висота дошки:
Access to 'Some food for thought' (SFFT) for the iChomp game can be purchased in the online shop
Алгоритм, який ви вивчите в цьому підручнику, здатний оптимально грати у великий клас ігор, тому він окупиться, витративши деякий час на його вивчення. Ключовою стане знаменита теорія Спрага-Грюнді. Якщо ви хочете знати підказки для гри в iChomp без вивчення теорії Спрага-Грюнді, то прокрутіть вниз до відповідного розділу. Перш ніж вдаватися в подробиці нам потрібно уточнити кілька термінів.
Позначення
-
Комбінаторні ігри: ігри з двома особами з ідеальною інформацією та виграють або програють результат і без шансів рухатись.
Неупереджені ігри: комбінаторні ігри, в яких допустимі ходи залежать тільки від позиції, а не від того, який з двох гравців в даний момент рухається. Крім того, виплати симетричні. Іншими словами, єдина відмінність між гравцем 1 і гравцем 2 полягає в тому, що гравець 1 йде першим. Приклад: Chomp
Партизанські ігри: ігри, які не є неупередженими. Приклад: Шахи.
Звичайна гра: гравець, який зробить останній хід, перемагає, тобто гравець, який не може зробити хід, тобто якому нема чого забирати, програє.
Misère Play: Гравець, який зробить останній хід, ПРОГРАЄ.
Chomp: гра, представлена на нашому ігровому сайті, яка використовує один квадрант і Misère Play.
Чи гра Nim, яка проводиться на нашій ігровій сторінцi, використовує звичайну гру чи Misere play?
- У нашій грі Nim використовується Misère play, тому що гравець, який приймає останній матч, програє гру.
Чи використовує гра Chomp, як вона грається на нашій сторінці Chomp гри, звичайну або Misere гру?
- Гра Chomp, як вона грається на нашій сторінці гри, використовує Misère play, оскільки гравець, який бере останні цукерки, програє.
Чому немає сенсу використовувати звичайну гру для Chomp?
- Використання звичайної гри означало б, що той, хто візьме останню плитку, виграє. Тому гравець, який рухається першим, міг миттєво виграти, взявши плитку в лівому верхньому куті.
Чи гра iChomp, як вона грається на цій веб-сторінці, використовує звичайну гру чи Misère Play?
- В iChomp виграє гравець, який візьме останню плитку, тому в цій грі використовується Normal play.
Чи є у вас пропозиція щодо того, як можна змінити дошку Chomp, щоб використовувати Normal Play і все ще грати в ту саму гру?
-
Почати можна було б з положення, коли (отруєна) цукерка в лівому верхньому кутку вже відсутня зі старту. Взяти останню цукерку з такої дошки означає, що можна було б виграти в Normal Play. У Misère Play і з цією плиткою інший гравець повинен був би взяти його і програти, що є тим самим результатом.
Таким чином, наявність плитки у лівому верхньому куті та використання Misère Play або відсутність цієї плитки з самого початку гри та використання Normal Play - це є абсолютно однакова гра.
Про компанію iChomp
- Гра iChomp покликана бути об'єднанням чотирьох Чомп ігри, зіграні одночасно, всі за правилом Normal Play. Це робить гру красивішою в двох аспектах, про що буде розказано нижче. Крім того, iChomp не так вже й складно грати, ніж Chomp, якщо застосувати теорію Спрeга Грунді, яка також описана нижче.
Про теорію Спрега-Грунді
-
Клас ігор, до якого він відноситься, - це неупереджені комбінаторні ігри. Ця теорія робить для нас дві речі:
- Він дає нам алгоритм, який визначає для кожної гри (тобто кожної позиції) число (ми будемо називати його SG-значенням), таке, що число дорівнює 0 тоді і тільки тоді, коли це програшна позиція (в літературі з комбінаторної теорії ігор називається "P-позиція" з "P", що вказує на те, що попередній гравець зіграв виграшний хід). Це означає, якщо це SG-значення дорівнює 1, 2, 3, ... то це виграшна позиція (в літературі називається 'N'-позиція). У цьому випадку той, хто рухається наступним, може забезпечити перемогу, якщо грати оптимально.
- Друге призначення SG-теорії - описати, як виграти гру, яка складається з декількох позицій, зіграних одночасно. Хід в такій комбінованій грі проводиться шляхом здійснення одного ходу в будь-якій з позицій, які об'єднуються.
Що потрібно знати, так це SG-значення кожної з об'єднаних позицій. Щоб отримати їх, потрібно знати значення SG після кожного ходу в будь-якій з цих комбінованих позицій. Вони також потрібні, щоб грати оптимально.
Наприклад: У грі Nim одна має одну , дві або більше купок сірників. Якщо ми знаємо SG-значення для гри кожної окремої купки, то SG-теорія підказує нам, як оптимально грати з усіма цими купками, відбираючи відповідну кількість сірників у будь-якої з цих купoк.
Чому саме iChomp?
-
iChomp - це нова версія Chomp, представлена конкурсами Caribou, яка відтворюється на цій веб-сторінці. «i» в iChomp означає «ізотропний», тобто всі напрямки розглядаються однаково.
У звичайному Chomp видалення однієї плитки також видаляє всі плитки на схід і південь від неї. Отже, напрямки Схід і Південь грають особливу роль.
В iChomp всі плитки в інших напрямках також можуть бути видалені в залежності від того, де знаходиться видалена плитка, що знаходиться найближче до центру. Якщо ця плитка знаходиться, наприклад, в північно-західному напрямку від центру, то знімаються і всі плитки на Півночі або Заході.
Прибравши штучні правила, наприклад, правило про те, що Схід і Південь особливі, зазвичай вважається, що це зробить гру математично красивішою.
Є так само ще щось, що робить iChomp краивішим в порівнянні з Chomp.
У Chomp плитка в лівому верхньому кутку відіграє особливу роль у порівнянні з іншими плитками. Якщо це єдина плитка на дошці, гра закінчена. Якщо видалено іншу плитку, гра продовжується. Можна було б запустити Chomp без цієї кутової плитки, тому всі плитки обробляються однаково, але це саме по собі було б штучним правилом щодо того, навіщо починати гру без цієї плитки, а не без інших плиток.
В iChomp всі плитки присутні на старті і всі обробляються однаково. Будь-яку плитку можна видалити без автоматичного закінчення гри.
Виникають деякі питання:
Чи iChomp є тривіальною грою тому, що це є комбінація або 4 тривіальні ігри Chomp у «Normal play»?
-
Відповідь – ні. Наприклад, гра «Nim» з однією купкою сірників є тривіальною. У розділі "Normal play" можна зняти всю купку за один хід і виграти. У Nim під 'Misère Play', можна прибрати всі, крім одного матчу, і виграти. Тим не менш, поєднання таких зднокупних Nim ігор з багатокупною грою Nim, як на нашій сторінці ігор Nim, не є тривіальним.
Аналогічно і тут: одна гра з використанням кутової плитки та «Normal play» є тривіальною, оскільки можна було б видалити всі плитки за один хід і виграти. Але поєднання 4 таких ігор не є тривіальним.
Короткий зміст порівняння
- IChomp математично красивіший за Chomp, оскільки штучно не виділяє південно-східні напрямки і не надає одній плитці особливої ролі. Цінність видається полягає в тому, що iChomp грати набагато складніше, ніж Chomp, але SG-теорія виручає. Досить знати SG-значення Chomp позицій до певного розміру, щоб легко розрахувати SG-значення iChomp позицій в 4 рази більше цього розміру і, таким чином, знати, як грати в iChomp оптимально до цього в 4 рази більшого розміру.
-
Відповідь – ні. Наприклад, гра «Nim» з однією купкою сірників є тривіальною. У розділі "Normal play" можна зняти всю купку за один хід і виграти. У Nim під 'Misère Play', можна прибрати всі, крім одного матчу, і виграти. Тим не менш, поєднання таких зднокупних Nim ігор з багатокупною грою Nim, як на нашій сторінці ігор Nim, не є тривіальним.
У SG-теорії необхідна математична операція, яка називається XOR. У разі, якщо ви з ним не знайомі, корисним буде наступний розділ.
Що таке XOR?
-
Ексклюзив Or (що є скорочення для XOR), є логічною операцією, яка виконується над двійковими даними. Використовуючи двійкові дані, ми могли мати одне з двох значень, правдиве (=1) або помилкове (=0). Операція XOR з двома двійковими значеннями визначається за допомогою наступної таблиці.
a b a XOR b 1 1 0 1 0 1 0 1 1 0 0 0
Хоча цю операцію легко використовувати для значень 1 (true) або 0 (false), для наших обчислень нам потрібно мати можливість виконувати XOR на двох числах. Це також можна зробити, однак потрібен новий крок, перш ніж ми зможемо виконати XOR.
Перше, що має статися, це числа потрібно буде перетворити в двійкові, тобто перевести іх з бази 10 в базу 2.
Як можна перетворити число з бази 10 в базу 2?
-
Наступний алгоритм може бути використаний для перетворення числа n в базі 10 в формат бази 2. (Нагадаємо, що 20 = 1):
- Знайдіть найвищий показник показника p числа 2, так що 2p ≤ n.
- Запишіть 1 і відніміть 2p від n.
- Якщо p = 0, то зупиніть інше відніміть 1 від p і продовжуйте.
- Якщо 2 p > n, то запишіть 0 інше відніміть 2p від n і запишіть a 1.
- Поверніться до кроку 3.
Послідовність 1 і 0, яку ви записали за цим алгоритмом, буде двійковим поданням числа n. Приклад:
Перетворимо число 13 в формат бази 2. Почнемо з пошуку найвищого степеня 2 менше або рівного 13, що дорівнює 23, або 8. Потім ми записуємо a 1 і віднімаємо 8 з 13, що дає нам 5. Далі перевіряємо 2(3-1) = 22 = 4. Починаючи з 4 ≤ 5, записуємо 1, а з 5 віднімаємо 4, що дає нам 1. Наступний нижній степінь 2 - 21 = 2. 2 > 1, тому записуємо 0. Наступний степінь 2 - 2 0 = 1, який дорівнює нашому n з 1, тому записуємо 1 і віднімаємо 1 з 1, даючи нам0. Оскільки p = 0 зупиняємо алгоритм. Тому 13 (база 10) = 1101 (основа 2).
Після того, як ми переведемо два числа в двійкове представлення, тепер ми можемо виконувати операцію XOR над відповідними цифрами двох двійкових чисел. Результатом є двійкове число, яке потім можна перетворити назад у базу 10, якщо це зручніше для подальшого використання цього значення XOR. Приклад:
Обчислимо XOR з чисел 6 і 13. Двійкове представлення для цих двох чисел дорівнює 6 = 110, а 13 = 1101. Спочатку додаємо 0's зліва від меншого числа, щоб обидва мали однакову кількість цифр, тому 6 = 0110. Потім ми можемо виконати XOR, вишикувавши їх і виконавши операцію над кожною з окремих цифр:
0110 XOR 1101 ------ 1011
Таким чином, 6 XOR 13 = 1011 (основа 2) = 1×23+0×22+1×2 1+1×20 = 8+2+1 = 11 (основа10).
Давайте перевіримо наше розуміння XOR за допомогою кількох запитань.
Що таке m XOR m для будь-якого числа m?
- Для будь-якого числа m ми маємо m XOR m = 0, тому що 0 XOR 0 = 0, а також 1 XOR 1 = 0.
Чи n XOR m = m XOR n для будь-яких чисел n, m?
- Так, тому що 1 XOR 0 = 0 XOR 1 (=1).
Що таке 0 XOR m для будь-якого числа m?
- 0 XOR m = m, тому що 0 XOR 0 = 0 і 0 XOR 1 = 1.
Якщо число m є XOR'ed з числом n через m XOR n, то які цифри m перевертаються?
- Якщо цифра в m є XOR'ed з 0, то цифра незмінна (тому що 0 XOR 0 = 0 і 1 XOR 0 = 1). Якщо цифра в m є XOR'ed з 1, то цифра перевертається (тому що 0 XOR 1 = 1 і 1 XOR 1 = 0). Таким чином, XOR n перевертає всі цифри, для яких відповідна цифра в n дорівнює 1.
-
Наступний алгоритм може бути використаний для перетворення числа n в базі 10 в формат бази 2. (Нагадаємо, що 20 = 1):
Алгоритм обчислення значення SG позиції Chomp.
-
Наступний алгоритм обчислює SG-значення будь-якої позиції P в будь-якій неупередженій комбінаторній грі. Ми пояснюємо це за допомогою гри Chomp.
- Кожна ігрова позиція, яка є програшною позицією, отримує SG-значення 0. У Chomp одна плитка (в північно-західному куті) є єдиною позицією без подальшого ходу і тому є програшною позицією з SG-значенням 0.
- Нам потрібні SG-значення всіх позицій, яких можна досягти з позиції Р за один хід. Отже, якщо позиція P має n плиток, то можливі n-1: за винятком плитки в північно-західному куті, всі інші плитки можна видалити разом з усіма плитками на південь/схід від цієї плитки.
- SG-значення позиції P є найменшим від'ємним числом, якого немає в цьому списку n-1 досяжних SG-значень.
Цей алгоритм є рекурсивним, оскільки для обчислення SG-значення позиції P нам потрібні SG-значення всіх позицій, досяжних від P за один хід. Це все ще працює, тому що необхідні SG-значення стосуються менших позицій меншої кількості плиток і відомо SG-значення найменшого можливого положення (один сегмент у північно-західному куті).
Спробуйте перевірити 3-ю властивість у грі вище, вибравши більшу ширину та висоту дошки та натиснувши «Randomize Board».
- Коли ви наводите курсор миші на плитку, ця плитка та інші плитки, які будуть видалені, підсвічуються. Число в цьому сегменті є SG-значенням квадранта в розділі "Normal Play" (а не "Misère Play"), що призведе до рельтату, якщо ця плитка натиснена. Ви можете перевірити, що число, показане в тексті 'SG значення Бази Десять:' поруч з квадрантом, є найменшим числом, не показаним у квадранті. Ви також можете перевірити, що якщо ви натиснете на плитку, то число, яке було в ній, тепер відображається як "SG значення Бази Десять:" нової позиції.
Як прискорити визначення SG-значень:
Оскільки одна і та ж позиція може бути досягнута з різних позицій за один хід, і може виникати неодноразово при обчисленні SG-значення більшої позиції, було б марною тратою зусиль обчислювати його знову і знову. Тому, як тільки SG-значення позиції P буде розраховано, його слід зберегти для подальшого використання.
Якщо потрібно обчислити SG-значення всіх позицій до певного розміру, то стане в нагоді наступний підхід. Почнемо з присвоєння єдиної позиції з однією плиткою (в Північно-Західному куті) SG-значення нуль. Потім ми використовуємо вищеописаний алгоритм для обчислення значень SG всіх позицій з 2 плитками, потім з 3 плитками і так далі.
Алгоритм обчислення SG-значення iChomp позиції .
-
Позиція iChomp складається з 4 позицій Chomp, по одній в кожному квадранті дошки.
- Спочатку ми визначаємо SG-значення кожної з 4 Chomp позицій, використовуючи правило Chomp 'Misère Play'. Порожній квадрант не є Chomp позицією, тому надамо йому значення −1.
- Потім ми додаємо 1 до кожного значення.
- Для кожного з 4 результуючих чисел обчислюємо двійкове представлення.
- Обчислюємо значення XOR 4 двійкових значень і отримуємо SG-значення цієї позиції (у двійковій формі). Якщо це значення дорівнює нулю, це програшна позиція, в іншому випадку - виграшна позиція.
-
Ми додаємо 1 для того, щоб отримати SG-значення позиції Chomp під "Звичайною грою" з SG-значення в "Misère Play". Наступна теорема пояснює це.
Теорема:
--------
Щоб отримати SG-значення позиції Chomp під "Normal Play" (тобто взяття останньої плитки виграє гру, яка не є поширеним способом гри в Chomp), потрібно додати 1 до SG-значення тієї ж позиції під "Misère Play" (тобто приймаючи останню плитку програшу, що є поширеним способом гри в Chomp).
Чи можете ви спробувати довести теорему шляхом індукції?
-
Доведення (шляхом індукції (і дуже детальнo)):
Базовий випадок (1 плитка):
-------------------
У розділі "Normal Play" порожня дошка без плитки є програшною позицією і, отже, має SG-значення нуль. Крім того, у розділі "Normal Play" для дошки з однією плиткою (у верхньому лівому куті) єдиним можливим переміщенням є видалення цієї плитки, що дає положення з SG-значенням 0. Отже, під "Normal Play" найменше невід‘ємне SG-значення, яке не може бути досягнуто переміщенням, дорівнює 1, так що це SG-значення позиції з однією плиткою під "Normal Play".
Під "Misère Play" наявність однієї плитки є програшною позицією з SG-значенням 0.
Таким чином, для 1 плитки SG-значення "Normal Play" на 1 більше, ніж значення "Misère Play".
Індуктивний крок
---------------
Індукційна гіпотеза (n плиток):
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
Ми припускаємо, що існує число n, так що для всіх позицій з плитками ≥1 і ≤n значення SG під “Normal Play" на одне більше, ніж при "Misère Play". Індукційна претензія (n+1 плитка):
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
Ми покажемо, що це також стосується всіх позицій з плитками n+1.
Крок індукції (n плиток → n+1):
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
Для будь-якої позиції "Misère Play" та "Normal Play" допускають однакові рухи, за винятком того, що "Normal Play" також дозволяє проводити всі плитки через верхній лівий кут.
Якщо позиція має n+1 плитки, то здійснення переміщення породжує позицію не більше n плиток, до якої ми можемо застосувати індукційну гіпотезу:
Таким чином, список отриманих SG-значень у розділі "Normal Play" отримано зі списку отриманих SG-значень у розділі "Misère Play", кожне з яких збільшено на 1, і шляхом додавання значення 0 шляхом прийняття всіх плиток.
Таким чином, найменше ненегативне число, яке НЕ можна отримати в рамках "Normal Play", на 1 вище, ніж найменше невід'ємне число, яке НЕ можна отримати в "Misère Play". Іншими словами, для вихідної позиції з n+1 плитками SG-значення в "Normal Play" є на один вище, ніж SG-значення в "Misère Play". ∎ (На цьому доказ завершено.)
-
Доведення (шляхом індукції (і дуже детальнo)):
Чому ми додали "1"?
Як грати в iChomp
-
Мета полягає в тому, щоб зробити хід таким чином, щоб SG-значення отриманої позиції дорівнювало нулю. Який би рух не зробив, він повинен бути в одному з 4 квадрантів. Це означає, що SG-значення позиції, де був здійснений хід, і SG-значення інших 3 незмінних квадрантів всіх XOR'ed повинні давати нуль. Це стосується тоді і тільки тоді, коли інші 3 SG-значення XOR'ed дають саме SG-значення нового квадранта після здійснення переміщення (див. далі доказ цього твердження). Тому порядок дій наступний:
- (простий) Випадок: Два з 4 квадрантів мають однакове SG-значення. Тоді XOR цих двох рівних значень дасть нуль, тому обидва квадранти повинні бути проігноровані.
- Якщо два інших квадранта також мають рівні SG-значення, то SG-значення всієї позиції дорівнює нулю, а позиція є програшною позицією. Потім приберіть всього одну плитку з будь-якого квадранта, щоб відтягнути поразку і мати більше шансів для суперника не зіграти оптимально.
- Якщо два інших квадранта мають неоднакові SG-значення, то виберіть квадрант з більшим SG-значенням. Перейдіть туди, клацнувши на плитці з вписаним числом, яке дорівнює SG-значенню іншого квадранта. В результаті виходять 2 пари квадрантів з попарно рівним SG-значенням і сумарним значенням XOR дорівнює нулю - програшна позиція.
- (Загальний) Випадок:
- Обчисліть 4 значення iChomp-SG, скажімо w,x,y,z з 4 квадрантів (кожен з яких є значеннями Chomp-SG цього квадранта плюс 1) і перетворіть їх на базові два.
- Потім знайдіть найбільш ліву позицію таку, щоб непарне число цих 4 чисел мало 1 в цій позиції. Наприклад, якщо 4 числа
w=11011
Тоді сама ліва позиція з 1 - це 5-я позиція (починаємо відлік позицій з правої). w і y мають там 1, тобто два числа (w і y) мають там 1. Два - парне число, тому потрібно ігнорувати цю позицію. Наступна позиція - 4-я позиція, знову зарахована справа. Тут теж рівномірно багато чисел мають там 1 (w і x). Потрібно ігнорувати і цю позицію. 3-тя позиція має 3 числа з 1 там (x, y, z). 3 - непарне число, тому ми вибираємо будь-яке з цих 3 чисел, наприклад, y=10100.
x= 1101
y=10100
z= 100- Якщо у всіх позиціях є парне число 1s, то значення XOR всіх 4 чисел дорівнює нулю і це програшна позиція. Наприклад
w'=11011
мати парне число 1 в кожній позиції. XOR цих 4 чисел дорівнює нулю, це програшна позиція. У цьому випадку з будь-якого квадранта знімається лише одна плитка, щоб відстрочити поразку і мати більше шансів для суперника не зіграти оптимально.
x'= 1011
y'=10110
z'= 110 - Якщо хоча б одна позиція має багато непарних 1, то ми знайшли число, як y вище (а не y').
- Ми XOR інші 3 числа, в нашому випадку w XOR x XOR z = 11011 XOR 1101 XOR 100 = 10011. Це значення завжди менше, ніж число, яке ми вибрали, тут y = 10100 (дивись докази нижче).
- У квадранті з вибраним значенням, тут y, ми робимо хід, в результаті якого позиція з SG-значенням дорівнює XOR інших 3 значень, в нашому прикладі 10011.
- Щоб дізнатися, на яку плитку натиснути, ми або перетворюємо 10011 в Base Ten (= 1×1 + 1×2 + 0×4 + 0×8 + 1×16 = 19) і натискаємо плитку з числом 19, або обчислюємо в двійковій формі 10100 − 10011 = 1 і перетворюємо це в базове Десять (= 1) і знаємо, що плитка для кліку повинна мати значення на 1 менше y (=20), тобто натиснути плитку з вписаним номером 19.
Чому це виграшний крок?
-
Будь ласка, нагадайте собі про властивості XOR, як показано раніше, щоб відповісти на наступні запитання.
якщо ви = w XOR x XOR y XOR z, то що таке y XOR u ?
-
Використовуючи правила XOR, вивчені раніше, ми отримуємо
y XOR u
= y XOR w XOR x XOR y XOR z
= y XOR y XOR w XOR x XOR z
= 0 XOR w XOR x XOR z
= w XOR x XOR z.
Якщо y замінено на y XOR u, то що таке новий XOR всіх 4 SG-значень?
-
Новий XOR буде
(y XOR u) XOR w XOR x XOR z
= (w XOR x XOR z) XOR (w XOR x XOR z)
= 0
через m XOR m = 0 для будь-якого числа m.
Це означає, що нове SG-значення всієї дошки буде нульовим, так що це буде програшна позиція, як і передбачалося.
Чому повинен існувати хід, який змінює SG-значення y на більш низьке значення?
- Відповідно до визначення: Позиція має SG-значення y тоді і тільки тоді, коли існують ходи, які генерують позиції з SG-значеннями 0,1,..,(y-1). Отже, якщо y > (y XOR u), то повинен існувати хід, що генерує SG-значення (y XOR u) < y.
Залишається відповісти:
Чому повинен існувати квадрант з SG-значенням y, який задовольняє y > (y XOR u)?
-
Нагадування:
Раніше, коли ми дізналися про властивості XOR, то побачили: XOR u перевертає всі цифри, для яких відповідна цифра в u дорівнює 1.
Якщо ≠ 0, то U містить найвищу степеню 2, скажімо 2р. Цей степінь 2 повинен зустрічатися в непарному числі з 4 SG-значень, тому хоча б в одному, скажімо y.
Це означає, що при обчисленні y XOR u цей 1 в y перетворюється на 0 на відповідний 1 в u. Можуть бути й інші двійкові цифри, перевернуті в y, розташовані праворуч від цього 1. Найбільше можливе значення y − (y XOR u) виникає, якщо цифри в y праворуч від цього 1 є нулями, а цифри у вас праворуч від цього 1 є одиницями. У цьому випадку u = 111..111 змінюється y = *100..00 (де * означає будь-яку кількість цифр) на y XOR u = *011..11. Їх відмінність полягає в:
y − (y XOR u)
= 2p − (2p−1 + 2p−2+ ... +20)
= 2p − (2p−1 + 2p−2+ ... +20)× (2-1)/(2-1)
= 2p − (2p−1)/(2-1)
= 1.
Це означає, що y принаймні на один більший ніж (y XOR u). ∎
-
Використовуючи правила XOR, вивчені раніше, ми отримуємо
Спробуйте цей алгоритм, граючи та вигравши проти "Складність: Важко".
-
Для початку виберіть «Складність: Важко», що гарантує оптимальну комп'ютерну гру. Якщо ви все-таки виграєте, то кожен хід ви зіграли оптимально.
SG-значення кожного квадранта показано в основі 10 і основі 2. Перевірте, щоб це число було найменшим значенням, яке не відображається в квадранті.
Під ним відображається XOR всіх 4 SG-значень, які називаються u. Перевірте значення вас, просто змінивши будь-яку пару з двох 1 в 4 SG-значеннях на 0, якщо два 1 знаходяться в однаковому положенні. Потім помістіть решту 1 в одне двійкове число і перетворіть його в основу 10.
Щоб здійснити переміщення, як описано вище:
- Знайдіть одне з 4 SG-значень, скажімо y, яке має 1 в тій же позиції, що і ліва більшість 1 в u.
- Обчисліть y XOR u у двійковій формі, а потім перетворіть його в основу 10.
- У y-квадранті натисніть плитку з обчисленим y XOR u
- Грайте свої ходи таким самим чином, поки не виграєте.
- Грайте ще раз, але цього разу почніть з випадкового ходу. Якщо вам не пощастило і ви не зіграли випадково виграшний хід, ви не зможете виграти цю гру, навіть якщо потім спробуєте грати оптимально.
Всі наведені вище інструкції припускають, що вам відомо SG-значення 4 квадрантів, що означає, що ви знаєте SG-значення кожного квадранта після кожного можливого переміщення.
Чи можете ви знайти SG-значення деяких Chomp позицій (у «Misère Play»)?
-
Для того щоб обчислити SG-значення позиції, потрібно знати SG-значення всіх позицій, які можна досягти від неї за один хід. Це рекурсивний процес. Тому нам потрібно почати з позицій з найменшою кількістю плиток і прокласти собі шлях вгору.
Чи можете ви знайти SG-значення 1,2,3,... плитки в один ряд?
-
Наявність лише 1 плитки (у верхньому лівому куті) є програшною позицією з таким SG-значенням 0.
Маючи 2 плитки (у верхньому ряду або лівій колонці), єдиний можливий хід - взяти одну плитку, отримавши згадане положення з SG-значенням 0. Отже, найменше ненегативне SG-значення, яке не може бути досягнуто переміщенням, дорівнює 1, так що SG-значення позиції з 2 плитками дорівнює 1.
Маючи 3 плитки у верхньому ряду, можна взяти або 1, або 2 плитки і отримати SG-значення 1 і 0, тому SG-значення, таким чином, SG-значення дорівнює 2.
Аналогічно, SG-значення n плиток у верхньому рядку дорівнює n-1.
Розглянемо 3 плитки, 2 у верхньому ряду і 2 в лівій колонці. Ми можемо видалити лише 1 плитку і досягти SG-значення 1, але не 0, тому найменше SG-значення, яке неможливо отримати, дорівнює 0, що, отже, є значенням SG цієї позиції. Це програшна позиція.
Чи можете ви знайти SG-значення позиції з плитками m+n−1, з яких n знаходяться у верхньому ряду, а m плитки - в лівому стовпці?
- Видалити плитки можна лише з верхнього рядка або з лівого стовпця. Таким чином, SG-значення таке ж, як і наявність двох квадрантів, один з n плитками у верхньому ряду, а інший з m плитками в лівому стовпці. Таким чином, SG-значення є (m-1) XOR (n-1). Це те саме, що грати в NIM з двома палями та правилом «Normal Play», де матчі можна видалити лише з однієї купи за один хід.
Чи можете ви знайти SG-значення позиції з плитками тільки в двох верхніх рядах?
-
Формули для цих позицій складніші. Наскільки нам відомо, раніше вони не публікувалися. Ви можете спробувати перевірити їх на наявність невеликої кількості плиток.
Нехай n і m — кількість плиток у верхньому і другому ряду.
Якщо n парний тоді
k = (n-2)/2
якщо m парний тоді
a = m/2
SG-значення = 2*k+a+1
інше (m - непарне)
a = (m-1)/2
якщо ≤ (k/2), то SG-значення = 2*k-a
інше значення SG = 3*(k-a)
інше (n - непарний)
k = (n-1)/2
якщо m парний тоді
a = m/2
якщо ≤ (k/2), то SG-значення = 2*k-a
інше значення SG = 3*(k-a)
інше (m - непарне)
a = (m-1)/2
SG-значення = 2*k+a+1
Перевірте, чи правильні формули, використовуючи ігрове поле вище.
- Мінімальну висоту дошки вибирайте так, щоб були квадранти всього з двома рядами плитки. Після застосування наведених вище формул ви повинні отримати SG-значення, яке на один нижче значення, показаного в розділі "SG Value Base Ten:", оскільки формули призначені для "Misère Play", тоді як iChomp використовує "Normal Play".
-
Наявність лише 1 плитки (у верхньому лівому куті) є програшною позицією з таким SG-значенням 0.
Як можна досить добре грати в iChomp, не знаючи SG-значень?
-
Почнемо зі спостереження: правила Chomp не мають різниці між напрямком Схід і Південь.
Що є наслідком для SG-значень двох позицій, які дзеркально симетричні один одному при дзеркальному відображенні по діагоналі, що починається з лівого верхнього кута?
- Оскільки напрямки Схід і Південь дзеркально відображені один в одному, це означає, що обидва повинні мати однакове значення SG.
Що це означає для iChomp, коли 2 квадранти мають положення, симетричні при обертанні квадрантів та/або діагональному дзеркалі?
- Обидва квадранти можна проігнорувати. Чому? Обидва квадранти мають однакове значення SG при мізерній грі і після додавання 1 також однакове значення SG при звичайній грі. XOR цих двох рівних значень дає нуль. Тому обидва квадранти не мають ніякого внеску в SG-значення всієї позиції ради.
Отже, яка стратегія гри повинна працювати?
-
Слід зробити хід, який створює дві пари квадрантів таким чином, щоб квадранти в кожній парі мали симетричні положення з рівними SG-значеннями, скажімо A і A, а також B і B. Тоді SG-значенням комбінації всіх 4 квадрантів є A XOR A XOR B XOR B = 0 XOR 0 = 0 або (A XOR B) XOR (A XOR B) = 0 тому завжди 0. Один створив програшну позицію.
Однаково не слід робити хід, який залишає два симетричних квадранти і два інших, з яких один може бути змінений в інший за один хід суперника. Це дозволило б супернику створити програшну позицію.
Деякі тестові питання
-
Ось кілька питань, де ви можете перевірити своє розуміння Chomp, iChomp і SG-теорії.
Чи достатньо знати SG-значення, щоб ідеально грати в Chomp?
- Так. Якщо SG-значення позиції дорівнює нулю, то це програшна позиція (тому що не існує жодного ходу, щоб зробити її нульовою, тому виграшного ходу не існує, тому це програшна позиція). Якщо SG-значення більше нуля, то це означає, що є хід, щоб зробити SG-значення отриманої позиції нульовим, тому відбувається виграшний хід.
Чи потрібно знати SG-значення Chompпозицій , щоб ідеально грати в Chomp?
- Ні. Щоб грати в Chomp, нам потрібно знайти хід, який породжує програшну позицію. Якщо такого ходу не існує, то це програшна позиція, і будь-який хід можна зіграти. Але, якщо такий хід буде знайдений, можна припинити пошуки. SG-значення не потрібно.
Для чого тоді потрібні SG-значення?
- Вони потрібні лише для того, щоб грати в кілька ігор Chomp паралельно як нова гра, як в iChomp.
Наскільки складніше в Chomp обчислити SG-значення позиції, ніж виграшний хід?
-
Щоб грати в Chomp, нам потрібно знайти хід, який породжує програшну позицію. Якщо такого ходу не існує, то це програшна позиція, і будь-який хід можна зіграти. Але, якщо такий хід буде знайдений, можна припинити пошуки.
Зусилля з пошуку SG-значення позиції, як правило, вище. Для знаходження SG-значення завжди потрібно шукати ВСІ ходи, щоб знайти всі SG-значення результуючих позицій і знайти найменше не від'ємне значення, до якого не можна дістатися в русі. Ця величина і є SG-значенням позиції.
Наприклад, в наших (Caribou) обчисленнях ми змогли визначити всі програшні позиції (і, таким чином, виграшні позиції) за допомогою до 93 плиток. Завдяки порівнянним обчислювальним зусиллям ми змогли обчислити SG-значення всіх позицій Chomp з до 82 плитками.
У цьому сенсі визначення SG-значень обчислювально дорожче, ніж визначення виграшного ходу.
Якщо Nim з 4 купками грати важче, ніж Nim з 1 купкою, то тоді iChomp з 4 квадрантами грати набагато важче, ніж Chomp з 1 квадрантом?
-
У Nim SG-значення однієї палі - це просто кількість збігів у цій купі. (Будь ласка, підтвердіть це, застосувавши вищенаведені коментарі, як обчислити SG-значення до одного стека в Nim.) Єдиною складністю відтворення декількох паль в Nim є XOR різні SG-значення цих паль, щоб отримати SG-значення всіх паль разом узятих.
У Chomp обчислювально дорого отримати SG-значення позиції (яке знаходиться в одному квадранті). В iChomp, як тільки відомі SG-значення 4 квадрантів, ці значення також повинні бути XOR'ed, але це набагато простіше, ніж знайти SG-значення одного квадранта.
Щоб грати в Chomp оптимально, не потрібно знати SG-значення позиції, знати виграшний хід досить добре, але, як показано вище, різниця не така вже й велика.
Так що відповідь - НІ, грати в iChomp оптимально не набагато складніше, ніж в Chomp.
У Chomp хід може створити позицію, яка має більш високе SG-значення?
- Так. SG-значення позиції - це найменше значення, яке не може бути згенероване переміщенням.
У Chomp можуть бути різні ходи, які створюють положення з однаковим SG-значенням?
-
Так. Ви можете побачити приклади, збільшивши розмір плати та натиснувши кнопку «Показати значення SG ходів». Наприклад, позиція
###
##
#
має 3 виграшні ходи, всі створюють позицію з SG-значенням 0. Ми навіть знайшли позицію з 7 переможними ходами:
+ 10 6 15 2 20 21 14 22 11 0 23 7 26 13 7 11 9 14 0 19 5 17 11 14 18 0 24 23 8 3 19 2 0 20 11 4 0 5 1 8 0 0 4 23 25 24
Слідкуйте за оновленнями або підписуйтесь на них: