Predpoklady: Minimax algoritmus v teórii hier , Funkcia hodnotenia v teórii hier
Alfa-Beta prerezávanie nie je v skutočnosti nový algoritmus, ale skôr optimalizačná technika pre minimax algoritmus. Výrazne znižuje čas výpočtu. To nám umožňuje hľadať oveľa rýchlejšie a dokonca ísť do hlbších úrovní v strome hry. Odreže vetvy v strome hry, ktoré netreba hľadať, pretože už existuje lepší dostupný ťah. Volá sa prerezávanie Alpha-Beta, pretože vo funkcii minimax odovzdáva 2 ďalšie parametre, a to alfa a beta.

Definujme parametre alfa a beta.

Alfa je najlepšia hodnota, ktorá maximalizátor v súčasnosti môže garantovať na tejto úrovni alebo vyššej.
Beta je najlepšia hodnota, ktorá minimalizátor v súčasnosti môže garantovať na tejto alebo nižšej úrovni.

Pseudokód:

 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) 

Vysvetlíme si vyššie uvedený algoritmus na príklade.

• Počiatočný hovor začína od A . Tu je hodnota alfa -NEKONEČNO a hodnota beta je + NEKONEČNO . Tieto hodnoty sa prenášajú do nasledujúcich uzlov v strome. o A maximalizátor musí zvoliť max B a C , takže A hovory B najprv
• o B minimalizátor musí zvoliť min D a A a teda volania D najprv.
• o D , pozerá sa na svoje ľavé dieťa, ktorým je listový uzol. Tento uzol vráti hodnotu 3. Teraz hodnota alfa at D je max(-INF, 3), čo je 3.
• Aby sa rozhodol, či stojí za to pozrieť sa na jeho pravý uzol alebo nie, kontroluje stav beta <=alfa. Toto je nepravda, pretože beta = +INF a alfa = 3. Takže pokračuje v hľadaní.
D sa teraz pozrie na svojho pravého potomka, ktorý vráti hodnotu 5.At D , alpha = max(3, 5), čo je 5. Teraz hodnota uzla D je 5 D vráti hodnotu 5 až B . o B , beta = min( +INF, 5), čo je 5. Minimalizátor má teraz zaručenú hodnotu 5 alebo menej. B teraz volá A aby zistil, či môže získať nižšiu hodnotu ako 5.
• o A hodnoty alfa a beta nie sú -INF a +INF, ale namiesto toho -INF a 5, pretože hodnota beta sa zmenila o B a to je čo B odovzdaný do A
• Teraz A pozerá na svoje ľavé dieťa, ktoré má 6. At A , alfa = max(-INF, 6), čo je 6. Tu sa podmienka stáva pravdivou. beta je 5 a alfa je 6. Takže beta <=alfa je pravda. Preto sa láme a A vráti 6 do B
• Všimnite si, ako nezáležalo na hodnote A 'správne dieťa je. Mohlo to byť +INF alebo -INF, aj tak by na tom nezáležalo, ani sme sa na to nemuseli pozerať, pretože minimalizátor mal garantovanú hodnotu 5 alebo menej. Takže akonáhle maximalizátor videl 6, vedel, že minimalizátor nikdy nepríde týmto smerom, pretože môže dostať 5 na ľavej strane B . Týmto spôsobom sme sa nemuseli pozerať na tých 9, a tým sme ušetrili výpočtový čas.
E vráti hodnotu 6 až B . o B , beta = min( 5, 6), čo je 5. Hodnota uzla B je tiež 5

Náš herný strom zatiaľ vyzerá takto. Číslo 9 je prečiarknuté, pretože nebolo nikdy vypočítané.

B vráti 5 až A . o A , alpha = max( -INF, 5), čo je 5. Teraz má maximalizér zaručenú hodnotu 5 alebo vyššiu. A teraz volá C aby ste zistili, či môže získať vyššiu hodnotu ako 5.
• o C , alfa = 5 a beta = + INF. C hovory F
• o F , alfa = 5 a beta = + INF. F pozrie sa na svoje ľavé dieťa, ktoré je 1. alfa = max( 5, 1), čo je stále 5.
F sa pozrie na svoje pravé potomstvo, ktoré je 2. Preto je najlepšia hodnota tohto uzla 2. Alfa stále zostáva 5 F vráti hodnotu 2 až C . o C , beta = min ( + INF, 2). Podmienka beta <= alfa sa stane pravdivou ako beta = 2 a alfa = 5. Takže sa poruší a nemusí ani vypočítať celý podstrom G .
• Intuícia za týmto zlom je, že pri C minimalizátorom bola garantovaná hodnota 2 alebo menšia. Ale maximalizér už mal garantovanú hodnotu 5, ak si vyberie B . Prečo by si teda maximalizátor vôbec vybral C a získať hodnotu menšiu ako 2? Opäť môžete vidieť, že nezáleží na tom, aké boli posledné 2 hodnoty. Tiež sme ušetrili veľa výpočtov preskočením celého podstromu.
C teraz vráti hodnotu 2 to A . Preto najlepšia hodnota pri A je max (5, 2), čo je 5.
• Optimálna hodnota, ktorú môže maximalizátor získať, je teda 5

Takto vyzerá náš posledný herný strom. Ako môžeš vidieť G bola prečiarknutá, pretože nebola nikdy vypočítaná.

CPP

Java

Python3

C#

Javascript

The optimal value is : 5