Стратегічні ігри та вирішення завдань
(Тут буде про історію Ним і подібні ігри, так що якщо ліньки, гортайте відразу до "Про визначення стратегії" (Це під 2 картинкою))
Зосередимо увагу на про стратегічних іграх. Їх можна поділити на два типи. Ті, що описуються простими правилами, тривають короткий час та кількість інформації в яких обмежена або відносно невелика, називатимемо малими стратегічними іграми.
В інших, подібних до шахів або го, повний контроль неможливий через тривалість партії, складність правил і особливо через величезну кількість можливих ходів у кожній позиції. На прикладі малих стратегічних ігор ми побачимо, як математика використовується в аналізі ігор визначення переваги одного з гравців і знаходження виграшної стратегії.
Взаємозв'язок між математикою та іграми може стосуватися різних аспектів ігор. Стосовно стратегічних ігор математика особливо корисна визначення виграшної стратегії. Стратегічна гра дуже схожа на процес вирішення математичної задачі: йдеться не про те, щоб виграти одну партію, здійснюючи більш вдалі ходи, а про те, щоб знайти спосіб, як вигравати завжди. З цієї причини при визначенні виграшних стратегій використовуються евристичні методи: спосіб від зворотного; припущення, що гра «вирішена»; застосування симетрії; проведення аналогії з іншою, вже вирішеною грою та інші. Вони аналогічні тим, що використовуються під час вирішення математичних завдань. Тому коли для певної гри відома виграшна стратегія, гра з розваги перетворюється на вирішене завдання. Зрозуміло, що це вірно тільки для певних ігор, які виходять за рамки простих розваг і описуються в математичнихтеоріях. Про подібні теорії, часом досить складні, ми, можливо, поговоримо пізніше.
Суть малої стратегічної гри для двох гравців, відома під назвою Ним, полягає в тому, що гравці викладають на стіл одну або кілька груп фішок і визначають правила, за якими потрібно знімати фішки зі столу. Мета гри - взяти останню фішку або, навпаки, змусити супротивника взяти останню фішку. Походження цієї гри невідоме. Дехто вважає, що вона родом зі Сходу. Також неясно і походження назви. Серед можливих версій — староанглійське слово «ним», яке означало «брати», «викрасти». Хтось дуже дотепний помітив, що якщо застосувати до словаNIMцентральну симетрію, вийде словоWIN— виграти в перекладі з англійської. Як би там не було, грі Ним більше ста років: перший аналіз виграшної стратегії для ігор
Ця гра набула популярності в Європі в70-тіроки XX століття завдяки фільму французького режисера Альона Рене «Минулого року в Марієнбаді» (1961). Герої фільму кілька разів грають в один із варіантів цієї гри. Тому версія гри з фільму (вона розглядатиметься у наступних постах під назвою «Гра5) іноді називається Марієнбад — на ім'я маленького курортного міста в Чехії, де відбувається дія картини.
Визначення загальної виграшної стратегії, яка застосовується до будь-якої гри такого типу, — один із найяскравіших проявів того, як математика використовується для аналізу ігор, і особливо того, наскільки ефективне представлення чисел у двійковій системі.
Про визначення стратегії
Спочатку ми проаналізуємо ігри з однією групою фішок, у яких кожному ходу можна брати зі столу мінімумоднуі максимумnфішок. Ми розглянемо два окремі випадки, потімнаведемо узагальнення. Найпростіший варіант подібної гри такий.
Гра 1: виграє перший
На стіл викладаються20фішок одного кольору. На кожному ходу один із двох гравців може братиоднуабодвіфішки. Той, хто бере останню фішку, виграє. Який із гравців має перевагу — той, хто ходить першим чи другий учасник? Як потрібно грати, щоб завжди вигравати? Що станеться, якщо зміниться кількість фішок? Що зміниться, якщо ми змінимо правила гри і той, хто бере останню фішку, програватиме? Це досить проста гра, тому її можна проаналізувати повністю, визначити виграшну стратегію та узагальнити її для будь-якої кількості фішок. Якщо ви не знайомі з цією грою, перед прочитанням спробуйте зіграти в неї самому і постаратися відповісти на ці запитання.
Зігравши кілька партій, ви швидко виявите, що якщо хтось із гравців залишив на столі3фішки, то наступним ходом він обов'язково виграє. Вірно помічено, але це не допоможе нам завжди вигравати: ми не знаємо, які ходи потрібно робити, щоб на столі залишилося фішки. Але тепер ми знаємо, що виграє той, хто взяв фішку номер17. Таким чином, кількість фішок у грі скорочується. Зробивши ще один подібний крок, ми побачимо, що гравець, який залишив на столі6фішок, теж завжди виграватиме. Загалом завжди виграє той, хто залишає на столі число фішок, кратне3. Це дозволяє сформулювати виграшну стратегію: коли в початковій позиції на столі20фішок, перший гравець завжди виграватиме, якщо братиме першим ходом2фішки і потім завжди залишатиме на столі кількість фішок, кратне3(якщо другий гравець знімаєодну
фішку, перший гравець повинен взятидві, і навпаки).У цій грі перший гравець має перевагу, тому що для нього є виграшна стратегія.
Зміна початкової кількості фішок може частково вплинути на цю стратегію і навіть на те, який гравець матиме перевагу. Тепер ми знаємо, що виграшна стратегія полягає в тому, щоб залишати на столі число фішок, кратне3. Щоб дізнатися, на чиєму боці перевага, достатньо розділити початкову кількість фішок на3і подивитися, який залишок від поділу. Якщо залишок дорівнює2(як у вихідному випадку), то перший гравець завжди виграє, якщо бере першим ходом2фішки, а потім залишає на столі число фішок, кратне3(якщо противник береоднуфішку, перший гравець бередві, і навпаки). Якщо залишок від поділу дорівнює1(наприклад, число фішок дорівнює19,25,100або2017) , то перший гравець також виграє. Для цього достатньо взяти першим ходом одну фішку. Нарешті, якщо залишок дорівнює0(кількість фішок ділиться на3), то виграє другий гравець: йому потрібно взятидвіфішки, якщо перший гравець взяводну, і навпаки. У цьому випадку перший гравець ніколи не зможе залишити на столі число фішок, кратне3.
Таким чином ми узагальнили гру для будь-якого початкового числа фішок. гру
можна узагальнити і далі, змінивши кількість фішок, які можна брати на кожному
Гра 2: виграє другий
Перший гравець пише на папері число від1до10. Другий гравець вигадує число від1до10і записує результат додавання цього числа з першим. На кожному ходу гравець додає до загальної суми нове придумане ним число від1до10. Той гравець, який запише тризначне число (100і більше), програє. Якпотрібно грати, щоб вигравати? Який із гравців має перевагу: той, хто ходить першим чи другим? Що станеться, якщо зміниться ціль гри чи правила?
Як уже пропонувалося раніше, буде зручно зіграти кілька партій самому, щоб спробувати визначити виграшну стратегію для одного з гравців та зрозуміти, як ця гра пов'язана з попередньою. Аналізуватимемо гру наступним чином: якщо програє той, хто напише100, виграє той, хто напише99. Яке число потрібно написати перед тим, щоб гарантовано отримати99на наступному ході? Це88, тому що в цьому випадку противник напише будь-яке число між89та98, після чого перший гравець легко отримає99. Як і в минулій грі, продовжуючи подібні міркування (перейшовши до88, потім77,66, .11), ми побачимо , що цього разу потрібно формувати групи з11. Тепер нам відома виграшна стратегія: той, хто першим записує11та наступні числа, кратні11, першим отримає99і виграє. Якщо противник додаєn, потрібно додавати11 - n. Так як на першому ходу перший гравець не може отримати11, а другий може це означає, що існує виграшна стратегія для другого гравця. Як і в минулій грі, при зміні кінцевого числа виграватиме перший гравець, якщо це число не буде кратне11. Якщо це число буде ділитися на11, завжди перемагатиме другий гравець.
Гра 3: загальний випадок
Припустимо, що на століmфішок і кожним ходом можна брати від1доmфішок (n & m). Виграє той, хто забирає останню фішку. Для якого гравця існує виграшна стратегія — для першого чи другого? У чому вона полягає? Якщо гравець, який взявостанню фішку, чи буде програвати, як зміниться стратегія?
Йдеться не про одну гру, а про групу абстрактних ігор. Дві попередні ігри – її окремі випадки. Отже, виграшна стратегія для цієї гри - це загальна стратегія, яка застосовна до нескінченної множини аналогічних ігор. Ця стратегія формулюється так. Поділимоmнаn + 1і визначимо залишок від розподілу. Він перебуватиме в інтервалі від0доn. Можливі два випадки:
1.Залишок від розподілу дорівнює0. У цьому випадку існує виграшна стратегія для другого гравця, який повинен залишати на столі число фішок, кратнеn + 1. Для цього на кожному ходу, якщо перший гравець береρфішок (0ρ< n + 1), другий повинен брати
n + 1 - ρфішок. Це число завжди позитивне, оскільки знаходиться на інтервалі від0доn.
2.Залишок від розподілу дорівнюєr(0 < r < n + 1).У цьому випадку існує виграшна стратегія для першого гравця. На першому ході він повинен взятиrфішок, залишивши на столі число фішок, кратнеn+1. Тепер він може діяти подібно до другого гравця з першого випадку. Іншими словами, якщо другий гравець береρфішок (0ρ< n + 1), перший повинен взятиn+1 - ρ.
Це загальне рішення застосовується до нескінченної безлічі ігор. Ви можете застосувати його для гри: на столі 2010 фішок, на кожному ходу можна брати від 1 до 49 фішок. Для якого гравця є виграшна стратегія? У чому вона полягає? Якщо ми змінимо правила і той, хто бере останню фішку, програватиме, то достатньо помітити наступне: для перемоги достатньо взяти передостанню фішку, залишивши на столі всього одну. В цьому випадкустратегія не зміниться, просто потрібно буде врахувати, що кількість фішок рівна
. для перемоги буде достатньо взяти передостанню фішку, залишивши на столі лише одну. У цьому випадку стратегія не зміниться, просто потрібно буде врахувати, що кількість фішок дорівнює
У цьому випадку якщо гравець бере останню фішку і програє, то визначення переваги трохи змінюється. від поділу.
Але тепер нам потрібні інші залишки від поділу. Якщо залишок0або від2доn - 1(1; n), то діє випадок2.Відповідно, якщо залишок1абоn, то діє випадок1.Всі ці випадки описані вище, але для них додається одна маленька деталь: тепер треба залишати на столі число фішок рівнеi + 1(i- це число кратнеn + 1).
Всі подібні ігри, в яких використовується лише одна група фішок, можна
вважати спрощеними варіантами гри Ним, про яку я напишу в наступному пості.