%% --------------------------------------------------------------
%%  Datei:  minimax.pl
%%  Datum:  30.04.1998
%% --------------------------------------------------------------
%%  Mini-Max-Beispiel mit alpha-beta-Pruning:
%%  -----------------------------------------
%%
%%	| ?- alphabeta(a1,-1000,1000,K,W).
%%
%%	a1:  alpha = -1000   beta = 1000
%%	b1:  alpha = -1000   beta = 1000
%%	c1:  alpha = -1000   beta = 1000
%%	d1:  alpha = -1000   beta = 1000
%%	e1:  alpha = -1000   beta = 1000
%%	e1:    NeuBeta : 10
%%	e2:  alpha = -1000   beta = 10
%%	d1:    NeuAlpha : 10
%%	d2:  alpha = 10   beta = 1000
%%	e3:  alpha = 10   beta = 1000
%%	Schnitt bei e3:   alpha : 10
%%	c1:    NeuBeta : 10
%%	c2:  alpha = -1000   beta = 10
%%	d3:  alpha = -1000   beta = 10
%%	e5:  alpha = -1000   beta = 10
%%	e6:  alpha = -1000   beta = 10
%%	  Schnitt bei d3:   beta: 10
%%	b1:    NeuAlpha : 10
%%	b2:  alpha = 10   beta = 1000
%%	c3:  alpha = 10   beta = 1000
%%	d5:  alpha = 10   beta = 1000
%%	e9:  alpha = 10   beta = 1000
%%	  Schnitt bei e9:   alpha : 10
%%	d6:  alpha = 10   beta = 1000
%%	e11:  alpha = 10   beta = 1000
%%	  Schnitt bei e11:   alpha : 10
%%	  Schnitt bei c3:   alpha : 10
%%
%%	K = b1,
%%	W = 10 ;
%%
%%	no
%%
%% --------------------------------------------------------------
%%  Beschreibung des Min-Max-Baums (groesseres Beispiel aus der
%%  KI-Vorlesung vom 29.04.1998):

nachf(a1,[b1, b2]).
nachf(b1,[c1, c2]).
nachf(b2,[c3, c4]).
nachf(c1,[d1, d2]).
nachf(c2,[d3,d4]).
nachf(d1,[e1,e2]).
nachf(d2,[e3,e4]).
nachf(d3,[e5,e6]).
nachf(d4,[e7,e8]).
nachf(d5,[e9,e10]).
nachf(d6,[e11,e12]).
nachf(d7,[e13,e14]).
nachf(d8,[e15,e16]).
nachf(c3,[d5,d6]).
nachf(c4,[d7,d8]).

wert(e1,10).
wert(e2,11).
wert(e3,9).
wert(e4,12).
wert(e5,14).
wert(e6,15).
wert(e7,13).
wert(e8,14).
wert(e9,5).
wert(e10,2).
wert(e11,4).
wert(e12,1).
wert(e13,3).
wert(e14,22).
wert(e15,20).
wert(e16,21).

max_dran(a1).
max_dran(c1).
max_dran(c2).
max_dran(c3).
max_dran(c4).
max_dran(e1).
max_dran(e2).
max_dran(e3).
max_dran(e4).
max_dran(e5).
max_dran(e6).
max_dran(e7).
max_dran(e8).
max_dran(e9).
max_dran(e10).
max_dran(e11).

min_dran(b1).
min_dran(b2).
min_dran(d1).
min_dran(d2).
min_dran(d3).
min_dran(d4).
min_dran(d5).
min_dran(d6).
min_dran(d7).
min_dran(d8).

%% --------------------------------------------------------------
%%  Beschreibung des Min-Max-Baums eines anderen Beispiels (kleineres
%%  Beispiel aus der KI-Vorlesung vom 29.04.1998):
%
%nachf(a,[b,i]).
%nachf(b,[c,g]).
%nachf(d,[f1,f2]).
%nachf(f1,[f3]).
%nachf(g,[h1,h2]).
%nachf(c,[d,e]).
%nachf(e,[e1]).
%nachf(h1,[h3]).
%nachf(i,[j1,j2]).
%nachf(j1,[j3]).
%nachf(j2,[k1,k2]).
%nachf(k2,[k3]).
%
%wert(f3,-10).
%wert(f2,10).
%wert(e1,10).
%wert(h3,10).
%wert(h2,-10).
%wert(j3,-10).
%wert(k1,-10).
%wert(k3,10).
%
%max_dran(a).
%max_dran(c).
%max_dran(g).
%max_dran(j1).
%max_dran(j2).
%max_dran(f3).
%max_dran(f2).
%max_dran(e1).
%max_dran(h3).
%max_dran(k3).
%min_dran(b).
%min_dran(i).
%min_dran(d).
%min_dran(e).
%min_dran(h1).
%min_dran(h1).
%min_dran(h2).
%min_dran(j3).
%min_dran(k1).
%min_dran(k2).
%% --------------------------------------------------------------

nachf(X,[]):- fail.


%%  Alpha-Beta-Suche:

alphabeta(K,Alpha, Beta, GuteStell,Wert):-
	write(K), write(':  alpha = '), write(Alpha),
	write('   beta = '), write(Beta), nl,
	nachf(K, KListe),!,
	best_begrenzt(KListe, Alpha, Beta, GuteStell, Wert);
	wert(K,Wert).


best_begrenzt([K|KListe],Alpha,Beta,GuteStell,GuterWert):-
	alphabeta(K,Alpha,Beta,_,Wert),
	gut_genug(KListe, Alpha,Beta,K,Wert,GuteStell,GuterWert).


gut_genug([],_,_,K,Wert,K,Wert):-!.	             %% keine Alternativen

gut_genug(_,Alpha,Beta,K,Wert,K,Wert):- 
	min_dran(K), Wert > Beta, 
	write('  Schnitt bei '), write(K), 
	write(':   beta: '), write(Beta), nl, !      %% Maximierer erreicht Grenze
	; max_dran(K), Alpha > Wert, 
	write('  Schnitt bei '), write(K),
	write(':   alpha : '), write(Alpha), nl, !.  %% Minimierer erreicht Grenze

gut_genug(KListe, Alpha, Beta, K, Wert, GuteStell, GuterWert):-
	neue_Grenzen(Alpha, Beta, K, Wert, NeuAlpha, NeuBeta),
	best_begrenzt(KListe, NeuAlpha, NeuBeta, K1, W1),
	bester_von(K, Wert, K1, W1, GuteStell, GuterWert).


neue_Grenzen(Alpha, Beta, K, Wert, Wert, Beta):-
	min_dran(K), Wert > Alpha,
	write(K), write(':    NeuAlpha : '),write(Wert), nl, !. 
	%% Maximierer erhoehte untere Grenze
	% NeuAlpha > Alpha

neue_Grenzen(Alpha, Beta, K, Wert, Alpha, Wert):-
	max_dran(K), Wert < Beta,
	write(K), write(':    NeuBeta : '), write(Wert), nl, !. 

%% Minimierer senkte obere Grenze
neue_Grenzen(Alpha, Beta, _, _, Alpha, Beta).


bester_von(K, Wert, K1, W1, K, Wert):-
	min_dran(K), Wert > W1, !;
	max_dran(K), W1 > Wert, !.

bester_von(_,_,K1, W1, K1, W1).

%% --------------------------------------------------------------