Виявляється, старенька завдання, але я про неї ще не чув. Запозичена в ЖЖ.
Дано: Кащей Безсмертний, який вкрав принцесу у Івана Царевича. І власне, Іван Царевич, який наречену хоче повернути.
Кащея вбити можна. Є 10 колодязів з отрутою, сила отрути від колодязя до колодязя поступово наростає. Більш сильна отрута є протиотрутою для слабшого (якщо випити спочатку з 2 колодязя, а потім з 3 - отруєння не буде). Якщо змішати два отрути, то суміш придбає властивості найсильнішого.
Сама битва: суперники приходять на ристалище з одним кубком в руках. Віддають кубок противнику, який випиває вміст. Але негідник Кащей побудував навколо останнього 10 колодязя фортеця, яка неприступна для Івана. Таким чином, у Кащея є доступ до найсильнішого отрути, а у Івана немає.
Мета: перемогти Кащея і вижити самому.
Можете подумати, а можете відразу заглянути у відповідь до мене.
Коли я вперше прочитав завдання, я подумав, що це як раз для теорії ігор і таблиць минимакса. Але спочатку треба було здогадатися про всі дії, які можуть зробити гравці. Я розділив ці дії на чотири групи:
- Випити щось перед боєм (або не пити нічого перед боєм)
- Запропонувати супернику якийсь кубок (в кубку може бути отрута з колодязів, або нешкідлива рідина, але за смаком якої неможливо визначити отруту це чи ні)
- Змішати вміст кубка суперника з чимось (або не змішувати ні з чим), потім випити
- Випити щось після бою (або не пити нічого після бою)
Відповідно, Кащей може використовувати для кожної групи дій отрута з 10 колодязів, а Іван тільки з 9. Отримуємо всі можливі дії і підраховуємо минимакс в програмі.
У грі у Івана 10000 можливостей, у Кащея 14641
Складаємо таблицю минимакса ...
Рішення
Іван
перед ареною випити отруту DRINK_1,
дати супернику кубок з отрутою GIVE_9,
самому змішати даний суперником кубок з отрутою MIX_2,
а потім запити отрутою NOTHING
Отже, Іван п'є отруту з першого колодязя, підносить супернику кубок з 9-м отрутою, а сам змішує вміст кубка від Кащея з отрутою з другого колодязя, випиває і залишається живий. Подивимося на ситуацію з боку Кащея:
Кащей
перед ареною випити отруту NOTHING,
дати супернику кубок з отрутою GIVE_9,
самому змішати даний суперником кубок з отрутою MIX_1,
а потім запити отрутою DRINK_10
Володіючи найсильнішим протиотрутою, Кащей боїться тільки того, що йому Іван піднесе нешкідливу рідину, і тоді випивши 10-й отрута, він програє. Щоб переконатися в тому, що підношення Івана містить отруту, він просто додає перший отрута в кубок і запиває своїм протиотрутою. Звернемо увагу, на те, що комп'ютер на місці Кащея запропонував видати 9-й кубок Івану, а не 10-й. У цьому немає ніякої прихованої логіки, просто зіграв роль порядок оцінки дій комп'ютером. 10-й отрута зіграв би так само.
А тепер ми зіставимо цим дві тактики один одному. Ось, що видав комп'ютер:
Шанси Івана на виживання при розумному дії Кащея: вижив
Шанси Кащея на виживання при розумному дії Івана: вижив
Отже, вибравши кращі стратегії, обидва персонажі залишаються живі. Але Іван не досягає своєї мети - принцеси. Тоді, може, є така тактика, коли один з персонажів помре? Слово комп'ютера:
Помре чи Іван, якщо Кащей обере будь-який інший варіант дій, а сам буде дотримуватися розумної стратегії: немає
Помре чи Кащей, якщо Іван обере будь-який інший варіант дій, а сам буде дотримуватися розумної стратегії: немає
Таким чином, з тим же успіхом, Кащей з Іваном могли б випити пива один з одним. Або напоїти принцесу якимось отрутою. Все одно, жоден з них в результаті цієї гри не отримає бажаного результату.
Тепер подивимося, чи змінилося що-небудь, якщо Кащей і Іван були б в однакових умовах і мали б рівний доступ до всіх 10 криниць. Стратегія їх обох виглядала б так:
перед ареною випити отруту DRINK_1,
дати супернику кубок з отрутою GIVE_10,
самому змішати даний суперником кубок з отрутою MIX_2,
а потім запити отрутою NOTHING
У цій ситуації у них у обох була б одна стратегія, близька до стратегії Івана. Знову ж таки, все приводиться до нічиєї: обидва виживуть. Таким чином, зусилля Кащея з будівництва фортеці навколо 10-го колодязя не мають ніякого сенсу. Тим краще для Івана, оскільки, це доводить нерозумність Кащея.
Іван - чесний і добрий малий, тому він ніколи не повинен порушувати правила. А ось Кащей - хитрюга, тому подумаємо ще трохи за нього.
Взагалі, завдання зводиться до нічиєї, навіть якщо для Івана залишаться два найслабших колодязя, а решта вісім будуть оточені фортецями Кащея. Будувати фортеці в такій кількості, очевидно, не було можливим для Кащея через витрат на проект. Але якщо подумати, то поставивши фортеця, скажімо, на 8-му колодязі, Кащей забезпечує собі беззастережну перемогу, але з маленькою хитрістю. Він не говорить про це Івану, але підступно переливає з 10-го колодязя склянки в колодязі з першого по сьомий і дев'ятий. Через властивостей отрути, в дев'яти колодязях з десяти буде найсильніший отрута, а найслабший отрута - восьмий буде у Кащея. Запускаємо програму:
У грі у Івана 10000 можливостей, у Кащея 14641
Складаємо таблицю минимакса ...
Рішення
Іван
перед ареною випити отруту DRINK_1,
дати супернику кубок з отрутою GIVE_10,
самому змішати даний суперником кубок з отрутою MIX_2,
а потім запити отрутою NOTHING
Кащей
перед ареною випити отруту DRINK_8,
дати супернику кубок з отрутою GIVE_1,
самому змішати даний суперником кубок з отрутою MIX_1,
а потім запити отрутою NOTHING
Шанси Івана на виживання при розумному дії Кащея: помер
Шанси Кащея на виживання при розумному дії Івана: вижив
Помре чи Іван, якщо Кащей обере будь-який інший варіант дій, а сам буде дотримуватися розумної стратегії: так
Помре чи Кащей, якщо Іван обере будь-який інший варіант дій, а сам буде дотримуватися розумної стратегії: немає
Резюме. плануйте бюджети правильно, мої підступні.
Вихідний код програми, яка становить таблицю минимакса.