Algorytm alfa-beta - jak zmieniają się wartości podczas jego działania?

Algorytm alfa-beta - jak zmieniają się wartości podczas jego działania?
BW
  • Rejestracja: dni
  • Ostatnio: dni
  • Postów: 10
0

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.

Kopiuj
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:

  1. Funkcja alphabeta bierze jako argument "najwyższą" pozycję na rysunku, czyli początek drzewa.
  2. 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.
  3. 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.
  4. 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.
  5. 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ść.
  6. 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.
  7. 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.
  8. 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.

_13th_Dragon
  • Rejestracja: dni
  • Ostatnio: dni
0

Napisz to w jakimś języku i sprawdź.

BW
  • Rejestracja: dni
  • Ostatnio: dni
  • Postów: 10
0

Chyba ogarnąłem - chodzi o namespace? Np. beta, na której operujemy w głębi X nie jest to samą betą, na której operujemy w głębi X-1 (po użyciu rekurencji). Dobrze myślę?

Zarejestruj się i dołącz do największej społeczności programistów w Polsce.

Otrzymaj wsparcie, dziel się wiedzą i rozwijaj swoje umiejętności z najlepszymi.