logo

TechCodeview

Мінімаксний алгоритм в теорії ігор | Набір 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.> 

>

функція chr python 

>

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>