# Różnice

Różnice między wybraną wersją a wersją aktualną.

 — pl:prolog:pllib:alfa_beta [2019/06/27 15:50] (aktualna) Linia 1: Linia 1: + ====== Alfa beta ====== + {{tag>​algorithms}} + ===== Description ===== + An implementation of the alpha-beta algorithm. + + **Source**: ​ PROLOG programming for artificial intelligence,​ 3rd Edition, Harlow, 2001, ISBN 0-201-40375-7. + ===== Download ===== + Program source code: {{alfa_beta.pl}} + ===== Listing ===== + + % Figure 22.5  An implementation of the alpha-beta algorithm. + + + % The alpha-beta algorithm + + alphabeta( Pos, Alpha, Beta, GoodPos, Val)  :- + moves( Pos, PosList), !, + boundedbest( PosList, Alpha, Beta, GoodPos, Val); + staticval( Pos, Val).                              % Static value of Pos + + boundedbest( [Pos | PosList], Alpha, Beta, GoodPos, GoodVal) ​ :- + alphabeta( Pos, Alpha, Beta, _, Val), + goodenough( PosList, Alpha, Beta, Pos, Val, GoodPos, GoodVal). + + goodenough( [], _, _, Pos, Val, Pos, Val)  :-  !.    % No other candidate + + goodenough( _, Alpha, Beta, Pos, Val, Pos, Val)  :- + min_to_move( Pos), Val > Beta, !                   % Maximizer attained upper bound + ; + max_to_move( Pos), Val < Alpha, !.                 % Minimizer attained lower bound + + goodenough( PosList, Alpha, Beta, Pos, Val, GoodPos, GoodVal) ​ :- + newbounds( Alpha, Beta, Pos, Val, NewAlpha, NewBeta), ​   % Refine bounds  ​ + boundedbest( PosList, NewAlpha, NewBeta, Pos1, Val1), + betterof( Pos, Val, Pos1, Val1, GoodPos, GoodVal). + + newbounds( Alpha, Beta, Pos, Val, Val, Beta)  :- + min_to_move( Pos), Val > Alpha, !.                 % Maximizer increased lower bound + + newbounds( Alpha, Beta, Pos, Val, Alpha, Val)  :- + ​max_to_move( Pos), Val < Beta, !.                 % Minimizer decreased upper bound + + newbounds( Alpha, Beta, _, _, Alpha, Beta). ​         % Otherwise bounds unchanged ​ + + betterof( Pos, Val, Pos1, Val1, Pos, Val)  :-        % Pos better than Pos1 + min_to_move( Pos), Val > Val1, ! + ; + max_to_move( Pos), Val < Val1, !. + + betterof( _, _, Pos1, Val1, Pos1, Val1). ​            % Otherwise Pos1 better + ​ + ===== Comments =====
pl/prolog/pllib/alfa_beta.txt · ostatnio zmienione: 2019/06/27 15:50 (edycja zewnętrzna)