Мінімакс — це свого роду алгоритм відстеження, який використовується в процесі прийняття рішень і теорії ігор, щоб знайти оптимальний хід для гравця, припускаючи, що ваш опонент також грає оптимально. Він широко використовується в покрокових іграх для двох гравців, таких як Tic-Tac-Toe, Backgammon, Mancala, Chess тощо.
У Minimax два гравці називаються максимайзером і мінімізатором. The максимайзер намагається отримати якомога вищий бал, поки мінімізатор намагається зробити навпаки й отримати найменший бал.
Кожен стан дошки має значення, пов’язане з ним. У даному стані, якщо максимайзер має перевагу, тоді рахунок на дошці матиме деяке позитивне значення. Якщо мінімізатор має перевагу в такому стані дошки, тоді воно матиме деяке від’ємне значення. Значення дошки розраховуються за допомогою деяких евристик, які є унікальними для кожного типу гри.
приклад:
Розглянемо гру, яка має 4 кінцевих стани та шляхи досягнення кінцевого стану від кореня до 4 листків ідеального бінарного дерева, як показано нижче. Припустімо, що ви максимізуючий гравець і отримуєте перший шанс перейти, тобто ви на корені, а ваш опонент на наступному рівні. Який хід ви б зробили як максимізуючий гравець, враховуючи, що ваш суперник також грає оптимально?
Оскільки це алгоритм на основі відстеження, він пробує всі можливі рухи, потім повертається назад і приймає рішення.
- Максимізатор йде ЛІВОРУЧ: тепер черга мінімайзерів. Мінімізатор тепер має вибір між 3 і 5. Будучи мінімізатором, він точно вибере найменше з обох, тобто 3
- Максимізатор йде ВПРАВО: тепер черга мінімайзерів. Мінімізатор тепер має вибір між 2 і 9. Він вибере 2, оскільки це найменше серед двох значень.
Будучи максимізатором, ви вибрали б більше значення, яке дорівнює 3. Отже, оптимальним рухом для максимізатора є піти ВЛІВОРУЧ, а оптимальним значенням є 3.
Тепер дерево гри виглядає так:
Наведене вище дерево показує два можливі бали, коли максимайзер робить ліворуч і праворуч.
Примітка. Незважаючи на те, що в правому піддереві є значення 9, мінімізатор ніколи не вибере його. Треба завжди виходити з того, що суперник грає оптимально.
Нижче наведено реалізацію того самого.
C++
aws sns
// A simple C++ program to find> // maximum score that> // maximizing player can get.> #include> using> namespace> std;> // Returns the optimal value a maximizer can obtain.> // depth is current depth in game tree.> // nodeIndex is index of current node in scores[].> // isMax is true if current move is> // of maximizer, else false> // scores[] stores leaves of Game tree.> // h is maximum height of Game tree> int> minimax(>int> depth,>int> nodeIndex,>bool> isMax,> >int> scores[],>int> h)> {> >// Terminating condition. i.e> >// leaf node is reached> >if> (depth == h)> >return> scores[nodeIndex];> >// If current move is maximizer,> >// find the maximum attainable> >// value> >if> (isMax)> >return> max(minimax(depth+1, nodeIndex*2,>false>, scores, h),> >minimax(depth+1, nodeIndex*2 + 1,>false>, scores, h));> >// Else (If current move is Minimizer), find the minimum> >// attainable value> >else> >return> min(minimax(depth+1, nodeIndex*2,>true>, scores, h),> >minimax(depth+1, nodeIndex*2 + 1,>true>, scores, h));> }> // A utility function to find Log n in base 2> int> log2(>int> n)> {> >return> (n==1)? 0 : 1 + log2(n/2);> }> // Driver code> int> main()> {> >// The number of elements in scores must be> >// a power of 2.> >int> scores[] = {3, 5, 2, 9, 12, 5, 23, 23};> >int> n =>sizeof>(scores)/>sizeof>(scores[0]);> >int> h = log2(n);> >int> res = minimax(0, 0,>true>, scores, h);> >cout <<>'The optimal value is : '> << res << endl;> >return> 0;> }> |
>
>
Java
// A simple java program to find maximum score that> // maximizing player can get.> import> java.io.*;> class> GFG {> > // Returns the optimal value a maximizer can obtain.> // depth is current depth in game tree.> // nodeIndex is index of current node in scores[].> // isMax is true if current move is of maximizer, else false> // scores[] stores leaves of Game tree.> // h is maximum height of Game tree> >static> int> minimax(>int> depth,>int> nodeIndex,>boolean> isMax,> >int> scores[],>int> h)> {> >// Terminating condition. i.e leaf node is reached> >if> (depth == h)> >return> scores[nodeIndex];> >// If current move is maximizer, find the maximum attainable> >// value> >if> (isMax)> >return> Math.max(minimax(depth+>1>, nodeIndex*>2>,>false>, scores, h),> >minimax(depth+>1>, nodeIndex*>2> +>1>,>false>, scores, h));> >// Else (If current move is Minimizer), find the minimum> >// attainable value> >else> >return> Math.min(minimax(depth+>1>, nodeIndex*>2>,>true>, scores, h),> >minimax(depth+>1>, nodeIndex*>2> +>1>,>true>, scores, h));> }> // A utility function to find Log n in base 2> >static> int> log2(>int> n)> {> return> (n==>1>)?>0> :>1> + log2(n/>2>);> }> // Driver code> >public> static> void> main (String[] args) {> >// The number of elements in scores must be> >// a power of 2.> >int> scores[] = {>3>,>5>,>2>,>9>,>12>,>5>,>23>,>23>};> >int> n = scores.length;> >int> h = log2(n);> >int> res = minimax(>0>,>0>,>true>, scores, h);> >System.out.println(>'The optimal value is : '> +res);> > >}> }> // This code is contributed by vt_m> |
>
>
C#
// A simple C# program to find maximum score that> // maximizing player can get.> using> System;> public> class> GFG> {> > // Returns the optimal value a maximizer can obtain.> // depth is current depth in game tree.> // nodeIndex is index of current node in scores[].> // isMax is true if current move is of maximizer, else false> // scores[] stores leaves of Game tree.> // h is maximum height of Game tree> static> int> minimax(>int> depth,>int> nodeIndex,>bool> isMax,> >int> []scores,>int> h)> {> >// Terminating condition. i.e leaf node is reached> >if> (depth == h)> >return> scores[nodeIndex];> >// If current move is maximizer, find the maximum attainable> >// value> >if> (isMax)> >return> Math.Max(minimax(depth+1, nodeIndex*2,>false>, scores, h),> >minimax(depth+1, nodeIndex*2 + 1,>false>, scores, h));> >// Else (If current move is Minimizer), find the minimum> >// attainable value> >else> >return> Math.Min(minimax(depth+1, nodeIndex*2,>true>, scores, h),> >minimax(depth+1, nodeIndex*2 + 1,>true>, scores, h));> }> // A utility function to find Log n in base 2> static> int> log2(>int> n)> {> >return> (n==1)? 0 : 1 + log2(n/2);> }> // Driver code> static> public> void> Main ()> {> >// The number of elements in scores must be> >// a power of 2.> >int> []scores = {3, 5, 2, 9, 12, 5, 23, 23};> >int> n = scores.Length;> >int> h = log2(n);> >int> res = minimax(0, 0,>true>, scores, h);> >Console.WriteLine(>'The optimal value is : '> +res);> > }> }> // This code is contributed by ajit.> |
>
javascript onclick
>
Python3
# A simple Python3 program to find> # maximum score that> # maximizing player can get> import> math> def> minimax (curDepth, nodeIndex,> >maxTurn, scores,> >targetDepth):> ># base case : targetDepth reached> >if> (curDepth>=>=> targetDepth):> >return> scores[nodeIndex]> > >if> (maxTurn):> >return> max>(minimax(curDepth>+> 1>, nodeIndex>*> 2>,> >False>, scores, targetDepth),> >minimax(curDepth>+> 1>, nodeIndex>*> 2> +> 1>,> >False>, scores, targetDepth))> > >else>:> >return> min>(minimax(curDepth>+> 1>, nodeIndex>*> 2>,> >True>, scores, targetDepth),> >minimax(curDepth>+> 1>, nodeIndex>*> 2> +> 1>,> >True>, scores, targetDepth))> > # Driver code> scores>=> [>3>,>5>,>2>,>9>,>12>,>5>,>23>,>23>]> treeDepth>=> math.log(>len>(scores),>2>)> print>(>'The optimal value is : '>, end>=> '')> print>(minimax(>0>,>0>,>True>, scores, treeDepth))> # This code is contributed> # by rootshadow> |
>
>
Javascript
безкоштовний ipconfig
> // Javascript program to find maximum score that> // maximizing player can get.> // Returns the optimal value a maximizer can obtain.> // depth is current depth in game tree.> // nodeIndex is index of current node in scores[].> // isMax is true if current move is of maximizer, else false> // scores[] stores leaves of Game tree.> // h is maximum height of Game tree> >function> minimax(depth, nodeIndex, isMax,> >scores, h)> {> >// Terminating condition. i.e leaf node is reached> >if> (depth == h)> >return> scores[nodeIndex];> > >// If current move is maximizer, find the maximum attainable> >// value> >if> (isMax)> >return> Math.max(minimax(depth+1, nodeIndex*2,>false>, scores, h),> >minimax(depth+1, nodeIndex*2 + 1,>false>, scores, h));> > >// Else (If current move is Minimizer), find the minimum> >// attainable value> >else> >return> Math.min(minimax(depth+1, nodeIndex*2,>true>, scores, h),> >minimax(depth+1, nodeIndex*2 + 1,>true>, scores, h));> }> > // A utility function to find Log n in base 2> >function> log2(n)> {> return> (n==1)? 0 : 1 + log2(n/2);> }> > // Driver Code> >// The number of elements in scores must be> >// a power of 2.> >let scores = [3, 5, 2, 9, 12, 5, 23, 23];> >let n = scores.length;> >let h = log2(n);> >let res = minimax(0, 0,>true>, scores, h);> >document.write(>'The optimal value is : '> +res);> > > > |
>
>
Вихід:
The optimal value is: 12>
Часова складність: O(b^d) b — коефіцієнт розгалуження, а d — кількість глибини або шару графа чи дерева.
Космічна складність: O(bd), де b — коефіцієнт розгалуження на d — максимальна глибина дерева, подібного до DFS.
Ідея цієї статті полягає в тому, щоб представити Minimax на простому прикладі.
- У наведеному вище прикладі для гравця є лише два варіанти. Загалом, варіантів може бути більше. У цьому випадку нам потрібно повторити для всіх можливих ходів і знайти максимум/мінімум. Наприклад, в Tic-Tac-Toe перший гравець може зробити 9 можливих ходів.
- У наведеному вище прикладі бали (листя дерева гри) надано нам. Для типової гри нам потрібно отримати ці значення
Незабаром ми розглянемо Tic Tac Toe з алгоритмом Minimax.
Цю статтю надав Акшай Л. Арадх'я.