Předpoklady: Minimax algoritmus v teorii her , Funkce hodnocení v teorii her
Alfa-Beta prořezávání není ve skutečnosti nový algoritmus, ale spíše optimalizační technika pro algoritmus minimax. Výrazně snižuje dobu výpočtu. To nám umožňuje hledat mnohem rychleji a dokonce se dostat do hlubších úrovní ve stromu hry. Odřízne větve ve stromu hry, které není třeba hledat, protože již existuje lepší dostupný tah. Říká se tomu prořezávání Alpha-Beta, protože ve funkci minimax předává 2 další parametry, a to alfa a beta.

Pojďme definovat parametry alfa a beta.

Alfa je nejlepší hodnota, která maximalizátor v současné době může garantovat na této úrovni nebo výše.
Beta je nejlepší hodnota, která minimalizátor v současné době může garantovat na této úrovni nebo níže.

Pseudo kó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) 

Pojďme si výše uvedený algoritmus objasnit na příkladu.

• První hovor začíná od A . Hodnota alfa zde je -NEKONEČNO a hodnota beta je + NEKONEČNO . Tyto hodnoty jsou předány následujícím uzlům ve stromu. Na A maximalizátor musí zvolit max B a C , tak A hovory B První
• Na B minimalizátor musí zvolit min D a A a proto volá D První.
• Na D , podívá se na svého levého potomka, což je listový uzel. Tento uzel vrací hodnotu 3. Nyní hodnota alpha at D je max( -INF, 3), což je 3.
• Aby se rozhodl, zda stojí za to podívat se na jeho pravý uzel, nebo ne, kontroluje podmínku beta <=alpha. Toto je nepravda, protože beta = +INF a alfa = 3. Takže pokračuje v hledání.
D se nyní podívá na svého pravého potomka, který vrátí hodnotu 5.At D , alpha = max(3, 5), což je 5. Nyní hodnota uzlu D je 5 D vrátí hodnotu 5 až B . Na B , beta = min( +INF, 5), což je 5. Minimalizátor má nyní zaručenou hodnotu 5 nebo menší. B nyní volá A aby zjistil, jestli může získat nižší hodnotu než 5.
• Na A hodnoty alfa a beta nejsou -INF a +INF, ale místo toho -INF a 5, protože hodnota beta byla změněna v B a to je co B předán A
• Nyní A dívá se na své levé dítě, kterému je 6. At A , alpha = max(-INF, 6), což je 6. Zde se podmínka stane pravdivou. beta je 5 a alfa je 6. Takže beta <=alfa je pravda. Proto se láme a A vrátí 6 do B
• Všimněte si, jak nezáleželo na hodnotě A 'správné dítě je. Mohlo to být +INF nebo -INF, na tom by stejně nezáleželo, nikdy jsme se na to nemuseli dívat, protože minimalizátor měl garantovanou hodnotu 5 nebo menší. Takže jakmile maximalizér viděl 6, věděl, že minimalizátor nikdy nepřijde touto cestou, protože může dostat 5 na levé straně B . Tímto způsobem jsme se nemuseli dívat na těch 9, a tím jsme ušetřili výpočetní čas.
E vrátí hodnotu 6 až B . Na B , beta = min( 5, 6), což je 5. Hodnota uzlu B je také 5

Náš herní strom zatím vypadá takto. Devítka je přeškrtnutá, protože nebyla nikdy spočítána.

B vrátí 5 to A . Na A , alpha = max( -INF, 5), což je 5. Nyní má maximalizér zaručenou hodnotu 5 nebo vyšší. A nyní volá C zjistit, zda může získat vyšší hodnotu než 5.
• Na C , alfa = 5 a beta = + INF. C hovory F
• Na F , alfa = 5 a beta = + INF. F podívá se na své levé dítě, které je 1. alfa = max( 5, 1), což je stále 5.
F se podívá na svého pravého potomka, což je 2. Nejlepší hodnota tohoto uzlu je tedy 2. Alfa stále zůstává 5 F vrátí hodnotu 2 až C . Na C , beta = min ( +INF, 2). Podmínka beta <= alfa se stane pravdivou jako beta = 2 a alfa = 5. Takže se poruší a nemusí ani počítat celý podstrom G .
• Intuice za tímto zlomem je, že at C minimalizátoru byla zaručena hodnota 2 nebo menší. Ale maximalizér měl již garantovanou hodnotu 5, pokud si vybere B . Tak proč by si maximalizér vůbec vybral C a získat hodnotu menší než 2? Opět můžete vidět, že nezáleží na tom, jaké byly poslední 2 hodnoty. Také jsme ušetřili spoustu výpočtů přeskočením celého podstromu.
C nyní vrací hodnotu 2 to A . Proto nejlepší hodnota na A je max( 5, 2), což je 5.
• Optimální hodnota, kterou může maximalizér získat, je tedy 5

Takto vypadá náš finální herní strom. Jak můžete vidět G byl přeškrtnut, protože nebyl nikdy spočítán.

CPP

Jáva

Python3

C#

Javascript

The optimal value is : 5