# Alfa beta

## Description

An implementation of the alpha-beta algorithm.

Source: PROLOG programming for artificial intelligence, 3rd Edition, Harlow, 2001, ISBN 0-201-40375-7.

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```