У теорії ігор мінімакс - це метод, який спрямований на мінімізацію очікуваних втрат. Для цього гравець припускає, що рішення, прийняте його опонентом, буде несприятливим. Тобто, найгірший сценарій очікується до руху суперника.
Іншими словами, метод мінімаксу складається з того, як прийняти найкраще рішення, припускаючи, що інший гравець вибере для вас найгірший сценарій.
Ми повинні взяти до уваги, що цей метод застосовний у грі для двох осіб (двоє гравців) і що це не кооператив, а гра з нульовою сумою. Це означає, що те, що виграє один гравець, втрачає інший і навпаки. Отже, кожен агент буде зацікавлений у максимізації власної корисності, навіть якщо це зашкодить іншому.
На цьому етапі ми також повинні пам’ятати, що теорія ігор - це розділ математики та економіки, який вивчає вибір, який оптимізує ситуацію людини, коли витрати та вигоди не фіксуються заздалегідь, а залежать від рішень інших.
Алгоритм мінімаксу в дереві рішень
Ми можемо побачити, як метод мінімакс застосовується в дереві рішень з кількома вузлами. Гра починається знизу і закінчується результатом на верхньому рівні.
Біля основи дерева суперник робить перший хід, тому очікується найгірший результат. Тоді, на другому рівні, гравець x повинен прагнути максимізувати свій прибуток, беручи до уваги рішення, прийняте раніше противником.
На третьому рівні знову черга суперника тощо. Нижче ми покажемо приклад.
Приклад алгоритму мінімаксу
У наступному дереві рішень ми показуємо результати, отримані гравцем х у кожен момент гри. Біля основи, на першому рівні, суперник приймає рішення. З цієї причини наведені сценарії, в яких гравець може програти -10 або виграти 5.
На другому рівні це залежить від гравця x, тому він максимізує свій прибуток. Якщо ви програєте 10 або виграєте 1, ви виграєте 1. Так само, між 5 або 7 ви виграєте 7.
Потім знову настає черга суперника, тому будуть наведені сценарії, в яких гравець x має найгірший результат, -3 та 4, залежно від випадку. Нарешті, між програшем 3 або перемогою 4 гравець x прийме рішення, яке дозволить останньому.
Ми повинні взяти до уваги, що значення кожного вузла будуть залежати від функції корисності.
Щоб краще зрозуміти дерево, припустимо, що в основі рішення лежить розподіл продукту. Конкурент (супротивник) може передавати розподіл на зовнішнє замовлення (див. Ліву сторону дерева). У цьому випадку він повинен вибрати, наприклад, між дилером А та Б. Таким чином, він вибирає першого, внаслідок чого гравець x втрачає 10 (якщо він вибрав B, гравець x виграє 12).
Однак, можливо, супротивник воліє поширювати свої товари сам, маючи можливість найняти моторизовані транспортні засоби або придбати вантажівку. З обох сценаріїв виберіть перший, який менш приємний для гравця x, оскільки він виграє 5, а не 10.