-
Notifications
You must be signed in to change notification settings - Fork 1
/
fig24_5.pl
40 lines (28 loc) · 1.58 KB
/
fig24_5.pl
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
% Figure 24.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