logo

TechCodeview

Іт Проблеми Та Рішення

Мінімаксний алгоритм в теорії ігор | Набір 4 (альфа-бета обрізка)

Мінімаксний алгоритм в теорії ігор | Набір 4 (альфа-бета обрізка)

Передумови: Мінімаксний алгоритм в теорії ігор , Функція оцінки в теорії ігор
Альфа-бета-відсікання насправді не є новим алгоритмом, а радше технікою оптимізації мінімаксного алгоритму. Це значно скорочує час обчислень. Це дозволяє нам шукати набагато швидше і навіть переходити на глибші рівні в дереві гри. Він обрізає гілки в дереві гри, які не потрібно шукати, оскільки вже існує кращий доступний хід. Це називається скороченням альфа-бета, оскільки воно передає 2 додаткові параметри у функції minimax, а саме альфа та бета.

Давайте визначимо параметри альфа і бета.

Альфа це найкраще значення, яке максимайзер наразі може гарантувати на цьому рівні або вище.
Бета це найкраще значення, яке мінімізатор наразі може гарантувати на цьому рівні або нижче.

Псевдокод: 

 function minimax(node, depth, isMaximizingPlayer, alpha, beta): if node is a leaf node : return value of the node if isMaximizingPlayer : bestVal = -INFINITY for each child node : value = minimax(node, depth+1, false, alpha, beta) bestVal = max( bestVal, value) alpha = max( alpha, bestVal) if beta  <= alpha: break return bestVal else : bestVal = +INFINITY for each child node : value = minimax(node, depth+1, true, alpha, beta) bestVal = min( bestVal, value) beta = min( beta, bestVal) if beta  <= alpha: break return bestVal 
 // Calling the function for the first time. minimax(0, 0, true, -INFINITY, +INFINITY)

Прояснимо наведений вище алгоритм на прикладі.

Альфа Бета Обрізка

  • Початковий виклик починається з А . Значення альфа тут таке -НЕСКІНЧЕННІСТЬ а значення бета становить +БЕЗКОНЕЧНІСТЬ . Ці значення передаються до наступних вузлів дерева. на А максимізатор повинен вибрати max Б і C , так А дзвінки Б перший
  • на Б це мінімізатор повинен вибрати min Д і І а отже і дзвінки Д перший.
  • на Д , він дивиться на свого лівого дочірнього елемента, який є листовим вузлом. Цей вузол повертає значення 3. Тепер значення alpha at Д є max(-INF, 3), що дорівнює 3.
  • Щоб вирішити, чи варто дивитися на правий вузол, він перевіряє умову beta <=alpha. Це невірно, оскільки beta = +INF і alpha = 3. Тому пошук продовжується.
    • D тепер переглядає праву дочірню частину, яка повертає значення 5.At Д , alpha = max(3, 5), що дорівнює 5. Тепер значення node Д дорівнює 5 D повертає значення 5 до Б . на Б , beta = min( +INF, 5), що дорівнює 5. Мінімізатор тепер гарантовано має значення 5 або менше. Б зараз дзвонить І щоб побачити, чи зможе він отримати значення менше 5.
  • на І значення альфа та бета не є -INF та +INF, а натомість -INF та 5 відповідно, оскільки значення бета було змінено на Б і ось що Б передано І
  • Зараз І дивиться на свою ліву дитину, якій 6. At І , alpha = max(-INF, 6), що дорівнює 6. Тут умова стає істинною. бета дорівнює 5, а альфа – 6. Отже, бета <=альфа вірно. Звідси ламається і І повертає 6 до Б
  • Зауважте, що це не мало значення І Права дитина. Це могло бути +INF або -INF, це все одно не мало б значення. Нам навіть не доводилося на це дивитися, тому що мінімізатор мав гарантоване значення 5 або менше. Отже, як тільки максимізатор побачив 6, він знав, що мінімайзер ніколи не піде сюди, оскільки він може отримати 5 ліворуч Б . Таким чином нам не потрібно було дивитися на ці 9 і, отже, заощадити час обчислень.
    • E повертає значення від 6 до Б . на Б , бета = min( 5, 6), що дорівнює 5. Значення node Б також 5

Поки що ось так виглядає наше ігрове дерево. 9 викреслено, оскільки його ніколи не обчислювали.

Альфа-бета-обрізка 2

    B повертає 5 до А . на А , alpha = max( -INF, 5), що дорівнює 5. Тепер максимізатор гарантує значення 5 або більше. А зараз дзвонить C щоб побачити, чи може він отримати більше значення, ніж 5.
  • на C , альфа = 5 і бета = +INF. C дзвінки Ф
  • на Ф , альфа = 5 і бета = +INF. Ф дивиться на свого лівого дочірнього елемента, який є 1. alpha = max( 5, 1), який все ще дорівнює 5.
    • F дивиться на правий дочірній елемент, який є 2. Отже, найкращим значенням цього вузла є 2. Альфа все ще залишається 5. F повертає значення 2 до C . на C , бета = хв (+INF, 2). Умова beta <= alpha стає істинною, якщо beta = 2 і alpha = 5. Таким чином, вона порушується, і їй навіть не потрібно обчислювати все піддерево Г .
  • Інтуїція, що стоїть за цим розривом, полягає в тому, що в C мінімізатор мав гарантоване значення 2 або менше. Але максимайзеру вже гарантовано значення 5, якщо він вибере Б . Тож навіщо максимайзеру вибирати C і отримати значення менше 2 ? Знову ж таки ви бачите, що не має значення, якими були останні 2 значення. Ми також заощадили багато обчислень, пропустивши ціле піддерево.
    • Тепер C повертає значення від 2 до А . Тому найкраще значення в А є max( 5, 2), що є 5.
  • Отже, оптимальне значення, яке може отримати максимізатор, дорівнює 5

Ось так виглядає наше фінальне дерево гри. Як ви можете бачити Г було викреслено, оскільки воно ніколи не обчислювалося.

Альфа-бета-обрізка 3

CPP




// C++ program to demonstrate> // working of Alpha-Beta Pruning> #include> using> namespace> std;> // Initial values of> // Alpha and Beta> const> int> MAX = 1000;> const> int> MIN = -1000;> // Returns optimal value for> // current player(Initially called> // for root and maximizer)> int> minimax(> int> depth,> int> nodeIndex,> > bool> maximizingPlayer,> > int> values[],> int> alpha,> > int> beta)> {> > > // Terminating condition. i.e> > // leaf node is reached> > if> (depth == 3)> > return> values[nodeIndex];> > if> (maximizingPlayer)> > {> > int> best = MIN;> > // Recur for left and> > // right children> > for> (> int> i = 0; i <2; i++)> > {> > > int> val = minimax(depth + 1, nodeIndex * 2 + i,> > false> , values, alpha, beta);> > best = max(best, val);> > alpha = max(alpha, best);> > // Alpha Beta Pruning> > if> (beta <= alpha)> > break> ;> > }> > return> best;> > }> > else> > {> > int> best = MAX;> > // Recur for left and> > // right children> > for> (> int> i = 0; i <2; i++)> > {> > int> val = minimax(depth + 1, nodeIndex * 2 + i,> > true> , values, alpha, beta);> > best = min(best, val);> > beta = min(beta, best);> > // Alpha Beta Pruning> > if> (beta <= alpha)> > break> ;> > }> > return> best;> > }> }> // Driver Code> int> main()> {> > int> values[8] = { 3, 5, 6, 9, 1, 2, 0, -1 };> > cout < <> 'The optimal value is : '> < < minimax(0, 0,> true> , values, MIN, MAX);;> > return> 0;> }>

Java




// Java program to demonstrate> // working of Alpha-Beta Pruning> import> java.io.*;> class> GFG {> // Initial values of> // Alpha and Beta> static> int> MAX => 1000> ;> static> int> MIN = -> 1000> ;> // Returns optimal value for> // current player (Initially called> // for root and maximizer)> static> int> minimax(> int> depth,> int> nodeIndex,> > Boolean maximizingPlayer,> > int> values[],> int> alpha,> > int> beta)> {> > // Terminating condition. i.e> > // leaf node is reached> > if> (depth ==> 3> )> > return> values[nodeIndex];> > if> (maximizingPlayer)> > {> > int> best = MIN;> > // Recur for left and> > // right children> > for> (> int> i => 0> ; i <> 2> ; i++)> > {> > int> val = minimax(depth +> 1> , nodeIndex *> 2> + i,> > false> , values, alpha, beta);> > best = Math.max(best, val);> > alpha = Math.max(alpha, best);> > // Alpha Beta Pruning> > if> (beta <= alpha)> > break> ;> > }> > return> best;> > }> > else> > {> > int> best = MAX;> > // Recur for left and> > // right children> > for> (> int> i => 0> ; i <> 2> ; i++)> > {> > > int> val = minimax(depth +> 1> , nodeIndex *> 2> + i,> > true> , values, alpha, beta);> > best = Math.min(best, val);> > beta = Math.min(beta, best);> > // Alpha Beta Pruning> > if> (beta <= alpha)> > break> ;> > }> > return> best;> > }> }> > // Driver Code> > public> static> void> main (String[] args)> > {> > > int> values[] = {> 3> ,> 5> ,> 6> ,> 9> ,> 1> ,> 2> ,> 0> , -> 1> };> > System.out.println(> 'The optimal value is : '> +> > minimax(> 0> ,> 0> ,> true> , values, MIN, MAX));> > > }> }> // This code is contributed by vt_m.>

Python3




# Python3 program to demonstrate> # working of Alpha-Beta Pruning> # Initial values of Alpha and Beta> MAX> ,> MIN> => 1000> ,> -> 1000> # Returns optimal value for current player> #(Initially called for root and maximizer)> def> minimax(depth, nodeIndex, maximizingPlayer,> > values, alpha, beta):> > > # Terminating condition. i.e> > # leaf node is reached> > if> depth> => => 3> :> > return> values[nodeIndex]> > if> maximizingPlayer:> > > best> => MIN> > # Recur for left and right children> > for> i> in> range> (> 0> ,> 2> ):> > > val> => minimax(depth> +> 1> , nodeIndex> *> 2> +> i,> > False> , values, alpha, beta)> > best> => max> (best, val)> > alpha> => max> (alpha, best)> > # Alpha Beta Pruning> > if> beta <> => alpha:> > break> > > return> best> > > else> :> > best> => MAX> > # Recur for left and> > # right children> > for> i> in> range> (> 0> ,> 2> ):> > > val> => minimax(depth> +> 1> , nodeIndex> *> 2> +> i,> > True> , values, alpha, beta)> > best> => min> (best, val)> > beta> => min> (beta, best)> > # Alpha Beta Pruning> > if> beta <> => alpha:> > break> > > return> best> > # Driver Code> if> __name__> => => '__main__'> :> > > values> => [> 3> ,> 5> ,> 6> ,> 9> ,> 1> ,> 2> ,> 0> ,> -> 1> ]> > print> (> 'The optimal value is :'> , minimax(> 0> ,> 0> ,> True> , values,> MIN> ,> MAX> ))> > # This code is contributed by Rituraj Jain>

C#




// C# program to demonstrate> // working of Alpha-Beta Pruning> using> System;> > class> GFG> {> // Initial values of> // Alpha and Beta> static> int> MAX = 1000;> static> int> MIN = -1000;> // Returns optimal value for> // current player (Initially called> // for root and maximizer)> static> int> minimax(> int> depth,> int> nodeIndex,> > Boolean maximizingPlayer,> > int> []values,> int> alpha,> > int> beta)> {> > // Terminating condition. i.e> > // leaf node is reached> > if> (depth == 3)> > return> values[nodeIndex];> > if> (maximizingPlayer)> > {> > int> best = MIN;> > // Recur for left and> > // right children> > for> (> int> i = 0; i <2; i++)> > {> > int> val = minimax(depth + 1, nodeIndex * 2 + i,> > false> , values, alpha, beta);> > best = Math.Max(best, val);> > alpha = Math.Max(alpha, best);> > // Alpha Beta Pruning> > if> (beta <= alpha)> > break> ;> > }> > return> best;> > }> > else> > {> > int> best = MAX;> > // Recur for left and> > // right children> > for> (> int> i = 0; i <2; i++)> > {> > > int> val = minimax(depth + 1, nodeIndex * 2 + i,> > true> , values, alpha, beta);> > best = Math.Min(best, val);> > beta = Math.Min(beta, best);> > // Alpha Beta Pruning> > if> (beta <= alpha)> > break> ;> > }> > return> best;> > }> }> // Driver Code> public> static> void> Main (String[] args)> {> > > int> []values = {3, 5, 6, 9, 1, 2, 0, -1};> > Console.WriteLine(> 'The optimal value is : '> +> > minimax(0, 0,> true> , values, MIN, MAX));> }> }> // This code is contributed by 29AjayKumar>

Javascript




> // Javascript program to demonstrate> // working of Alpha-Beta Pruning> // Initial values of> // Alpha and Beta> let MAX = 1000;> let MIN = -1000;> // Returns optimal value for> // current player (Initially called> // for root and maximizer)> function> minimax(depth,nodeIndex,maximizingPlayer,values,alpha,beta)> {> > // Terminating condition. i.e> > // leaf node is reached> > if> (depth == 3)> > return> values[nodeIndex];> > > if> (maximizingPlayer)> > {> > let best = MIN;> > > // Recur for left and> > // right children> > for> (let i = 0; i <2; i++)> > {> > let val = minimax(depth + 1, nodeIndex * 2 + i,> > false> , values, alpha, beta);> > best = Math.max(best, val);> > alpha = Math.max(alpha, best);> > > // Alpha Beta Pruning> > if> (beta <= alpha)> > break> ;> > }> > return> best;> > }> > else> > {> > let best = MAX;> > > // Recur for left and> > // right children> > for> (let i = 0; i <2; i++)> > {> > > let val = minimax(depth + 1, nodeIndex * 2 + i,> > true> , values, alpha, beta);> > best = Math.min(best, val);> > beta = Math.min(beta, best);> > > // Alpha Beta Pruning> > if> (beta <= alpha)> > break> ;> > }> > return> best;> > }> }> // Driver Code> let values=[3, 5, 6, 9, 1, 2, 0, -1];> document.write(> 'The optimal value is : '> +> > minimax(0, 0,> true> , values, MIN, MAX));> // This code is contributed by rag2127> >

Вихід 

The optimal value is : 5


Поділитися

Вам Може Сподобатися

85 найпоширеніших прізвищ у світі

85 найпоширеніших прізвищ у світі

Як перетворити словник Python на JSON?

Як перетворити словник Python на JSON?

Кращі Статті

Категорія

Блог Перетворення Java Математика Колекції Java Відмінності Рядок Java

Цікаві Статті