Алгоритм для вирішення складних завдань у теорії – мінімакс

Мінімакс – метод, що сприяє визначенню оптимального вибору в невигідній ситуації.

Сьогодні вас чекає алгоритм для вирішення складних завдань у теорії ігор – від теорії до практики.

Під час дослідження теорії ігор у нашій минулій статті було з’ясовано:

• Теорія ігор – ключовий фундамент, без якого подальші кроки ускладнюються.
• Теорія ігор – арсенал інструментів для прийняття раціональних, обдуманих та точних рішень, а також для розуміння даних.
• У грі, яку ми аналізуємо, обов’язково беруть участь щонайменше два учасники. Кожен з них має власні інтереси та варіанти дій.
• Рішення приймається на підставі інформації про дії інших учасників.
• Існують загальноприйняті правила, доступні всім.

Більшість повсякденних ситуацій можна розглядати з точки зору теорії ігор. Навіть звичайні розмови про зарплату чи місце для відпустки підпадають під вплив теорії ігор.

Отже, існує алгоритм, що дозволяє знаходити оптимальні рішення навіть у складних ситуаціях. Цей алгоритм має назву “правило мінімакс”.

Мінімакс: стратегія

У теорії ігор завдання кожного гравця полягає у пошуку стратегії, що максимізує його вигоду.

Теорія ігор можна розділити на ігри з нульовою та ненульовою сумою. Гра з нульовою сумою означає, що виграш одного буде програшем для всіх інших гравців. Багато класичних ігор та життєвих ситуацій належать до ігор з нульовою сумою. Це означає, що кожен гравець прагне покращити свою позицію, водночас погіршуючи позицію інших гравців.

Якщо гравець розуміє, що дії інших можуть негативно вплинути на його позицію, йому потрібна стратегія, що зменшує цей вплив та мінімізує втрати. Для цього використовується правило мінімакс.

Правило мінімаксу

Щоб зрозуміти, як функціонує правило мінімаксу, необхідно зрозуміти логіку гравців:

1. У деяких іграх поразка виражається числом, наприклад, грошовою втратою після гри. В інших випадках поразка просто вказує, хто переміг і хто програв.
2. Кожен інший гравець робить рішення, що можуть збільшити вашу максимальну можливу втрату. Наприклад, через його дії ви можете втратити 10 або 500 очок. Максимальна можлива втрата в цьому випадку – 500 очок.
3. Мета полягає в тому, щоб на кожному кроці приймати рішення, що зменшує цю втрату. Інакше кажучи, навіть якщо втрата відбувається, то не 500, а 10 – мінімальна з можливих варіантів.

Правило мінімаксу визначає стратегію, що мінімізує максимально можливу втрату. Ознака такої стратегії виглядає так:

Це найкраща мінімаксна стратегія, бо найгірший можливий варіант в ній значно кращий за найгірший в інших стратегіях.

Алгоритм в дії

Розгляньмо алгоритм мінімаксу на прикладі гри в хрестики-нулики. Для перемоги треба скласти лінію по горизонталі, вертикалі чи діагоналі. Враховуючи це, створимо алгоритм для гравця, який ходить другим:

1. Перший гравець розміщує хрестик у будь-якій клітині поля. Всього 9 клітин, одна зайнята, залишилося 8.
2. Ми послідовно розглядаємо всі можливі клітини, де можна розмістити нулик, і оцінюємо ситуацію – чи перемагаємо ми, чи програємо. Якщо неясно, переходимо на нову ситуацію та виконуємо такий же алгоритм.
3. Цей процес триває, доки всі клітини не заповняться – отримаємо багато можливих варіантів та розгалужень.
4. Для успішних варіантів, ми додаємо певну кількість балів за кожен наш хід до конкретної клітини, а для програшних – віднімаємо таку ж кількість.
5. Після таких розрахунків ми отримуємо оцінку для кожної з 8 вільних клітин.
6. Нарешті, вибираємо клітину з найвищими балами для наступного ходу і розміщуємо нулик там.

Отже, ми рекурсивно розглядаємо всі можливі ходи (або до певної глибини вкладеності, якщо ресурсів не вистачає), оцінюємо результати для кожної клітини. Таким чином, обираємо клітину, яка найкраще підходить для нашої стратегії.

Для охочих створити власну гру – запрошуємо на курси програмування від IT школи GoMother. В залежності від віку дитини та бажаного кінцевого результату ми підберемо оптимальну мову програмування.

Мінімакс: як працює цей принцип у реальному житті

Уявіть, що в невеликому місті є три різні продуктові магазини, і кожен з них прагне максимізувати свій прибуток. Мета полягає у тому, щоб покупці обирали саме його магазин. Одним із логічних рішень може бути зменшення цін на основні продукти, щоб залучити клієнтів. Клієнти, які прийшли по хліб і молоко, можуть придбати інші товари.

Проте продавець усвідомлює, що конкуренти можуть зробити теж саме або запропонувати інші акції та зниження цін на інші товари. Це означає, що продавцю доведеться реагувати, щоб зберегти свою позицію лідера та утримати більшість клієнтів у себе. Отже, конкуренти також робитимуть свої кроки.

Якщо продавець має дані про продаж, релевантні показники та цифри, він може розрахувати кілька варіантів розвитку подій з певною глибиною, наприклад, на 2-4 ходи вперед з урахуванням конкурентів. Потім він аналізує найпоширеніші рішення і вибирає ті, які приносять найбільший результат. Це оптимальний крок у боротьбі за клієнтів.

Ця стратегія називається максимінним алгоритмом. Суть у тому, щоби максимізувати мінімально можливий виграш.

Застосування в галузі інформаційних технологій

Мінімаксний алгоритм знаходить застосування у широкому спектрі ігор, де комп’ютер повинен приймати рішення, оптимальні йому, з невизначених дій гравця. Це можуть бути як класичні ігри, наприклад, шашки або аркади, так і прикладні випадки: вибір найкращої угоди, визначення поведінкової моделі для успішного проходження відбору або дії в ситуаціях, які неможливо передбачити заздалегідь.

У наступному розділі ми перевіримо роботу правила мінімаксу на практиці – створимо гру “хрестики-нулики” та навчимо комп’ютер вибирати оптимальні ходи. Тож слідкуйте за оновленнями на нашому сайті та підписуйтесь на наш Instagram!