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 ===== | ||
| + | <code prolog> | ||
| + | % 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 | ||
| + | </code> | ||
| + | ===== Comments ===== | ||
