• Алгоритм міні-макс — це рекурсивний алгоритм, який використовується в процесі прийняття рішень і в теорії ігор. Він забезпечує оптимальний хід для гравця за умови, що суперник також грає оптимально.
• Алгоритм Mini-Max використовує рекурсію для пошуку в дереві гри.
• Алгоритм Min-Max здебільшого використовується для ігор в AI. Такі як шахи, шашки, хрестики-нулики, го та різноманітні ігри для гравців. Цей алгоритм обчислює мінімаксне рішення для поточного стану.
• У цьому алгоритмі в гру грають два гравці, один називається MAX, а інший — MIN.
• Обидва гравці борються з цим, оскільки гравець суперника отримує мінімальну вигоду, тоді як вони отримують максимальну вигоду.
• Обидва гравці гри є суперниками один одного, де MAX вибере максимальне значення, а MIN вибере мінімізоване значення.
• Алгоритм minimax виконує алгоритм пошуку в глибину для дослідження повного дерева гри.
• Алгоритм minimax продовжує весь шлях вниз до кінцевого вузла дерева, а потім повертається до дерева як рекурсія.

Псевдокод для алгоритму MinMax:

 function minimax(node, depth, maximizingPlayer) is if depth ==0 or node is a terminal node then return static evaluation of node if MaximizingPlayer then // for Maximizer Player maxEva= -infinity for each child of node do eva= minimax(child, depth-1, false) maxEva= max(maxEva,eva) //gives Maximum of the values return maxEva else // for Minimizer player minEva= +infinity for each child of node do eva= minimax(child, depth-1, true) minEva= min(minEva, eva) //gives minimum of the values return minEva 

Початковий виклик:

Мінімакс (вузол, 3, істина)

Робота алгоритму Min-Max:

• Роботу мінімаксного алгоритму легко описати на прикладі. Нижче ми взяли приклад дерева гри, яке представляє гру для двох гравців.
• У цьому прикладі є два гравці, один називається Maximizer, а інший — Minimizer.
• Maximizer намагатиметься отримати максимально можливий бал, а Minimizer намагатиметься отримати мінімально можливий бал.
• Цей алгоритм застосовує DFS, тому в цьому дереві гри ми повинні пройти весь шлях через листя, щоб досягти кінцевих вузлів.
• На кінцевому вузлі надаються кінцеві значення, тому ми будемо порівнювати ці значення та повертатися до дерева, доки не відбудеться початковий стан. Нижче наведено основні кроки, пов’язані з розв’язуванням дерева гри для двох гравців:

Крок 1: На першому кроці алгоритм генерує все дерево гри та застосовує функцію корисності, щоб отримати значення корисності для станів терміналу. На наведеній нижче діаграмі дерева візьмемо A — початковий стан дерева. Припустімо, що максимізатор виконує перший хід, який має початкове значення в найгіршому випадку =- нескінченність, а мінімізер виконує наступний хід, який має початкове значення в найгіршому випадку = +нескінченність.

крок 2: Тепер спочатку ми знаходимо значення утиліт для Maximizer, його початкове значення -∞, тому ми порівняємо кожне значення в термінальному стані з початковим значенням Maximizer і визначимо значення вищих вузлів. Серед усіх знайде максимум.

• Для вузла D max(-1,- -∞) => max(-1,4)= 4
• Для вузла E max(2, -∞) => max(2, 6)= 6
• Для вузла F max(-3, -∞) => max(-3,-5) = -3
• Для вузла G max(0, -∞) = max(0, 7) = 7

крок 3: На наступному кроці настає черга мінімізатора, тож він порівнює значення всіх вузлів із +∞ і знайде 3^rdзначення вузла шару.

• Для вузла B= min(4,6) = 4
• Для вузла C= min (-3, 7) = -3

крок 4: Тепер настала черга Maximizer, і він знову вибере максимальне значення з усіх вузлів і знайде максимальне значення для кореневого вузла. У цьому ігровому дереві є лише 4 шари, отже, ми відразу переходимо до кореневого вузла, але в реальних іграх буде більше ніж 4 шари.

• Для вузла A max(4, -3)= 4

Це був повний робочий процес мінімаксної гри для двох гравців.

Властивості алгоритму Mini-Max:

Повний-Алгоритм Min-Max завершено. Він точно знайде рішення (якщо воно існує) у скінченному дереві пошуку.Оптимально-Алгоритм Min-Max є оптимальним, якщо обидва суперники грають оптимально.Складність часу -Оскільки він виконує DFS для дерева гри, то часова складність алгоритму Min-Max становить O(b^м) , де b – коефіцієнт розгалуження ігрового дерева, а m – максимальна глибина дерева.Космічна складність-Просторова складність алгоритму Mini-max також подібна до DFS про .

Обмеження мінімаксного алгоритму:

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