Witam,
mam pytanie odnośnie algorytmu alfa-beta, a konkretnie o to, jak zmieniają się wartości alfy i bety w czasie jego działania i jak jest to zaimplementowane w przykładowym pseudokodzie.
01 function alphabeta(node, depth, α, β, maximizingPlayer)
02 if depth = 0 or node is a terminal node
03 return the heuristic value of node
04 if maximizingPlayer
05 for each child of node
06 α := max(α, alphabeta(child, depth - 1, α, β, FALSE))
07 if β ≤ α
08 break (* β cut-off *)
09 return α
10 else
11 for each child of node
12 β := min(β, alphabeta(child, depth - 1, α, β, TRUE))
13 if β ≤ α
14 break (* α cut-off *)
15 return β
(* Initial call *)
alphabeta(origin, depth, -∞, +∞, TRUE)
Mój problem polega na tym, że używając algorytmu na przykładowym drzewie i śledząc kod linijka po linijce, wedle mojego rozumowania w pewnym momencie wartości alfa i beta przyjmują wartości a=5 oraz b=5 i następuje wykonanie polecenia "break", co przerywa gałąź - jestem na 99% pewny, że tak być nie powinno, gdyż gałąź przerywa się w moim rozumowaniu nie w tym momencie co trzeba, ale zaraz wyjaśnię na przykładzie.
Rysunek znajduje się w załączniku.
Moje (w którymś miejscu błędne) rozumowanie:
- Funkcja alphabeta bierze jako argument "najwyższą" pozycję na rysunku, czyli początek drzewa.
- Następnie z racji tego, że występuje for each child of node, rozpatrujemy po kolei każde z węzłów niżej (w podanym wyżej kodzie to linijki 05 do 06), poczynając od lewej strony.
- Nie możemy jednak od razu zwrócić alfy, gdyż przyjmuje ona maksymalną wartość z dwóch wartości: dotychczasowa alfa oraz rezultat funkcji alphabeta o jedną głębię mniejszą. Jest to więc rekurencja.
- Wchodzimy głębiej i rozpatrujemy dzieci tego węzła, znowu od lewej do prawej - są to wartości 5 i 6 (na rysunku w lewym dolnym rogu). Jako, że węzeł wyżej oczekuje wartości minimalnej, działamy na części kodu od linijki 11 do 15.
- Dla poszczególnego węzła, zwracana jest jego wartość heurystyczna i jeśli jest ona mniejsza od bety, to jest ustawiana jako beta. Czyli pierwsze beta dostanie wartość 5 (pierwotnie miała nieskończoność). Potem sprawdzane jest czy 6 jest mniejsze od bety, jednak nie jest, więc wartość bety zostaje 5. **Break **nie zachodzi (jeszcze), bo alfa nadal równa się minus-nieskończoność.
- Wartość bety, czyli de facto najmniejsza liczba spośród 5 i 6 jest zwracana do węzła wyżej (oczekuje on wartości minimalnej). Jest to wykonywane, gdy skończy się już pętla (linijki 11-14) za pomocą polecenia return b. Wartość b (bety) jest zwracana do wyrażenia, które opisałem w punkcie 3, czyli wracamy do linijki 06. Teraz α := max(α, alphabeta(child, depth - 1, α, β, FALSE)) możemy zapisać jako α := max(α, 5)), gdzie 5 jest obecną wartością beta.
- Alfa zostaje przypisane do liczby większej spośród dotychczasowej wartości alfa oraz obecnej wartości beta. Jako, że alfa do tej pory równała się minus nieskończoność, alfa dostaje wartość 5.
- I tu zaczyna się mój problem. Jako, że alfa=5 i beta=5, prawdziwy staje się warunek if β ≤ α: break. A to przerywa pętle, tym samym przerywając dalsze szukanie (cała prawa gałąź została pominięta), a tak się dziać nie powinno.
Oczywiście **break **powinien zostać wykonany, ale dopiero po rozpatrzeniu drugiego węzła w prawym dolnym rogu.
Byłbym ogromnie wdzięczny, gdyby ktoś mógł wskazać błąd w moim rozumowaniu.
- Tree.jpg (27 KB) - ściągnięć: 989
