%%  Datei:  minimax_alpha_beta.folien.pl
%%  Datum:  31.07.2002
%%
%%  Minimax-Suche mit Alpha/Beta-Pruning
%%  ------------------------------------
%%
%%  Idee (nur terminaler Fall):
%%    Wenn ein Zweig bereits nachweislich ein Gewinnzug 
%%    ist, brauchen die anderen nicht mehr untersucht zu 
%%    werden.
%%
%%  Allgemein (auch nichtterminale Fälle):
%%    1. Maximierer am Zug (Alpha-Pruning):
%%         Wenn die bisher untersuchten Zweige dem 
%%         Maximierer bereits einen Wert von mindestens alpha
%%         garantieren, brauchen diejenigen Zweige, die 
%%         nachweislich nur einen kleineren Wert erreichen, 
%%         nicht genau untersucht zu werden. Letzteres ist fuer 
%%         einen Zweig der Fall, sobald ein Folgezug fuer den 
%%         Minimierer mit weniger als alpha bewertet wird.
%%    2. Minimierer am Zug (Beta-Pruning):
%%         Wenn die bisher untersuchten Zweige dem 
%%         Minimierer bereits einen Wert von hoechstens beta
%%         garantieren, brauchen diejenigen Zweige, die 
%%         nachweislich nur einen größeren Wert erreichen, 
%%         nicht genau untersucht zu werden...
%%
%%  Minimax mit Alpha/Beta-Pruning

%%  Gegeben eine Spielsituation 'Pos' und einen alpha-Wert 'A'
%%  und einen beta-Wert 'B', liefert 'minimax(Pos,A,B,BPos,BVal)'
%%  die bzw. eine beste Nachfolgesituation 'BPos' zusammen mit 
%%  der Bewertung 'BVal' dieser Position:

minimax(Pos,A,B,BPos,BVal) :-
    moves(Pos,PosL),
    boundedbest(PosL,A,B,BPos,BVal)
    ;
    statwert(Pos,BVal).


boundedbest([Pos|PosL],A,B,BPos,BVal) :-
    minimax(Pos,A,B,_,Val),
    goodenough(PosL,A,B,Pos,Val,BPos,BVal).


goodenough([],_,_,Pos,Val,Pos,Val).

goodenough(_,A,B,Pos,Val,Pos,Val) :-
	min_to_move(Pos), Val > B, !
	;	
	max_to_move(Pos), Val < A, !.

goodenough(PosL,A,B,Pos,Val,BPos,BVal) :-
	newbounds(A,B,Pos,Val,NewA,NewB),
	boundedbest(PosL,NewA,NewB,Pos1,Val1),
	bester(Pos,Val,Pos1,Val1,BPos,BVal).


newbounds(A,B,Pos,Val,Val,B) :-
	min_to_move(Pos), Val > A, !.

newbounds(A,B,Pos,Val,A,Val) :-
	max_to_move(Pos), Val < B, !.

newbounds(A,B,_,_,A,B).